分析 注意到一定存在包含 xxx 中 ∑j=1ixj≥∑x\sum_{j=1}^ix_j\geq\sum x∑j=1ixj≥∑x 的第一个 iii 的最优方案。因为如果不包含,也就是 xxx 和 yyy 选择的两段都小于各自的 ...
prufer 序列
发现标题字打错了,然后改不了标题就重新发了一遍。 简介 prufer 序列可以把一个结点带标号的树用 n−2n-2n−2 个值域为 [1,n][1,n][1,n] 的整数表示。 一棵树对应唯一的 prufer 序列,一个 prufe...
P9989 题解
“笑って走っていく日も 泣きながら帰る日も この街と共に生きてる”——《街》 分析 操作过后的数一定至少变为原来的 12\frac{1}{2}21,所以问题变成了如何判断区间内是否会有数被修改。 可以维护 lcm\text{lcm...
P5494 题解 & 平衡树合并
这是一篇平衡树合并题解,平衡树合并的复杂度 并不是假的,本题复杂度 O(nlogn)O(n \log n)O(nlogn),更通用的可以证明到 O(log2n)O(\log^2 n)O(log2n),比如支持序列 全局加全局取膜。...
网络流常见建模
你眼中倒映的世界 一瞬永远 —— 《梦语》 分析 首先答案有单调性,考虑二分。 然后每次留下来的构成一颗三叉树,父亲是儿子的中位数,考虑树形 dp。 上很经典的中位数套路,设二分的值为 vvv,≥v\geq v≥v 的 gvg_vg...
ABC299G 题解
“まだ動くまだ進む 物語の上を泳げ” —— 《スイマー》 分析 维护一个栈,每次加入一个值。 如果栈顶在之后也会出现并且比加入的值大就弹出。 这样使得每个值尽可能放在前面。 粗略的证明一下。假设有两个序列 A,BA,BA,B,AAA...
ABC295G 题解
“「あるべき人間の姿へ」 「正しい人間の姿へ」 そう思えばなんだか 人間全てが汚く思えてくるな”—— 《不可解》 题意简述 给定一张点数为 NNN 的有向图,初始 pi(1≤pi≤i,1≤i<N)p_i(1\leq p_i \...
ABC279F 并查集题解
“我仍然在无人问津的阴雨霉湿之地” —— 《世末歌者》 题意 高橋君有 NNN 瓶糖水,青木君有 MMM 瓶糖水。 高橋君的第 iii 瓶糖水有 AiA_iAi 份糖 BiB_iBi 份水。 青木君的第 iii 瓶糖水有 C...
ARC158C 题解
“かけがえのない日々を ここで 積みかさねて ひとつひとつ いまさらわかった”—— 《想いよひとつになれ》 题意简述 设 f(x)f(x)f(x) 为 xxx 的数字和。例如 f(158)=1+5+8=14f(158)=1+5+8=...
ABC290G 题解
“空高く舞う鳥へ かさねたハート”—— 《Jump up HIGH!!》 题意简述 有一颗深度为 DDD 的满 KKK 叉树,你需要剪掉一些边使其存在大小为 XXX 的联通分量,求最少剪掉的边的条数。 分析 考虑选择 所有 大小大...