NOIP训练营内部试题-光速传播字符串

题目

Day3T3

Hja 拥有一套时光穿梭技术，能把字符串以超越光速的速度传播，但是唯一
的问题是可能会 GG。在传输的过程中，可能有四种情况：
1、字符串没有发生改变。
2、字符串的某一位由 0 变 1 或者由 1 变 0。
3、某一位消失了。
4、多了一位。
为了防止字符串 GG，Hja 保证发送的字符串只由 01 组成，并且所有字符
串开始的长度均为?，并且所有为 1 的位置的下标之和一定是? + 1的倍数。在
给定了你这些条件之后，Hja 告诉你传输之后的字符串，并按照以下规则复原
字符串：
1、对于一个字符串，按照四种规则从前到后的优先级依次尝试能否复原为
一个合法的字符串。
2、对于同一种操作，更靠前的位置更加优先。
3、对于同一种操作的同一位置，0 比 1 更加优先。
4、如果没有任何一种方法复原字符串，则输出−1。
【输入格式】
第一行一个整数?，代表所有字符串的长度。
接下来若干行，每行一个字符串。
【输出格式】
对于每个字符串，输出一行代表答案。
【样例输入】
4
0000
011
1011
11011
【样例输出】
0000
0110
1001
1111
【数据范围与规定】
对于100%的数据，4 ≤ ? ≤ 1000，字符串数量不超过3000。

题解

略恶心的模拟：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 2005

int n,num[MAXN];

char s[MAXN];

bool check1(char *s){

    int len = strlen(s+1);

    if(len != n) return false;

    int Sum = 0;

    for(int i=1; i<=n; ++i) if(s[i] == '1') Sum += i;

    for(int i=1; i<=n; ++i)

        if(s[i] == '1'){

            Sum -= i;

            if(Sum % (n+1) == 0){

                s[i] = '0';

                printf('%s\n',s+1);

                return true;

            }

            Sum += i;

        }

    return false;

}

bool check4(char *s){

    int len = strlen(s+1);

    if(len != n) return false;

    int Sum = 0;

    for(int i=1; i<=len; ++i) if(s[i] == '1') Sum += i;

    if(Sum % (n+1) == 0){

        printf('%s\n',s+1);

        return true;

    }

    return false;

}

bool check3(char *s){//多了一位   ---- >  消掉 

    int len = strlen(s+1);

    if(len != n+1) return false;

    int Sum = 0;

    for(int i=1; i<=len; ++i) {

        num[i] = num[i-1];

        if(s[i] == '1') Sum += i,++num[i];

    }

    for(int i=1; i<=len; ++i){

        Sum -= num[len] - num[i];

        if(s[i] == '1') Sum -= i;

        if(Sum % (n+1) == 0){

            for(int j=1; j<i; ++j) printf('%c',s[j]);

            for(int j=i+1; j<=len; ++j) printf('%c',s[j]);

            printf('\n');

            return true;

        }

        Sum += num[len] - num[i];

        if(s[i] == '1') Sum += i;

    }

    return false;

}

bool check2(char *s){

    int len = strlen (s+1);

    if(len != n-1) return false;

    int Sum = 0;

    for(int i=1; i<=len; ++i){

        num[i] = num[i-1];

        if(s[i] == '1') Sum += i,++num[i];

    }

    for(int i=1; i<=n; ++i){

        Sum += num[len] - num[i-1];

        if(Sum % (n+1) == 0){

            for(int j=1; j<i; ++j) printf('%c',s[j]);

            printf('0');

            for(int j=i; j<=len; ++j) printf('%c',s[j]);

            printf('\n');

            return true;

        }

        Sum += i;

        if(Sum % (n+1) == 0){

            for(int j=1; j<i; ++j) printf('%c',s[j]);

            printf('1');

            for(int j=i; j<=len; ++j) printf('%c',s[j]);

            printf('\n');

            return true;

        }

        Sum -= i + num[len] - num[i-1];

    }

    return false;

}

int main(int argc,char *argv[]){

    freopen('a.in','r',stdin);

    freopen('a.out','w',stdout);

    scanf('%d',&n);

    while(~scanf('%s',s+1)){

        bool ok = false;

        ok = check4(s);

        if(ok) continue;

        ok = check1(s);

        if(ok) continue;

        ok = check2(s);

        if(ok) continue;

        ok = check3(s);

        if(ok) continue;

        printf('-1\n');

    }

    fclose(stdin);fclose(stdout);

    return 0;

}