597
京東網上商城
uva 1378 - A Funny Stone Game sg函數
07年論文的第一個例題，看了2天都沒看懂，那句把每一顆石子看作是一堆石子，如果它是第p堆中的石子，把麼它所代表的這堆石子的個數為n-1-p，晚上看電影突然想明白了，意思是如果第p堆一開始為t，那麼就可以看做t個數目為n-1-p的石子。一切問題迎刃而解
寫了個O(n^3)的算法，但感覺不用枚舉，還能有優化
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int sg[25];
int org[25];
void init()
{
int vis[100],i,j,k;//vis開大點 防溢出
sg[0]=0;
for(i=1;i<23;i++)
{
memset(vis,0,sizeof(vis));
for(j=0;j<i;j++)
for(k=j;k<i;k++)
{
vis[sg[j]^sg[k]]=1;
}
for(j=0;vis[j];j++);
sg[i]=j;
}
}
int main()
{
int C=0;
init();
while(~scanf("%d",&n)&&n)
{
int t,i,j,k,ans=0;
for(i=0;i<n;i++)
{
scanf("%d",&t);
org[i]=t;
if(t&1)
ans^=sg[n-i-1];
}
bool ok=1;
printf("Game %d: ",++C);
for(i=0;ok&&i<n;i++)
if(org[i])
for(j=i+1;ok&&j<n;j++)
for(k=j;ok&&k<n;k++)
if((ans^sg[n-i-1]^sg[n-j-1]^sg[n-k-1])==0)
{
printf("%d %d %d\n",i,j,k);
ok=0;
}
if(ok)puts("-1 -1 -1");
}
}
最後更新：2017-04-03 15:21:46