「NOIP模拟赛」词编码
一个发送机可以通过一条隧道发送一些以二进制代码组成的单词。在其尽头的接收机可以使用特殊技术恢复到最初的单词。每个单词最初都由0和1组成。所有的单词最-初长度都为n(4≤N ≤l000)。当穿过隧道之后单词可能发生以下几种情况之一：
(1)任意(一个)0被1取代
(2)任意(一个)符号被删除
(3)一个符号(0或1)被插入到任何位置
(4)不改变
我们知道最初的单词都具有以下性质：有1的位置号的总和是N+1的倍数，或者是0.
Input
N和转换后的单词，每个单词占一行。单词数不大于2001，不会有其它任何东西，除了一些空格与空行。
Outpul
你的程序应该打印输出原始序列的词，注意换行： 。
若有多解，操作4优先，不行则按操作1,2，3优先。同一操作，按操作位置最先的优先(从左到右数起l，2,3，…N)，还有操作2时，被删数列，先在被删数列添0，不行再添1。如果没答案输出-1
Sample Input
4
0000
011
1011
11011
Sample Output
0000
0110
1001
1111
题解
根据长度模拟即可。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,l,sum,f[2005]; char ch[2005]; bool solve4() { if(sum%(n+1))return 0; printf("%s\n",ch+1); return 1; } bool solve1() { for(int i=1;i<=l;i++) if(ch[i]=='1'&&(sum-i)%(n+1)==0) {ch[i]='0';printf("%s\n",ch+1);return 1;} return 0; } bool solve2() { for(int i=1;i<=l+1;i++) if((f[i]+sum)%(n+1)==0) { for(int j=1;j<=i-1;j++) printf("%c",ch[j]); printf("0"); for(int j=i;j<=l;j++) printf("%c",ch[j]); printf("\n"); return 1; } for(int i=1;i<=l+1;i++) if((f[i]+sum+i)%(n+1)==0) { for(int j=1;j<=i-1;j++) printf("%c",ch[j]); printf("1"); for(int j=i;j<=l;j++) printf("%c",ch[j]); printf("\n"); return 1; } return 0; } bool solve3() { for(int i=1;i<=l;i++) { int t=sum-f[i+1]; if(ch[i]=='1')t-=i; if(t%(n+1)==0) { for(int j=1;j<=i-1;j++) printf("%c",ch[j]); for(int j=i+1;j<=l;j++) printf("%c",ch[j]); printf("\n"); return 1; } } return 0; } int main() { //freopen("word.in","r",stdin); //freopen("word.out","w",stdout); n=read(); while(scanf("%s",ch+1)!=EOF) { l=strlen(ch+1); sum=0;memset(f,0,sizeof(f)); for(int i=l;i;i--) if(ch[i]=='1') sum+=i,f[i]=f[i+1]+1; else f[i]=f[i+1]; if(l==n) { if(solve4())continue; if(solve1())continue; } else if(l<n) { if(solve2())continue; } else { if(solve3())continue; } printf("-1\n"); } return 0; } |
Subscribe
计数器 9793782
OI 课件=>
OI 课件=>