【博弈论】【SG函数】【枚举】bzoj1874 [BeiJing2009 WinterCamp]取石子游戏
2024-08-26 17:43:08
枚举第一步可能达到的状态,判断是否是必败态即可。
#include<cstdio>
#include<set>
#include<cstring>
using namespace std;
int SG[1001],a[1001],b[1001],n,m,all;
int sg(int x)
{
if(SG[x]!=-1) return SG[x];
set<int>S;
for(int i=1;i<=m;++i)
{
if(b[i]>x) break;
S.insert(sg(x-b[i]));
}
for(int i=0;;++i)
if(S.find(i)==S.end())
return SG[x]=i;
}
int main()
{
memset(SG,-1,sizeof(SG));
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i) scanf("%d",&b[i]);
for(int i=1;i<=n;++i) all^=sg(a[i]);
puts(all?"YES":"NO");
if(all)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
int t=0;
for(int k=1;k<i;++k) t^=sg(a[k]);
for(int k=i+1;k<=n;++k) t^=sg(a[k]);
if(!(t^sg(a[i]-b[j])))
{
printf("%d %d\n",i,b[j]);
return 0;
}
}
}
return 0;
}
最新文章
- SpringMVC RequestMapping &; 请求参数
- Teredo 是一项 IPv6/IPv4 转换技术
- LSMW应用
- SQLServer存储过程入门
- daxuez.com
- algorithm@ dijkstra algorithm &; prim algorithm
- 快捷键Ctrl+c、Ctrl+d、Ctrl+u、Ctrl+a、Ctrl+e
- UESTC_我要长高 CDOJ 594
- sulime text3
- Linux用户相关的操作命令
- FZU 1627 Revival&#39;s road
- Copy Constructor的构造操作
- Struts2第六篇【文件上传和下载】
- 【Luogu3398】仓鼠找sugar(树链剖分)
- 基于PHP的快递查询免费开放平台案例-快宝开放平台
- Android adb基本命令-cd,ls,目录相关命令
- python学习Day14 带参装饰器、可迭代对象、迭代器对象、for 迭代器工作原理、枚举对象、生成器
- matlab积分使用
- JavaScript系统对象
- 【PHP面试题】通俗易懂的两个面试必问的排序算法讲解:冒泡排序和快速排序