从题意来看,是基本的SG函数应用,把刚学的set用进去优化,发现不行...
TLE...
再看看SG的原理,网上大部分都是采用递归,而那些题解报告都是一把抄,嗤之以鼻..
下面是直接TLE的代码:
/********************* S-Nim Sevenster 2012.08.26 12:55 *********************/ #include<iostream> #include<algorithm> #include<set> using namespace std; bool cmp( int a,int b ){ return a>b; } void setSG( int *sg,int *S,int Sn ) { //sort( S,S+Sn,cmp ); sg[0]=0; set<int> se; set<int>::iterator it; for( int i=1;i<=10000;i++ ) { se.erase(se.begin(),se.end()); for( int j=0;j<Sn;j++ ) { if( i-S[j]<0 ) continue; se.insert( sg[i-S[j]] ); } int fnum=0; while( true ) { if( se.find(fnum)==se.end() ) { sg[i]=fnum; break; } fnum++; } } return ; } int main() { int S_size; int S[111];int sg[11111]; while( scanf("%d",&S_size)!=EOF&&S_size ) { for( int i=0;i<S_size;i++ ) scanf( "%d",&S[i] ); setSG( sg,S,S_size ); int T,n,data; scanf( "%d",&T ); while( T-- ) { int xo=0; scanf( "%d",&n ); for( int i=0;i<n;i++ ) { scanf( "%d",&data ); xo^=sg[data]; } printf( "%c",xo?'W':'L' ); } printf( "\n" ); } return 0; }
看来STL不能胡乱用=.=
悲催悲催...
/********************* S-Nim Sevenster 2012.08.26 12:55 *********************/ #include<iostream> #include<algorithm> #include<set> using namespace std; bool cmp( int a,int b ){ return a>b; } void setSG( int *sg,int *S,int Sn ) { //sort( S,S+Sn,cmp ); sg[0]=0; //set<int> se; //set<int>::iterator it; bool flag[111]; for( int i=1;i<=10000;i++ ) { memset(flag,0,sizeof(flag)); for( int j=0;j<Sn;j++ ) { if( i-S[j]<0 ) continue; flag[sg[i-S[j]]]=1; } for( int j=0;j<=101;j++ ) if( flag[j]==0 ) { sg[i]=j; break; } } return ; } int main() { int S_size; int S[111];int sg[11111]; while( scanf("%d",&S_size)!=EOF&&S_size ) { for( int i=0;i<S_size;i++ ) scanf( "%d",&S[i] ); setSG( sg,S,S_size ); int T,n,data; scanf( "%d",&T ); while( T-- ) { int xo=0; scanf( "%d",&n ); for( int i=0;i<n;i++ ) { scanf( "%d",&data ); xo^=sg[data]; } printf( "%c",xo?'W':'L' ); } printf( "\n" ); } return 0; }