【 HDU 2177 】取(2堆)石子游戏 （威佐夫博弈）---饶文津

BUPT2017 wintertraining(15) #5C hdu2177

题意

两个人轮流取石子，可以取一堆的任意非负整数个或两堆取相同个，先取完的输。 给定若干组数据：a,b表示两堆的石子数量，求先手输还是赢，赢还要求第一步之后的两堆石子数，如果有取相同的方案，先输出。

题解

威佐夫博弈问题。 必输的状态（奇异局势）：（0，0），（1，2），（3，5），..（a_k,a_k+k）其中a_k是前面未出现过的最小的正整数。 有一些性质：每个正整数在必输状态中出现且仅出现一次。 于是可以计算并存储下必输状态(X,Y)，x[k]为第k个必输状态的较小的数，y[i]为必输状态中是较小的数i 对应的较大的数，z[i]为必输状态中较大的数i 对应的较小的数。 先手输的情况就是一开始就是必输态，也就是k=b-a，x[k]==a。 先手赢的情况，是将局面变成必输态: 取走两个相同的数后，差k不变，若a>x[k]，则可变成(x[k]，y[x[k]])。 只取第一堆： 若b在它所在的必输态中是较大的数（z[b]!=0），且a>z[b]，则可变成（z[b],b）。 只取第二堆：

第二堆仍更大：若a在必输态中是较小的数(y[a]!=0)，且b>y[a]，则可变成（a,y[a]）。第二堆更小了：若a在必输态中是较大的数，因为b>a>z[a]，可以变成（z[a],a）。

这题数据比较水，错误的代码也ac了。按我现在的思路我也不敢说一定是正确的代码。 另外也可以用公式直接求出奇异局势： a_k = [kcdot (1+√5)/2],b_k= a_k + k

代码#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define N 1000005 using namespace std; int a,b,vis[N<<1],x[N],y[N],z[N<<1],k; int main() { for(int i=1;i<N;i++) if(!vis[i]){ x[++k]=i;y[i]=i+k;z[i+k]=i; vis[i]=vis[y[i]]=1; } while(scanf("%d%d",&a,&b),a||b){ if(x[b-a]==a) puts("0"); else{ puts("1"); if(a>x[b-a]) printf("%d %dn",x[b-a],y[x[b-a]]); if(z[b]&&a>z[b]) printf("%d %dn",z[b],b); if(y[a]&&b>y[a]) printf("%d %dn",a,y[a]); if(z[a])printf("%d %dn",z[a],a); } } return 0; } ---来自腾讯云社区的---饶文津