lessons/课程/12-历年真题/04-CSP-S2023消除状态与截止期调度.md

CSP-S 2023 真题：消除栈状态与带前置约束的截止期调度

本节目标

学习把反复相邻消除变成前缀规范形相等，以及用 Lawler 逆序调度检验树上种植顺序。

前置知识与课前自测

前置：栈、哈希、二分答案、拓扑排序、等差数列。

1. 相邻相同字符消除的最终规范形是否与消除顺序有关？
2. 有前置约束和截止期时，正序选当前截止期最早任务一定正确吗？

答案

1. 用“同顶则弹，否则压”的栈归约得到唯一规范形。 2. 不一定，松截止期父任务可能挡着紧截止期孩子；应使用 Lawler 逆序贪心。

问题动机

一题在字符串上反复消除，另一题在树上选择种植时刻，表面上没有共性。但它们都需要丢掉完整过程，只保留会影响未来的边界：前者保留简化后的栈顶状态，后者把生长累积转成每个节点的最晚完成期限。

精选例题 1：消消乐

来源、题意与范围

• 洛谷-P9753 消消乐
• $n\le2\times10^6$；统计能通过反复删除相邻相同字符变为空串的非空子串数。

Hint 1：规范栈

扫描字符：若等于栈顶则弹出，否则压入。

Hint 2：前缀状态

子串可消除当且仅当它两端的前缀规范状态相同。

Hint 3：不要存整串栈

把 `(父状态,新字符)` 相同的栈节点合并编号。

Observations

• 逐子串模拟是 $O(n^2)$；关键是删除规则 cc -> empty 可看成每个字符都是自身逆元。
• 前缀规范形是一个持久化栈状态；相同状态不应因创建时间不同而有不同编号。
• 扫描到新前缀状态时，之前相同状态出现次数就是以当前位置结尾的可消除子串数。

Editorial 与证明

维护规范栈。压入时用哈希表把 (state,char) 映射到唯一节点，消除时回父状态。设前缀状态为 $Si$。子串 $(l..r)$ 的归约结果对应 $S{l-1}^{-1}S_r$，为空当且仅当两状态相同。于是统计相等前缀状态对。

每字符一次压/弹和哈希，期望 $O(n)$，空间 $O(n)$。

核心伪代码与附件

state = empty_stack; frequency[state] = 1
for character c:
    if top(state) == c: state = parent(state)
    else: state = intern(parent_state=state, top=c)
    answer += frequency[state]
    frequency[state] += 1

完整 C++17 附件

精选例题 2：种树

来源、题意与范围

• 洛谷-P9755 种树
• 树上 n 个地块，父地块种后才能种孩子，每天种一个；第 x 天增长 max(b_i+x*c_i,1)，求所有树达到目标高度的最少总天数，$n\le10^5$。

Hint 1：二分完成日 D

固定 D 后，每个点可计算“最晚必须在哪天种”。

Hint 2：正序 EDF 的陷阱

孩子的截止期可能很紧但尚未可用，不能只看当前可种点。

Hint 3：逆序 Lawler

从第 n 个种植位置倒排，每次在尚未安排且没有未安排孩子的点中选截止期最大的。

Observations

• 完成日越晚越容易，存在单调性；固定 D 后生长问题退化为每个单位任务的截止期。
• 每点越早种高度越高，最晚种植日可在 [1,D] 二分。
• 前置关系是父先子后；逆排时可选对象恰是当前叶子。把截止期最大的叶放最晚是交换论证安全的。

Editorial

二分 D。计算每点从种植日 t 到 D 的增长和；$b_i\ge 1$，$c_i$ 为任意整数（可正可负）。当 $c_i\ge 0$ 时高 $h(t) = b_i + (D-t)\cdot c_i$；当 $c_i<0$ 时先按等差递减，降到 1 后保持每日 1。若第 1 天都不足则不可行，否则二分最大 t 得 deadline。

检验调度时以未安排孩子数为度，把所有原树叶按 deadline 放入大根堆。从时间 n 倒到 1，每次取截止期最大叶；若其 deadline 小于当前时间失败，移除后父亲成为叶则入堆。

正确性证明

截止期定义与高度条件充要。Lawler 交换：任一可行逆序安排的最后任务必为当前极大元（叶）；若它不是可选叶中截止期最大的，可把最大截止期叶换到该位置，它没有未安排后继且更晚截止，不破坏可行性。归纳得到贪心检验充要。外层二分因此返回最小完成日。

复杂度 $O(n\log D\cdot(\log n+\log D))=O(n\log^2 D+n\log n\log D)$；其中每个 $D$ 为每点二分 deadline，范围 $D\le10^9$。

核心伪代码与附件

feasible(D):
    for each vertex i:
        deadline[i] = latest planting day whose growth through D reaches a[i]
    heap = all current tree leaves keyed by deadline
    for time from n down to 1:
        u = pop largest deadline
        if deadline[u] < time: return false
        remove u; if parent becomes leaf, push parent
    return true
answer = first feasible D by binary search

完整 C++17 附件

实现指南

《消消乐》对每个左端点重新扫描右端，栈中存字符与当前连续次数；只在栈空时统计合法段，避免把中间短暂消除误当终态。《种树》的外层答案判定要用 64/128 位计算生长和；内层 Lawler 逆序调度必须每次取当前可作为最后任务的节点，不是正序贪心。

扩展与联系

消消乐把局部重写变成群规范形；种树把非线性增长变成截止期，再调用经典调度结构。两题都经历了两次模型转换。

总结与自检

1. 相同栈内容为何必须共享状态 ID？
2. 可消除子串为何对应相等前缀状态？
3. 种树正序 EDF 的最小反例是什么？
4. Lawler 为何选最大截止期叶放最后？

课后训练建议

消消乐与 $O(n^2)$ 子串判定对拍；种树对 n≤8 枚举所有拓扑序，对拍固定 D 的贪心可行性。