# 题解：非交叉的1212子序列

出题人建模：将1、2视为括号，用栈配对后得到嵌套森林。Codex（GPT-6）给出该建模的交换证明，发现最长单链贪心的反例，并以森林不可比图的匹配亏量动态规划完成线性时间、流式实现。

## 先固定1到2的配对

把1视为左括号、2视为右括号。从左到右扫描，遇到2时与最近的未配对1匹配；没有可用1时忽略该2。未匹配的1最终也不构成节点。每条配对线成为一个节点，直接包含关系构成森林。

为什么可以固定这些配对？等价地，不断从剩余字符串中删除相邻的12并固定为一对。取任意最优合法选法，考察下一对相邻端点 $p,q$ ：

- 两端都未使用时，不必选择这条固定配对。
- 已经互相配对时，保持不变。
- 只有一个端点用于某条配对时，把该配对缩短为 $(p,q)$ .另一端被释放，配对所属的1212仍然合法，因为缩短不会碰到其另一条、不相交的配对。
- 两端分别用于不同配对时，这两条线必定交叉，故合法选法中不会出现这种情况。

这里“相邻”指删除已固定配对后的相邻。尚未固定的端点没有位于二者之间；之前固定的配对不会跨过尚未删除的端点，所以缩短也不会与它们交叉。每次调整保留所选1212的数量。全部删除结束后，剩余串只有若干2再接若干1，不再可能含有未固定的1到2配对。由此得到只使用栈配对、数量不减的选法。

反过来，栈配对之间天然不交叉。森林中互不可比的两个节点，对应两条先后分离的配对线，其四个端点按顺序恰好构成1212。因此问题等价于：在森林节点中配出最多组，每组两个节点互不为祖先，且每个节点最多用一次。

## 合并不同子树的匹配

对森林中的第 $i$ 棵树，记节点数为 $s_i$ ，内部最大匹配后剩余的节点数为 $d_i$ ，称为匹配亏量。不同树的任意两个节点都可配对。令 $S=\sum s_i$ ，整个森林的最小剩余数为

$$D=\max\left(S\bmod2,\ \max_i(d_i+s_i-S)\right)$$

空森林取 $D=0$ .下面证明该公式。

任何匹配都受到奇偶性限制，至少剩下 $S\bmod2$ 个节点。对树 $i$ ，内部至多消去 $s_i-d_i$ 个节点，外部只有 $S-s_i$ 个节点可与它配对，因此至少剩下 $d_i-(S-s_i)$ 个。以上给出下界。

为了达到下界，先在每棵树内部取最大匹配，再不断配对来自不同树的剩余节点，直到未匹配节点只在一棵树 $T$ 中。若还剩至少两个，就找一条两端都在 $T$ 外的已有匹配边，拆成两条与 $T$ 内剩余节点相连的边，匹配数增加一。

继续直到只剩零或一个节点，达到奇偶下界；或者不存在完全位于 $T$ 外的匹配边。后一种情形下，全部外部节点都已经与 $T$ 内节点配对，$T$ 原有的内部最大匹配未被拆掉，剩余数恰为 $d_T+s_T-S$ .因此上述下界一定可达。

一棵树的根不能与自己的任何后代配对，所以先合并其所有孩子组成的森林，再令节点数和亏量各加一。

## 两个整数即可汇总一层

每个栈帧只保存孩子子树的节点数总和 $S$ ，以及 $M=\max_i(s_i+d_i)$ .某个1与2闭合时，得到

$$s=S+1,\qquad d=1+\max(S\bmod2,M-S)$$

然后把这棵子树并入父帧。扫描结束时，没有闭合的1不是节点，将它们的孩子森林直接合并到外层，不额外增加节点或亏量。最终虚根表示整个森林，答案为 $(S-D)/2$ .

每个字符只进出栈一次，时间 $O(n)$ ，空间 $O(n)$ ；不用存储整棵树或递归遍历。实现每层只存两个整数，避免深链导致调用栈溢出。

## 最长单链贪心的反例

出题人的“优先选择最长单链所在分支，再任取另一分支配对并拆根”贪心不能保证最优。字符串

```text
11221122111112222122
```

会使该策略得到4，但下列五组位置都合法：

$$
(1,4,9,20),\quad(2,3,10,17),\quad(5,8,11,16),\quad(6,7,12,15),\quad(13,14,18,19)
$$

它们使用全部20个位置，没有1到2配对线交叉，因此达到上界5。错误原因是单链长度不能刻画整个分支需要从外部获得多少匹配；亏量公式保留了这个信息。该反例在修正输入字符映射之后仍然成立，不是字符读错造成的假反例。

[标准程序](std.cpp)使用亏量动态规划。验证包括长度不超过12的全部8191个二进制字符串的直接子序列打包检查，以及千万字符的闭式结构测试，见[测试说明](tests/README.md)和[性能记录](../../../docs/benchmark-R37.json)。