| ||||||||||
| 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