2025 vertigo - 杂题选讲 - hhz

*表示没写 / 懒得写。有些非常蠢的题删掉了。

ppt 里有很多找不到 source 的题目，没有记下来。

[0] QOJ3301 Economic One-way Roads

• 有向图强联通 $\Leftrightarrow$ 能被耳分解
• 无向图边双联通 $\Leftrightarrow$ 能被耳分解
• 无向图点双联通 $\Leftrightarrow$ 能被开耳分解

[3] [APIO2022] 游戏

可以对每个非关键点 $u$ 维护 $l_u,r_u$，表示 $\le l_u$ 的点都可以到达 $u$，$u$ 可以到达所有 $\ge r_u$ 的点。每次暴力更新，均摊是 $\mathcal O((n+m)k)$ 的。看起来没什么进一步优化可能了，注意到我们只关系是否有点 $l_u\ge r_u$，所以没必要更新的时候就不用更新。对 $k$ 分块：如果更新之后两个点在一个块里，那么更新具体编号，$\mathcal O((n+m)\sqrt k)$，否则只要更新块编号。把分块改成线段树就是 $\mathcal O((n+m)\log k)$。

[0] [THUPC 2024 决赛] 朔望

首先对 $w$ 二项式反演，直接枚举 $S$ 算贡献，发现是一个分数 $\text{lcm},\gcd$ 的形式，直接维护所有质因子，求的时候双指针。

[2]【UNR #6】稳健型选手

chain：转化成括号序 $\rightarrow$ 会 $q=1$ $\rightarrow$ 发现是容易两端拓展的结构 $\rightarrow$ 二区间并。

转化为每次询问一个长度为偶数的区间 $[l,r]$，定义一个括号串 $s$ 的价值为 $\sum\limits_{i=0}^{r-l}a_{l+i}[s_i=\texttt )]$，求所有合法括号串中最大的价值。对于 $q=1$ 的部分分，有一个很经典的反悔贪心：每次先往后加两个 $\texttt )$，然后把前面价值最小的一个 $\texttt)$ 改成 $\texttt ($，而且从后往前做也可以，每次加 $\texttt ($ 就好了。这种支持两端拓展的区间信息一般用莫队或者分治结构维护，直接上二区间并。每次合并的时候一定是把左区间部分 $\texttt )$ 换成 $\texttt ($，并把右区间同样数量的 $\texttt ($ 换成 $\texttt )$，主席树，$\mathcal O(n\log^2n)$。

[0] 【UNR #6】小火车

这个 $2^k$ 很可疑，发现问题就是找到两个和相同的子集，meet in the middle 一下，二分和并双指针就对了，$\mathcal O(2^n\log V)$。

[1] 【UNR #6】面基之路

chain：$k$ 个人分别走不好做，统一 $\rightarrow$ 枚举边

题目和所有人都走到一个点等价，因为相遇之后可以跟着第一个人走。枚举边 $(x,y)$，$k$ 个关键点按照 $(dis_{u,x},dis_{u,y})$ 排序，肯定是一个前缀从 $x\rightarrow y$，剩下的 $y\rightarrow x$，$\mathcal O((n+m)k\log n)$。

[1] QOJ1875 Nein

分类讨论 $x$ 的位数并不好做。倒过来，求第 $k$ 大的 $10^n-1$ 的倍数，且没有 $9$。前面判定的条件是把数划分成 $n$ 个一段，和是 $10^n-1$ 的倍数。按位确定答案，同时枚举和 $T\cdot (10^n-1)$，其中 $T$ 是答案划分段数的上限。最后是一个简单的 dp，因为严重跑不满，所以能过。

[1] [IOI 2022] 无线电信号塔

如果我们选出了塔序列 $\{p\}$，只要判断 $p$ 内相邻塔的合法性即可。容易想到算出一个点 $i$ 最近的可以传输信号的塔 $L_i,R_i$（$\ge a_i+d$），显然 $[L_i,R_i]$ 成两两包含结构。那么如果对区间包含结构建出树，叶子节点的个数就是答案。一个区间 $[L_i,R_i]$ 是叶子的条件是 $\min a[L_i:R_i]\ge a_i$，于是对于每个点算出最大合法的 $d$，剩下就是一个主席树能解决的了。

有个特殊情况：可能在整个序列中的区间 $[L_i,R_i]$ 内的最小值可能 $<a_i$，但是询问区间刚好把最小值砍掉了。分类讨论一下这种数最多只有两个，分别是前 / 后缀最小值中最小的不合法的数，倍增特判。

[1] QOJ8047 DFS Order 4

套路的，把 dfn 序给树形态做一个单射，那么树需要满足对于任意一个点 $u_0$ 和他的下一个兄弟 $u_1$，令 $v_0$ 表示 $u_0$ 的最后一个儿子，需要满足 $a_{u_0}<a_{u_1}<a_{v_1}$，暴力设计状态 $f_{i,j}$ 表示大小为 $i$ 的树，根节点最后一个儿子编号为 $j$ 的方案，是个二维卷积，$\mathcal O(n^4)$。

抽象一下，其实我们在进行一个 DAG 拓扑序计数，瓶颈就在于上面的特殊边（如下图 1 为树，2 为拓扑序限制）。这个大家都很熟悉了，直接容斥掉，变成反向边或者没有边。剩下的就是一棵树，树的拓扑序是 $n!\prod\limits_u\dfrac 1{sz_u}$。

令 $f_{i,j}$ 表示大小为 $i$ 的树，其中 $i$ 的最后一个儿子有额外的边连着一个大小为 $j$ 的树（蓝边红边都可以），此时所有除根节点之外节点的贡献，$\mathcal O(n^3)$，转移顺序是加父亲或者加一个最左边的儿子，所以加儿子的时候，儿子 $sz$ 必须 $>1$，否则不合法。

---

NOIP 之后补。

[4]【UNR #7】鸽子收费站

[4] QOJ4219 Insects