第二十届东北地区大学生程序设计竞赛题解

包含题目：A、C、E、G、H、I、L。

A. 求求你不要再摔馍片了

思路

处理每一包馍片时，只有两种选择：

不扔，留在前半段；
扔到最后，进入后半段。

由于所有馍片都按原顺序处理，而且每包最多只能扔一次，所以最终吃的序列一定可以看成：

未被扔的子序列 + 被扔的子序列

两个子序列内部都保持原来的相对顺序。

每吃一包固定获得 1 点开心度，因此基础贡献恒为 n。只需要最大化相邻两包之间的额外贡献：

w(x, y) = (y - x + 5) mod 5

味道只有 5 种，可以用动态规划记录两个子序列的边界状态。

设：

dp[la][fb][lb]

表示处理完当前前缀后：

前半段最后一个味道为 la；
后半段第一个味道为 fb；
后半段最后一个味道为 lb；
当前两个子序列内部额外开心度的最大值。

用 0 表示对应子序列为空。

处理当前味道 t：

放入前半段：若 la != 0，增加 w(la, t)；
放入后半段：若后半段非空，增加 w(lb, t)；否则初始化 fb = lb = t。

最后如果两个子序列都非空，还要补上前半段末尾到后半段开头的贡献 w(la, fb)。

答案为：

max(dp + bridge) + n

正确性

任意合法操作都会把原序列划分成“未扔子序列”和“被扔子序列”两部分，并且两部分内部顺序不变；反过来，任意这样的划分也能由对应的扔与不扔操作得到。

DP 对每个馍片都枚举它进入哪一个子序列，并记录计算未来贡献所需的全部信息：前半段末尾、后半段开头和后半段末尾。内部相邻贡献在转移时已经加入，两个子序列拼接处的贡献在结束时统一加入，因此不会漏算或重算。

复杂度

状态数为 6^3，每个馍片转移一次。

时间复杂度：O(n)
空间复杂度：O(1)

C. 电梯

关键转化

一部电梯的停靠楼层序列为：

1 = a1 < a2 < ... < ak = n

它能让相邻停靠楼层之间直达，也就是覆盖若干对：

(a1, a2), (a2, a3), ..., (a{k-1}, ak)

题目要求所有楼层对 (x, y) 都至少被某一部电梯作为相邻停靠楼层覆盖。

下界

考虑任意分界线 k，即左边楼层为 1..k，右边楼层为 k+1..n。

跨过这条分界线的楼层对一共有：

k(n-k)

每部电梯从 1 到 n，停靠序列严格递增，因此它恰好只会有一段相邻停靠楼层跨过这条分界线。所以一部电梯最多覆盖一个跨该分界线的楼层对。

因此：

m >= k(n-k)

对所有 k 取最大值：

m >= floor(n^2 / 4)

构造

按两层之间的距离 d = y - x 来覆盖所有楼层对。

对于固定距离 d：

如果 d <= n - d，输出 d 部电梯。第 r 部电梯停靠：
```
1, r, r+d, r+2d, ..., n
```
去掉重复的 1 和 n，只保留严格递增序列。这样所有距离为 d 的楼层对都会在某条等差序列里相邻出现。
如果 d > n - d，距离为 d 的楼层对只有 n-d 个。对每个 (l, l+d) 单独输出一部：
```
1, l, l+d, n
```
同样去掉重复楼层。

固定距离 d 使用的电梯数为：

min(d, n-d)

总数为：

sum_{d=1}^{n-1} min(d, n-d) = floor(n^2 / 4)

正好达到下界，因此最优。

复杂度

输出规模为 O(n^2)，n <= 1000 时停靠层总数满足题目限制。

E. 猜 01 序列

观察

设隐藏序列中 1 的总数为 S。一次询问集合 I 中有 x 个 1，返回值为：

x(S-x)

返回值大于 0 当且仅当：

I 中至少有一个 1，I 外也至少有一个 1

如果能找到一个确定为 1 的位置，再询问包含它的集合，就能得到：

1 * (S - 1) = S - 1

答案就是返回值加 1。

二进制定位

因为：

n <= 100000 < 2^17

用 pos - 1 的 17 位二进制编号区分所有位置。

从高位到低位处理。

先寻找第一次返回正数的询问。对于当前二进制位，询问这一位为 1 的所有位置。如果返回正数，说明这一位为 1 的位置里有 1，这一位为 0 的位置里也有 1。此后选择位为 1 的一边作为候选集合。

之后继续处理更低位。每次在当前候选集合内，询问当前位为 1 的那些位置：

若返回正数，说明这一半里有 1，保留这一半；
若返回 0，由于候选集合外已经确定还有至少一个 1，所以询问集合不可能包含所有 1，只能说明这一半没有 1，保留另一半。

处理完 17 位后，候选集合只剩一个位置，并且它一定是 1。

记录最后一次正返回值 last_positive。当候选集合最终定位到单个 1 时，最后一次正返回值对应的询问集合中恰好只有这一个 1，因此：

last_positive = S - 1

输出：

last_positive + 1

如果从未出现正返回值，说明不存在两个不同位置都为 1，答案只能是 1。

复杂度

最多询问 17 次。每次构造询问集合扫描所有位置。

时间复杂度：O(17n)
询问次数：<= 17

G. 冰灯配色

思路

一次操作选择 x，第 i 盏灯变为：

a_i xor x

希望它变成 7，则必须满足：

a_i xor x = 7

对于固定的 a_i，能让它变成 7 的 x 是唯一的：

x = a_i xor 7

因此选择某个 x，本质上就是选择某一种初始状态 v，把所有状态为 v 的灯同时变成 7。

答案就是 0..7 八种状态中出现次数的最大值。

复杂度

时间复杂度：O(n)
空间复杂度：O(1)

H. 可能是字符串签到题

关键结论

对于一个查询子串 s[l..r]，出现次数最多的子串一定可以取为某个单字符。

原因是：任意一个非空子串如果出现了 cnt 次，那么它的第一个字符也至少出现了 cnt 次。所以任何子串的出现次数都不会超过某个字符的出现次数。

另一方面，单个字符本身也是合法子串。因此最大出现次数就是：

s[l..r] 中出现次数最多的字符的出现次数

做法

对 26 个小写字母分别做前缀和。

设：

pre[c][i]

表示前 i 个字符中字母 c 出现了多少次。

查询 [l, r] 时枚举 26 个字母：

pre[c][r] - pre[c][l-1]

取最大值即可。

复杂度

预处理：O(26n)
单次查询：O(26)
空间复杂度：O(26n)

I. 灯带

关键结论

受限制区间两两不相交。每个受限制区间最多只能使用两种颜色。

设最长受限制区间长度为 mx，三种颜色数量为 r, g, b，总数为 n。

一个区间最多只能使用两种颜色，因此任何一个受限制区间长度都不能超过某两种颜色数量之和的最大值：

mx <= n - min(r, g, b)

这是必要条件。

它也是充分条件。

构造

把所有受限制区间按长度从大到小排序处理，维护三种颜色剩余数量。

设当前区间长度为 L，当前三种颜色剩余数量从小到大为：

x <= y <= z

若 x + z >= L，就用剩余最少的颜色和剩余最多的颜色填当前区间。

否则，因为 mx <= n - min(r,g,b) 且当前区间按长度递减处理，可以证明 y + z >= L，于是用中间颜色和最多颜色填当前区间。

填充时，先尽量使用较少的那种颜色，不够的部分用较多的颜色补齐。

受限制区间处理完后，剩余位置不受约束，直接按剩余颜色数量填入即可。

正确性要点

按长度从大到小处理，可以保证最难填的区间优先被满足。

每次选择“较少颜色 + 较多颜色”，或者在不足时选择“中间颜色 + 较多颜色”，本质上是在避免最大的颜色长期独大，同时尽量消耗较少的颜色。处理完当前区间后，剩余颜色仍满足之后更短区间所需的两色容量条件。

由于区间互不相交，一个区间内部的具体排列不会影响其他区间。每个受限制区间只使用两种颜色，所以约束满足；最后未受限制位置任意填色即可。

复杂度

时间复杂度：O(m log m + n)
空间复杂度：O(n)

L. 拯救猫猫

思路

让一只狗睡着，只会取消这只狗的视线；狗所在格子本身仍然不能经过。

因此格子可以分成三类：

没有被任何狗看到：一开始就可以走；
恰好只被一只狗看到：只有让这只狗睡着时才可以走；
被至少两只狗看到：让一只狗睡着后仍然不安全，永远不能走。

先求出每个可行走格子被多少只狗看到，以及如果只被一只狗看到，它属于哪只狗。

视线预处理

对四个方向分别扫描：

行从左到右处理向右看的狗；
行从右到左处理向左看的狗；
列从上到下处理向下看的狗；
列从下到上处理向上看的狗。

扫描时维护当前方向上正在产生视线的狗编号。遇到障碍或任意狗，视线被阻断；遇到普通空格、S、E，若当前有有效视线，就给该格子的覆盖次数加一。

同时维护一个异或值 xr[cell]。当一个格子只被一只狗看到时，xr[cell] 就是这只狗的编号。

连通性处理

先把所有初始安全格子，也就是覆盖次数为 0 的可走格子，用并查集合并相邻连通块。

然后枚举每只狗。对于当前狗，只需要临时加入“恰好只被这只狗看到”的格子。

为了避免每次重建并查集，使用可撤销并查集：

记录当前并查集快照；
标记这只狗睡着后恢复安全的格子；
把这些格子与相邻的初始安全格子、以及同样被当前狗恢复的格子合并；
判断 S 和 E 是否连通；
回滚并查集。

狗按照读入时的行列顺序编号。第一次使 S 和 E 连通的狗，就是行坐标最小、列坐标也最小的答案。

如果本来 S 和 E 已经连通，那么枚举第一只狗时也会判断成功，因此会输出字典序最小的狗。

正确性

一只狗睡着后，只有它独占视线覆盖的格子会从不可走变为可走；被多只狗看到的格子仍然至少被其他狗看到，不可走。障碍和狗所在格子始终不可走。

因此对某只狗而言，新的可走区域恰好等于：

初始安全格子 + 只被这只狗看到的格子

可撤销并查集临时合并的正是这些格子之间的相邻关系，所以 S 与 E 是否同属一个并查集，等价于让该狗睡着后是否存在逃脱路径。

按行列顺序枚举狗并在首次成功时停止，满足题目要求的最小坐标优先。

复杂度

每个格子的视线统计只会在四次扫描中处理常数次；每个独占视线格子只属于一只狗，枚举狗时也只会被临时处理一次。

时间复杂度：O(nm alpha(nm))
空间复杂度：O(nm)

目前还没有评论...