题目
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;
}
联系客服