自动搬运

查看原文

来自洛谷，原作者为

	Trinity **

搬运于2025-08-24 21:32:09，当前版本为作者最后更新于2018-08-19 20:38:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1942 词编码_NOI导刊

题目描述

长度为 $n$ 的 $01$ 串满足是 $1$ 位置号总和整除$(n+1)$，而且可以进行以下四种操作：
$1$ . 将一个 $0$ 变成 $1$
$2$ . 删去一个 $0$ 或 $1$
$3$ . 插入一个 $0$ 或 $1$
$4$ . 不改变
现给你多个变换后的 $01$ 串，需要你求出变换前的 $01$ 串
有以下规定：
多解情况，以 $4$ 操作优先 $1$,$2$,$3$ 操作次之。
同一操作，以从左到右顺序优先。
操作 $2$ ,以删 $0$ 优先。
无解，输出$-1$

分析

本题暴力分较高，无论用 $sring+STL$ 还是 $char$ 数组+模拟来维护，都躲不过 操作$2$ , $3$的一次循环，还有模拟修改位置的一次循环，总复杂度为$O($数据组数$\times n^2)$,$1000$的数据范围可以过 $80$ 分。
所以我们有两种思路，一种是通过数学观察，避免真正地进行操作，另一种是降低插入和删除的操作复杂度（经过实测，套上平衡树板子，因为常数过大而数据范围太小只过了40分，千万不要尝试）。

解答

$~~~~~~~$我们通过题目条件原串长度固定为 $n$，而每种修改操作只会修改一个字符，所以新串的长度仅会是 $n-1$ , $n$或 $n+1$，悄悄告诉你们加上这句话可以把暴力从 $70$ 升到 $80$分。
$~~~~~~~$针对操作 $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$
$~~~~~~~$显然第 $x$ 个字符就是修改的字符（当然这些是废话，跑一遍循环照样可以得这个答案，但是时间省一点是一点）
$~~~~~~~$这已经说的不能再详细了，看暴力和$AC$代码吧
$~~~~~~~$两份代码中的 $STL$ 十分实用，特别是当你写暴力的时候，简直爽。
$~~~~~~~s.insert(pos,string\ t)~~~~~~$在 $s$ 的 $pos$ 位置后插入 $t$
$~~~~~~~s.erase(pos,length)~~~~~~~~~~$从 $s$ 的 $pos$ 位置删去长度为 $length$的字符

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$ 代码

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$ 用的是真的爽。