plan R 3

[×] CF547D Mike and Fish

[★★] HDU6664 Andy and Maze

首先有一个正常的 color-coding 做法是随机染 $k$ 种颜色做，但是这里有一个在 $k$ 比较小的时候稍微优一点的随机：只随机两个颜色，规定合法的被统计的链一半黑一半白，那么正确概率应该是 $\dfrac{1+[2|k]}{2^k}$，每次做就折半，在链中间的边统计。

[★★] CF1698G Long Binary String

这个异或的形式很像多项式取模，试着看成在 $\mathbb P_2$ 下做多项式乘法，先把题目字符串前导零去了，令其为 $S(z)$，那么需要求的就是 $F(z)S(z)=z^k+1$，把未知数翘了得到 $z^k+1\equiv 0\pmod{S(z)}$，容易发现这是 BSGS，而且多项式各种操作可以用位运算代替，那么复杂度是 $\mathcal O(n2^{\frac{n}{2}})$​。

[★] QOJ7686 The Phantom Menace

欧拉回路，还原边的顺序也是正常的倒着加回去就好了。

[★] QOJ7640 Colorful Cycles

考虑一个充要条件：存在一个点双，里面出现过三种颜色的边，而且存在至少三个点有至少两种不同颜色的相邻边。充要证明是容易的：找到这三个点，必然有一种方案可以把三个点练成环，同时三色环上必然存在至少三个这样的端点。实现上可以借鉴的是判断一条边在哪个连通分量里，把圆方树建立出来，判断一下边的两个端点共用了哪个方点。

[★] QOJ7681 Prefix Mahjong

如果只要判定一个序列，那么令 $f_{i,0/1/2,0/1/2,0/1}$ 表示 $i-2,i-1$ 开头的顺子个数，有没有雀头。因为按照值域，所以写成矩阵扔到值域线段树上，再加上 $f=0/1$ 所以可以把矩阵乘做到 $\mathcal O(n^2)$，就能过了。

[★] QOJ7645 Shoes

发现每天完成的一定是左右两段连续的商店，所以令 $f_{l,r}$ 表示 $[l,r]$ 的最小天数，可以做到 $\mathcal O(n^3)$。特殊的，这题可以分布转移，只要 $f$ 压成一个 $(已经多少天，当前天用了多少时间)$ 的二元组就好。

[★] QOJ3869 Gastronomic Event

• 引理 1：最终最优解一定存在一个点 $u$ 使得：$u$ 的一部分子树全部都是根向边，另一部分都是叶向边。

调整法，对于 $u$，每次找到满足上面性质的，包含 $u$ 的极大连通块，并且翻转内部所有的边，容易发现答案不会更劣。

• 引理 2：以重心作为 $u$ 一定能取到最优解。

假如当前 $u$ 不是重心，考虑一条向重心的边 $u\rightarrow v$（假设是这个方向的，不是就整体翻转一下），令 $u$ 子树里面根向边个数为 $r$，叶向边个数为 $l$，子树外大小为 $s$，那么 $\Delta=(r-s)l$，这个一定是非负的。

然后就是经典多重背包优化了，时间复杂度 $\mathcal O(\dfrac{n\sqrt n}{\omega})$。

[★★] QOJ7606 Digital Nim

直接求单个点的胜负态是难的，关键在于这个必输状态其实很密，两两之间不会隔 $>180$，这暗示我们可以类似倍增去做这个问题。令 $\text{lst}(x)$ 表示 $x$ 距离上一个必输态的距离，那么有 $\text{lst}(x+1)=\begin{cases}\text{lst}(x)+1&S(x)>\text{lst}(x)\\1&\text{otherwise.}\end{cases}$。因为 $\text{lst}$ 的取值只和上一个 $\text{lst}$ 和 $S(x)$，所以可以直接数位 dp。

[★] QOJ5109 Spider Walk

扫描线一下，倒着 dp，发现是一个区间等差数列 chkmin，线段树维护，有点小细节。

[★★★] 「RiOI-2」change

有难度的贪心题，主要是策略的选择。

我们最终对于每个 $i$，最后新兑换成 $i$ 号元素使用的一定是一个以 $i-1$ 为后缀的元素集合，否则可以调整法。所以我们从前往后扫描，维护一个队列，表示如果之前所有元素都从后依次往前合并成了 $i-1$ 号元素，那么初始的代价。操作变成了每次新扫描的时候把队列里的元素 $x_{i-1}$ 个合并成一个元素，再加入新的 $c_i$ 个值为 $v_i$ 的元素。因为是贪心，所以队列里的值要单调，每次插入元素的时候如果不满足单调先贪心换掉。优化的话发现只有 $\mathcal O(n)$ 种元素，把队列记成二元组 $(c,v)$ 表示有 $c$ 个值为 $v$ 的元素，然后如果 $v>V_{\max}$ 的话，这种元素肯定没用，直接扔掉就好了。每个元素最多被合并 $\mathcal O(\log V)$ 次，时间复杂度 $\mathcal O(n\log V)$。

[★] 「SFCOI-3」进行一个走的行

因为事件是有序的，起点终点量级又是 $\mathcal O(n)$ 的，统一一下。差分了一下，令 $S(x)$ 表示事件 $1\sim x$ 需要付出的代价总和，那么 $ans(l,r,x)=ans(1,r,x+S(l-1))-ans(1,l-1,x+S(l-1))$。从左往右扫描线，用平衡树维护，每次把两个连续段并起来，均摊下来是 $\mathcal O(n\log n\log V)$ 的，注意一下可交区间合并一定要定义严格的偏序关系，也就是不能出现相同节点。

[★★] QOJ7644 Good Splits

直接做并不好做，根据「很久想不出来的计数题都是容斥」定理，我们假设要是用容斥。如果连线上下连算两种方案，那么答案很容易算：$f_n=\sum\limits_{i=0}^{n}\text{Cat}(i)\text{Cat}(n-i)\dbinom{2n}{2i}$，其中 $\text{Cat}(n)$ 代表卡特兰数。我们希望容斥到一个 $g_n$ 表示上下只算一次的方案数，乍一看好像无法建立什么联系，因为有两个变量：连通块数（指上下连线紧密联系的匹配）和上下匹配的计算次数。

我们建立一个中间状态 $h_n$，表示 $n$ 对匹配构成一个连通块的方案数，现在可以容斥了：观察到连通块不会交叉，只会包含，所以枚举编号 $1$ 所在的连通块，$h_n=f_n-\sum\limits_{i=1}^{n-1}h_iS_{2i,n-i}$，其中 $S_{i,j}$ 表示把 $j$ 对匹配分到 $i$ 个集合的方案数，这个可以对 $f$ 背包。发现 $h$ 推到 $g$ 也是一个背包，$\mathcal O(n^3)$。

[★] QOJ6538 Lonely King

发现最终不会存在蓝边，而且每条匹配链一定是从一个叶子到一个祖先。令 $f_{u,i}$ 表示子树 $u$，节点 $i$ 要匹配到祖先，每次两个节点合并转移式应该是：

$$f_{x,i}+f_{y,j}+a_ua_i\rightarrow f_{z,j}\\ f_{x,i}+f_{y,j}+a_ua_j\rightarrow f_{z,i}$$

这个可以建李超树，查 $a_u$ 点，然后对 $b$ 整体加，最后合并，时间复杂度 $\mathcal O(n\log n\log V)$。

[★] QOJ6684 Trie

自底向上做确定边，我们要做的就是对子树的关键字符串排序。发现确定 $u,v$ 子树大小是 $\min(sz_u,sz_v)$ 的，那么直接暴力比较就可以按照启发式合并复杂度分析，时间复杂度 $\mathcal O(n|\Sigma|\log n\log |\Sigma|)$，其中 $|\Sigma|=26$。

[★★] QOJ6101 Ring Road

离线多次两点最短路，可以树上扫等做法，这里最好的是分治。先三度化了，那么分为两种询问：来自分治中心边两侧的，和同侧的。前者因为跨过分治中心边的最多只有六个点（如下图距离），所以暴力跑 $6$ 次 dijkstra，后面分治下去求就好了。注意同侧的询问可能先走到另一侧又走回来，提前更新一下答案。

[★★] QOJ4581 Energy Generation

直接 dp 并不是很可行，根据「不会的题可能是流」定理，我们假设是要用流。每个点有四个属性，并不能很好的刻画，如果是两种属性就可以二分图了，启发我们对属性降维。如果我们把右上，右下，左下，左上四个方向的属性分别定为 $[+,+],[+,-],[-,-],[-,+]$，那么令关系对集合为 $S$，$i$ 节点的原来属性为 $p_i$，新属性为 $q_i$，总代价就是：

$$\sum\limits_{i=1}^n(1-\text{dis}(p_i,q_i))P+\sum\limits_{(u,v)\in S}(1-\text{dis}(q_u,q_v))G$$

其中 $\text{dis}(x,y)$ 表示 $x,y$ 的 Hamming Distance。这样每一维就独立开了。容易建立最小割模型，二分图两点分别代表 $+,-$ 两种属性，割了的边代表了选择了这个属性，为了保证两种属性至少选一种且不能同时都选，分别建立两部对应点对的 $+\infty$​ 的流量边，同时给连接源点和汇点边加上一个较大值，这样保证能割中间的关系边先割中间的边。

[★] QOJ4843 Infectious Disease

有往 min-max 去想，但是不是很成功。发现第 $i$ 天感染的人最多 $d_i=\min(2^i,n-3^i)$，算一下 $\sum\limits_id_i^2$ 量级是对的，直接做。

[★★] [ZJOI2022] 树

暴力 $f_{i,j,k,l}$ 表示考虑前 $i$ 个点是哪棵树的叶子，第一棵树有 $j$ 个点需要有儿子，其中 $k$ 个已经有儿子了，第二棵树有 $l$ 个点没有钦定父亲，暴力是 $\mathcal O(n^5)$ 的。$j,k$ 两维看起来很累赘，「所有都满足条件」这类直接容斥，化一下式子，令 $f_1(S),f_2(S)$ 表示第一棵树 / 第二棵树钦定了 $S$ 集合为叶子的方案数，那么子集反演得到：

$$\begin{aligned} ans&=\sum\limits_{S}f_1(S)f_2(U\backslash S)\\ &=\sum\limits_{S}\left(\sum\limits_{S\subseteq T_1}(-1)^{|T_1|-|S|}f_1(T_1)\right)\left(\sum\limits_{U\backslash S\subseteq T_2}(-1)^{|T_2|-|U\backslash S|}f_2(T_2)\right)\\ &=\sum\limits_{S}\sum\limits_{T}[S\cup T=U]f_1(S)f_2(T)(-1)^{|S|+|T|-|U|}2^{|S\cap T|}\\ &=\sum\limits_{S}\sum\limits_{T\subseteq S}f_1(S)f_2(U\backslash T)(-2)^{|S|-|T|} \end{aligned}$$

令 $f_{i,j,k}$ 表示考虑完了前 $i$ 个点，第一棵树有 $j$ 个点没有钦定叶子，$i+1\sim n$ 的点在第二棵树有 $k$ 个未钦定的，直接做就是 $\mathcal O(n^3)$​ 的。

[★] QOJ7569 Lines

题目并没有保证 $a,b,c$ 具有凸性，而没有任何凸性和单调性的 $(\max,+)$ 卷积目前只能暴力。试着把每个函数的 $(k,b)$ 看成一个点，容易发现取的 $t$ 相当于用斜率为 $k$ 的线去切这个点集，所以有用的只有上凸包。又因为每个点的 $y$ 是 $a,b,c$ 卷起来的，所以把 $a,b,c$ 凸包求出来再做闵可夫斯基和就对了。

[★] QOJ7077 Sheep Village

把圆方树建出来，对于每个环就是一个经典的匹配距离最小问题，具体见「classic : 1」。这里有一个好写的方法，dfs 的生成树的过程中每次遇到返祖边直接跑就好了。

[★] QOJ5138 Torch

如果两个人允许互相超越，那么答案就是第二个人的最终位置减掉中途第二个人超过第一个人最大的距离，易证是对的，然后随做。

[★★] QOJ9440 Train Seats

题目等价于给定一个序列，对序列建立广义线段树，最大化每个节点的值之和。具体见「classic : 2」，时间复杂度 $\mathcal O(n\log n)$。

[★] 「RiOI-03」网格

简化一下只要 $(x,y)$ 为白格子，$(x+1,y)$ 为红格子的格子对数。这题特殊在于每次都是对行列操作，所以分类讨论一下三行的时间戳大小：

• 染色顺序为 cab / cba，其中 a 染白色，b 染红色。
• 染色顺序为 acb，其中 c 染白色，b 染红色。
• 染色顺序为 bca，其中 a 染白色，c 染红色。

拿个树状数组嗯维护。

[★] CF1550F Jumping Around

[★] CF1305G Kuroni and Antihype

两个蓝莓算法板题，可以借鉴的是第二题的虚点补全贡献的思想。

[×] QOJ5146 Skills

[★] QOJ5148 Tree Distance

尝试点分治。每次分治 $u,v$ 两点距离都可以写成 $d_u+d_v$ 的形式，其中 $d_u$ 表示 $u$ 到分治中心的距离。容易发现如果 $(u,v)$ 要形成支配对那么 $\max(d_u,d_v)\le \max\limits_{u\le w\le v}d_w$，经典结论这玩意儿是 $\mathcal O(n)$ 级别的，二维数点，时间复杂度 $\mathcal O(n\log ^2n+q\log n)$。

[★] QOJ2830 Data Structure

你只需要一堆拉稀的分讨。

[★★] QOJ7071 Maximize the Ratio

如果要判定答案是否 $\ge mid$，容易得到 $\mathcal O(n^3)$ 的凸包 dp：枚举凸包和 $k=0$ 直线的切点，$f_u$ 表示当前决策到 $u$ 的最小代价，对所有线段按照斜率排序暴力转移得到 $\mathcal O(n^3\log V)$ 的算法。使用一个经典的 shuffle trick：随机排列的前缀最大值个数期望为 $\mathcal O(\log n)$，所以每次枚举点的时候先 check 能不能比前面的答案大，如果能就精确二分一下，时间复杂度 $\mathcal O(n^3+n^2\log n\log V)$。同理有一个类似的结论：一个随机的值为 $1,-1$ 的序列最大前缀和绝对值期望是 $\mathcal O(\sqrt n)$ 的。

[×] QOJ6327 Count Arithmetic Progression

[★] QOJ6322 Forestry

写出暴力 dp 式，是一个前缀后缀的转移，线段树合并。

[★] QOJ6331 Jewel Game

有向图上 dp，先把不在环上的转移全部转移了，如果无法转移找一个当前环上值最优的节点断开，继续暴力转移。

[×] QOJ6134 Soldier Game

[★★] QOJ5568 Cyclic Shifts

我们肯定希望每次 shift 的数都尽量多，尝试从 $k=n-1$ 找找规律：如果我们 shift 除了 $a_i$ 的 $n-1$ 个数，等价于先交换 $i-1$ 和 $i$，再整体向右 shift 一次，而且如果我们需要交换多对相邻的数，只要两两不交也是可以做到的，每次 shift 的代价上界是 $\dfrac{2}{n}$，只要最终在 $n$ 次以内排完就做完了。有一种叫奇偶排序的东西，一共排序 $n-1$ 轮，如果轮数为奇数，那么分别排序二元组 $(2i-1,2i)$，否则分别排序 $(2i,2i+1)$，套上来就好了。

[★] QOJ5258 Mortgage

询问形式是 $\min\limits_{l\le i\le r}\dfrac{s_i-t}{i-l+1}$，这不是求 $(l-1,t)$ 和 $[l,r]$ 节点构成凸包的切点嘛，嗯。

[★] QOJ5256 Insertions

分讨一下，二维数点。

[★] QOJ7182 Very Sparse Table

初想法是构建一棵三叉树，扩展到 $\sqrt n$ 叉树，这里需要注意的一点是 $[l,r]$ 的叉数为 $\sqrt{r-l+1}$，如果直接为 $\sqrt n$ 是分析不出来的，写一下发现过了。

[×] QOJ10738 One Must Imagine Sisyphus Happy

[清华集训 2016] 如何优雅地求和

QOJ5155 Faster Than Light

QOJ7520 Monster Generator

QOJ10514 疲配

QOJ10518 腐蚀与膨胀

QOJ10516 最近公共祖先

QOJ6379 LaLa and Monster Hunting (Part 2)

QOJ6329 Colorful Graph

[省选联考 2023] 过河卒

QOJ9542 Friendship is Magic

QOJ7103 Red Black Tree

QOJ10746 Las Vegas

QOJ5573 Holiday Regifting

T613944 IOer

QOJ9639 字符串

CF547E Mike and Friends

CF587F Duff is Mad

QOJ5530 No Zero-Sum Subsegment

QOJ5434 Binary Substrings

QOJ5439 Meet in the Middle

QOJ5441 Quartz Collection