题解【AT2173 [AGC007F] Shik and Copying String】

**题意** : 定义字符串的复制操作如下 ： 将字符串 $S$ 复制得到 $S'$。则 $|S'|=|S|$ ，且 $S'[1]=S[1]$ ，而 $S'[i]=S[i]$ 或者 $S'[i-1]$。 现在给出字符串 $S,T$ ，问 $S$ 至少经过几次复制之后可以得到 $T$。 $|S|\leq 10^6$ ，时限$\texttt{2s}$。 ------------ 首先特判 $S=T$。 考虑 $T$ 中的每个字符来源于 $S$ 中的那个字符，表示对应关系的边是不会相交的，且一定是一个字符对应一个区间。 假设我们得知了对应关系和所需步数，那么可以采取这样的策略 ： 先一直尽量右移，直到移动到需要覆盖的左边界处，然后向下到达底线，然后横向覆盖。（实际上就是让路径尽量靠右） 如图 ：  不难证明这是最优策略。 考虑我们得知了对应关系，如何得到最优步数。 我们从后往前考虑每个 $T$ 中需要匹配的左端点，让路径尽量靠右，若目前的层数无法完成，则加一层。 具体地，用**队列**维护上一条路径的所有（右侧）转折点。这些转折点的横纵坐标都是单调增加的。 当 $S_i$ 要前往 $T_j$。 末端弹出（pop）那些横坐标在 $j$ 后面的所有转折点。 然后，所有转折点都向左下方移动一位。 若起点衔接不紧密，则会新增（push）一个转折点。如图 ：  （深蓝色是上一条路径的转折点，深红色是新路径的转折点） 答案是所有转折点的纵坐标的最大值 $+1$。 若事先未给定匹配关系，从后往前考虑 $T$ ，贪心地选择 $S$ 中能匹配的最靠右的字符即可。 复杂度为 $O(n)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 1005000 using namespace std; char s[MaxN],t[MaxN]; int n,pre[MaxN],p[255],ans,ql,qr; struct Data{int i,j;}q[MaxN]; int main() { scanf("%d%s%s",&n,s+1,t+1); bool fl=1; for (int i=1;i<=n;i++) if (s[i]!=t[i])fl=0; if (fl){puts("0");return 0;} for (int i=1;i<=n;i++){ pre[i]=p[s[i]]; p[s[i]]=i; } int ql=1,qr=0; for (int i=n,las=n+1,c=0;i;i--){ if (t[i]==t[i-1])continue; while(p[t[i]]>min(las,i))p[t[i]]=pre[p[t[i]]]; if (!p[t[i]]){puts("-1");return 0;} int u=p[t[i]],v=i; while(ql<=qr&&v<q[ql].i-c+1)ql++; if (las!=u&&u<v)q[++qr]=((Data){u+c,1-c}); if (ql<=qr)ans=max(ans,q[ql].j+c); c++;las=u; }printf("%d",ans+1); return 0; } ```