题解 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)$当中转移过来就行了 还要记一下从哪个位置转移过来的，然后你就可以输出方案了 代码很短，重点在于理解这个玄学算法 上代码~ ```C #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;//拜拜程序~ } ```