题目描述地址：http://cdqz.openjudge.cn/noip/1009/
摘要：
一个发送机可以通过一条隧道发送一些以二进制代码组成的单词。，在其尽头的接收机可以使用特殊技术恢复到最初的单词。每个单词最初都由0和1组成。所有的单词最初长上簦都为n(4≤N ≤1000)。当穿过隧道之后单词可能发生以下几种情况之一：
(1)任意(一个)0被1取代
(2)任意(一个)符号被删除
(3)一个符号(0或1)被插入到任何位置
(4)不改变
我们知道最初的单词都具有以下性质：有1的位置号的总和是N+1的倍数，或者是0。
【input】
N和转换后的单词，每个单词占一行。单词数不大于2001．不会有其它任何东西，除了一些空格与空行，
【Output】
你的程序应该打印输出原始序列的词，注意换行。
若有多解，操作4优先，不行则按操作1，2,3优先。同一操作，按操作位置最先的优先。同一操作，按操作位置最先的优先(从左到右数起l，2,3，…N)，还有操作2时，被删数列，先在被删数列添0，不行再添l。
如果没答案输出-1
【Sample input】
4
0000
011
1011
11011
【Sample Output】
0000
0110
1001
1111
这道题其实很简单的，只是一个简单的模拟罢了。唯一需要注意的就是时间复杂度的问题。我最开始是纯裸的，完全没有加优化，惨痛T掉3个点……下来想了一下，其实这道题用前缀和是相当容易的。
设a[i]表示处理后的串中从第i位开始的1的总数，先计算出1的位置的编号和，如果可行直接输出，否则判断位数。
1.如果位数为n-1，则肯定是删除了一位，此时枚举下标i，如果第i位上插入一个0，则和增加a[i]，1的话就增加a[i]+i+1，一旦成功就输出，如果所有位置的插入都不成功，就输出-1.
2.位数为n，则肯定有一个1是被0取代了。枚举下标i，第i位上将1变成0后将和减去i+1，成功就直接输出，否则输出-1.
3.位数为n+1，则肯定增加了一位，此时枚举下标i（该删除的位），删除第i位只需将和减去a[i]（i位上为0），a[i]+i（i位上为1），成功就输出，都不成功输出-1。
注意事项：
1.C++中字符串是零索引的，但是题目中却要求一索引。
2.字符串总数不定！！！不是n！！
3.求和其实有很多种方法，比如树状数组（我当时也想过，但是没写出来）。
4.那substr什么的太不稳定了，还是for一遍吧！（复杂度差不多）
废话说了一堆，最后我想吐槽几句标程，神马意思！！！！没加任何优化！！！！跑得飞快！！！！这不科学！！！！
代码：
View Code 1 #include<iostream> 2 #include<fstream> 3 #include<string> 4 5 using namespace std; 6 7 string s; 8 int n,len,sbwhc[2012]; 9 10 int main() 11 { 12 ifstream cin("word.in"); 13 ofstream cout("word.out"); 14 15 cin>>n; 16 while(cin>>s) 17 { 18 int k=0; 19 len=s.length(); 20 memset(sbwhc,0,sizeof(sbwhc)); 21 22 sbwhc[len]=0; 23 for(int i=len-1;i>=0;i--) 24 if(s[i]=='1') sbwhc[i]=sbwhc[i+1]+1; 25 else sbwhc[i]=sbwhc[i+1]; 26 27 for(int i=0;i<len;i++) 28 if(s[i]=='1') k+=i+1; 29 30 if(k%(n+1)==0&&len==n) 31 { 32 cout<<s<<endl; 33 continue; 34 } 35 36 if(len==n) 37 { 38 bool f=false; 39 for(int i=0;i<len;i++) 40 { 41 if(s[i]=='1') 42 if((k-i-1)%(n+1)==0) 43 { 44 f=true; 45 s[i]='0'; 46 cout<<s<<endl; 47 break; 48 } 49 } 50 if(!f) cout<<-1<<endl; 51 continue; 52 } 53 54 if(len<n) 55 { 56 bool f=false; 57 for(int i=0;i<=len;i++) 58 { 59 if((k+sbwhc[i])%(n+1)==0) 60 { 61 f=true; 62 for(int j=0;j<i;j++) cout<<s[j]; 63 cout<<"0"; 64 for(int j=i;j<len;j++) cout<<s[j]; 65 cout<<endl; 66 break; 67 } 68 69 if((k+sbwhc[i]+i+1)%(n+1)==0) 70 { 71 f=true; 72 for(int j=0;j<i;j++) cout<<s[j]; 73 cout<<"1"; 74 for(int j=i;j<len;j++) cout<<s[j]; 75 cout<<endl; 76 break; 77 } 78 } 79 if(!f) cout<<-1<<endl; 80 continue; 81 } 82 83 if(len>n) 84 { 85 bool f=false; 86 for(int i=0;i<len;i++) 87 { 88 if(s[i]=='0') 89 if((k-sbwhc[i])%(n+1)==0) 90 { 91 f=true; 92 s.erase(i,1); 93 cout<<s<<endl; 94 break; 95 } 96 97 if(s[i]=='1') 98 if((k-sbwhc[i]-i)%(n+1)==0) 99 { 100 f=true; 101 s.erase(i,1); 102 cout<<s<<endl; 103 break; 104 } 105 } 106 107 if(!f) cout<<-1<<endl; 108 continue; 109 } 110 } 111 return 0; 112 }
转载于:https://www.cnblogs.com/stickjitb/archive/2012/05/25/2518695.html
