UVA1378 A funny stone game

博弈论。

就是有一堆石子你拿走一堆中的一个,然后再向后面两堆中加两个问胜负

i<j<=k

所以我们可以直接通过sg函数计算,考虑问题的奇偶性,如果这一位是奇的我们才考虑,偶的可以模仿

然后对所有sg异或一下,找到三个数异或起来能使当前先手必败即可。

By:大奕哥

 #include<bits/stdc++.h>
using namespace std;
int sg[],a[],v[],n,cnt;
void init()
{
for(int i=;i<=;++i)
{
memset(v,,sizeof(v));
for(int j=;j<i;++j)
for(int k=;k<=j;++k)
{
v[sg[j]^sg[k]]=;
}
int pos=;
while()
{
if(!v[pos]){sg[i]=pos;break;}
pos++;
}
}
return;
}
int main()
{
init();
while(~scanf("%d",&n)&&n)
{
int ans=;
for(int i=;i<=n;++i)
{
scanf("%d",&a[i]);
if(a[i]&)
ans^=sg[n-i+];
}
printf("Game %d:",++cnt);
if(!ans)
puts(" -1 -1 -1");
bool flag=;
for(int i=;i<n;++i)
if(a[i]&&!flag)
for(int j=i+;j<=n;++j)
if(!flag)
for(int k=j;k<=n;++k)
if((ans^sg[n-i+]^sg[n-j+]^sg[n-k+])==)
{
printf(" %d %d %d\n",i-,j-,k-);
flag=;break;
}
}
return ;
}
上一篇:Nginx实现文件的上传和下载


下一篇:Educational Codeforces Round 23 E. Choosing The Commander trie数