asp.net 电商网站开发,安徽合肥制作网站公司,廉政网站建设,绍兴中小企业名录【AcWing 235. 魔法珠
题意#xff1a;
有n堆魔法珠#xff0c;第i堆有ai个#xff0c;两个人轮流进行以下操作#xff1a; 当轮到某人操作时#xff0c;如果每堆中魔法珠的数量均为 1#xff0c;那么他就输了。 问谁赢谁输
题解#xff1a;
经典博弈论问题 注意本…【AcWing 235. 魔法珠
题意
有n堆魔法珠第i堆有ai个两个人轮流进行以下操作 当轮到某人操作时如果每堆中魔法珠的数量均为 1那么他就输了。 问谁赢谁输
题解
经典博弈论问题 注意本题中的操作方法为将p分为小于p的约数 我们先求出p的约数(小于p)然后对于每个约数跑遍dfs求出sg所有sg异或起来因为题目说要消失一堆所以消失哪一堆就异或哪一堆记得再填回去(因为每次只消失一堆其他还在) 详细过程看代码
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn2000;
int a[maxn];
int sg[maxn];
int N;
int dfs(int x){if(sg[x]!-1)return sg[x];if(x1) return sg[x]0;int vis[maxn];vectorintvec;vec.clear();memset(vis,0,sizeof(vis));for(int i1;i*ix;i){if(x%i0){vec.push_back(i);if(x/i!ix/ix)vec.push_back(x/i); }}int ans0;for(int i0;ivec.size();i){ans^dfs(vec[i]);}for(int i0;ivec.size();i){ans^dfs(vec[i]);//去掉第i堆 vis[ans]1;ans^dfs(vec[i]);//再加回去 }for(int i0;imaxn;i){if(!vis[i])return sg[x]i;}}
int main()
{memset(sg,-1,sizeof(sg));while(cinN){int ans0;int x;for(int i1;iN;i){cinx; ans^dfs(x);}if(ans)puts(freda);else puts(rainbow); }return 0;
}
相关文章：
