首页 > 代码库 > codeforces 88E Interesting Game
codeforces 88E Interesting Game
题目大意：
两个好朋友再将一堆物品分堆，每次都将一堆物品分成数量连续的至少两个堆，直到一个人不能分堆为输
第一次做博弈问题，看了百度文库的http://wenku.baidu.com/link?url=C6qxEhqBEJJFDPC2nSW8kaOer2s_WyOxAhUi0QzF_-B38Gw7KqbbjFvuiaLUvuoGYtliZE_JAH_PO1VPpOT1Vo5OvbyPzBR3Q5IlmWYIHuy
感觉讲的还是蛮好的
这里因为每次至少要分两个堆
所以初始sg[0] = sg[1] = sg[2] = 0 ,为 P 态（必胜态）
假设某堆物品n可以分成a ， a+1 , a+2 , a+3 ... a+k-1 这样k堆
根据等差数列方程可得 (2*a+k-1)*k = 2*n
那么我们就可以找所有 可作为 2*n的因子的k ， 这里因为a>=1 ，所以(2*a+k-1)>k的，所以只要找2~sqrt(2*n+0.5)中符合的k的因子就好了，然后判断里面的a是否存在
如果都成立说明这是一种分的方式，这就是一个n的可到达点，记录当前的点sg值已访问过，当前点的sg值是由这个点中所有堆的异或值得到
我们这里异或过程中不断记录异或的前缀和减少计算过程
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 using namespace std; 6 const int N = 100010; 7 8 int sg[N] , sum[N] , minn[N] , vis[N]; 9 10 void init_sg()11 {12 sg[0] = sg[1] = sg[2] = 0;13 sum[0] = sum[1] = sum[2] = 0;14 memset(minn , 0x3f , sizeof(minn));15 for(int n=3 ; n<=100000 ; n++){16 int t = 2*n;17 int factor = (int)(sqrt(t+0.5));18 for(int k=2 ; k<=factor ; k++){19 if(t % k == 0 && t/k+1-k>0 && !((t/k+1-k)&1)){20 int a = (t/k+1-k)/2;21 int p = sum[a+k-1]^sum[a-1];22 vis[p] = n;23 if(p == 0) minn[n] = min(minn[n] , k);24 }25 }26 //找没有出现过的最小的sg函数27 int v = 0;28 while(1){29 if(vis[v] != n){30 sg[n] = v;31 break;32 }33 v++;34 }35 //记录当前的sum[]前缀36 sum[n] = sum[n-1]^sg[n];37 }38 }39 40 int main()41 {42 // freopen("a.in" , "r" , stdin);43 init_sg();44 int n;45 while(scanf("%d" , &n) == 1)46 {47 if(!sg[n]){48 puts("-1");49 continue;50 }51 printf("%d\n" , minn[n]);52 }53 return 0;54 }
codeforces 88E Interesting Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。