题解：P11269 【MX-S5-T3】IMAWANOKIWA (Construction ver.)
~要是今年联赛放这个我就被创烂了。~
被这题硬控了 3h，跟大家分享一下我的巨大冗长的小丑分讨做法。
题意就不赘述了。
首先我们需要让最后剩下来的数最小。
因为值域只有
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 2 |
| 2 | 1 | 2 | 1 |
容易发现只有
依据这个我们容易得出三个结论：
只有 0 的情况才能结果为 0 。
只有 1 、2 的情况结果取决于 2 数量的奇偶性。
只有 0 、1 的情况结果一定为 1 。
那么既有
首先我们考虑最基础的，假设只有一个 0 ，那么手玩几组样例会发现，只有形如 ...12021... ，也就是中间为 0 、两侧紧贴 2 、更左更右都只有 1 的情况结果才会为 2 ，其余结果都为 1 。
这个也是很好证明的，一个
其余情况若只有一边有
那若
稍微推一推就会发现若 0 的数量大于 2 则一定可以使得结果为 1 。
考虑序列最后一定可以化为形如
如果你推到了这一步，那么恭喜你可以在本题获得 25 分的高分啦！！！
到这本题看似完成了一半。
~然而这才刚刚开始。~
题目里还需要我们操作方案的字典序最小。
这个我们还是可以考虑分讨。
对于以下三种：
只有 0 的情况、只有 1 、2 的情况、只有 0 、1 的情况。
我们只需要一直操作第一个就行了。
对于只有一个 0 的情况：
若形如 ...12021... 。
那么答案已经确定，也只需一直操作第一个就行了。
若右边有偶数个 2 ：
那么右边至少是可以自己消掉的，我们可以先操作第一个直到遇到
若左边有偶数个 2 ：
那么此时右边是奇数个
若左右都是奇数个 2 ：
因为已经判掉了答案为
对于 0 的数量大于一：
我们显然可以先一直选第一个直到只剩下两个
若不看左边的 0 ，右边可以将答案消为一：
那么直接按一个
若不看左边的 0 ，右边不合法：
那么我们需要先用左边的
到这这个题才算做完了，当然还有若干 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;
}