Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
建议管理员核对数据, 藐视有 c > 10000的情况。代码中 加了句 if( c > 10000 )while(1); TLE了, 没加就AC。。 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n, c; int ont, offt; int on[102], off[102]; typedef struct { int len; __int64 a[20], b[20]; }ANS; ANS que[3]; __int64 P2[4], P1[4]; __int64 P[52]; struct node { char s[102]; }ans[20]; bool cmp( struct node a, struct node b ) { if( strcmp( &(a.s[1]), &(b.s[1]) ) < 0 )return true; else return false; } void solve() { __int64 d = 1; for(int i=1; i <= 50; i++ ){ P[i] = (d<<(i)); } for(int i=0;i<4;i++){ P1[i] = 0; P2[i] = 0; } for(int i=1; i <= 50; i++ ) { if(i%2){ P1[0] += P[i]; P2[0] += P[i]; } if( (i%2) == 0 ){ P1[1] += P[i]; P2[1] += P[i]; } P1[2] += P[i]; P2[2] += P[i]; if( (i%3) == 1 ) { P1[3] += P[i]; } if( ((i+50)%3) == 1 )P2[3] += P[i]; } int a = 0, b = 1; que[0].len = 1; que[0].a[0] = P1[2]; que[0].b[0] = P2[2]; __int64 x, y; for(int i = 1; i <= c; i++){ a = 1-a; b = 1-b; que[a].len = 0; for(int j = 0; j < que[b].len; j++){ for(int k = 0; k < 4; k++ ){ x = que[b].a[j]^P1[k]; y = que[b].b[j]^P2[k]; int z; for( z = 0; z < que[a].len; z++ ){ if( x == que[a].a[z] && y == que[a].b[z] ){ break; } } if(z >= que[a].len){ que[a].a[que[a].len] = x; que[a].b[que[a].len] = y; que[a].len++; } } } } int i; for( i=0; i<que[a].len; i++){ for(int k=1;k<=n;k++){ if(k<=50){ ans[i].s[k] = ( (P[k]&que[a].a[i]) == 0 ? '0' : '1' ); } else{ ans[i].s[k] = ( (P[k-50]&que[a].b[i]) == 0 ? '0' : '1' ); } } ans[i].s[n+1]=0; } sort(ans,ans+que[a].len,cmp); for(int k=0; k<que[a].len;k++){ for( i=1;i<ont;i++){ if( (ans[k].s[on[i]] == '0' ) )break; } if(i < ont )continue; for( i=1;i<offt;i++){ if( (ans[k].s[off[i]] == '1') )break; } if(i<offt)continue; printf("%s\n", &ans[k].s[1]); } } int main() { int ds, i; scanf("%d", &n ); { scanf("%d",&c); if( c > 10000 )while(1); // 不加这句话 就AC, 加了就TLE ont = 1; do { scanf("%d",&ds ); if( ds > n )continue; if( ds <= 0 )break; for( i = 1; i < ont; i++ )if( on[i] == ds )break; if( i >= ont )on[ont++] = ds; }while(1); offt = 1; do { scanf("%d",&ds ); if( ds > n )continue; if( ds <= 0 )break; for( i = 1; i < offt; i++ )if( off[i] == ds )break; if( i >= offt )off[offt++] = ds; }while(1); solve(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator