首页 > 代码库 > bzoj 1188 : [HNOI2007]分裂游戏 sg函数
bzoj 1188 : [HNOI2007]分裂游戏 sg函数
题目链接
给n个位置， 每个位置有一个小球。 现在两个人进行操作， 每次操作可以选择一个位置i， 拿走一个小球。然后在位置j, k(i<j<=k)处放置一个小球。 问你先进行什么操作会先手必胜以及方法数量。
感觉这题好神
如果一个位置有偶数个小球， 那么等价于这个位置没有小球。 因为第二个人可以进行和第一个人相同的操作。 所以初始值%2。
然后我们把每个位置看成一个状态， 如果i有一个小球， 等价于j, k 也有一个小球。 然后转移。
方法数量就n^3枚举就可以了。
#include <bits/stdc++.h>using namespace std;#define mem1(a) memset(a, -1, sizeof(a))int sg[22], a[22], n;int mex(int x){ if(~sg[x]) return sg[x]; bool vis[1000]; memset(vis, 0, sizeof(vis)); for(int i = x + 1; i <= n; i++) { for(int j = i; j <= n; j++) { vis[mex(i)^mex(j)] = 1; } } for(int i = 0; ; i++) { if(!vis[i]) return sg[x] = i; }}int main(){ int t; cin>>t; while(t--) { cin>>n; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } mem1(sg); int ans = 0, cnt = 0; for(int i = 1; i <= n; i++) { if(a[i]&1) { ans ^= mex(i); } } int flag = 0; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { for(int k = j; k <= n; k++) { ans ^= mex(i)^mex(j)^mex(k); if(!flag && ans == 0) { printf("%d %d %d\n", i-1, j-1, k-1); flag = 1; } if(ans == 0) { cnt++; } ans ^= mex(i)^mex(j)^mex(k); } } } if(cnt != 0) cout<<cnt<<endl; else { printf("-1 -1 -1\n0\n"); } } return 0;}
bzoj 1188 : [HNOI2007]分裂游戏 sg函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。