题解 CF906E【Reverses】
cyffff
·
·
题解
\text{Link}
题意
给两个长度相同的串 A,B，允许翻转 A 的任意个子区间，求翻转最少次数使得 A 与 B 相等并求出方案。
## 思路
构造 $C=a_1b_1a_2b_2...a_nb_n$。
我们首先想如果翻转了 $A$ 中的 $[l,r]$ 意味着 $a_l=b_r,a_{l+1}=b_{r-1}...$，所以在 $C$ 中 $a_lb_la_{l+1}b_{l+1}...a_rb_r$ 这段区间是回文的，则问题转化为偶回文子串划分问题，可以参考 [$\text{CF932G}$]( https://www.luogu.com.cn/problem/CF932G) 的方法处理。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
const int N=1e6+10;
int n;
int dp[N],f[N],ansl[N];
char str[N],inp1[N],inp2[N];
struct Palindromic_Tree{
struct node{
int ch[26];
int fail,len,diff,slink;
}a[N];
int last,siz;
inline void init(){
siz=1,last=0;
a[0].fail=1,a[1].fail=0;
a[0].len=0,a[1].len=-1;
}
inline int getfail(int p,int x){
while(str[x]!=str[x-a[p].len-1])
p=a[p].fail;
return p;
}
inline void insert(char ch,int x){
int p=getfail(last,x);
int w=ch-'a';
if(!a[p].ch[w]){
int cur=++siz;
a[cur].len=a[p].len+2;
int tmp=getfail(a[p].fail,x);
a[cur].fail=a[tmp].ch[w];
a[p].ch[w]=cur;
a[cur].diff=a[cur].len-a[a[cur].fail].len;
a[cur].slink=(a[cur].diff==a[a[cur].fail].diff)?a[a[cur].fail].slink:a[cur].fail;
}
last=a[p].ch[w];
}
inline void calc(){
init();
n=readstr(inp1);
n=readstr(inp2);
for(int i=1;i<=n;i++) str[i*2-1]=inp1[i],str[i*2]=inp2[i];
memset(dp,127,sizeof(dp));
dp[0]=0;
str[0]='\n';
n<<=1;
for(int i=1;i<=n;i++){
insert(str[i],i);
if(i%2==0&&str[i]==str[i-1]&&dp[i]>dp[i-2])
dp[i]=dp[i-2],ansl[i]=i-2;
for(int j=last;j;j=a[j].slink){
f[j]=i-a[a[j].slink].len-a[j].diff;
if(a[a[j].fail].diff==a[j].diff&&dp[f[j]]>dp[f[a[j].fail]]){
f[j]=f[a[j].fail];
}
if(i%2==0&&dp[i]>dp[f[j]]+1)
dp[i]=dp[f[j]]+1,ansl[i]=f[j];
}
}
if(dp[n]>1e9){
write(-1);
return ;
}
write(dp[n]),putc('\n');
for(int i=n;i>=1;i=ansl[i]){
if(i-ansl[i]!=2)
write(ansl[i]/2+1),putc(' '),write(i/2),putc('\n');
}
}
}PAM;
int main(){
PAM.calc();
flush();
return 0;
}
```
推荐一下 [$\text{zhylj}$ 的题解](https://www.luogu.com.cn/blog/ryoku/solution-cf932g)。
再见 qwq~