取(2堆)石子游戏（威佐夫博弈+hdu2177）
时间：2015-08-06 00:28:56
收藏：0
阅读：256
Description
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子?
Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000，且a<=b。a=b=0退出。
Output
输出也有若干行，如果最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况.
Sample Input
1 2 5 8 4 7 2 2 0 0
Sample Output
0 1 4 7 3 5 0 1 0 0 1 2
转载请注明出处：寻找&星空の孩子
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2177
关于威佐夫博弈还有一片：http://blog.csdn.net/u010579068/article/details/47306029
思路：先把所有P点打表，然后如果是P点那么直接输出0;
如果是N点，那么先匹配同时减去后为P点的情况；
然后分三种情况讨论：(n,m) ----->题目保证n<m，坑！
1、如果Px==n && Py<m
2、如果Py==m && Px<n
3、如果Py==n && Px<m
注意：同一个情况，小的先输出 eg(n,m)=(5,8)------>(3,5)
//前几个奇异局势是：
//（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、
//（8，13）、（9，15）、（11，18）、（12，20）
//规律：假设（x,y）且x<y;那么x一定是没出现过的最小的正整数;
//而y=x+k;
//打表先
#include<stdio.h>
#include<math.h>
struct stone
{
int x;
int y;
} num[400000];
bool vis[1000005]= {false};
int cnt;
void init()
{
int k=1;
num[0].x=0;
num[0].y=0;
vis[0]=true;
for(int i=1;; i++)
{
if(!vis[i])
{
num[k].x=i;
num[k].y=i+k;
vis[num[k].x]=true;
vis[num[k].y]=true;
k++;
}
if(num[k-1].y>1000000) break;
}
cnt=k;//个数
}
void Print(int x,int y)
{
// printf("n=%d,m=%d,t=%d\n",x,y,tt);
int x1,x2,y1,y2;
x1=x2=y1=y2=0;
for(int i=0; i<cnt; i++)
{
if(num[i].x<x)
{
if(x-num[i].x==y-num[i].y)
{
printf("%d %d\n",num[i].x,num[i].y);
}
}
if(num[i].x==x&&num[i].y<y)
{
x1=num[i].x;
y1=num[i].y;
}
if(num[i].y==y&&num[i].x<x)
{
x1=num[i].x;
y1=num[i].y;
}
if(num[i].y==x&&num[i].x<y)
{
//这里不需要交换
x2=num[i].x;
y2=num[i].y;
}
else if(num[i].x>y) break;
}
if(x1+y1!=0)
printf("%d %d\n",x1,y1);
if(x!=y&&x2+y2)
printf("%d %d\n",x2,y2);
}
int main()
{
int n,m,k,t;
init();
// printf("cnt=%d\n",cnt);
// printf("%d %d\n",num[cnt-1].x,num[cnt-1].y);
while(scanf("%d%d",&n,&m),n+m)
{
//题目保证了 n<m
int kt=0;
k=m-n;
t=k*(1+sqrt(5))/2;
if(t==n)
printf("0\n");
else
{
printf("1\n");
Print(n,m);
}
}
return 0;
}
WA了一次，考虑多了点。
#include<stdio.h>
#include<math.h>
struct stone
{
int x;
int y;
} num[400000];
bool vis[1000005]= {false};
int cnt;
void init()
{
int k=1;
num[0].x=0;
num[0].y=0;
vis[0]=true;
for(int i=1;; i++)
{
if(!vis[i])
{
num[k].x=i;
num[k].y=i+k;
vis[num[k].x]=true;
vis[num[k].y]=true;
k++;
}
if(num[k-1].y>1000000) break;
}
cnt=k;//个数
}
void Print(int x,int y,int tt)
{
// printf("n=%d,m=%d,t=%d\n",x,y,tt);
int x1,x2,y1,y2;
x1=x2=y1=y2=0;
for(int i=0; i<cnt; i++)
{
if(num[i].x<x)
{
if(x-num[i].x==y-num[i].y)
{
if(tt)
printf("%d %d\n",num[i].y,num[i].x);
else
printf("%d %d\n",num[i].x,num[i].y);
}
}
if(num[i].x==x&&num[i].y<y)
{
if(tt)
{
x1=num[i].y;
y1=num[i].x;
}
else
{
x1=num[i].x;
y1=num[i].y;
}
}
if(num[i].y==y&&num[i].x<x)
{
if(tt)
{
x1=num[i].y;
y1=num[i].x;
}
else
{
x1=num[i].x;
y1=num[i].y;
}
}
if(num[i].y==x&&num[i].x<y)
{
if(tt)
{
x2=num[i].x;
y2=num[i].y;
}
else
{
x2=num[i].y;
y2=num[i].x;
}
}
else if(num[i].x>y) break;
}
if(x1+y1!=0)
printf("%d %d\n",x1,y1);
if(x!=y&&x2+y2)
printf("%d %d\n",y2,x2);//不用交换，坑！
}
int main()
{
int n,m,k,t;
init();
// printf("cnt=%d\n",cnt);
// printf("%d %d\n",num[cnt-1].x,num[cnt-1].y);
while(scanf("%d%d",&n,&m),n+m)
{
int kt=0;
if(n>m)//交换n，m的值。使n>m ;
{
n^=m;
m^=n;
n^=m;
kt=1;
}
k=m-n;
t=k*(1+sqrt(5))/2;
if(t==n)
printf("0\n");
else
{
printf("1\n");
Print(n,m,kt);
}
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/u010579068/article/details/47306179
评论（0）