自动搬运

查看原文

来自洛谷，原作者为

	qijianci 义无反顾奋不顾身不顾一切地——向前冲！

搬运于2025-08-24 23:05:55，当前版本为作者最后更新于2024-11-10 22:31:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

~要是今年联赛放这个我就被创烂了。~

被这题硬控了 3h，跟大家分享一下我的巨大冗长的小丑分讨做法。

题意就不赘述了。

首先我们需要让最后剩下来的数最小。

因为值域只有 $2$，我们可以先给操作结果打一个表。

	0	1	2
0		1	1
1	1		2
2		2	1

容易发现只有 $0$、$0$ 才能合并出 $0$，$2$、$2$ 才能消掉一个 $2$ 。

依据这个我们容易得出三个结论：

只有 $0$ 的情况才能结果为 $0$。

只有 $1$、$2$ 的情况结果取决于 $2$ 数量的奇偶性。

只有 $0$、$1$ 的情况结果一定为 $1$。

那么既有 $0$ 又有 $2$ 的情况如何判断呢？

首先我们考虑最基础的，假设只有一个 $0$，那么手玩几组样例会发现，只有形如 $...12021...$，也就是中间为 $0$、两侧紧贴 $2$、更左更右都只有 $1$ 的情况结果才会为 $2$ ，其余结果都为 $1$。

这个也是很好证明的，一个 $0$ 最多只能消掉一个 $2$，且 $1$ 可以把 $0$ 去掉。上面这种情况 $0$ 一定会抵消掉一个 $2$， $2$ 又无法被 $1$ 消掉，因此结果一定为 $2$。

其余情况若只有一边有 $2$，那 $2$ 的奇偶性一定可以被 $0$ 控制，若两边都有 $2$ 且有一边的数量大于2，那么若数量为偶数可以自行抵消，若数量为奇数那数量至少为3，可以把最靠近 $0$ 的两个 $2$ 先合并成为 $1$ 来控制 $0$ 的有无来控制 $2$ 的奇偶性。

那若 $0$ 的数量大于 2 怎么办呢？

稍微推一推就会发现若 $0$ 的数量大于 2 则一定可以使得结果为 $1$。

考虑序列最后一定可以化为形如 $2020202...$ 的形式，我们一定可以通过把中间相邻的 $0$ $2$ 合并为 $1$ 来消去中间的 $0$ 和 $2$，仅剩最左和最右的 $2$，最后合并这两个 $2$ 就行了，唯一的corner case：$2002$ 只需要 $0$ $2$ 相互抵消就行了。

如果你推到了这一步，那么恭喜你可以在本题获得 25 分的高分啦！！！

到这本题看似完成了一半。

~然而这才刚刚开始。~

题目里还需要我们操作方案的字典序最小。

这个我们还是可以考虑分讨。

对于以下三种：

只有 $0$ 的情况、只有 $1$、$2$ 的情况、只有 $0$、$1$ 的情况。

我们只需要一直操作第一个就行了。

对于只有一个 $0$ 的情况：

若形如 $...12021...$。

那么答案已经确定，也只需一直操作第一个就行了。

若右边有偶数个 $2$：

那么右边至少是可以自己消掉的，我们可以先操作第一个直到遇到 $0$，然后再分讨一下下一次操作是否会改变 $2$ 的奇偶性。

若左边有偶数个 $2$：

那么此时右边是奇数个 $2$，我们可以先操作第一个直到遇到 $0$，然后再使 $0$ 消掉右边的 $2$。

若左右都是奇数个 $2$：

因为已经判掉了答案为 $2$ 的情况，所以左右一定至少有一边可以用 $1$ 消掉 $0$。为了保证字典序，我们应该优先用右边的 $1$ 来消掉，这样左边就可以一直选第一个，若右边不合法才优先用左边的。

对于 $0$ 的数量大于一：

我们显然可以先一直选第一个直到只剩下两个 $0$，因为数量大于一一定合法。

若不看左边的 $0$，右边可以将答案消为一：

那么直接按一个 $0$ 的方案做就行了。

若不看左边的 $0$，右边不合法：

那么我们需要先用左边的 $0$ 消掉一个 $2$，剩下的就简单了。

到这这个题才算做完了，当然还有若干 corner 我没有讲的很详细，如果你选择了我的~小丑~做法，剩下的就自己慢慢发现吧。

end.

最后讲些闲话。

出题人的做法确实会比我的更优秀。

我多遇上了 inf 的分讨，多消耗了 inf 的时间，才堪堪完成了这道题，但当看到“恭喜你，通过了此题”的时候，喜悦仍压过了烦闷，轻松仍压过了疲倦......

或许这 就是信竞的魅力所在吧。

代码

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define popc __builtin_popcount
const int N=1e5+5,B=13331;
int n,T,sum[N],s[N],cnt;
ull pw[N],ans[N];
string t;
void g(int x){s[x+1]=popc(s[x]+s[x+1]);}
void sol1(){
    int i,j,k,l,r,x,y,z;
    for(i=1,s[n+1]=1;i<=n;++i)if(s[i]==0){x=i;break;}
    for(i=1;i<=n;++i)sum[i]=sum[i-1]+(s[i]==2);
    if((sum[n]-sum[x])%2==0){
        for(i=1;i<x;++i)ans[++cnt]=1,g(i);
        if(!s[x])for(i=x+1;i<=n&&s[i]==2;++i)ans[++cnt]=2,g(i);
    } else if(sum[x]%2==0){
        for(i=1;i<x-1;++i)ans[++cnt]=1;
        for(i=x+1;i<=n&&s[i]!=2;++i)ans[++cnt]=3-(x==1),g(i);
        if(x>1)ans[++cnt]=2;
    } else {
        if(sum[n]-sum[x]==1&&s[x+1]==2){
            if(s[x-1]==2){
                for(i=1;sum[x]-sum[i+1]>=2;++i)ans[++cnt]=1,g(i);
                for(++i;i<x;++i)ans[++cnt]=2;
            } else {
                for(i=1;i<x-2;++i)ans[++cnt]=1;
                ans[++cnt]=2;
            }
        } else {
            for(i=1;i<x-1;++i)ans[++cnt]=1;
            for(i=x+1;i<=n&&s[i]==2;++i)ans[++cnt]=3,g(i);
            ans[++cnt]=2;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y,z;
    cin>>T,pw[0]=s[0]=1;
    l=T;
    for(i=1;i<N;++i)pw[i]=pw[i-1]*B;
    while(T--){
        cin>>t,n=t.size(),ans[0]=cnt=0,r=n;
        for(i=1,s[n+1]=0;i<=n;++i)s[i]=t[i-1]-'0';
        for(i=1,x=0;i<=n;++i)
            s[i]?0:(x++,y=i),sum[i]=sum[i-1]+(s[i]==2);
        if(x==n)printf("0 ");
        else if(!x)printf("%d ",(sum[n]&1)+1);
        else if(x==1&&sum[n]==2&&s[y+1]==2&&s[y-1]==2)printf("2 ");
        else printf("1 ");
        if(x==n||!x||(x==1&&sum[n]==2&&s[y+1]==2&&s[y-1]==2)||!sum[n])
            while(cnt<n-1)ans[++cnt]=1;
        else if(x==1)sol1();
        else {
            for(i=n;i;--i)if(!s[i]){x=i;break;}
            for(i=x-1;i;--i)if(!s[i]){k=i;break;}
            if(sum[n]-sum[k]==2&&s[x+1]==2&&s[x-1]==2){
                for(i=1;i<k-1;++i)ans[++cnt]=1,g(i);
                if(k==1||!s[k-1]){
                    if(k>1)ans[++cnt]=1;
                    for(i=k+1;i<x-1;++i)ans[++cnt]=2;
                    ans[++cnt]=1,ans[++cnt]=2;
                } else if(s[k-1]==1){
                    for(i=k+1;i<x-1;++i)ans[++cnt]=3;
                    ans[++cnt]=2,ans[++cnt]=1,ans[++cnt]=2;
                } else {
                    if(s[k+1]==1){
                        ans[++cnt]=2;
                        for(i=k;i<x-1;++i)ans[++cnt]=1;
                        ans[++cnt]=2;
                    } else {
                        for(i=k+1;i<x-1;++i)ans[++cnt]=3;
                        ans[++cnt]=2,ans[++cnt]=2;
                    }
                }
            } else {
                for(i=1;i<k;++i)ans[++cnt]=1,g(i);
                if(!s[k]){
                    if(sum[n]-sum[k]==3&&k+1<x-1&&s[k+1]==2&&s[x-1]==2&&s[x+1]==2){
                        for(i=k+1;i<x-1;++i)ans[++cnt]=2;ans[++cnt]=1;
                        ans[++cnt]=2;while(cnt<n-1)ans[++cnt]=1;
                    } else ans[++cnt]=1,g(k++);
                } if(cnt<n-1)for(i=k;i<=n;++i)s[i-k+1]=s[i];n=n-k+1,sol1();
            }
        } for(n=r;cnt<n-1;)ans[++cnt]=1;
        while(cnt)ans[0]+=ans[cnt]*pw[n-1-cnt],cnt--;
        printf("%llu\n",ans[0]);
    } return 0;
}