Codeforces Round 916 (Div. 3)
内容提要
本文是Codeforces Round 916 (Div. 3)的题解，作者因公司来电中断比赛，赛后补题。文章逐题讲解A至G2的解法：A统计字母出现次数；B构造序列满足恰好k个逆序对；C枚举最终题目并分配剩余机会给最大b_i；D三种活动各取前三暴力枚举；E2按a+b-2排序贪心；F树上DFS组队；G2建图加并查集，答案为2的幂次乘环内节点数。
延伸解读
题目难度与解题策略
本场 Div.3 的题目从 A 到 G2 难度递增。A、B 题属于简单模拟和构造，适合快速解决；C、D 题需要一定的贪心和枚举技巧；E2、F、G2 则涉及更复杂的贪心、树形 DP 和图论。对于参赛者来说，合理分配时间，优先解决简单题，再挑战难题，是取得好成绩的关键。
贪心与枚举的典型应用
C 题通过枚举最终完成的题目，并将剩余机会分配给收益最大的题目，体现了贪心思想。D 题则利用每种活动只需考虑前三名，进行暴力枚举，降低了复杂度。E2 题通过计算代价并排序，按序操作，是贪心策略的典型应用。这些题目展示了如何通过分析问题结构来设计高效算法。
图论与数据结构的综合运用
G2 题要求点亮所有灯，通过建图、并查集和反向路径压缩，将问题转化为寻找必选节点和环，最终答案涉及 2 的幂次和环内节点数。F 题则利用树形 DFS 解决组队问题。这些题目综合了图论、并查集和树形 DP，对选手的数据结构能力有较高要求。
Q&A
Codeforces Round 916 (Div. 3) 的 A 题 Problemsolving Log 怎么解？
统计每个字母在字符串中出现的次数，如果某个字母的出现次数大于等于它在字母表中的位置（A为1，B为2，...），则答案加1。
B 题 Preparing for the Contest 如何构造序列？
将最大的 k 个值按递增顺序放在序列后面，其余值按递减顺序放在前面，这样恰好有 k 个相邻对满足前者大于后者。
C 题 Quests 的解题思路是什么？
枚举最终写到了哪道题，然后剩余的所有写题机会都分配给已解锁题目中 b_i 最大的那道题，取最大值。
D 题 Three Activities 怎么选择三天使伙伴总数最大？
对每种活动按伙伴数量降序排序，各取前三名，然后暴力枚举三种活动的组合，确保三天不同，取总和最大。
E2 题 Game with Marbles (Hard Version) 的贪心策略是什么？
计算每种颜色的代价 a_i + b_i - 2，按代价从大到小排序，然后 Alice 和 Bob 轮流选择，Alice 选择时她丢掉一个该颜色石头且 Bob 丢掉全部，Bob 选择时反之，最后计算 Alice 与 Bob 石头数量之差。
F 题 Programming Competition 如何求最多组队数？
建树后 DFS，对于每个节点，统计其子树大小，并传入外部可用节点数，若外部有可用节点则配对，答案加1并减少外部计数，最终答案除以2。
G2 题 Light Bulbs (Hard Version) 的建图与并查集如何应用？
通过栈模拟区间连接，仅连接每个区间最后出现的节点以压缩边数，然后拓扑排序找出必选节点，对于环使用并查集缩点，统计环内节点数，最终答案为 2^{必选节点数} 乘以每个环的 2*环内节点数，模 998244353。
