Shannon’s Channel

总览#

M. Find the Easiest Problem#

题意： 给定一次 ICPC 赛制比赛的所有提交记录。若一支队伍曾经通过某题，就计入这道题的通过队伍数。求通过队伍数最多的题目；若有多题并列，输出题目 ID 字典序最小的一题。

思路：

对每道题维护一个集合，读入一条提交记录时，只有结果为 accepted 才将队伍名加入对应集合。集合会自动去重，因此集合大小恰好等于通过该题的不同队伍数。

最后枚举所有出现过的题目，选择集合大小最大的题目；若通过队伍数相同，则选择题目 ID 更小的一题。题目 ID 仅为 A 到 Z，也可以直接开 $26$ 个集合。

实现： 使用 set<string> 数组存储每道题的通过队伍。维护当前答案时，先比较集合大小，再比较题目 ID 即可。

复杂度： 设共有 $n$ 条提交记录。每次插入集合的复杂度为 $O(\log n)$，总时间复杂度为 $O(n\log n)$，额外空间复杂度为 $O(n)$。

A. World Cup#

题意： $32$ 支队伍的实力互不相同，中国队编号为 $1$。可以任意安排小组赛分组，比赛中实力更强的一方必胜。求中国队能够取得的最好名次：冠军、亚军、四强、八强、十六强或小组未出线，分别输出 $1,2,4,8,16,32$。

思路：

将所有实力排序，记中国队从强到弱的名次为 $pos$，即实力严格大于中国队的队伍数加一。只需根据 $pos$ 判断答案。

可以按“希望最终在哪一轮输掉”倒推。中国队要在某轮输，前面的轮次必须都赢下来；据此安排小组赛和淘汰赛路径中需要比中国队弱的队伍，并数出中国队最多能排到第几名。

1. 夺冠： 只有实力第一才能击败所有对手，因此 $pos=1$。
2. 决赛失利： 必须先进入决赛，因此中国队要是自己半区最强。比它强的队伍可以都放在另一半区，作为另外半区各条路径的胜者，最后由其中的冠军淘汰中国队。另一半区至多容纳这 $4$ 支更强队伍，故中国队至多排在第 $5$ 名，即 $pos\le5$。
3. 半决赛失利： 要先赢下四分之一决赛。一个队伍能走到四分之一决赛，需要有 $6$ 支比它弱的队伍为其安排出路径；中国队和四分之一决赛的对手各需要这样一组 $6$ 支队伍。中国队再战胜该对手时，对手本身也比中国队弱；而对手路径中的 $6$ 支队伍当然也比中国队弱。两组路径不重叠，因此共有 $6+6+1=13$ 支队伍比中国队弱，得到 $pos\le32-13=19$。
4. 四分之一决赛失利： 中国队需要先赢下十六强赛。可以让它以小组第二出线，再战胜一个小组第一；对应地需要有 $6$ 支比它弱的队伍，故 $pos\le26$。
5. 十六强失利： 只要能从小组前二出线即可。小组赛中一共 $6$ 个胜场分给四支队伍，前二至少各需两胜；中国队只要比两支同组队伍强，就能取得两胜，因此 $pos\le30$。
6. 小组未出线： $pos\ge31$ 时，最多只有一支队伍比中国队弱，无法在小组赛拿到前二，答案为 $32$。

综上，直接按阈值 $1,5,19,26,30$ 分类即可。

实现： 读入实力后排序，用 upper_bound 求出中国队前面有多少支更强队伍，从而得到 $pos$。随后使用 if-else 输出对应结果。

复杂度： 每组数据排序的时间复杂度为 $O(32\log 32)$，额外空间复杂度为 $O(32)$。

F. Make Max#

题意： 给定一个正整数序列。一次操作可以选择一个不全相等的连续子数组，将其中所有数变成该子数组的最大值。求最多能进行多少次操作。

思路：

将相邻且相等的元素看成一个连续段。设当前最小段的值为 $x$，长度为 $len$，左右相邻段的值为 $L,R$；不存在的一侧视为无穷大。令：

将该段提升为 $y$ 可以贡献恰好 $len$ 次操作：从靠近值为 $y$ 的一端开始，每次选择一个值为 $x$ 的元素和相邻的一个值为 $y$ 的元素，就能只把这个元素改为 $y$。逐个扩张直到整个段都变成 $y$，共进行 $len$ 次。

若直接把这段提升到大于 $y$ 的值，就会跳过从 $x$ 到 $y$ 的这些操作机会，无法得到更优答案。因此每次只提升到两侧较小值是最优的。提升后与同值相邻段合并，继续处理当前所有段中值最小的一段，直到整个序列只剩一个段。

实现：

初始时每个位置单独作为一个段，维护：

• num[i]：以 i 为代表的段长度；
• f[i][0]、f[i][1]：该段左右相邻段的代表位置，组成双向链表；
• ok[i]：该段是否已在合并中失效。

优先队列存储 (段值, 段代表)，每次取出值最小的有效段。将段值改为左右较小值时，答案加上 num[i]；然后合并所有同值相邻段并更新双向链表。

优先队列中会保留段合并前的旧记录，弹出时通过 ok 跳过即可。设 v 为当前存活段数：与一侧合并时 v 减一，左右两侧同时合并时 v 减二；当 v=1 时结束。

复杂度： 每次合并都会减少至少一个连续段，总共至多进行 $O(n)$ 次有效处理。每次优先队列操作的复杂度为 $O(\log n)$，总时间复杂度为 $O(n\log n)$，额外空间复杂度为 $O(n)$。

C. Permutation Counting 4#

题意： 给定 $n$ 个区间 $[l_i,r_i]$，统计满足 $l_i\le p_i\le r_i$ 的排列 $p$ 的数量，对 $2$ 取模。

思路：

这题只问排列数的奇偶性，所以可以把合法方案两两配对，能配掉的就不影响答案。

把每个区间 $[l,r]$ 看成一条以 $l$ 和 $r+1$ 为端点的线段。如果出现两条一模一样的线，比如两个都是 $[l,r]$，那么一个合法排列里这两个区间拿到的两个数 $x,y$ 可以交换，交换两次又变回来，于是方案被两两配对，答案是偶数。

而这些线还能做“加减法”：两条首尾相接的线（如 $(l,m)$ 和 $(m,r)$）可以拼成一条更长的线 $(l,r)$，反过来也能拆开。这一步等价于行列式里的“一行加到另一行”，属于初等行变换，不会改变答案的奇偶性。这样，图里有环时，沿着环把相邻的线一条条拼起来，最后一定会和环上的某条线重合，也就是拼出两条一模一样的线；反过来也一样。所以“有环”和“有两条相同的线”是一回事，都会让答案变成偶数。

做法： 把区间 $[l,r]$ 看成图中的边 $(l,r+1)$，用并查集依次加边。若某条边的两端点已经连通，说明成环，输出 0；全加完都没成环则输出 1。

复杂度： 并查集的时间复杂度为 $O(n\,\alpha(n))$，额外空间复杂度为 $O(n)$。