题解：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$ 个数和不变。
$$
\color{red}\_\_\quad \color{black}1\quad \color{blue}\_\_\quad \color{black}1\quad \color{red}\_\_\quad \color{black}1\quad \color{blue}\_\_\quad \color{black}1\quad \color{red}\_\_\quad \color{black}1\quad \color{blue}\_\_\quad \color{black}1\quad \color{red}\_\_\quad \color{black}1\quad \color{blue}\_\_\quad
$$
于是当所有 $1$ 都聚在一起的时候，左边的 $0$ 个数和右边的 $0$ 个数即为定值，因此结论得证（当 $k$ 为偶数的时候一个位置的长为 $k+1$ 的连续段不可能翻到其它位置的连续段）。
模拟即可。操作次数很少。
```cpp
#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
```