題目
Day3T3
Hja 擁有一套時(shí)光穿梭技術(shù)，能把字符串以超越光速的速度傳播，但是唯一
的問(wèn)題是可能會(huì) GG。在傳輸?shù)倪^(guò)程中，可能有四種情況：
1、字符串沒(méi)有發(fā)生改變。
2、字符串的某一位由 0 變 1 或者由 1 變 0。
3、某一位消失了。
4、多了一位。
為了防止字符串 GG，Hja 保證發(fā)送的字符串只由 01 組成，并且所有字符
串開(kāi)始的長(zhǎng)度均為?，并且所有為 1 的位置的下標(biāo)之和一定是? + 1的倍數(shù)。在
給定了你這些條件之后，Hja 告訴你傳輸之后的字符串，并按照以下規(guī)則復(fù)原
字符串：
1、對(duì)于一個(gè)字符串，按照四種規(guī)則從前到后的優(yōu)先級(jí)依次嘗試能否復(fù)原為
一個(gè)合法的字符串。
2、對(duì)于同一種操作，更靠前的位置更加優(yōu)先。
3、對(duì)于同一種操作的同一位置，0 比 1 更加優(yōu)先。
4、如果沒(méi)有任何一種方法復(fù)原字符串，則輸出?1。
【輸入格式】
第一行一個(gè)整數(shù)?，代表所有字符串的長(zhǎng)度。
接下來(lái)若干行，每行一個(gè)字符串。
【輸出格式】
對(duì)于每個(gè)字符串，輸出一行代表答案。
【樣例輸入】
4
0000
011
1011
11011
【樣例輸出】
0000
0110
1001
1111
【數(shù)據(jù)范圍與規(guī)定】
對(duì)于100%的數(shù)據(jù)，4 ≤ ? ≤ 1000，字符串?dāng)?shù)量不超過(guò)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;
}
聯(lián)系客服
