NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 22 题

定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串 $\texttt{BCA}$ 可以将 $\texttt A$ 移到 $\texttt B$ 之前，变字符串 $\texttt{ABC}$。如果要将字符串 $\texttt{DACHEBGIF}$ 变成 $\texttt{ABCDEFGHI}$ 最少需要________次操作。

别急着动字符，先找原串里已经排好序的‘不动’部分。这道题考的是字符串排序与最长公共子序列（LCS）的关系：最少移动次数等于总长度减去原串中已按目标顺序出现的元素个数。

学生常误以为每次移动只能相邻交换，或者觉得要把所有错位的字母一个个挪过去，结果算出远大于4的答案。还有人会忽略‘任意位置’这个条件，导致不必要的操作。其实只要保留原串中相对顺序正确的子序列，把剩下的移到旁边即可。

字符串最少操作次数

题目允许一次将任意字符移到任意位置，目标是将 DACHEBGIF 变成 ABCDEFGHI。显然，我们不需要移动那些在原串中已经按正确相对顺序出现的字符，只需把其余字符逐一插入到正确位置。因此，最少操作次数 = 字符串长度 - 原串中已按目标顺序出现的最大子序列长度。

目标串是 ABCDEFGHI。我们扫描原串 DACHEBGIF，找出其中最长的子序列，使得该子序列在目标串中的相对顺序一致（即它是目标串的一个子序列）。

逐个检查：

• A 出现在原串第2位，是目标串第1位，OK。
• C 出现在第3位，是目标串第3位，OK。
• E 出现在第5位，是目标串第5位，OK。
• G 出现在第7位，是目标串第7位，OK。
• I 出现在第9位，是目标串第9位，OK。

这样我们得到了子序列 ACEGI，长度5。再看其他可能：如果尝试包含 B，B 在原串第4位，而 A 在第2位，C 在第3位，B 的相对位置在 A、C 之后，但目标串中 B 在 A 之后、C 之前，所以包含 B 会破坏顺序，无法形成长度更大的子序列。同理，包含 D 或 F 也会打乱顺序。

因此，最长公共子序列（LCS）长度为 5。原串总长度是 9，所以最少需要移动 9 - 5 = 4 次。

命题视角：这类题常出现在初赛填空题，考察对“任意移动”操作的理解以及最长公共子序列的直观应用。命题人喜欢在字符串中嵌入一些看似可保留但实际会破坏顺序的字符（如 B、D、F），让学生误以为能保留更多，从而算错。

避坑提醒：不要试图用贪心逐个插入，那样会重复计算；也不要误以为每次只能移动相邻字符。记住：只要保留原串中相对顺序正确的最大子序列，其余字符各需一次移动。

考频与趋势：根据题库统计，基础语法类题目共考过 1295 次，覆盖 11 个考试级别（2008-2026）。逐年分布为：2008年1题、2011年1题、2019年3题、2023年287题、2024年413题、2025年401题、2026年109题、null年80题。分赛事来看，GESP 一级 332 题、二级 283 题、三级 215 题、四级 186 题、七级 91 题、八级 79 题、六级 78 题、五级 23 题；CSP 提高级仅 3 题、入门级 3 题；NOIP 提高组初赛 2 题。可见字符串与排序相关题目在近年（2023-2025）考频显著上升，尤其在 GESP 一级至四级中占比很大。

预测：基于上述数据，未来 GESP 一级至四级仍会频繁出现此类“字符串最少移动次数”的题目，形式可能略有变化（如目标串不同、允许的移动规则微调），但核心思路不变。暂无足够依据预测 CSP 或 NOIP 会大幅增加此类题型，因为它们在近年考频较低。