在 ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b) 中： 求解过程中始终有 ∣x∣≤∣b∣|x| \leq |b|∣x∣≤∣b∣ , ∣y∣≤∣a∣|y| \leq |a|∣y∣≤∣a∣。 证明如下： 设 ∣a∣≥∣b∣|a| \geq |b|∣a∣≥∣b∣ , 则求出的 x 满足 ∣ ...

最小生成树 Prim 把点分为已经加入 MSTMSTMST 的 和未被加入的，每次把距离已加入的点最近的边加入 MSTMSTMST 中。 Kruskal 把边从小到大排序，不会产生环就加入，否则跳过。 证明: 考虑归纳法。 若当前只存在 最小边链接的节点，则答案为最小边。 若当前只存在 最小边链接的节点，则答案为最 ...

A. 思维题，没想出来 答案长这样： B. 式子很好推，有两种设法：         ~~~~~~~~         i 到 i+1 的期望         ~~~~~~~~         i 到 n 的期望 其中 第一种可以求通项，第二种要矩阵加速递推。 C. 枚举 j ,然后字典树分层计数。 使用 01trie ...

图论 0.有感而发 眼睛瞎了有利于打Dijkstra。 by NotDeep 如果这题我不会做，那么一定是图论。 by NotDeep 1. 基本算法 ​ Case 1:Case\ 1:Case 1: Dijkstra         ~~~~~~~~        本质是 贪心+DP贪心+DP贪心+DP。         ~ ...

## 1. 状态 ​ 区间DPDPDP的状态一般 设 f[l][r] 表示区间 [l][r] ....。但有些时候可以直接设 fif_ifi​ 表示 [1,i][1,i][1,i]…。 ​ ​ 转移的时候会依靠断点，即 f[l][r]=min/maxf[l][r]=min/maxf[l][r]=min/max{f[l][k]+f[ ...

分数 : 606060 （50+10+0+050+10+0+050+10+0+0) A. stick 先是一个数字，然后一串000，最后一串888。贪就完了。 注意模数是 9982449982449982448535353。挂分 50pts50pts50pts B. game 正解爆搜。少打 break挂 90pts90pts90 ...

Day 0 晚上去了酒店，和另外几个人一起复习了 TarjanTarjanTarjan ，然后就睡了。 睡觉前想着 2.5h2.5h2.5h 写前两个题，后两个题打下暴力，应该能拿 一等。 Day 1 + 上午 7 : 407\ :\ 407 : 40 早上起来的最早，但发现自己感冒了。喝了只 蒲地蓝蒲地蓝蒲地蓝 ，还戴上了 ...

线性DP 定义: 具有线性"阶段"划分的DPDPDP被称为线性DPDPDP。 经典模型 LISLISLIS , LCSLCSLCS , LCISLCISLCIS(最长公共上升子序列) , 最长公共子序列最长公共子序列最长公共子序列 , 数字三角形数字三角形数字三角形。 例题： LCS 题意： ...