Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

建议管理员核对数据, 藐视有 c > 10000的情况。

Posted by whitesea at 2008-08-11 19:27:14 on Problem 1176 and last updated at 2008-08-11 19:29:36
代码中 加了句 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator