首页 > 代码库 > HDU 2177 威佐夫博奕 hdu1527升级版

HDU 2177 威佐夫博奕 hdu1527升级版

2024-07-18 15:18:19   231人阅读

取(2堆)石子游戏

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1075    Accepted Submission(s): 649


Problem 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
 
 
思路：
当a和b满足奇异局势时，那么你必输，输出0。反之由威佐夫博奕性质知所有非奇异局势都可以一步转化成奇异局势。
转化奇异函数步骤：
1、同时从两堆中取相同数目的物品，k=b-a，那么当a-X[k]==b-Y[k]（X[k]与Y[k]为两堆物品数量）时，那么a和b肯定能转化成X[k]和Y[k]即从第一堆中取a-X[k]个从第二堆中取b-Y[k]个（很好证明）。
2、从一堆中取一部分物品，那么遍历一下就行了，由于a<=b，那么从b中取物品肯定能达到奇异局势，当a==X[i]||a==Y[i](0<=i<=1000000)，那么就可以从b中取一部分物品就可以转化成X[i]、Y[i]。所以咱们还需要打表0------1000000的奇异局势。
 
打表奇异局势：由ak=k*(sqrt(5)+1)/2，b=ak+k。  遍历k就行了。
 
 
代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 #include <iostream> 6 #include <math.h> 7 #include <map> 8 using namespace std; 9 #define N 100000010 #define LL __int6411 12 map<pair<int,int>,int>visited;13 int X[N+2], Y[N+2];           //这里若改成map(int,int)X,Y提交后500多MS，可以看出当数据大的话map不如数组模拟hash匹配 14 15 void init(){                 //打表奇异局势 16     double i, j, k, r=(sqrt(5)+1.0)/2.0;17     int a, b;18     for(i=0;i<=N;i++){19         a=i*r;20         b=a+i;21         if(b>N) break;22         X[(int)i]=a;23         Y[(int)i]=b;24     }25 }26 27 main()28 {29     int a, b;30     double j, k, r=(sqrt(5)+1.0)/2.0;31     int i;32     init();33     while(scanf("%d %d",&a,&b)==2&&(a||b)){34         visited.clear();35         k=b-a;36         if(a==(int)(k*r)){       //当a和b满足奇异局势时必输 37             printf("0\n");continue;38         }39         printf("1\n");40         if(a-X[(int)k]==b-Y[(int)k]&&a-X[(int)k]>0&&b-Y[(int)k]>0){  //看同时从两堆物品中取相同数目的物品时能否达到奇异局势 41             printf("%d %d\n",X[(int)k],Y[(int)k]);42             visited[make_pair(X[(int)k],Y[(int)k])]=1;43         }44         for(i=0;i<=N;i++){                                 //从1堆物品中取 45             if(a==X[i]&&visited.find(make_pair(X[i],Y[i]))==visited.end()){46                 printf("%d %d\n",X[i],Y[i]);47             //    visited[make_pair(X[i],Y[i])]=1;48             break;49             }50             if(a==Y[i]&&visited.find(make_pair(X[i],Y[i]))==visited.end()){51                 printf("%d %d\n",X[i],Y[i]);52             //    visited[make_pair(X[i],Y[i])]=1;53             break;54             }55         }56     }57 }

 


联系
我们