Shannon’s Channel

总览#

B. 生日礼物#

题意： 给定一个只包含 0、1、2 的字符串。每次可以将一个 2 改为 0 或 1，也可以删除一对相邻的 0 或一对相邻的 1。求经过任意次操作后，字符串的最短长度。

思路：

先暂时不考虑 2。每次删除一对相邻字符时，删除位置之间原本隔着偶数个字符，因此最终能相消的一对相同字符在原串中的位置一定一奇一偶。分别统计奇数位和偶数位上的 0、1 数量；对同一种字符，奇偶位置可以两两相消，剩下的数量就是两边数量之差的绝对值。

相消结束后，剩余的 0/1 字符串一定是交替的：要么形如 010101...，要么形如 101010...。记剩余的 0 数量为 cnt0，剩余的 1 数量为 cnt1。

接下来处理所有 2。每个 2 都可以改为 0 或 1，从而抵消一个尚未平衡的 0 或 1。因此，优先用 2 消去剩余的 0，再用剩余的 2 消去剩余的 1；先处理哪一种不影响最终答案。每个 2 最多减少一个剩余字符。若 0/1 都已平衡后仍有 2，它们可以两两相消，最后至多剩下一个。

所以依次计算：

1. cnt0 = |偶数位的 0 数量 - 奇数位的 0 数量|；
2. cnt1 = |偶数位的 1 数量 - 奇数位的 1 数量|；
3. 用 2 先消去 cnt0，再消去 cnt1；
4. 剩余 2 的贡献为其数量对 $2$ 取模。

三部分剩余数量之和就是答案。

实现： 扫描字符串时，0 和 1 按下标奇偶分别计数，2 单独计数。随后只需常数次取绝对值、取最小值和取模。

复杂度： 每个字符只扫描一次，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

E. Nanjing#

题意： 给定长度为 $n$ 的字符串 $S$，可以将它循环左移 $d$ 次，其中 $0\le d\le k$。求所有可能的移位中，子串 nanjing 出现次数的最大值。

思路：

为了处理跨越原字符串末尾的子串，将字符串复制一遍，得到

1
T = S + S

先统计原串中 nanjing 的数量，记为 base。这里七个字符对应下标区间 $[i,i+6]$，所以遍历原串时应保证 i + 7 <= n。

接着考虑从左移 $d-1$ 次变成左移 $d$ 次。当前字符串中，长度为 $7$ 的子串起点范围是

。

左移一次后，起点为 $d-1$ 的子串离开窗口，起点为 $d+n-7$ 的子串进入窗口。因此只需判断这两个长度为 $7$ 的子串：前者是 nanjing 就让当前数量减一，后者是 nanjing 就让当前数量加一。每次更新后用 ans 维护最大值。

移位 $n$ 次后会回到原字符串，所以令 k = min(k, n) 即可。这里保留 $d=n$ 这一种与原串相同的状态，与代码中的循环一致。

实现： 把字符串复制为 s0 + s0 后，按下标比较七个字符。最初使用 substr 会反复构造临时字符串，可以改为直接比较字符，避免不必要的开销，也能更直观地检查七位子串的边界。

复杂度： 每次只比较固定的 $7$ 个字符，初始统计和增量更新均为 $O(n)$，总时间复杂度为 $O(n)$，额外空间复杂度为 $O(n)$。

J. 社交媒体#

题意： 平台上有 $k$ 个用户，其中有 $n$ 个是你的好友。每条评论由用户 $a_i$ 在用户 $b_i$ 的帖子下发表；只有当 $a_i$ 和 $b_i$ 都是你的好友时，你才能看到这条评论。你可以至多新增两位好友，求最多能看到多少条评论。

思路：

将贡献分成三部分：

1. 已有好友之间的评论。 如果一条评论的两个端点都在好友集合中，那么无论如何都能看到，先统计为 base。
2. 新增用户与已有好友之间的评论。 对每个当前不是好友的用户 $u$，统计它与已有好友相连的评论数，记为 deg[u]。如果只新增 $u$，答案增加 deg[u]。
3. 两位新增用户之间的评论。 对两个都不是好友的用户 $u,v$，除了各自与已有好友的贡献 deg[u] + deg[v] 外，还要加上他们之间的评论数 cnt(u,v)。

因此，先枚举所有非好友用户对 $(u,v)$，更新

。

随后将所有非好友的 deg 排序，取最大的一个和最大的两个，分别对应只新增一位好友、以及新增两位好友但不考虑两位新增用户之间评论的情况。最终答案为 base + add。

处理评论时，用集合判断用户是否已经是好友：

• 两端都是好友：base++；
• 恰有一端是好友：给另一端的 deg 加一；
• 两端都不是好友：将两个端点按编号排序后，记录无向点对 (u,v) 的评论数量 cnt。

自环需要单独处理：若评论的两个端点都是同一个非好友用户，那么新增这一位好友后即可看到它，所以直接令该用户的 deg 加一。

实现： 使用 set 保存好友集合，使用 map<pair<int,int>, int> 统计两个非好友之间的评论数。cnt 只会记录确实存在评论的非好友点对；没有评论的点对额外贡献为零，因此遍历 cnt 就足够。由于最多新增两位好友，最后只需要比较一个 deg、两个最大的 deg，以及所有点对的组合贡献。

复杂度： 设评论数为 $m$。每条评论进行集合查询和至多一次 map 操作，时间复杂度为 $O(m\log k + m\log m)$，排序非好友贡献的复杂度为 $O(k\log k)$；空间复杂度为 $O(k+m)$。

K. 纸条#

题意： 一行共有 $w$ 个格子，其中部分为红格、部分为黑格。每张纸条恰好覆盖连续的 $k$ 个格子。要求覆盖所有红格、不覆盖黑格，且任意两个纸条不能覆盖同一个格子。构造使用纸条数最少的方案；若无解，输出 -1。

思路：

黑格不能被纸条覆盖，因此任何纸条都不能跨越黑格。将黑格按位置排序，并在两端补上位置 $0$ 和 $w+1$ 作为边界。这样两个相邻黑格之间的部分可以独立处理。

考虑左右边界为 $L,R$ 的一段。先从左到右贪心：找到最左侧尚未被当前纸条覆盖的红格，就从这个红格开始放一张纸条；随后跳过这张纸条覆盖范围内的所有红格，继续寻找下一张纸条。这样放置时，纸条数已经最少。

此时可能出现最后一张纸条越过右边界 $R$ 的情况。将最后一张纸条向左移动，直到它的右端恰好不覆盖黑格；若移动后与前一张纸条重叠，则将前一张也向左推。依次向左调整所有受影响的纸条，仍能保持所有红格被覆盖且纸条数不变。

若最终最左侧纸条碰到或越过左边界 $L$，说明这一段无法在不覆盖黑格、不重叠的条件下完成覆盖，整体无解。否则记录这一段调整后的所有纸条起点。将所有段的结果合并即可。

实现： 将红格和黑格的位置放在一起排序，用黑格作为分段标记。每一段先记录贪心选出的纸条起点；再从右向左修改起点，使相邻两张纸条不重叠，且最后一张不越过右边界。纸条数就是所有分段中贪心选取数量之和。

复杂度： 排序复杂度为 $O((n+m)\log(n+m))$。每个红格和每张选出的纸条只在线性扫描或调整中处理常数次，额外时间为 $O(n+m)$，空间复杂度为 $O(n+m)$。