题解【AT2173 [AGC007F] Shik and Copying String】
command_block
2021-04-26 20:56:57
**题意** : 定义字符串的复制操作如下 :
将字符串 $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$ 中的那个字符,表示对应关系的边是不会相交的,且一定是一个字符对应一个区间。
假设我们得知了对应关系和所需步数,那么可以采取这样的策略 : 先一直尽量右移,直到移动到需要覆盖的左边界处,然后向下到达底线,然后横向覆盖。(实际上就是让路径尽量靠右)
如图 :
![](https://cdn.luogu.com.cn/upload/image_hosting/5vcyvglv.png?x-oss-process=image/resize,w_500)
不难证明这是最优策略。
考虑我们得知了对应关系,如何得到最优步数。
我们从后往前考虑每个 $T$ 中需要匹配的左端点,让路径尽量靠右,若目前的层数无法完成,则加一层。
具体地,用**队列**维护上一条路径的所有(右侧)转折点。这些转折点的横纵坐标都是单调增加的。
当 $S_i$ 要前往 $T_j$。
末端弹出(pop)那些横坐标在 $j$ 后面的所有转折点。
然后,所有转折点都向左下方移动一位。
若起点衔接不紧密,则会新增(push)一个转折点。如图 :
![](https://cdn.luogu.com.cn/upload/image_hosting/6aser8dt.png?x-oss-process=image/resize,w_400)
(深蓝色是上一条路径的转折点,深红色是新路径的转折点)
答案是所有转折点的纵坐标的最大值 $+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;
}
```