CF1237H

· · 题解

题意

有一个长度为 n（n 为偶数）的 01 序列，你可以进行不超过 n+1 次操作，每次操作将一个长度为偶数的前缀翻转（reverse 不是 flip）。
你需要构造一种方案使得这个序列变成目标序列，或者声明无解。

题解

好像有正经的做法，这里给一个靠谱的随机化乱搞。

首先考虑，由于翻转的前缀都是偶数，那么相当于把 01 两个两个捆绑在一起。
将 00 设为 0，01 为 1，10 为 2，11 为 3。 那么相当于是，翻转序列的一个前缀，并且 1 \leftrightarrow 2。

显然如果 a 中 cnt_0,cnt_3,cnt_1+cnt_2 都必须和 b 相等。

考虑这样一个构造过程：
从后往前扫，每次把最后一位确定了，然后将剩下的部分变成子问题。

比如说我们现在在对 1 到 i 这个前缀进行处理。
首先我们需要找到一个 a_j = b_i，然后将其翻转至第 1 位，再翻转至第 i 位。
这样我们用了 2 步处理了原序列中的 2 位。

但是这样有一个问题：现在要搞个 b_i=1，但是 a 中只有 2 怎么办？
我们选择一个 2，翻到第 1 位后再进行一次翻转，他还是 2，再翻转至 b_i 位变成 1 即可。

这样还是有个问题，这样我们用 3 步才处理了原序列中的 2 位，超过步数限制咋办？

我们运用人类智慧，每次在合法的数中随机选取一个，基本上是不是能保证不存在 a 中 1,2 只出现 1 个的情况了啊？

在加上还有 \dfrac 1 4 的概率不需要操作，有 \dfrac 1 4 的概率要找的数已经在第 1 个位置了，容错性很强。

看了一下评测记录，用的最多次数的一个点也只有 2915 次，看上去非常靠谱。

代码

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define pii pair<int,int>
#define fi first
#define se second
#define rd(x) x=read()
#define wt(x) write(x)
using namespace std;
const int N=4000+5;
const int M=1e5+5;
const int mod=998244353;
int read(){int x=0;char ch=getchar();while(ch>'9'||ch<'0'){ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;}
void write(int x){if(x<0){putchar('-');x=-x;}if(x>=10)write(x/10);putchar(x%10+'0');}
int n,m,k;
char s[N],t[N];
int a[N],b[N];
int c1,c2,c3;
unsigned seed=std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
vector<int> ans;
vector<int> p;
void rev(int x)
{
    ans.push_back(x*2);reverse(a+1,a+x+1);
    for (int i=1;i<=x;i++) if (a[i]==1 || a[i]==2) a[i]=3-a[i];
}
void DOIT()
{
    scanf("%s",s+1);scanf("%s",t+1);
    n=strlen(s+1);n/=2;
    c1=c2=c3=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i*2-1]=='0' && s[i*2]=='0') a[i]=0;
        if (s[i*2-1]=='0' && s[i*2]=='1') a[i]=1;
        if (s[i*2-1]=='1' && s[i*2]=='0') a[i]=2;
        if (s[i*2-1]=='1' && s[i*2]=='1') a[i]=3;
        if (t[i*2-1]=='0' && t[i*2]=='0') b[i]=0;
        if (t[i*2-1]=='0' && t[i*2]=='1') b[i]=1;
        if (t[i*2-1]=='1' && t[i*2]=='0') b[i]=2;
        if (t[i*2-1]=='1' && t[i*2]=='1') b[i]=3;
        if (a[i]==0) c1++;else if (a[i]==3) c2++;else c3++;
        if (b[i]==0) c1--;else if (b[i]==3) c2--;else c3--;
    }
    if (c1!=0 || c2!=0 || c3!=0) {puts("-1");return;}
    ans.clear();
    for (int i=n;i>=1;i--)
    {
        if (a[i]==b[i]) continue;
        if (a[1]==b[i] && (a[1]==0 || a[1]==3)) {rev(i);continue;}
        if (a[1]==3-b[i] && (a[1]==1 || a[1]==2)) {rev(i);continue;}
        p.clear();for (int j=1;j<=i;j++) if (a[j]==b[i]) p.push_back(j);
        if (p.size())
        {
            int P=rnd()%p.size();P=p[P];
            rev(P);rev(i);
        } else 
        {
            for (int j=1;j<=i;j++) if (a[j]==3-b[i]) p.push_back(j);
            int P=rnd()%p.size();P=p[P];
            rev(P);rev(1);rev(i);
        }
    }
    cout<<ans.size()<<"\n";
    for (int x:ans) cout<<x<<" ";cout<<"\n";
}
signed main()
{
    int JYZ;rd(JYZ);while (JYZ--) DOIT();
}

/* 

*/