|
i]=0;
}
For(0,k,j)
{
RD(t);
vis[i][t]=1;//建图
}
}
while(1)
{
RD(x);
if(x==0)
{
break;
}
sum=0;
For(0,x,i)
{
RD(p);
sum^=dfs(p);
}
if(sum!=0)
{
printf("WIN\n");
}
else
{
printf("LOSE\n");
}
}
}
return 0;
}
POJ2068 Nim
题意是圆桌上有2n个人，奇数一队，偶数一队，每个人都有一个拿走棋子的最高限额，问你最后1对能否获胜。
还是用强大的sg函数过的，记录下每个状态的sg。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int n,s,m[22],sg[22][8200],sum;
int dfs(int x,int y)
{
if(sg[x][y]!=-1)
{
return sg[x][y];
}
int i,j;
FOR(1,m[x],i)
{
if(y-i<0)
{
break;
}
if(x+1>=2*n)
{
j=0;
}
else
{
j=x+1;
}
if(dfs(j,y-i)==0)
{
return sg[x][y]=1;
}
}
return sg[x][y]=0;
}
int main()
{
int i;
while(1)
{
RD(n);
if(n==0)
{
break;
}
RD(s);
For(0,2*n,i)
{
RD(m[i]);
}
mem(sg,-1);
FOR(0,2*n,i)
{
sg[i][0]=1;
}
sum=dfs(0,s);
if(sum==0)
{
printf("0\n");
}
else
{
printf("1\n");
}
}
return 0;
}
POJ3537 Crosses and Crosses
题意：给出一个1*n的矩形，上面有n个方格，现有两人分别在上面画×，谁先能画出三个×相连就赢了。这就是一个sg函数的母问题转化为子问题的题目，由于在第x位置画了×后，则就转变成(x-3)个格子画×和(n-x-2)个格子画×。。。这就能不断的分解下去，最后将所有sg值异或起来就是正解了。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int sg[2001];
int dfs(int x)
{
if(x<0)
{
return 0;
}
if(sg[x]>=0)
{
return sg[x];
}
int i,y;
bool v[2001]={false};
FOR(1,x,i)
{
y=dfs(i-3)^dfs(x-i-2);//找后继（经典）
v[y]=true;
}
for(i=0;;i++)
{
if(v[i]==false |