题解：CF1530G What a Reversal

冷月葬T魂 · 2024-05-08 16:44:41 · 题解

构造好题。*3300 的难度应该是有的。

首先注意到操作可逆，于是我们可以对 a 和 b 都进行操作。

于是在第一阶段我们从后往前贪心让 a 和 b 的最后一位匹配，每次只需要一次翻转。

但是注意到 k 大于等于 1 的个数的时候是 trivial 的，并且容易出现无解。

所以当剩下未匹配的 1 个数为 k+1 时进入下一阶段。

发现我们可以容易地将 k+1 个 1 给并在一起，具体地，设现在存在所有 1 的极小区间为 [l,r]，则不断翻转 [l+1,r] 和 [l,r-1] 即可。

通过手玩注意到当 k 为奇数的时候这个长为 k+1 的连续段可以被翻到序列开头，只需考虑 0111..1 怎么做即可。

通过打表注意到当 k 为偶数的时候一个位置的长为 k+1 的连续段好像不可能翻到其它位置的连续段。

于是尝试寻找不变量，这个不变量应当和奇偶性有关。考虑 k+1 个 1 把所有 0 分成了 k+2 段（将 01 序列转成整数序列的技巧），那么发现所有偶数段的 0 个数和不变，所有奇数段的 0 个数和不变。

于是当所有 1 都聚在一起的时候，左边的 0 个数和右边的 0 个数即为定值，因此结论得证（当 k 为偶数的时候一个位置的长为 k+1 的连续段不可能翻到其它位置的连续段）。

模拟即可。操作次数很少。

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](){}()
#define debuga(...) [](){}()
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; typedef long long ll;
constexpr int N=2e3+5; using pii = pair<int,int>;
int n,K,a[N],b[N]; vector<pii> ans1,ans2;
void DoA(int l,int r) { ans1.emplace_back(l,r); reverse(a+l,a+r+1); }
void DoB(int l,int r) { ans2.emplace_back(l,r); reverse(b+l,b+r+1); }
bool DONE(){
    if(memcmp(a+1,b+1,n<<2)!=0) return false;
    cout<<ans1.size()+ans2.size()<<'\n';
    reverse(ans2.begin(),ans2.end());
    for(auto [l,r]:ans1) cout<<l<<' '<<r<<'\n';
    for(auto [l,r]:ans2) cout<<l<<' '<<r<<'\n';
    return true;
}
void Mian(){
    ans1.clear(); ans2.clear();
    cin>>n>>K; char str[N]; cin>>str; For(i,1,n) a[i]=str[i-1]-'0';; cin>>str; For(i,1,n) b[i]=str[i-1]-'0';
    if(DONE()) return;
    if(K==0) return cout<<"-1\n",void();
    int A1=count(a+1,a+1+n,1);
    if(A1!=count(b+1,b+1+n,1)) return cout<<"-1\n",void();
    if(K>A1) return cout<<"-1\n",void();
    if(K==A1){
        DoA(find(a+1,a+1+n,1)-a,n);
        DoB(find(b+1,b+1+n,1)-b,n);
        if(DONE()) return;
        DoA(find(a+1,a+1+n,1)-a,n);
        if(DONE()) return; else return cout<<"-1\n",void();
    }
    int p=n;
    while(p>0&&A1>K+1){
        if(a[p]==b[p]) { A1-=a[p--]; continue; }
        if(a[p]==0){
            int tt=0,o=0; Rev(i,p,1) if((tt+=a[i])==K) { o=i; break; }
            assert(o); DoA(o,p);
        }
        else{
            int tt=0,o=0; Rev(i,p,1) if((tt+=b[i])==K) { o=i; break; }
            assert(o); DoB(o,p);
        }
        assert(a[p]==b[p]); p--; A1--;
    }
    if(p==0) return assert(DONE()),void();
    debug(A1); debuga(a,1,p); debuga(b,1,p);
    int l=1,r=p; while(a[l]==0) l++;; while(a[r]==0) r--;
    For(_,1,K){
        if(_&1) { DoA(l+1,r); while(a[r]==0) r--; }
        else { DoA(l,r-1); while(a[l]==0) l++; }
    }
    debuga(a,1,p);
    if(K&1) { For(_,1,K+1) if(_&1) DoA(1,r-1); else DoA(2,r); }
    debuga(a,1,p);
        l=1,r=p; while(b[l]==0) l++;; while(b[r]==0) r--;
    For(_,1,K){
        if(_&1) { DoB(l+1,r); while(b[r]==0) r--; }
        else { DoB(l,r-1); while(b[l]==0) l++; }
    }
    debuga(b,1,p);
    if(K&1) { For(_,1,K+1) if(_&1) DoB(1,r-1); else DoB(2,r); }
    debuga(b,1,p);
    if(DONE()) return; else return cout<<"-1\n",assert(~K&1),void();
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    int T; cin>>T; while(T--) Mian();
    return 0;
}

// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING

// Started Coding On: May 08 Wed, 15 : 39 : 16