【高2025级 + 高2026级】261105 NOIP 模拟测试（代码源精选2）模拟赛总结

本场四道题没一个简单的（此处“简单”更接近于评价人的“不简单”，而非只指难度）。

T1 长廊（corridor）

Statement

原题未找到。

长廊中有盏灯，从左到右编号为至。字符串描述它们的状态：字符 1 表示亮着，字符 0 表示熄灭。

一次操作可以交换两盏相邻的灯的状态。给定的一个约数和整数，澈溪希望每一段连续的盏灯中都有恰好盏亮着。

请计算至少需要多少次操作。若无法做到，输出。

Sol

令为中字符 1 的数量，当且仅当有解。

合法解显然为一个长为的段重复次。

根据贪心，应当把前面的移到最终解中在前面的。

从 0 开始编号字符 1，编号对取模为的就放在第块的第个。

对于一个余数，若将这些字符 1 放在，则贡献为。

先变成，发现这个是货仓选址。

又发现当增加，其中所有字符 1 都应该对应地相对模数右移了，因此中位数严格单调递增。

所以最优决策就是全部尽量选中位数，可能有一个前缀决策点偏左，一个后缀决策点偏右（因为要给其他模数的决策留空间）。

核心代码：

LL ans = 0;
nmf(i, 0, d - 1)
{
    int l = i + 1;
    int r = k - (d - 1 - i);
    nmf(j, 0, n / k - 1) vec[i][j] -= j * k;
    sort(vec[i].begin(), vec[i].end());
    int mid = vec[i][vec[i].size() / 2];
    mid = max(mid, l);
    mid = min(mid, r);
    nmf(j, 0, n / k - 1) ans += abs(mid - vec[i][j]);
}
cout << ans << endl;

T2 书脊（spine）

Statement

原题未找到。

有条图书记录，编号为至，最初按编号从小到大排列。每条记录有个字段，每个字段的值都是或。第条记录的字段值用长度为的字符串表示，其中第个字符就是第个字段的值。

一次操作可以选择一个字段，将当前的全部记录按该字段的值从小到大进行稳定排序，费用为。也就是说，字段值为的记录排在字段值为的记录之前；字段值相同的记录保持操作前的相对顺序。允许多次选择同一个字段。

给定一个至的排列，你希望最终从前到后的记录编号恰好为。请计算最小总费用，以及达到这个最小费用的操作方案数。

一套操作方案由依次选择的字段编号组成。操作次数不同，或者某一步选择的字段不同，就视为不同方案。允许不进行操作，这算作一套方案。若无法达到目标，按输出格式的要求报告无解。

第一行包含两个正整数。
第二行包含个正整数。
接下来行，第行包含长度为、只含字符 0 和 1 的字符串。
最后一行包含个整数。

，是至的一个排列。

Sol

显然状压。

考虑排序过程，最后进行的排序效果最优先，倒数第二个排序效果次之，稳定排序等价于按“最后使用的字段、倒数第二个字段……最后是原编号”作字典序排序。如果同一个字段被使用了两次，那么较早的一次会被完全覆盖（考虑较早的一次时，已经按这个字段排序了），所以每个字段最多只会被使用一次。

操作顺序是从低优先级到高优先级。为了 DP 方便，我们从高优先级字段向低优先级字段进行选择，即考虑操作序列的一个后缀。

目标排列要求相邻两条记录在的前面（即）。
对于任意字段，按它升序排序时，0 一定在 1 前面。我们定义两个集合：

：能够区分和的字段集合。
：在这个字段上，是 1，是 0。即如果优先按这个字段排序，会被排在前面，这与目标方向相反！
假设我们已经从高到低选好了一些字段集合。

考虑在后缀已知的情况下确定禁止集合。

如果，说明和已经被高优先级字段区分开了，顺序已经确定。
如果，说明还没区分开。此时如果我们接下来选了一个属于的字段，那么会第一次被排到前面，且后续操作无法补救。因此，这些字段绝对不能选。

结论：在当前已选集合下，下一步禁止选择的字段集合为：。

定义表示恰好在高优先级序列中选用了集合的方案数，转移时枚举下一个字段。如果不在上面求出的“禁止集”中，则可以转移：。

如果方案停止时，还有相邻对没被区分开（），它们就会按原编号排序。所以如果原编号是，那就不合法，不能停。因此停止的充要条件是：所有未被区分的相邻对，都满足原编号顺序。

直接求禁止集需要枚举所有相邻对，太慢了。注意我们需要找的是所有满足（即）的的并集。

可以通过预处理 + 子集或变换来实现：

令。
构造，表示所有的的并集。特殊地，如果，说明原编号是反序的，我们加一个“虚拟位” （第位为 1）来表示这个反序必须被某个字段翻转过来。
做子集或变换（相当于求的所有子集的并集）：
这样，就代表了当未选集合为时，所有不能选的字段集合。如果的第位为 1，说明字段被禁止，若第位为 1，则不能停止。

依此转移即可，注意加一个 ok 数组判定可达性，还要预处理 cost 数组记录选择字段集合对应的代价。

时间复杂度，空间复杂度。