官方题解写得太好了,通俗易懂,推荐大家去看官方题解
看完之后我竟然觉得英语很亲切???~~懂了,下次英语六级就用codeforces复习~~

C1. Prefix Flip (Easy Version)

Easy Version,官方题解给出了两种做法。
Solution 1: O(n) time with 3n operations
Solution 2: O(n^2^) time with 2n operations
在这里插入图片描述
首先,对于[1,i]区间内的所有字符先全部取反,再翻转的操作,等价于另一个操作:
把区间分成两半,对称的两个字符有四种情况,00->11,11->00, 01->01,10->10,即对称的两个字符,若为00/11则操作后直接全部取反,若为01/10则操作后不变。举个例子10111,前后位置对称的字符依次是11,01,1(单个字符直接取反),那么对称的字符依次变为00,01,0,那么字符串操作后变为00010。

介绍一下Solution 2。设第一个字符串为a,第二个字符串为b,从后往前遍历a,如果a[i]!=b[i]那么就需要改变a[i],即需要操作[1,i]区间的字符串。但是a[i]不一定能够改变,比如a[1]=0,a[i]=1,那么这样即使操作了[1,i]区间也没有效果(对称位置分别为0,1,操作后还是0,1),所以在这种情况下需要先取反a[1],使得a[1]=a[i],之后便可操作[1,i]区间。因此,对于每个字符最多需要进行2次操作,总操作数<=2*n,模拟每次操作耗时O(n),所以总复杂度O(n^2^)。

// O(n^2), the number of operations are less than 2*n
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int T,n;
char a[N],b[N];
vector<int>ans;
char f(char i) // 0->1, 1->0
{
    return i=='1'?'0':'1';
}
void change(int l,int r) // O(n) per operation
{
    int len=r-l+1;
    int mid=(l+r)/2;
    for(int i=l;i<=mid;i++)
    {
        int j=r+1-i;
        if(a[i]==[j])
        {
            a[i]=f(a[i]);
            a[j]=f(a[j]);
        }
    }
    if(len&1)a[mid]=f(a[mid]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        cin>>n>>a+1>>b+1;
        ans.clear();
        for(int i=n;i>=1;i--)
        {
            if(a[i]!=b[i])
            {
                if(a[i]==a[j]) // 不用变a[1],只要变[1,i]
                {
                    change(1,i);
                    ans.push_back(i);
                }
                else  // 变a[1]之后,再变[1,i]
                {
                    change(1,1);
                    change(1,i);
                    ans.push_back(1);
                    ans.push_back(i);
                }
            }
        }
        int sz=ans.size();
        printf("%d",sz);
        for(int i=0;i<sz;i++)
            printf(" %d",ans[i]);
        printf("\n");
    }
    return 0;
}

C2. Prefix Flip (Hard Version)

在这里插入图片描述
Hard Version也有几种做法,就介绍一下我认为最简单的做法吧。

首先,考虑将a和b都转换为全0字符串。
如何转换呢?其实只要从前往后遍历,遇到a[i]!=a[i+1]就操作[1,i]区间,这样就能保证遍历到 i 时,[1,i-1]一定是全为0或全为1的字符串, 那么遍历到最后,如果最后一个字符是0,那么字符串就会变成全0;如果最后一个字符是1,那么字符串就会变成全1,再操作一次变成全0即可。
最后,只要把a,b变成全0字符串的操作记录下来,a->0,0<-b,然后正序输出a的操作(最多n个),逆序输出b的操作(最多n个)。

比Easy Version优化的地方在于:我们不需要每次浪费O(n)时间来模拟操作[1,i]区间的过程;每次直接O(1)就可得解,所以总复杂度为O(n),并且总操作数<=2*n。

// O(n), the number of operations are less than 2*n
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n;
char a[N],b[N];
vector<int>ans1,ans2;
void solve(char s[],vector<int> &g)
{
    for(int i=1;i<=n-1;i++)
    {
        if(s[i]!=s[i+1])
            g.push_back(i);
    }
    if(s[n]=='1')g.push_back(n); // 全1,再操作一次变成全0
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        cin>>n>>a+1>>b+1; // a,b下标从1开始
        ans1.clear();
        ans2.clear();
        solve(a,ans1); // 注意传参是a,不是a+1
        solve(b,ans2);
        int sz1=ans1.size();
        int sz2=ans2.size();
        printf("%d",sz1+sz2);
        for(int i=0;i<sz1;i++)
            printf(" %d",ans1[i]);
        for(int i=sz2-1;i>=0;i--) // 倒序输出
            printf(" %d",ans2[i]);
        printf("\n");
    }
    return 0;
}