P11269 【MX-S5-T3】IMAWANOKIWA (Construction ver.)
题目翻译：
对一个初始长度为 \(n\) 的序列 \(a\) 进行操作，每次操作可以任选两个相邻的数 \(a_j,a_{j+1}\) 将这两个数删去，在加上 \(popc(a_j+a_{j+1})\)
- \(popc(x)\),表示 \(x\) 在二进制下 \(1\) 的个数
而我们要求出一个操作序列，由于是删二加一，因此总共会有 \(n-1\)次操作，且最后会剩下一个数，而要求的就是使最后的数为 \(t\) 的最小字典序的操作序列。 - 令操作序列 \(p_i\) 表示第 \(i\) 次操作所选择的 \(j\)，则要求出字典序最小的操作序列。并将它进行转换变为答案。
性质分析：
因为只有 \(0,1,2\) 三个数，而每次操作只会选择两个数，我们可以先对每次的结果经行一个打表：
| \(0\) | \(1\) | \(2\) | |
|---|---|---|---|
| \(0\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(1\) | \(1\) | \(2\) |
| \(2\) | \(1\) | \(2\) | \(1\) |
根据该表可以很容易得到一下性质：
\(1.\)若只有 \(0\) 那最终答案一定只为 \(0\)
\(2.\)若只有 \(1\) 那最终答案一定只为 \(1\)
\(3.\)若只有 \(1,2\) 那最终答案一定只为 \(1\)
\(2.\)若只有 \(1,2\) 那最终答案跟 \(2\) 的奇偶有关，因为只有两个 \(2\) 才能消掉 \(2\)
\(t\) 情况讨论：
根据以上的性质发现，若既有 \(0\) 和 \(2\) 那答案就不唯一，那我们可以找不同的情况下的答案：
分析 \(0\) 的个数：
\(1.\)若 \(0\) 的个数为零，那只有形如 \(…12021…\)的形式结果才有可能为 \(2\)，也就是中间一个 \(0\) 两边紧靠两个 \(2\)，接着左右只有 \(1\)。其他情况答案都肯定为 \(1\) 理由如下：
因为一个 \(0\) 可以消掉一个 \(2\) 使其变为 \(1\),而会剩下一个 \(2\) 而 \(2\) 无法消掉 \(1\) 那最终答案很明显就是 \(2\)
其他情况也就是 \(2\) 在一侧或者大于数量大于 \(2\) 那\(2\)的奇偶性一定可以被 \(0\) 控制，若为偶可以消掉一个变为奇，若为奇那也可以消掉一个变为偶。若同时 \(2\) 自己也可以自行抵消，变为 \(1\) 在控制 \(0\)，以此来控制 \(2\) 的奇偶性，所以答案只会为 \(1\)
若 \(0\) 的个数大于 \(1\)，那最终答案一定可以为 \(1\)，理由如下：
由于 \(2\) 可以消掉 \(1\), 而 \(1\) 又可以消掉 \(0\)然后又被 \(2\) 消掉，且 \(0\) 之间相互抵消，而 \(2\) 与 \(2\) 之间会抵消为 \(1\)。若先不考虑 \(0\) 与 \(2\) 之间的转换，那序列最终一定会变成 \(2,0\) 交替出现即\(2020202\)的形式，那中间的数相互抵消，最后也就为\(1\)。
那只需要判断 \(0,1,2\) 的个数和出现的位置，就能判断最终答案的 \(t\) 也就可以拿到 \(25\) 分的答案分
操作序列讨论：
要求出字典序最小，那尽量就从前面取。继续分论：
\(1.\)只有 \(0\) ,只有 \(1\)，只有 \(0,1\)，只有 \(1,2\) :
只需要一直消第一个即可
\(2.\)只有一个 \(0\)：
- 形如 \(12021\)，已经知道情况：
也就一直消第一个即可
- 若右边又偶数个 \(2\):
那么右边至少是可以自己消掉的，我们可以先操作第一个直到遇到 \(0\) 然后再分讨一下下一次操作是否会改变 \(2\) 的奇偶性。
- 若左边又偶数个 \(2\):
那么此时右边是奇数个 \(2\)，我们可以先操作第一个直到遇到 \(0\)，然后再使 \(0\) 消掉右边的 \(2\)。
- 若左右都只有奇数个 \(2\):
因为已经判掉了答案为 \(2\) 的情况，所以左右一定至少有一边可以用 \(1\) 消掉 \(0\)。为了保证字典序，我们应该优先用右边的 \(1\) 来消掉，这样左边就可以一直选第一个，若右边不合法才优先用左边的。
\(3.\)若 \(0\) 的个数大于 \(1\) ：
我们显然可以先一直选第一个直到只剩下两个 \(0\)，因为数量大于 \(1\) ,所以一定合法。
- 若不看左边的 \(0\)，右边可以将答案消为一：
那么直接按一个 \(0\) 的方案做就行了。
- 若不看左边的 \(0\)，右边不合法：
那么我们需要先用左边的 \(0\) 消掉一个 \(2\)，剩下的就简单了。
完整代码：
#include<bits/stdc++.h>
#define ull unsigned long long
#define popc __builtin_popcount
using namespace std;
const int N=1e5+5;
const int B=13331;
int n,T,cnt;
int sum[N],s[N];
ull pw[N],ans[N];
string t;
void get(int x){
s[x+1]=popc(s[x]+s[x+1]);
}
void sol1(){
int i,x;
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;
get(i);
}
if(!s[x]){
for(i=x+1;i<=n && s[i]==2;i++){
ans[++cnt]=2;
get(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);
get(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;
get(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;
get(i);
}
ans[++cnt]=2;
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
freopen("popc.in","r",stdin);
freopen("popc.out","w",stdout);
int i,k,r,x,y;
cin>>T;
pw[0]=s[0]=1;
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){
cout<<"0 ";
}
else if(!x){
cout<<(sum[n]&1)+1<<" ";
}
else if(x==1 && sum[n]==2 && s[y+1]==2 && s[y-1]==2){
cout<<"2 ";
}
else{
cout<<"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;
get(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;
get(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;
get(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--;
}
cout<<ans[0]<<endl;
}
return 0;
}