P1053 编辑字符串 官方题解

【数据点 1∼41\sim 41∼4】

• 这一档保证 $n\leq 10$。先找出所有满足 $s_i\neq t_i$ 的位置，并用二进制状态记录哪些位置已经被修改。
• 令 $f_{p,S}$ 表示光标位于位置 $p$，已经完成集合 $S$ 中的修改时，至少需要多少次移动。
• 每次向顺时针或逆时针移动一格，并把新位置对应的修改加入状态。对状态图进行最短路即可。
• 修改次数本身是固定的，只需要在最少移动次数上加上失配位置数量。时间复杂度为 $\mathcal{O}(n2^n)$。

【数据点 5∼85\sim 85∼8】

• 这一档保证失配位置不超过两个。只有一个失配位置时，沿环上较短的一侧到达它即可。
• 有两个失配位置时，可以枚举先到达哪一个位置，以及到达第一个位置后是否原路返回，再取四种路线中的最小值。
• 这个过程提示我们，一条最优路线只需要记录顺时针走到的最远位置与逆时针走到的最远位置。

【数据点 9∼129\sim 129∼12】

• 这一档的失配位置在环上构成一个连续区间。把位置 $1$ 作为切口后，这个区间至多被分成左右两段。
• 若顺时针最远走 $r$ 步，逆时针最远走 $l$ 步，覆盖两段的最少移动次数为

• 较短的那一侧需要走一个来回，另一侧只走一次。枚举区间的断开方式即可。

【数据点 13∼1613\sim 1613∼16】

• 对一般的失配集合，光标走过的顺时针部分与逆时针部分仍然分别是一个连续前缀。
• 可以枚举两个前缀的长度，再用失配位置的前缀和判断它们是否已经覆盖全部位置。
• 每对前缀都使用 $\min(2r+l,r+2l)$ 计算移动次数。时间复杂度为 $\mathcal{O}(n^2)$。
• 当前瓶颈在于枚举了大量没有失配位置作为端点的前缀。

【正解】

设失配位置为 $p_1<p_2<\cdots<p_m$，并记 $d_i=p_i-1$。

• 枚举 $0\leq i\leq m$，让 $p_1,\ldots,p_i$ 从顺时针一侧覆盖，其余位置从逆时针一侧覆盖。
• 两侧最远距离分别为 $d_i$ 与 $n-d_{i+1}$。边界处约定 $d_0=0$，$d_{m+1}=n$。
• 当前划分的移动次数为

• 在所有划分中取最小值，再加上固定的 $m$ 次修改。时间复杂度为 $\mathcal{O}(n)$。

【正确性说明】

• 任意一条路线在顺时针与逆时针方向走过的位置都各自构成一个前缀，所以一定对应某个划分 $i$。
• 固定两个前缀以后，光标最后停在其中一侧。另一侧必须走一个来回，因此移动次数至少为 $\min(2r+l,r+2l)$。
• 先完整走较短侧并返回，再走另一侧，恰好达到这个下界。因此枚举已经覆盖所有最优路线。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/24Name:edit.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 10001011using namespace std;12int c,T,n,Cnt,Pos[MAXN];13char s[MAXN],t[MAXN];14void Solve(){15    scanf("%d%s%s",&n,s+1,t+1);16    Cnt=0;17    for(int i=1;i<=n;i++){18        if(s[i]!=t[i]) Pos[++Cnt]=i-1;19    }20    if(!Cnt){printf("0\n");return;}21    int Move=n;22    for(int i=0;i<=Cnt;i++){23        int Clockwise=i?Pos[i]:0;24        int Counter=i==Cnt?0:n-Pos[i+1];25        Move=min(Move,min(Clockwise*2+Counter,Clockwise+Counter*2));26    }27    printf("%d\n",Cnt+Move);28    return;29}30int main(){31    scanf("%d%d",&c,&T);32    while(T-->0) Solve();33    return 0;34}