题解 CF906E 【Reverses】

· · 题解

这道题有两个做法，一个是空间复杂度O(\Sigma n)的回文树解法，另一个解法是O(n)空间复杂度的dp解法

然后这个菜鸡过于菜了导致他根本不会什么回文树解法

题意

给你两个串s1,s2唯一能做的操作是翻转s1的一个区间，问你翻转几次能够将s1变成s2,无解则输出-1,否则输出方案，要求翻转的区间互不相交

一个并不平凡的转化

我们构造一个新的串出来

按照样例为例

abcxxxdef

cbaxxxfed

我们将两个字符串交替写下

acbbcaxxxxxxdfeefd

发现一件事如果s2的一个区间(l,r)是s1的(l,r)这个区间翻转形成的 那么转化后的字符串上(2l-1,2r)这个区间一定是一个回文串

那么我们的问题就转化为了将一个字符串拆分成若干个偶回文串，其中如果一个偶回文串的长度是2则不付出代价，求最小拆分代价

为了解决这个问题我们需要先解决最小回文串拆分问题，这篇题解的大部分都在讲述最小回文串拆分问题

最小回文串拆分

为了做这道题我们首先要证明一个结论

看这张图

如果x,y,z都是一个回文串并且y是x的最长回文后缀，z是y的最长回文后缀

那么这里有两个非常强劲的结论

如果字符串v和字符串u的长度相等，那么u和v是两个一模一样的字符串

如果u的长度比v的长度大，那么u的长度也一定比z的长度大,并且u的长度不可能比v的长度小

首先我们先来证一下比较好证的第一个结论

显然u的长度比y大的时候v和u的长度不可能相等，所以我们来考虑u的长度不小于y的情况

那么我们来看这张图

由于x是回文串所以uy=yu，由于y也是回文串所以vz=zv，所以我们发现v是x的一个前缀，所以显然当u和v的长度相等的时候u和v是两个一膜一样的字符串

接下来我们来证明第二个结论

我们采取反证法来证明这个结论

假设z的长度大于u的话，并且此时v还比u小

那么我们发现z是zu的一个长度过半的公共前后缀(这东西看图就能知道)由于z是一个回文串，那么我们可以立即推得此时z+u是一个回文串 又因为v比u小所以zu这个串的长度比y大，还是x的一个后缀，这与y是x的最长回文后缀的性质相矛盾……，因此我们就证明了这个相当棒的结论

有了这个性质有什么用呢？

我们来考虑一个比较trival的O(N^2)dp然后看看能不能优化一发这个dp

我们设Ph(i)表示i这个前缀的所有回文后缀集合,也就是一堆整数x_{1},x_{2},x_{3}……x_{n}，显然我们可以O(n)的从Ph(i-1)递推到Ph(i)(对于每个x考虑字符串的第x-1位和第i位是不是同一个字符,是就插入x-1,否则我们什么也不做)

那么我们会有另一个非常显然的转移方程，设dp(i)表示i这个前缀的最小回文拆分数，则有转移方程

dp(i)=\min_{j \in Ph(i)}dp(j-1)+1

暴力转移下来是O(n^2)的

那么有没有什么办法可以强行将这个dp优化到O(nlogn)呢？

答案是有的，考虑我们之前证明的性质,假设Ph(i)这个数组是排好序的，那么这个数组的差分数组(这里的差分定义为前向差分，也就是 \Delta i=x_{i}-x_{i-1})一定单调(因为v \leq u)并且一个更加强的结论是差分数组之多有O(log(n))个不同的取值，证明就是如果差分数组开始下降的话回文后缀的长度会至少折半(因为v<u的时候z也一定小于u)这样就有O(log(n))个本质不同的值了

有了这个性质之后我们可以将Ph(i)用一些等差数列来表示,每个等差数列只需存储(首项,公差,项数)这个三元组就能表示了,注意这里我们存储的时候是将Delta相等的值存储到同一三元组当中，因此x1永远自己成一个三元组，因为他的差分无意义

那么我们考虑有了Ph(i-1)的等差数列表示之后可不可以快速的递推到Ph(i)的等差数列表示呢?

答案是肯定的，为什么呢？

因为根据我们的结论，只要u和v长度一样，那么u和v完 全 一 致,那么同一个等差数列中的元素就应该长这样

容易看出x1,x2,x3……xn后面的字符(蓝色位置)都是一样的

因此整个集合(灰色位置和绿色位置)能否转移成功主要看x1(绿色位置)能不能成功的转移

此时还有一个小问题就是即使x1可以成功的转移，他可能也会被踢出等差数列，原因是红色位置的字符串没有成功转移导致x1的\Delta值改变了

那么这种情况下我们把每一个项数大于二的三元组(s,delta,siz)拆成s和(s+delta,delta,siz-1)转移就行了

最后记得合并一下公差相等的等差数列就行了

还要处理下边界条件，插入(i,i)这个显然的回文串,如果(i-1,i)是个回文串的话也要插入这个回文串

接下来是如何运用这个等差数列表示的集合加速我们的递推了

画图可以得到一个性质是如果Ph(i)有一个三元组(s,delta,siz)且siz大于2的话,Ph(i-delta)会有一个三元组是(s,delta,siz-1)

这东西有什么用呢？

我们建一个辅助数组dp(i,\Delta)表示

dp(i,\Delta)=\min_{j \in (s,\Delta,siz)}dp(j-1)+1

也就是所有属于这个等差数列的回文后缀对答案的贡献

那么我们可以轻易的得到一个递推式就是

dp(i,\Delta)=\min(dp(i-\Delta,\Delta),dp(mx\Delta-1)+1)

其中mx\Delta表示所有差分为\Delta的回文后缀中最靠右的那个

当然这个前提是等差数列的项数不为1，项数为1的话直接暴力转移就行了

那么我们就可以先递推出dp(i,\Delta)来然后暴力扫一遍就可以更新dp(i)了

此时你可以直接强行拿map存储dp(i,\Delta)这个数组就行，复杂度O(nlog^2n)

不过这里有一个更加优雅的做法，采用滚动数组,我们将dp(i,\Delta)的值存储在数组的第i-\Delta位置,这样其实是将dp值存储在上图的红色位置上，显然在碰到下一个循环节之前红色位置不会再次成为回文串，因此我们的滚动数组是无冲突的

至此我们使用了O(nlogn)的时间复杂度和O(n)的空间复杂度解决了这个问题

关于本题

其实在刚才的dp上胡乱改改就行了

首先维护等差数列的时候只插入偶回文串

然后我们还要处理长度是2的回文串免费这个限制

解决方案相当粗暴，如果(i-1,i)是回文串，那么直接让dp(i)从dp(i-2)当中转移过来就行了

还要记一下从哪个位置转移过来的，然后你就可以输出方案了

代码很短，重点在于理解这个玄学算法

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e6+10;int n;char mde[N];char mde1[N>>1];char mde2[N>>1];
struct nod//dp用的结构体 
{int v;int fr;friend bool operator <(nod a,nod b){return (a.v==b.v)?a.fr<b.fr:a.v<b.v;}}dp[N],g[N];
struct data{int s;int d;int siz;inline int cmx(){return s+d*(siz-1);}}se[2][500];int tp[2];
int al[N];int ar[N];int atp;
inline void ins1(data* b,int& hd,const int& s)//插入一个位置 
{
    if(hd==0){b[++hd]=(data){s,0x3f3f3f3f,1};}
    else 
    {
        int del=s-b[hd].cmx();
        if(del==b[hd].d)b[hd].siz++;else b[++hd]=(data){s,del,1};
    }
}
inline void ins2(data* b,int& hd,const data& p)//插入一个等差数列 
{if(b[hd].d==p.d)b[hd].siz+=p.siz;else b[++hd]=p;}
inline void trs(data* a,int tp,data* b,int& hd,const char& c)//转移 
{
    hd=0;
    for(int i=1;i<=tp;i++)
        if(mde[a[i].s-1]==c)
        {ins1(b,hd,a[i].s-1);if(a[i].siz!=1)ins2(b,hd,(data){a[i].s+a[i].d-1,a[i].d,a[i].siz-1});}
}
int main()
{
    scanf("%s",mde1+1);scanf("%s",mde2+1);for(n=1;mde1[n+1]!='\0';n++);
    for(int i=1;i<=n;i++)mde[i<<1]=mde1[i];for(int i=1;i<=n;i++)mde[(i<<1)-1]=mde2[i];n<<=1;mde[0]='#';
    for(int i=1;i<=n;i++)g[i]=(nod){0x3f3f3f3f,0};
    for(int i=1;i<=n;i++)dp[i]=(nod){0x3f3f3f3f,0};
    for(int i=1,p=1,q=0;i<=n;i++,p^=1,q^=1)
    {
        trs(se[q],tp[q],se[p],tp[p],mde[i]);
        if(mde[i]==mde[i-1])ins1(se[p],tp[p],i-1);if(i&1)continue;//小剪枝 
        if(mde[i]==mde[i-1])dp[i]=min(dp[i],(nod){dp[i-2].v,i-2});data* a=se[p];
        for(int j=1;j<=tp[p];j++)
        {
            nod ret=(nod){0x3f3f3f3f,0};int ed=a[j].cmx()-1;//计算dp(i,delta) 
            if(a[j].siz==1){ret=min((nod){dp[ed].v+1,ed},ret);}
            else {ret=min((nod){dp[ed].v+1,ed},g[a[j].s-a[j].d]);}//滚动数组 
            if(a[j].s-a[j].d>=0)g[a[j].s-a[j].d]=ret;dp[i]=min(dp[i],ret);
        }
    }if(dp[n].v==0x3f3f3f3f){printf("-1\n");return 0;}//输出方案 
    for(int p=n;p;p=dp[p].fr)if(dp[p].fr<p-2){al[++atp]=dp[p].fr+1,ar[atp]=p;}
    printf("%d\n",atp);for(int i=1;i<=atp;i++)printf("%d %d\n",(al[i]+1)>>1,(ar[i]+1)>>1);return 0;//拜拜程序~ 
}