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

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>答案</summary>

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

</details>

## 问题动机

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

## 精选例题 1：消消乐

### 来源、题意与范围

- [洛谷-P9753 消消乐](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P9753)
- $n\le2\times10^6$；统计能通过反复删除相邻相同字符变为空串的非空子串数。

<details><summary>Hint 1：规范栈</summary>扫描字符：若等于栈顶则弹出，否则压入。</details>
<details><summary>Hint 2：前缀状态</summary>子串可消除当且仅当它两端的前缀规范状态相同。</details>
<details><summary>Hint 3：不要存整串栈</summary>把 `(父状态,新字符)` 相同的栈节点合并编号。</details>

### Observations

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

### Editorial 与证明

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

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

### 核心伪代码与附件

```text
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 附件](../../参考实现/12-历年真题/洛谷-P9753.cpp)

## 精选例题 2：种树

### 来源、题意与范围

- [洛谷-P9755 种树](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P9755)
- 树上 n 个地块，父地块种后才能种孩子，每天种一个；第 x 天增长 `max(b_i+x*c_i,1)`，求所有树达到目标高度的最少总天数，$n\le10^5$。

<details><summary>Hint 1：二分完成日 D</summary>固定 D 后，每个点可计算“最晚必须在哪天种”。</details>
<details><summary>Hint 2：正序 EDF 的陷阱</summary>孩子的截止期可能很紧但尚未可用，不能只看当前可种点。</details>
<details><summary>Hint 3：逆序 Lawler</summary>从第 n 个种植位置倒排，每次在尚未安排且没有未安排孩子的点中选截止期最大的。</details>

### 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$。

### 核心伪代码与附件

```text
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 附件](../../参考实现/12-历年真题/洛谷-P9755.cpp)

## 实现指南

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

## 扩展与联系

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

## 总结与自检

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

## 课后训练建议

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