7.1 ~ 7.31 做题总结

· · 个人记录

有题解的题挂链接,没题解的题简要说明思路。过水的题不记录。

难度评价系统来自 https://www.luogu.com.cn/article/u98dxgp0。贺个图:

【2】P9019 [USACO23JAN] Tractor Paths P

https://www.luogu.com.cn/article/z0jzzjxt。

【1+】ABC218H Red and Blue Lamps

https://www.luogu.com.cn/article/uus68s48。

【0】AGC005A STring

做括号匹配状物,用栈删掉 ST 即可。

【0】AGC005B Minimum Sum

单调栈求出 \min 的贡献区间,直接算即可。

【1】AGC005C Tree Restoring

https://www.luogu.com.cn/article/na7qdrxb。vp 时没调出来。

【2】AGC005D ~K Perm Counting

【0】AGC008A Simple Calculator

对 \pm a, \pm b 的四种情形都算一下。

【1】AGC008B Contiguous Repainting

https://www.luogu.com.cn/article/yd3iynkt。

【1】AGC008C Tetromino Tiling

https://www.luogu.com.cn/article/yd3iynkt。

【1+】AGC008D K-th K

https://www.luogu.com.cn/article/yd3iynkt。

【2】CF1485D Multiples and Power Differences

https://www.luogu.com.cn/article/x8oa0rtu。

【3】P5170 【模板】类欧几里德算法

https://www.luogu.com.cn/article/o6kg8c2i。

【2】ABC313G Redistribution of Piles

https://www.luogu.com.cn/article/o6kg8c2i。

【2】ABC283Ex Popcount Sum

https://www.luogu.com.cn/article/evot0dj4。

【2】ARC222F Triple Transformation

【1+】CF1208G Polygons

https://www.luogu.com.cn/article/zl0absn1。

【1+】P6776 [NOI2020] 超现实树

:::::success[题解]

考察合法的树的形态。我们注意到,下图所示的树是无效的:

原因是,这种树无法生成下面这种形态的树:

其中 T 可以是任意树。

我们将所有无效树丢掉,有用的树其实只会有四种形态:

如果这四种形态的树都存在,那么这一层的树可以被生成。

考虑递归判定。我们将四种情形对应的子树抽取出来,作为新的集合 \mathscr{T} 判断。如果四种情况都合法,那么原集合就是合法的。

递归的终止条件是 \mathscr{T}=\varnothing 或者 \mathscr{T} 包含单点。

分析一下复杂度,四种情形几乎无交,唯一有交的是 这种形态的树,可以忽略掉。那么每层递归的总代价是 |\mathscr{T}| 的,复杂度就是 O(n)。

:::::

【2】CF468C Hack it!

:::::success[题解]

观察取 l=1,r=10^{m} 时的情形,设此时的 \sum f(i) 为 g(l,r)。

考虑令 l \gets l+1,r \gets r+1。此时 r 形如 \tt{100\cdots01},有 g \gets g+1。故我们可以通过微调 l,r 改变 g 的取值。

那么只要取充分大的 m,将 g 调整到 a 的倍数即可。取 m=18,则

\begin{aligned} g(1,10^{18}) &= \sum_{i=1}^{10^{18}} f(i)\\ &=18 \dfrac{10^{18}}{10} \sum_{d=0}^9 d+f(10^{18})\\ &= 45 \times 18 \times 10^{17}+1\\ &= 81 \times 10^{18}+1 \end{aligned}

记 b=(81 \times 10^{18}+1) \bmod a,只要调整 a-b 次,故取 l=a-b+1,r=10^{18}+a-b 即可。

:::::

【1+】CF1951E No Palindromes

:::::success[题解]

先判掉 S 自身非回文的情形,此时直接将整体作为构造。

否则,我们断言,若有解,则必然存在划分段数 k \le 2 的解。

::::success[证明]{open}

考察一个 k=3 的解 A,B,C,其中 A,B,C 都不是回文串。

若 AB 非回文,可将 AB 和 C 作为构造,故存在 k=2 的解。BC 非回文同理。

下面假设 AB,BC,ABC 均为回文串。

由 ABC 回文,AB 回文,可得 ABC 存在周期 |C|。 同理得 |A| 也是周期。

由弱周期引理,ABC 存在周期 p=\gcd(|A|,|C|)。这说明,A,B,C 都可以视为一个循环串,即 A=G^a。

因为 AB=G^{a+b} 回文,所以生成元 G 回文。那么 A,B,C 都是回文串,矛盾。

因此,上述情形不可能发生。对 k>3 的情形归纳即可。

::::

得到这个观察后,枚举分界点,使用哈希 / Manacher 判定即可。复杂度 O(n)。

:::::

【1】CodeChef Divisible Subset

:::::success[题解]

我们断言,将 S 任意排列为序列 a_i,并将子集退化为区间,必然有解。

先考虑怎么找构造。记 a_i 的前缀和为 s_i,则只要找到 s_{l-1} \equiv s_r \pmod n 的 l,r 即可。顺序扫描并用哈希表维护即可,复杂度 O(n)。

考虑 s_0 \sim s_n 有 n+1 个数字,而模 n 意义下只有 n 个不同的数,根据鸽巢原理,我们一定能找到一对相同的 s_i。这就证明了有解性。

:::::

【2】CF1667C Half Queen Cover

:::::success[题解]

先分析 k 的理论下界。

考虑在左上角 k \times k 的子矩形中放置半皇后。行列的限制是容易的,问题主要是对角线的约束。

对于右下角的 (n-k) \times (n-k) 网格,其可以划分为 2(n-k)-1 条对角线,且每个半皇后恰好覆盖一条。列出不等式

k \ge 2(n-k)-1

解得 k \ge \lfloor \frac{2n+1}{3} \rfloor。接下来我们断言这个下界可以取到。

手玩 n 为奇数且较小的情况,可以找到这样的构造:

也就是构造两条骑士形的路线。

当 n 是偶数时,两个点可能会覆盖同一条对角线,不过精细分析一下,此时所有对角线仍能被覆盖,故依然按照这个做法构造即可。

:::::

【2】CF1438F Olha and Igor

:::::success[题解]

考虑随机 u,v,w 并分析每个点作为 LCA 的概率。

对于点 x,当且仅当 u,v,w 分居 x 的三棵子树时,x 会被作为回答。粗略估计一下,忽略常数以后的概率是

p_x=\dfrac{(2^{h-d})^2 (2^h-2^{h-d})}{(2^h)^3}

其中 d 是节点 x 的深度,定义域 d \in [2,h)。将上式展开

\begin{aligned} p_x&=\dfrac{(2^{h-d})^2 (2^h-2^{h-d})}{(2^h)^3}\\ &= \dfrac{2^{4h-3d}}{2^{3h}} \end{aligned}

可以发现 p_x 关于 d 单调减,且下降速度很快。

考虑用 420 次询问随机 u,v,w,并取出最大和次大,这两个点有极大概率是根的左右儿子。确定左右儿子以后是简单的,枚举每个点,以一个儿子定根去询问即可。

:::::

【1】P4587 [FJOI2016] 神秘数

考虑神秘数怎么求。使用增量法,设 [1,x] 都能被表示,加入 a_i 时若 a_i \le x 则令 x \gets x+a_i,否则爆掉。

观察到 x \gets x+a_i 至少使 x 乘二。可持久化线段树维护区间 \le k 的前缀和即可,2log。

【3】P7447 [Ynoi2007] rgxsxrs

【1+】P7115 [NOIP2020] 移球游戏

https://www.luogu.com.cn/article/747byi86。

【0】P5270 无论怎样神树大人都会删库跑路

容易发现答案有周期性,算 $O(1)$ 个周期以后加起来即可。 ### 【0】[P3435 [POI 2006] OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435) 最长周期可以对偶成最短 border,直接做的话就是 fail 树上最浅祖先。 然后把 fail 树搞出来,随便做一下就是线性了。卡空间,用了 `forward_list`。 ### 【0】[P2375 [NOI2014] 动物园](https://www.luogu.com.cn/problem/P2375) 直接做就是暴力跳 $\pi$ 跳到 $2j \ge i$ 的位置。 放 fail 树上考虑,那就是找到最浅的祖先满足 $2j \ge i$ 然后将深度作为答案,倍增优化即可 $O(Tn \log n)$。 线性做法的话,就是类似并查集那样路径压缩一下,减少跳 fail 的次数,均摊下来是线性的。 ### 【0】[P4248 [AHOI2013] 差异](https://www.luogu.com.cn/problem/P4248) 前面 $\sum\limits_{1 \le i<j \le n} (|T_i|+|T_j|)$ 容易推式子变成 $\frac{n(n-1)(n+1)}{2}$ 从而 $O(1)$ 计算。 求出 $\text{ht}$ 数组后,相当于我们要对区间 $\min$ 求和。这是 [AGC005B](https://www.luogu.com.cn/problem/AT_agc005_b),做法是单调栈求出以 $\text{ht}[x]$ 为 $\min$ 的极长区间,算一下贡献。 注意单调栈一侧取等一侧不取的细节。 ### 【0】[P3804 【模板】后缀自动机(SAM)](https://www.luogu.com.cn/problem/P3804) 用 SAM 求出后缀树,对每个子树根统计叶子树乘 len 取 max。 ### 【3】[P4173 残缺的字符串](https://www.luogu.com.cn/problem/P4173) 对字符串 $A,B$,令通配符为 $0$,其余字符为 $ 1 \sim 26$,构造判别函数 $$ F(A,B)=\sum A[i] B[i] (A[i]-B[i])^2 $$ 则 $F =0$ 是 $A,B$ 等价的充要条件。 考虑将 $B$ 平移 $j$ 位算出所有的 $F$ 值。打开以后是 $a_i^2b_{j+i}+b_{j+i}^2a_i-2a_i^2b_{j+i}^2$,三次差卷积,1log。 ### 【0】[P3306 [SDOI2013] 随机数生成器](https://www.luogu.com.cn/problem/P3306) 解一阶线性递推。套路地构造 $\lambda=a\lambda-b$ 得到通项,最终只要 BSGS 求离散对数。细节比较多,要讨论一些没有逆元的情形。 ### 【2+】[T779806 LCP](https://www.luogu.com.cn/problem/T779806?contestId=337061) 考虑 SA 并求出 $h$ 数组,答案为 $\sum a_ia_j \min \limits_{k=i+1}^j h_k$。对 $h$ 建小根笛卡尔树变成 $\sum a_ia_j \text{dep}_{\text{lca}(i,j)}$。 另一个转化方法是,对反串建 SAM 并拉出后缀树,式子也是 $\sum a_ia_j \text{dep}_{\text{lca}(i,j)}$。 在树上这个式子可以直接维护,用静态 Top Tree 记录上下界点距离,分 Rake 和 Compress 点讨论即可,1log。另一个想法是拆成和平方减平方和 HLD 维护,2log。 ### 【1+】[AGC064C Erase and Divide Game](https://www.luogu.com.cn/problem/AT_agc064_c) <https://www.luogu.com.cn/article/dqfeng6u>。 ### 【1】[UOJ1087 Catalogue of Catalogues](https://uoj.ac/problem/1087) 其实我不知道为啥是对的。 显然只要拉出一棵生成树。然后开始剥叶子,从目标点到叶子拉出一条毛毛虫,将虫足切断,并将虫身激活,然后在虫足上不断 shuffle,如果向右了就切断前一条边,期望 $\log n$ 轮可以做完,然后删掉叶子。 写了就过了。 ### 【1+】[CF1739F Keyboard Design](https://www.luogu.com.cn/problem/CF1739F) <https://www.luogu.com.cn/article/e6ov9xdx>。 ### 【1】[ABC465C Reverse Permutation](https://www.luogu.com.cn/problem/AT_abc465_c) 显然难于 DEF。赛时贺的平衡树板子。 ~~正解怎么做,我还没补,别急。~~ 想了一下想明白了。 最终序列一定是双调的,只要维护前后两段。这个可以动态维护翻转次数的奇偶性来决定当前数字是插到前面还是后面。 ### 【0】[ABC465D X to Y](https://www.luogu.com.cn/problem/AT_abc465_d) 注意到 $k \ge 2$ 且操作可逆,容易想到 meet in the middle 的思路,做 $\log$ 轮操作插入哈希表,然后算一下答案。 需要精细实现,不然复杂度会爆。 ### 【0】[ABC465E Digit Circus](https://www.luogu.com.cn/problem/AT_abc465_e) <https://www.luogu.com.cn/article/mopv6vjh>。 ### 【0】[ABC465F Sjeltzer?](https://www.luogu.com.cn/problem/AT_abc465_f) <https://www.luogu.com.cn/article/6kw2nni0>。 ### 【3-】[ABC465G Sum of Mex of Mod of Linear](https://www.luogu.com.cn/problem/AT_abc465_g) ### 【0】[CF906D Power Tower](https://www.luogu.com.cn/problem/CF906D) 考虑欧拉降幂,结论是 $\log$ 层以后终止。所以写个递归暴力降幂即可。 ### 【3】[CF516E Drazil and His Happy Friends](https://www.luogu.com.cn/problem/CF516E) ### 【2+】[AGC044D Guess the Password](https://www.luogu.com.cn/problem/AT_agc044_d) ### 【3】[P10787 [NOI2024] 树的定向](https://www.luogu.com.cn/problem/P10787) <https://www.luogu.com.cn/article/q49ekt8v>。 ### 【2】[CF1746E1 Joking (Easy Version)](https://www.luogu.com.cn/problem/CF1746E1) ### 【2】[CF1951F Inversion Composition](https://www.luogu.com.cn/problem/CF1951F) ### 【2】[CF1764G3 Doremy's Perfect DS Class (Hard Version)](https://www.luogu.com.cn/problem/CF1764G3) 考虑一下 $1$ 有什么性质。不难发现取 $k=1$ 是没有意义的,而取 $k>1$ 时必有 $\lfloor \frac{a_x}{k} \rfloor=0$。 尝试取 $k=2$。我们希望用若干次操作区分 $1$ 的位置,可以想到二分。具体来说,我们做如下两次询问: ![](https://cdn.luogu.com.cn/upload/image_hosting/aj2l8g0b.png) 称两个数 $x,y$ 可配对,当且仅当 $\lfloor \frac{x}{2} \rfloor=\lfloor \frac{y}{2} \rfloor$。每次询问时折半,则每个配对的贡献为 $1$,左右区间内部无法配对的数一定可以两两配对。忽略 $1,n$ 的影响,两个区间的答案应该相等。 在插入 $1$ 后,$1$ 所在的区间答案会增加 $1$。这样我们就能使用 $2$ 次询问将规模折半,次数 $2 \log n$。 但是我们发现 $n$ 是偶数就爆了,原因是插入一个 $n$ 也会让答案增加 $1$。$n$ 是奇数不会破坏求解,故下文均在 $n$ 为偶数的基础上讨论。 考虑二分 $n$ 的位置。取 $k=n$,则 $x \in [l,r]$ 时答案为 $2$,否则为 $1$。可以做到 $3\log n$ 次询问,通过 G1。 事实上,当 $1,n$ 分居两侧时,我们可以用一次 $k=n$ 的询问区分出 $n$ 的位置。 ![](https://cdn.luogu.com.cn/upload/image_hosting/i4ykq08a.png) 由于二分是缩区间的过程,我们舍掉右区间后就不会再被 $n$ 干扰了。这样询问次数就是 $2\log n+1$,通过 G2。 多出来一次询问怎么卡掉,我们设法在末轮二分用 $1$ 次询问区分两个数。 ![](https://cdn.luogu.com.cn/upload/image_hosting/vmf8cz7u.png) 如图,我们猜测某个数字是 $1$,并进行紫色区间所示的询问。在之前的二分过程中,我们必然询问过两个蓝色区间,故将三个询问的答案对比即可。 另一个 corner case 是,最后剩下 $1,n$ 两个数。我们发现,此时在先前的二分中,我们并没有区分 $1,n$ 的步骤,也就是询问次数 $\le 18$,故直接用 $2$ 次询问区分即可。 这样次数就卡到了 $2 \log n$,可以通过 G3。 ### 【2+】[CF1028G Guess the number](https://www.luogu.com.cn/problem/CF1028G) ### 【2】[ABC373G No Cross Matching](https://www.luogu.com.cn/problem/AT_abc373_g) 分析 $n=2$ 的情形。画出不共线的四点 $A,B,C,D

显然有 |AC|+|BD| < |AD|+|BC|。

直接给出断言,使得 \sum\limits_{i=1}^n \sqrt{(x'_{p_i}-x_i)^2+(y'_{p_i}-y_i)^2} 取 \min 的 p 必合法。

证明考虑调整法,将两条有交线段改为不交,总和减少,交点数目减小,故总和最小必能使得构造合法。

考虑建一张完全二分图,边权是端点距离,则只要找出最小权完美匹配。转化为费用流模型,在残量网络上找构造即可,可以通过。

【2】P4313 文理分科

题目是一个最小割对偶最大流的模型。

做法可以看一下 Alex_Wei 网络流中关于 集合划分模型的单边联合代价 的部分。

【3-】AGC025E Walking on a Tree

https://www.luogu.com.cn/article/xtm2i2p3。

【3】P6624 [省选联考 2020 A 卷] 作业题

https://www.luogu.com.cn/article/1xerym0z。

【1】QOJ3678 LED-led Paths

https://www.luogu.com.cn/article/gojt67n2。

【3】P6790 [SNOI2020] 生成树

https://www.luogu.com.cn/article/fbwm6aep。

【3+】QOJ9278 Linear Algebra Intensifies

https://www.luogu.com.cn/article/fbwm6aep。

【1】CF487E Tourists

建立原图的广义圆方树,变成单点修改,询问一条毛毛虫的点权 \min,毛毛虫剖分即可。

上面的做法有点魔怔,考虑将圆点的权值挂在方点上,方点开个 multiset 维护,树剖线段树维护树链最小值即可。

【2】P12446 [COTS 2025] 答好位 / Vrsta

题解:https://www.luogu.com.cn/article/cefjfku3。

【0】ABC433G Substring Game

建立 SAM 后在自动机上博弈 dp 即可。

【1】P10238 [yLCPC2024] F. PANDORA PARADOXXX

考虑时光倒流,只要合并连通块维护直径。维护每个连通块的直径端点,两个连通块合并的直径端点必然是这四个点之二,只要枚举 6 种情况,并查集维护即可。

【0】P8563 Magenta Potion

注意到 |V| \ge 2,故长度 \ge 62 的区间必然是 too large,剩余情形暴力即可。

【1】P8564 ρars/ey

显然是树形背包,设计 f_{u,i} 为 u 子树剩余 i 个点的最小代价,转移是 (\min,+) 卷积和对 f_{u,1} 的 chkmin。细节有点多,调了很久。

【1+】P10572 [JRKSJ R8] +1-1

原则是用一堆必要条件拼出充要。

先判掉不连通,) 开头、( 结尾的无解情形。特判 () 和只有奇数路径,然后只保留 \tt{(} \to \tt{)} 的边,在子图上判定。

这有两种情形,第一种是存在偶数路径,第二种是 S 连通块有 ((,T 连通块有 )),分别判定即可。

维护路径长度奇偶可能性可以用带权并查集,额外判定奇环即可。

【4】P8566 You are the Miserable

【2】P2619 [国家集训队] Tree I

题解:https://www.luogu.com.cn/article/6tzippna。

【1】P15922 [TOPC 2023] Finding Bridges

先时光倒流变成加边,求割边数目。

维护连通块的生成森林,如果一条边连通两个新的连通块,则这条边是桥,反之删去环上所有桥。

lct 维护就魔怔了。考虑建超级源点,树剖线段树维护即可,2log。

【1】QOJ8672 排队

使用插入—标记—回收算法转化为数据结构问题。

在标记部分,我们需要将 S 中 [l_i,r_i] 的值域段整体 +1。考虑 FHQ 维护,拆出三段后将中间段平移,再将三棵树 join 起来。

视 n,q 同阶复杂度 O(n \log n)。

【1】CF1172F Nauuo and Bug

https://www.luogu.com.cn/article/7e6a7ddl。

【2】P8264 [Ynoi Easy Round 2020] TEST_100

考虑允许离线怎么做。使用插入—标记—回收算法配合 FHQ-Treap,在标记时 split 成两段,对 [1,a_i] 取相反数并加上 a_i,对 (a_i,+\infty) 减去 a_i 即可。

考虑强制在线。注意到函数复合有交换律,这启示我们分块。我们在整块内使用平衡树合并求出 1 \sim V 每个数变成了什么,询问时散块暴力,整块使用预处理的信息。

取块长为 \sqrt{n} 复杂度平衡,视 n,q,V 同阶为 O(n\sqrt{n})。

注意实现细节,整块预处理要用笛卡尔树式建树,不然复杂度会多 \log。整块处理常数过大,我的实现取块长 B=3 \times 10^3 最快。

【2】P14891 Trink

https://www.luogu.com.cn/article/xvecls4f。

【0】ARC225A Four Coloring

https://www.luogu.com.cn/article/b6amf4fw。

【0】ARC225B Independent Nim

SG 函数是用来刻画有向图游戏的 AND 的。

本题是有向图游戏的 OR,只要存在一个必胜态,整个就必胜。因为我们可以选择一个必胜态,把必败留给对手。

观察到必败当且仅当出现 11。于是扫一遍即可。

【1】ARC225C K Spanning Tree

先求出 MST 再调整。调整的时候删掉所有 1 边,然后顺次补上 1 和 0 边。

【1】ARC225D Gap Swap (easy)

答案是 \frac{1}{2} \sum|i-p_i|。你问我为啥,我咋知道。

【2】ARC225E Gap Swap (hard)

答案是 \sum|i-p_i|-\text{inv}。你问我为啥,我咋知道。

【1】P7044 「MCOI-03」括号

https://www.luogu.com.cn/article/i4tfa6jo。

【2】P9655 『GROI-R2』 Beside You

列一个 dp 是,f_{u,i} 表示前缀和为 i 的最大点数,转移是对 f 的整体加法 & 平移,对深度启发式合并等价于长剖,线性。

【3】P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces

【1】P9746 「KDOI-06-S」合并序列

正经做法我只会 n^4,写一下:

先解决判定性问题,考虑区间 DP。

对原序列的一个子段 [l,r],如果其能被缩成单点,当且仅当 \exists l \le a \le b \le c \le d \le r,使得 [l,a],[b,c],[d,r] 都能被缩成单点,且 [l,a] 段的点权异或 [d,r] 段的点权等于 [b,c] 段的点权。

观察操作性质,容易发现操作不会改变序列的整体异或和。因此,每个子段的点权就是原序列的区间异或和。

记 f_{l,r} 表示 [l,r] 是否能缩成单点,枚举 a,b,c,d 进行转移,复杂度 O(n^6)。

每一段的寻找是相对独立的,这启示我们将判定拆成三部分。定义:

你说的对,但是:https://www.luogu.com.cn/discuss/1327193。

【0】P17115 [Algo Beat 009 & MROI-R1] ANDOR

\huge{\text{AND + OR = ADD}}

问三次 add 可以确定三个数。最后一个反推出来。

没想细节,应该不会假吧。

【0】CF383E Vowels

题意即为给定 F,求 G 满足 g_T=\sum \limits_{S \cap T \ne \varnothing} f_S。

容斥

\begin{aligned} g_T&= \sum_{S \cap T \ne \varnothing} f_S\\ &=\sum f_S- \sum_{S \cap T = \varnothing} f_S\\ &= 2^{|U|} -\sum_{S \subseteq (U \setminus T)} f_S \end{aligned}

一次 FMT。

【1】QOJ12325 Data Structure Problem

https://www.luogu.com.cn/article/ebyy72kp。

【1】ARC052D 9

注意到 n 的数码和至多 90,n \bmod k>90 无解。

枚举 n \bmod k=b,此时 b \le 90\land b < k。此时相当于要求形如 kx+b 的数字中,有几个数码和 =b(在模 k 意义下)。x 的范围是 kx+b \le m \iff x \le \left\lfloor \dfrac{m-b}{k} \right\rfloor。

阈值分治,设定阈值 B。

取 B=3 \times 10^4。两部分都跑 3e7,1s 下可以通过。

【1】P10853 【MX-X2-T2】「Cfz Round 4」Xor Counting

钦定 a_i \le a_j 后对条件容斥,只要分别计算如下两类点对的数目:

两个条件不可能同时成立。故计算一侧即可。下面以 a_i \oplus a_j>a_j 为例说明,另一种同理。

扫描到 a_j 时,只要统计 i<j \land a_i \oplus a_j>a_j 的 i 的数目。枚举并钦定 a_i,a_j 二进制下 LCP 长度为 k,我们的要求是:

条件等价于 a_i 的二进制第 k+1 位为 0,且 a_i 的高 k 位与 a_j 相同。

这可以使用 01-Trie 维护,从高位向低位建立,查询时走出 a_i 对应的树链直到第 k+1 位,统计左子树大小即可。

可以动态走出 a_j 的树链代替枚举 k,复杂度 O(n \log V)。

【0】P4314 CPU 监控

历史最值板子题。

【1】U398115 Min Swaps

设给定的排列是 p_i,尝试构造最终排列 q_i。

得到 q_i 以后容易计算答案:连边 p_i \to q_i,2n 减去连通块数目即为所求。

考察 q_i 的形态,其形如 [0 1] [2 3] 这样两两分组。

如果 p_i 和 q_i 中恰有对应的双匹配块,则直接匹配走,并且删掉做完这些后,p_i 中每个块恰有两个可以匹配的 q_i 待选块。

我们猜测,对 p_i 中每个块,从两个待选块中随意找出一个匹配,必能得到最优解。

复杂度 O(n)。

【1】P9534 [YsOI2023] 广度优先遍历

建立 BFS 树后只要处理横叉边和返祖边。

对着题目给的代码鱼鱼蒸一下,可以瞪出来如下性质:

跑拓扑排序即可得到构造。

【1+】P9745 「KDOI-06-S」树上异或

https://www.luogu.com.cn/article/9bwcvpoe。

【2】CF1704E Count Seconds

直观的想法是用拓扑排序状物直接模拟,但无法处理 a_i=0 时不推流的限制。

我们充分发扬人类智慧,直接模拟 n 轮推流,由于 DAG 最长路 \le n-1,故远处的流量一定被下传掉,忽略 a_i=0 的限制即可。复杂度 O(nm)。

【2】CF1620G Subsequences Galore

赛时题意不清晰,以为是 dp of dp,内层子序列自动机。

https://www.luogu.com.cn/article/wfkspxa9。

【1】ABC338G evall

考虑按照加号分段。对每个只有乘法的段内部,算出钦定左字符选,钦定右字符选,两个字符都选的权值和。对第三种情况求一个前缀和。

对这个段做一个划段 dp,形如 f_i=\sum\limits_{j<i} (f_j+r_j+l_i+s_{i-1}-s_{j})。这是可以前缀和优化的,于是线性。细节没想。

专家研究:上面的 dp 是假的。

【1+】P14241 [CCPC 2024 Shandong I] 传感器

https://www.luogu.com.cn/article/dhc1zrhx。

【2】QOJ7178 Bishops

谁家高联二试组合题。

https://www.luogu.com.cn/article/8brh43ua。

【2】QOJ5458 Shortest Path Query

预处理 f_{u,x} 表示 1 \to u 走恰好 x 条黑边,经过白边数目的最小值,查询答案为 \min\limits_{x} (a\times x+b\times f_{u,x})。

转二维平面分析,将 (x,f_{u,x}) 视作一个点,则询问是求 ax_i+by_i 的最小值。根据斜率优化的结论,我们只需保留下凸壳上的点。

定理 n \times n 网格的整点凸壳顶点数至多 O(n^{2/3})。

根据定理,单调栈维护下凸壳后,DP 转移和询问都可暴力扫描。

复杂度 O((m+q) n^{2/3})。

【2+】AGC006F Blackout

将矩阵视作图的邻接矩阵,问题重新表述为:

现有 n 个点的有向图 G,初始有 m 条边,若存在边 x \to y 和 y \to z 则连边 z \to x。最大化边数并输出。

我们注意到特定的 G 可以变为完全图,考虑如何刻画这类图的性质。

对 G 进行 DFS,按照 DFS 树上深度\bmod 3 进行三染色。

详细证明可以看这篇题解,这里只给结论。

复杂度 O(n+m)。实现时,可以对图建立反边做三染色。

【3】P8293 [省选联考 2022] 序列变换

https://www.luogu.com.cn/article/chwy48cu。

【0】TC12494 TheLargestString

$$ f_{i,j}=\max(f[i-1][j-1], f[i-1][j-1][0:j-1] + a[i] + f[i-1][j-1][j-1:i+j-2] + b[j]) $$ 注意 $f$ 记的是字符串。复杂度 $O(n^3)$。 ### 【1】[P13635 [NWRRC 2021] Halfway There](https://www.luogu.com.cn/problem/P13635) 打表发现答案是 $\le n/2$ 的最大的与 $n$ 互质的正整数。 直接枚举即可,考虑 hack 造成 $2 \times 3 \times 5 \times \cdots$ 这样,最劣复杂度 $O(\omega(n))$。 ### 【2+】[P7838 「Wdoi-3」夜雀 treating](https://www.luogu.com.cn/problem/P7838) 独立想出来 $O(n^2)$ 贪心。就是对值域双指针,维护两个队列,删去最靠前的 $0$,然后懒惰删除维护。 Hall 定理的转化没想出来。 <https://www.luogu.com.cn/article/1d8nvuab>。 ### 【1】[CF1514D Cut and Stick](https://www.luogu.com.cn/problem/CF1514D) 找出绝对众数 $x$ 后,设其出现次数为 $c$,区间长度为 $l$。贪心地,将若干 $x$ 划为一段不劣,故答案为 $2c-l$。找绝对众数用线段树维护摩尔投票,出现次数二分即可。duel 时脑抽爆写莫队。 ### 【2】[CF1519E Off by One](https://www.luogu.com.cn/problem/CF1519E) <https://www.luogu.com.cn/article/bgwzhxzn>。 ### 【2+】[P9139 [THUPC 2023 初赛] 喵了个喵 II](https://www.luogu.com.cn/problem/P9139) <https://www.luogu.com.cn/article/q0b9nuh8>。 ### 【3】[P17141 [NOI 2026] 传送](https://www.luogu.com.cn/problem/P17141) <https://www.luogu.com.cn/article/e71jw4dd>。 评【3】的原因是我没写过淀粉树。 ### 【1】[P9731 [CEOI 2023] Balance](https://www.luogu.com.cn/problem/P9731) <https://www.luogu.com.cn/article/14b3uifb>。 ### 【2】[P9070 [CTS2023] 琪露诺的符卡交换](https://www.luogu.com.cn/problem/P9070) <https://www.luogu.com.cn/article/vnmet8bt>。