8.9 Codeforces Div.2 A-D 总结

怎么说呢，今天我没打后面两题的原因是做不出来了(总之就是太菜了)。

A. Three Numbers on the Blackboard

题目：给定三个非负整数 a,b,c，每次可任选一个数替换为另外两数之和。求任意次操作后三元组的最小极差（最大值 − 最小值）。

结论：排序为 x ≤ y ≤ z，答案为

$\begin{cases} z - x & \text{if } z \le x + y, \\ y & \text{otherwise}. \end{cases}$

解释：

• 当 z ≤ x+y 时，三元组已满足三角形不等式，任何替换只会扩大或维持极差，因此不做操作最优。
• 当 z > x+y 时，将 z 替换为 x+y，得到 (x, y, x+y)，其极差为 (x+y) − x = y；再次替换只会让极差 ≥ y，故一步到位即可。

复杂度：O(t)，每组一次排序。

---

B. Domino Tiles

题目：长度 n 的 01? 串，把每个 ? 替换为 0 或 1，要求对所有 1≤i<n，相邻两多米诺的权重 $s_i+s_{i+1} 与 s_{i+1}+s_{i+2}$ 互不相等。计数方案数模 998244353。

核心化简：

$s_i + s_{i+1} \neq s_{i+1} + s_{i+2} \quad \Longleftrightarrow \quad s_i \neq s_{i+2}$

即串上同奇偶位置构成的两条子链必须各自为 0/1 严格交替序列。

计数：奇数位链与偶数位链完全独立。每条链有 2 种模式（以 0 开始或以 1 开始），分别检查串中已确定的字符（0/1，忽略 ?）是否冲突。设 odd_cnt 与 even_cnt 为两链合法模式数，则答案为

$odd\_cnt \times even\_cnt \pmod{998244353}.$

复杂度：$O(Σn) ≤ O(2·10⁵)$。

---

C. Hot Potatoes at the Fairy Warehouse

题目：2n 个小矮妖围成一圈，奇数位=红队，偶数位=蓝队。初始某些位置持有土豆。共 k 轮：每轮开始每个土豆持有者同时选择：保留土豆；或若顺时针邻居位置为空则把土豆传给他。结束时仍持有土豆的人被淘汰；红队得分为被淘汰的蓝队人数，蓝队得分=被淘汰的红队人数。双方合作最大化自身得分，输出两方得分。

关键观察：

1. 零和：Red + Blue = 总土豆数 P。
2. 相邻位必属不同队伍，因此持有土豆既能"阻挡"前方的对手土豆（它无法传给你），又维持着自己的控制权。
3. 过早传土豆 = 把控制权交给对手 + 解除对对手的阻挡，对己方两方面都不利。

最优策略（唯一均衡）：所有土豆在前 k−1 轮全部保留，到最后一轮才"能传则传"（即顺时针邻居为空就前移一格，否则留原地）。

结论：最终配置只与初始配置有关（和 k 无关，只要 k ≥ 1），且每个连续 1 的块中：

• 块内的每个土豆被下一个土豆阻挡 → 留在原位；
• 块尾的土豆（其顺时针下一位是 0）会前移一格进入空隙。

公式（环形，0-indexed）：

$final[i] = (s[i]=1 \land s[i+1]=1) \;\lor\; (s[i-1]=1 \land s[i]=0).$

最后按 1-indexed 奇偶统计：final[i]=1 且 i 为偶 → Red 得分；为奇 → Blue 得分。

复杂度：$O(Σn) ≤ O(10⁵)$。

---

D. A Ribbon for Tomorrow

题目：二进制串 s，可任意次选择两个下标 l≤r 满足 s[l]=s[r]，反转子串 s[l..r]。求可达的不同串数模 998244353。

不变量（核心）：

1. 端点不变：s[1] 与 s[n] 永远保持原值（因为每次反转 l=1 或 r=n 时需要 s[1]=s[r]=c 或 s[l]=s[n]=c，反转后不变）。
2. runs 总数不变：反转时内部 runs 反转（数量不变），边界 (l-1,l) 与 (r,r+1) 字符不变 → runs 交界点不变。
3. 由 1、2 得：0-run 数 R0、1-run 数 R1 各自不变；0 总数 Z0、1 总数 Z1 不变。

可达性：操作可在相邻同类 run 之间任意传递"质量"（甚至切出新的 run），因此对 0 来说：每个可达串的 0-runs 长度恰好是 Z0 的一个 R0-部分正整数分拆；1-runs 同理，且两者独立。

答案（隔板法）：

$\binom{Z_0-1}{R_0-1} \times \binom{Z_1-1}{R_1-1} \pmod{998244353},$

其中当某字符不出现（R=0）时其因子取 1。

实现：预处理阶乘与逆阶乘到 10⁶，每组 O(n) 统计 Z0,Z1,R0,R1。

复杂度：$O(MAXN) 预处理 + O(Σn) ≤ O(10⁶)$。

---

四道题的共同考点总结

| 题号 | 类型 | 核心技巧 |

|------|------|----------|

| A | 贪心 / 结论题 | 三角形不等式，一步替换终止 |

| B | 计数 / 转化 | 相邻多米诺权重不等 ⇨ 隔位不等 ⇨ 双独立交替链 |

| C | 博弈论 / 结论题 | 零和结构 + 相邻必异队 → "保留到最后一轮传一次" |

| D | 组合计数 / 不变量 | 端点、runs 数不变 + 分拆计数 = 两个组合数相乘 |

四道题都是先分析性质/不变量/等价条件，再 O(n) 或 O(1) 计算，没有用到高级数据结构或复杂 DP 优化，关键在于耐心手动化简规则。