作物解锁条件: 题解¶

方法与贡献¶

Codex（GPT-6）使用标准布尔电路表示表达式，结合迭代解析与事件队列实现本题，见 std.cpp。核心是单调性：作物只会从不可用变成可用，表达式没有逻辑非，所以每个中间条件也只会从假变真。

把条件变成电路¶

每种作物对应一个变量结点。表达式每次逻辑与或逻辑或创建一个二输入门，从两个操作数结点各连一条有向边到门。表达式根再连向它所解锁的作物。不同表达式中对同一作物的引用共用变量结点，但每个运算门分别创建。

用操作数栈和运算符栈从左到右解析。编号压入操作数栈；左括号压入符号栈；右括号使栈顶运算依次归约至左括号。遇到逻辑运算符时，先归约优先级不低于它的栈顶运算，直到左括号或更低优先级。最后归约剩余运算。归约按右操作数、左操作数的顺序弹出两个结点并创建门。每个记号只进出栈一次，深括号不使用函数递归。

只传播变真事件¶

与门初始还需要两个真输入，或门需要一个，每个衍生变量需要其条件根的一次真事件。先将基础变量标真并入队。

取出一个刚变真的结点，扫描它的出边。对于仍为假的目标，所需事件数减一；减到零就标真并入队。已经为真的结点不再入队。基础变量不依赖其他结点。

重复输入仍应保留两条边。例如 \(A\land A\) 的与门有两条来自 \(A\) 的边，\(A\) 变真时两次减计数，恰好得到真；不能去重后仍要求两次事件。或门第一次触发后忽略其余事件。

正确性¶

解析栈按优先级和括号归约，所以每个门代表对应子表达式。对队列事件归纳：基础变量确实可用；与门收到两个已真的输入，或门收到一个，衍生变量收到真条件，因此所有被标真的作物都可由规则获得，不会凭环生成新作物。

反过来，按任一合法解锁过程的步数归纳。初始基础变量全部入队；若某表达式的变量足以使它为真，则自叶到根的相关门最终都会触发，其作物也会入队。因此所有可获得的作物都被找出。队列停止时得到从基础作物出发的最小不动点，与任意合法解锁顺序一致。

复杂度与边界¶

设 \(S\) 为表达式总字符数。图的结点和边数均为 \(O(N+M+S)\) ，每个结点至多入队一次，每条边扫描一次，加上解析，总时间与空间均为 \(O(N+M+S)\) .使用平坦邻接链表保存边，不为每个结点单独申请容器。

当 \(N=0\) 时没有初始事件，全部衍生作物不可得；当 \(M=0\) 时输出为空。自依赖与互相依赖无需特殊检测；没有外部触发的环自然保持为假。反复扫描所有表达式虽容易编写，但长依赖链会导致平方级工作量，不作为完整范围的参考程序。

数据生成与验证¶

使用 Python 3 标准库运行 tests/generate.py --out-dir <目录> 可按 plan.json 生成输入；可重复使用 --case 选择编号，使用 --std <可执行程序路径> 同时生成输出。先自行以 C++17 编译所需源码。固定计划与种子可重现输入；生成大数据放在题目目录之外。

性能记录保留每份正式输入和源码的哈希、五轮时间及峰值工作集。所有交付方案均通过完整数据。303 个小输入使用独立表达式求值与逐轮重算不动点核验；正式长链、闭环、带初始触发的环、深括号和宽表达式分别有可直接证明的预期结果。