BEST 定理 / 有向图欧拉回路计数 November 4, 2024 • 笔记 • Comment 无向图欧拉回路计数是 NPC 的。有向图欧拉回路计数则可使用 BEST 定理求解。Read More
环上邮局 / 环上决策单调性 June 4, 2024 • 题解 • Comment 邮局 是决策单调性优化 dp 的经典应用，其属于限制段数的序列划分问题，可以通过二分队列 + wqs 二分的方式做到 $O(n\log L\log n)$，其中 $L$ 指的是坐标的值域，此处不多赘述。Read More
做题笔记 2024 NFLS NOI 模拟赛 May 25, 2024 • 题解 • Comment 2024.5.21 树数术 给一颗 $n$ 个点的树和一个长为 $m$ 的序列 $a_{1\dots m}$，序列中每个数表示树上的一个节点。$q$ 次询问，每次询问给出 $a$ 的 $k$ 个子区间，将这 $k$ 个子区间顺次拼接成新的序列，求新序列上有多少个数是前缀 $\operatorname{lca}$。Read More
