P1942 词编码_NOI导刊 by HydraNazis
Trinity
·
·
题解
P1942 词编码_NOI导刊
题目描述
长度为 n 的 01 串满足是 1 位置号总和整除(n+1)，而且可以进行以下四种操作：
1$ . 将一个 $0$ 变成 $1
2$ . 删去一个 $0$ 或 $1
3$ . 插入一个 $0$ 或 $1
现给你多个**变换后**的 $01$ 串，需要你求出变换前的 $01$ 串
有以下规定：
多解情况，以 $4$ 操作优先 $1$,$2$,$3$ 操作次之。
同一操作，以从左到右顺序优先。
操作 $2$ ,以删 $0$ 优先。
无解，输出$-1
分析
本题暴力分较高，无论用 sring+STL 还是 char 数组+模拟来维护，都躲不过 操作2 , 3的一次循环，还有模拟修改位置的一次循环，总复杂度为O(数据组数\times n^2),1000的数据范围可以过 80 分。
所以我们有两种思路，一种是通过数学观察，避免真正地进行操作，另一种是降低插入和删除的操作复杂度（经过实测，套上平衡树板子，因为常数过大而数据范围太小只过了40分，千万不要尝试）。
解答
$~~~~~~~$针对操作 $4$，直接计算出题目要求的有 $1$ 位置号和（以下称要求值），而且要满足长度要求，判断一下即可。
$~~~~~~~$针对操作 $2$ 和 $3$，我们发现一旦添加或删去一个字符，整个串的要求值会改变，而暴力的思想就是强行重算。我们仔细观察，其实这两个操作只是改变了选择操作位置之后所有 $1$ 的位置号，从而改变要求值。
$~~~~~~~$解释完后，一些同学已经明白该怎么搞了，但是不知道代码具体怎么实现的可以继续看看。
$~~~~~~~$我们考虑对每组数据维护一个前缀和 $pre$ （准确来说是后缀和，反正是相同的），记录从位置 $1$ 到位置 $i$ 有多少个 $1$ 出现，我们就知道修改位置后有多少个 $1$。
$~~~~~~~$针对 $2$ 的逆过程，选择添加的位置以后，每有一个 $1$ ，就会使操作前的的要求值加上$1$，最后根据添的是 $1$ 或 $0$ 加上这一位的数。
$~~~~~~~$针对 $3$ 的逆过程，删去的原理也是一样的。
$~~~~~~~$针对 $1$ 的逆过程，换成 $0$ 改变的是这一位，在原来的要求值上加上选择的位置值。
$~~~~~~~$看证明：
$~~~~~~~sum \mod (n+1)=0~~~~~~~~~~~~~~~~~~~~~$正向操作时满足
$~~~~~~~(sum+x) \mod (n+1)=x\ne 0~~~~$操作后满足
$~~~~~~~$而且$1\leq x\leq n
$~~~~~~~$这已经说的不能再详细了，看暴力和$AC$代码吧
$~~~~~~~$两份代码中的 $STL$ 十分实用，特别是当你写暴力的时候，简直爽。
$~~~~~~~s.insert(pos,string\ t)~~~~~~$在 $s$ 的 $pos$ 位置**后**插入 $t
```cpp
inline bool check(string str)
{
int len=str.length(),sum=0;
for(int i=0;i<=len-1;i++)
if(str[i]=='1')sum+=i+1;
if(sum%(n+1)==0||sum==0)return true;
return false;
}
inline string solve(string str)//你懂得，就很暴力。
{
int len=str.length();
string test=str;
if(len==n&&check(test))return str;
if(len==n)
{
for(int i=0;i<=len-1;i++)
{
test[i]='0';
if(check(test))return test;
test=str;
}
return "-1";
}
if(len<n)
{
for(int i=0;i<=len;i++)
{
test.insert(i,"0");
if(check(test))return test;
test=str;
test.insert(i,"1");
if(check(test))return test;
test=str;
}
return "-1";
}
if(len>n)
{
for(int i=0;i<=len-1;i++)
{
test.erase(i,1);
if(check(test))return test;
test=str;
}
return "-1";
}
}
int main()
{
string s;
n=read();
while(cin>>s)cout<<solve(s)<<endl;
return 0;
}
```
然后上 $AC$ 代码
```cpp
int n,sum,cnt,pre[N],x;
string s;
inline string solve(string str)
{
sum=cnt=x=0;
memset(pre,0,sizeof(pre));
int len=str.length();
if(len<n-1&&len>n+1)return "-1";//长度错误。
for(int i=0;i<=len-1;i++)
{
if(str[i]=='1')cnt++,sum+=i+1,pre[i+1]=pre[i]+1;
else pre[i+1]=pre[i];//cnt->1的个数，sum->要求值，pre->前缀和，有多少个1.
}
x=sum%(n+1);
if(len==n)
{
if(!x||!sum)return str;
else if(str[x-1]=='1'){str[x-1]='0';return str;}//如以上所说。
return "-1";
}
if(len<n)
{
for(int i=0;i<=len;i++)
if((sum+(cnt-pre[i]))%(n+1)==0){str.insert(i,"0");return str;}//题目要求0优先，两个循环一定不要写在一起，否则···
for(int i=0;i<=len;i++)
if((sum+(cnt-pre[i])+i+1)%(n+1)==0){str.insert(i,"1");return str;}
return "-1";
}
if(len>n)
{
for(int i=0;i<=len-1;i++)
{
if((sum-(cnt-pre[i+1]))%(n+1)==0&&str[i]=='0'){str.erase(i,1);return str;}//一定要带上str【i】的条件，否则···
if((sum-(cnt-pre[i+1])-i-1)%(n+1)==0&&str[i]=='1'){str.erase(i,1);return str;}
}
return "-1";
}
}
int main()
{
n=read();
while(cin>>s)cout<<solve(s)<<endl;
return 0;
}//完美谢幕。
```
## 总结
说大实话，这其实不太能称得上提高组的题目，暴力分太多，优化很好想，但是对于题目的理解**十！分！重！要！**
题面给的十分毒瘤，没有明显表明多组数据，还有不明所以的句子。
最重要的一点，$string$ 用的是真的爽。