【AcWing 235. 魔法珠

題意：

有n堆魔法珠，第i堆有ai個，兩個人輪流進行以下操作：

當輪到某人操作時，如果每堆中魔法珠的數量均為 1，那么他就輸了。
問誰贏誰輸

題解：

經典博弈論問題
注意本題中的操作方法為將p分為小于p的約數
我們先求出p的約數(小于p)，然后對于每個約數跑遍dfs求出sg，所有sg異或起來，因為題目說要消失一堆，所以消失哪一堆就異或哪一堆，記得再填回去(因為每次只消失一堆，其他還在)
詳細過程看代碼

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2000; int a[maxn]; int sg[maxn]; int N; int dfs(int x){if(sg[x]!=-1)return sg[x];if(x==1) return sg[x]=0;int vis[maxn];vector<int>vec;vec.clear();memset(vis,0,sizeof(vis));for(int i=1;i*i<=x;i++){if(x%i==0){vec.push_back(i);if(x/i!=i&&x/i<x)vec.push_back(x/i); }}int ans=0;for(int i=0;i<vec.size();i++){ans^=dfs(vec[i]);}for(int i=0;i<vec.size();i++){ans^=dfs(vec[i]);//去掉第i堆 vis[ans]=1;ans^=dfs(vec[i]);//再加回去 }for(int i=0;i<maxn;i++){if(!vis[i])return sg[x]=i;}} int main() {memset(sg,-1,sizeof(sg));while(cin>>N){int ans=0;int x;for(int i=1;i<=N;i++){cin>>x; ans^=dfs(x);}if(ans)puts("freda");else puts("rainbow"); }return 0; }

總結

以上是生活随笔為你收集整理的【AcWing 235. 魔法珠的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。