hdu1851_A Simple Game
题意 :n堆石子,分别有M1,M2,·······,Mn个石子,各堆分别最多取L1,L2,·····Ln个石头,两个人分别取,一次只能从一堆中取,取走最后一个石子的人获胜。后选的人获胜输出Yes,否则输出No。
思路:先看一堆石子,然后求该堆的sg函数,最后由SG定理可知 将每堆石子的SG函数值异或,即可得解。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; #define maxn 22 int main() { int n,m,l,i,j,k,T; int sg[maxn],vis[maxn],fsg; cin>>T; while(T--) { scanf("%d",&n); fsg=0; for(i=0; i<n; i++) { scanf("%d%d",&m,&l); /** /////////////求每一堆的sg[m]函数值*/ for(j=0; j<=l; j++) sg[j]=j; for(k=l+1; k<=m; k++) { memset(vis,0,sizeof(vis)); for(j=k-l;j<k;j++) vis[sg[j]]=1; for(j=0;;j++) if(!vis[j]) { sg[k]=j; break; } } /** //////////////////*/ fsg^=sg[m]; } if(!fsg) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }