杂题

todo list

Online Judge	Problem\(^{[1]}\)	State
N/A\(^{[2]}\)	Problem #0	\(\color{green}\checkmark\) / \(\color{red}\times\) / \(\color{grey}\circ\)\(^{[3]}\)
Luogu	P3611	\(\color{green}\checkmark\)
Luogu	P5194	\(\color{green}\checkmark\)
Luogu	P2895	\(\color{green}\checkmark\)
Luogu	P2758	\(\color{green}\checkmark\)
Luogu	P1455	\(\color{green}\checkmark\)
Luogu	P2256	\(\color{green}\checkmark\)
Luogu	P1113	\(\color{green}\checkmark\)
Luogu	P2419	\(\color{green}\checkmark\)
Luogu	P1629	\(\color{green}\checkmark\)
Luogu	P5837	\(\color{green}\checkmark\)
Luogu	P1550	\(\color{green}\checkmark\)
Luogu	P1991	\(\color{green}\checkmark\)
Luogu	P5663	\(\color{green}\checkmark\)
Luogu	P1825	\(\color{green}\checkmark\)
UVa	10048	\(\color{green}\checkmark\)
UVa	532	\(\color{green}\checkmark\)
Codeforces	#735 E	\(\color{green}\checkmark\)
Codeforces	#413 D	\(\color{green}\checkmark\) / \(\color{green}\checkmark\)
Codeforces	#601 C	\(\color{green}\checkmark\)

[1] Problem 的链接均来自 Luogu Online Judge .
[2] 第一行用作格式说明示例 .
[3] 点击后面的 \(\color{green}\checkmark\) 的 State 可以看见提交记录哦 .
[*] 题目排序：大概是按 OJ 为第一关键字，难度为第二关键字排序
[*] 有些题用的是古老提交记录（2020-..-..）可能 Code Style 会非常不一样 .

题解

想要代码可以找我（洛谷 227514 私信）如果我还活着就会回复的qwq

Online Judge	Problem	Tag
Luogu	P3611	二分，堆
Luogu	P5194	搜索
Luogu	P2895	搜索
Luogu	P2758	dp
Luogu	P1455	并查集，背包
Luogu	P2256	并查集
Luogu	P1113	拓扑排序，dp
Luogu	P2419	Floyd
Luogu	P1629	最短路
Luogu	P5837	最短路
Luogu	P1550	最小生成树
Luogu	P1991	最小生成树
Luogu	P5663	最短路
Luogu	P1825	搜索
UVa	10048	最短路
UVa	532	搜索
Codeforces	#735 E	树 dp
Codeforces	#413 D	迷惑 dp
Codeforces	#601 C	概率 dp

1. P3611

显然先二分，然后就变成维护一个数据结构 \(\mathcal T\)，支持

全局减一个常数 \(k\)，随即修改一个数
查最小值

操作 \(1\) 可以变成把那个数加上 \(k\) 然后改，相当于维护了一个出场时间 .

用一个堆就可以搞了 .

2. P5194

每个砝码的质量至少等于前面两个砝码的质量的和

又有砝码的质量是有符号 \(32\) 位整数，类似一个 Fibonacci 数列，\(n\) 是不会很大的 .

暴搜加个剪枝就艹过去了？？？~~不明觉厉~~

3. P2895

简单 bfs .

~~rnm 连 bfs 都不会写了，给洛谷贡献 15 条提交记录~~

4. P2758

编辑距离，挺经典的 dp，老早就 A 了，还写过题解 Link .

重新写一遍才发现不会用 scanf("%s") .

5. P1455

每个联通块合并，然后 01 背包 .

~~我原来的代码我自己都认不出来草~~

6. P2256

并查集板子，Trick .

7. P1113

拓扑排序，然后 dp，非常简单 .

8. P2419

Floyd 传递闭包板子 .

9. P1629

反图最短路，经典小 trick.

10. P5837

一开始想二分，暴毙 .

我们要求的就是找一个生成树 \(\mathcal T\)，使得边上的

\[\dfrac{\min f_i}{\sum c_i} \]

最大 .

俩限制肯定不好求，我们考虑固定一个 . \(\min f_i\) 看起来挺可做 .

\(f_i\) 最多只有 \(O(m) = 1000\) 个取值，枚举 \(F = \min f_i\) . 用 Dijkstra 跑在边的流量 \(\ge F\) 的限制下的最短路求 \(\sum c_i\) .

不用担心 \(F\) 是否能取到，因为如果 \(C = \sum c_i\) 一定，那么

\[\dfrac FC < \dfrac{F+1}{C} \]

取不到的会被最优性舍掉的

这题好棒/cy .

11. P1550

最小生成树（MST）板子

12. P1991

yeeeeeeeeeeeeeeeah

二分 \(D\)，然后就变成判断连通块个数

肯定是在最小生成树上找边选呐，然后没了

欧几里得距离最小生成树可以暴力搞

13. P5663

~~卧槽这不是矩阵快速幂吗~~

~~卧槽这不是大力找奇环最短路吗~~

注意到如果 \(L\) 可以，那么 \(\ge L\) 且与 \(L\) 同奇偶性的都可以 .

Dijkstra 求经过奇数条边的最短路 \(d_1\) 和经过偶数条边的最短路 \(d_0\)，两者可以互相转移（可以共用一个 priority_queue） .

然后只需判断 \(d_{L\bmod 2}(a) \le L\) 即可 .

14. P1825

bfs

15. UVa10048

全源最小瓶颈路，可以 Floyd .

注意输出格式

16. UVa542

~~和 P2360 一模一样~~

我草原来 _start 不能用 .

多组数据要清空！
多组数据要清空！
多组数据要清空！
多组数据要清空！
多组数据要清空！

好，正片开始 .

dp 还是得刷表法 = =

17. CF #735 E

参考：https://www.luogu.com.cn/blog/IC1805/solution-cf735e

~~好神啊，但是教练说挺水 .~~

呼呼，肯定一眼树形 dp，树 dp 尽管多水我都不会做 .

Ver 1.

定义一个 \(dp_{u, i, j}\) 表示子树内离 \(u\) 最近的着色点到 \(x\) 的距离为 \(i\)，子树内离 \(u\) 最远的非合法点到 \(u\) 的距离为 \(j\) 的方案数 .

然后我们发现 对于非合法子树，\(j\) 的转移与 \(i\) 无关（具体可以看链接证明），于是

Ver 2.

于是 \(dp\) 数组可以压起来：

\(dp\) 数组现在定义为：\(dp_{u, i}\)（\(0\le i\le 2k\)）表示：

若 \(0\le i\le k\) 表示以 \(u\) 为根的子树是一棵合法子树，且子树内离 \(u\) 最近的染色点与 \(u\) 的距离为 \(i\) ;
若 \(k<i\le 2k\) 表示以 \(u\) 为根的子树是一棵非合法子树，且子树内离 \(u\) 最远的染色点与 \(u\) 的距离为 \(i-k-1\) ;

显而易见，\(dp_{x,0}=dp_{x,k+1}=1\) .

转移（刷表法）如下：

枚举 \((x, i), (v, j)\) 且 \(v\) 为 \(u\) 的儿子，则考虑合并 \(dp_{x, i}\) 和 \(dp_{v, j}\) .

首先由乘法原理贡献就是 \(dp_{x,i}\cdot dp_{y,j}\) .

考虑转移到哪（状态都是分类讨论定义的，肯定是要分类讨论的）：

\(i/j\)	\(i\le k\)	\(i>k\)
\(j\le k\)	\(dp_{x, \min(i, j+1)}\)	\(\begin{cases}dp_{x,i}&i+j-k\le k\\dp_{x,j+1} & i+j-k>k\end{cases}\)
\(j>k\)	Impossible	\(dp_{x, \max(i, j+1)}\)

\(i>k, j\le k\) 的部分比较玄妙，因为俩情况杂糅在一起，仔细体会下 .

综合一下：

\(0\le i+j\le k\)：转移到 \(dp_{\min(i, j+1)}\) .
\(k< i+j\le 2k\)：转移到 \(dp_{\max(i, j+1)}\) .

于是答案就是 \(\sum_{i=0}^k dp_{1, i}\)，没了 .

时间复杂度 \(O(nk^2)\) .

可能会补其他复杂度做法 .

18. CF #413 D

参考：

~~好神啊，但是教练说挺水 .~~

极简题解（~~时间管理大师~~）：

定义一个状态为最长不上升后缀的数字和，于是合并的过程可以直接用加法代替，然后根据下一次的价值进行转移即可 .

先做点平凡的定义：

一个 Basic 状态定义为只有 \(2\) 和 \(4\) 的一个序列 .

一个状态定义为一个 Basic 状态经过 \(2048\) 规则向左合并后形成的序列 .

大体思路：考虑一个加数的过程，也就是题目里给出的 .

由于相同的两个数字会被合并，所以状态中必然没有两个相邻数字相同

我们只关心状态可以扩展到哪些状态，于是我们考虑将状态分成若干个下降序列，那么如果在后面加一个数，肯定只会对最后一个下降序列有影响，并且下降序列必然不会合并 .

我们不妨把最后一个下降序列（即下降后缀）定义为这个状态的「代表段」 .

所以我们整一个类似 Hash 的东西，把每个状态 \(S\) 用它的代表段元素和表示，记作 \(c(S)\) .

考虑在末尾添一个数的过程，\(S\) 添加一个数 \(x\) 变成 \(S_0\)，让我们看看 \(c\) 的变化：

若 \(S\) 的最后一个数 \(t\) 满足 \(t\ge x\) ，那么 \(c(S_0) = c(S) + x\) .
否则 \(c(S_0) = x\) .

开始 dp .

定义 \(dp_{i, j}\) 表示前 \(i\) 个数已经处理完毕，状态的 \(c\) 值为 \(j\) 的方案数 .

加一个数 \(x\),讨论转移（以下均为从 \(dp_{i-1,j}\) 转移）：

若 \(x=2\)，那么必然转移到 \(dp_{i, j+2}\) .
若 \(x=4\) .
- 若状态末尾有 \(2\)，则转移到 \(dp_{i, 4}\)（~~重启人生~~后缀更新） .
- 若不然，则转移到 \(dp_{i, j+4}\)
若 \(x=0\)，就相当于 \(x=2\) 的方案数加 \(x=4\) 的方案数 .

有了前面讨论 \(c\) 的变化，转移就轻而易举了 .

「若状态 \(S\) 末尾有 \(2\)」怎么判断？

代表段里每个元素都是 \(2\) 的次幂，并且一定单调减，于是所有 \(\neq 2\) 的元素都是 \(4\) 的倍数 .

又由于最简性，\(2\) 最多出现一次，于是就有

若 \(c(S)\bmod 4 = 0\)，则状态 \(S\) 末尾无 \(2\)

若 \(c(S)\bmod 4 = 2\)，则状态 \(S\) 末尾有 \(2\)

于是答案是

\[\sum_{i=2^k}^{\infty}dp_{n, i} \]

不是很好做，于是我们可以在转移的时候把所有 \(\ge 2^k\) 的 \(c\) 大力并到 \(2^k\) 上（就是所有 \(dp_{i,j}\) 全部换成 \(dp_{i,\min(j, 2^k)}\)），这样答案就是 \(dp_{n, 2^k}\) 了 .

其实可以滚动数组，但是没必要 .

时间复杂度 \(O(n2^k)\) .

提交记录那里有两条，前面的是边读边 dp（半刷表），后面的是读完再 dp（刷表） .

18. CF #601 C

参考：https://www.luogu.com.cn/problem/solution/CF601C 第一篇

题解都说简单，概率 dp 不会实锤了

得分是 \(a_i\) .

排名的定义为 \(1+k\)， \(k\) 表示总分严格比他低的人数。

Then，定义 \(dp_{i,j}\) 表示前 \(i\) 人总分 \(j\) 的期望人数，因为对于每轮比赛，对于除了 \(a_i\) 的 \(m−1\) 种得分就是等概率分布（古典），于是

\[dp_{i,j}=\dfrac{1}{m+1}\sum_{k=1}^m[k\neq a_i]dp_{i-1,j-k} \]

然后这个 \(\sum\) 可以前缀和优化，答案就是

\[1+\sum_{i=1}^{\sum c_i}dp_{n,i} \]

时间复杂度 \(O(n^2m)\) .

~~partial_sum 咋用啊~~