Ural 1540. Battle for the Ring

发布时间:2016-12-10 11:18:09 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Ural 1540. Battle for the Ring",主要涉及到Ural 1540. Battle for the Ring方面的内容,对于Ural 1540. Battle for the Ring感兴趣的同学可以参考一下。

Ural 1540. Battle for the Ring 题大意就是给你一堆石子,每个石子都有权重,每次取一堆中的一个石子,将这堆石子中所有权重比该石子小的全部拿掉,分成若干堆新石子。 不能操作的输。 用状态sg[cur][l][r]表示第cur堆石子l 到 r的sg值。 记忆化搜索之。。。 #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<set> #include<queue> #include<map> #include<sstream> #include<iostream> using namespace std; #define FOR(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define DOR(i,a,b) for(int (i)=(a);(i)>=(b);(i)--) #define bug puts("Fuck"); #define LL long long #define pb push_back #define mp make_pair #define nMax 101 #define eps 1e-8 #define inf 0x7fffffff #define CLR(a) memset((a),(0),sizeof((a))) set<int> S; int val[60][200]; int sg[60][nMax][nMax]; int SG(int cur,int l,int r){ if(sg[cur][l][r] != -1) return sg[cur][l][r]; if(l>r) return sg[cur][l][r] = 0; // one can't move any more int vis[nMax];CLR(vis); for(int i=l;i<=r;i++) { // if I choose the ith number int j=l,k=l,ret=0; while(j<=r){ while(j<=r && val[cur][j] <= val[cur][i]) j++; k = j; while(k<=r && val[cur][k] > val[cur][i]) k++; if(j > r) break; ret ^= SG(cur,j,k-1); // the leaved numbers j = k; } vis[ret]=1; } for(int i=0;;i++) if(!vis[i]) return sg[cur][l][r] = i; } int const oo = 1000111; int main(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif int n;scanf("%d",&n); int ret = 0; memset(sg,-1,sizeof(sg)); for(int i=0;i<n;i++) { scanf("%d",&val[i][0]); for(int j=1;j<=val[i][0];j++) { scanf("%d",&val[i][j]); } ret ^= SG(i,1,val[i][0]); } if(ret == 0) printf("S\n"); else { int chain=oo,num=oo; for(int i=0;i<n;i++) { ret ^= SG(i,1,val[i][0]); for(int c=1;c<=val[i][0];c++) { int res = 0; int j=1,k=1; while(j<=val[i][0]){ while(j<=val[i][0] && val[i][j] <= val[i][c]) j++; k=j; while(k<=val[i][0] && val[i][k] > val[i][c]) k++; if(j>val[i][0]) break; res ^= SG(i,j,k-1); j = k; } if( (res^ret)==0 ) { if(c < num) { chain = i + 1; num = c; } } } if(chain != oo) break; ret ^= SG(i,1,val[i][0]); } printf("G\n"); printf("%d %d\n",chain,num); } return 0; }

上一篇:sysobjects的相关内容
下一篇:web.xml error-page 不起作用解决方案

相关文章

相关评论