[BeiJing2009 WinterCamp]取石子游戏 Nim SG 函数
2024-08-31 14:18:41
Code:
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1003
int arr[13],step[13],SG[maxn];
bool vis[maxn];
int main(){
//freopen("input.in","r",stdin);
int n,m,MAX=0,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&arr[i]), MAX=max(MAX,arr[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i) scanf("%d",&step[i]);
SG[0]=0;
for(int i=1;i<=1000;++i) {
memset(vis,0,sizeof(vis));
for(int j=1;j<=m&&step[j]<=i;++j) vis[SG[i-step[j]]]=1;
for(int j=0;;++j)
if(!vis[j]){
SG[i]=j;
break;
}
}
for(int i=1;i<=n;++i) ans^=SG[arr[i]];
if(ans==0)printf("NO");
else printf("YES\n");
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m&&step[j]<=arr[i];++j)
if((ans^SG[arr[i]])==SG[arr[i]-step[j]]) {
printf("%d %d",i,step[j]);
return 0;
}
}
return 0;
}
最新文章
- Thinking in Unity3D
- node在centos下的安装
- php : DOM 操作 XML
- The CLR&#39;s Execution Model
- 系统的 host文件的作用
- trunc的使用
- 「Poetize3」Heaven Cow与God Bull
- 卡特兰数(Catalan)简介
- 腾讯QQ是用什么语言开发的(转)
- python自动化测试
- iOS 开发者旅途中的指南针 - LLDB 调试技术
- [刷题]算法竞赛入门经典(第2版) 4-9/UVa1591 - Data Mining
- python_18_反射
- 013_UDP专项研究监控
- C语言中数组使用负数值的标记
- 电脑一键U盘启动快捷键
- 服务端spark gbdt模型计算性能优化
- bzoj1227 P2154 [SDOI2009]虔诚的墓主人
- leetcode第四题:两个有序数组的中位数
- Android 使用正则表达式验证邮箱格式是否正确