P1244 NOI2000 青蛙过河 每一次操作，先将荷叶铺满生成一垛，再类似二进制分组的合并。上限为 $(m+1)2^n$。 P4408 NOI2003 逃学的小孩 有结论 A 和 B 一定要在树的直径的两端。找到一条直径，并以两点跑一次多源最短路即可。 P1949 NOI2001 聪明的打字员 直接 $10$ 进制状压 bfs 可以过。 P5751 NOI1999 01串 先进行前缀和，然后每个限制都是对两个前缀和的差的限制。差分约束板子题。 P5763 NOI1999 内存分配 小模拟题，有点 CSP-S 2023 T3 的感觉。直接记录每一个被占用的内存块，暴力维护队列即可。 P7302 NOI1998 免费的馅饼 不难有 $f_i$ 表示最后一个接的点是 $i$，从 $j$ 点转移有限制 $\lvert{p_i-p_j}\rvert\le2(t_i-t_j)$，由绝对值的非负性可以拆成两个必须同时满足的条件 $$ \left \{ \begin{array}{l} p_i-p_j\le2t_i-2t_j\\p_j-p_i\le2t_i-2t_j \end{array} \ri
AGC023F 01 on Tree 给出一棵 $n$ 个节点的树，以及一个空序列。 每个节点上有一个取值在 ${0, 1}$ 中的数。 每次你可以选择没有父亲节点的点删除，并且将这个节点上的数字放在当前数列末尾。 请你求出这个数列可能得到的最小逆序对数。 $n\le 2\times 10^5 $ 如果没有先删父亲的限制，那么最优序列一定形如 $0000\cdots 1111$。不妨先忽略这一限制，将所有点统一处理。选中某个点操作就将这个点和父亲“合并”，表示选完父亲后立即选这个点。这样是等价的。考虑从根出发，当前的最优决策一定会最先和根合并，而后继的操作最优性同理。多个点合并在一起后，新点不难表示为其 $0,1$ 的个数 $a_i,b_i$，两个点 $i,j$ 当满足 $b_ia_j<b_ja_i$ 时 $i$ 先选更优。使用优先队列维护合并，答案在合并过程中统计即可。 这一类贪心的本质是将序列的贪心放在树上，且限制生成序列的拓扑序，可以使用贪心选取前继化为类似于序列的问题，其中比较方法和序列相同。 HDU-6326 Monster Hunter 给出一棵 $n\le 10
划水记 Day -1 (2023.12.29) 学校元旦晚会，Rick Roll 诈骗全班，感觉良好。 好久没做过绿油油的火车了，一颠一颠颠睡过去就很神秘。 Day 0 (2023.12.30) 好好好，都来北京了，早餐吃 KFC ？？？ 北京站开始随机游走。 好好好，都来北京了，中餐吃麦当劳？？？ 领了胸牌和 T 恤，回房间睡了两个小时到 15:20。晚饭吃了点烤鸭。 试机，冷身赛，统统不重要，口胡口胡就过去了。但是面了几个人，不错。 Day 1 (2023.12.31) 自助早餐吃的有点多，进考场晕乎乎的/cf 宣读比赛规则，每三个题换一次气球颜色，红蓝绿黄，逆天坏了。 开题是 $12$ 题，拿到 A 就感觉很可做，写了十分钟感觉有点细节锅了。遂看榜。发现已经 rk300+，去跟了个水到逆天的 T4。然后把离散化板子题 T2 给切了，dfs 序板子题 T3 同样是一眼秒。赛时 $00:40$ 拿到气球，在临近的座位中略有落后。这时候去补 T1，给大家表演一个狂吃四发罚时，一路红到头，开始遥遥落后。T8 的位置比较神秘，感觉比 T1 简单多了。$O(n\sqrt{n})$ 做法感觉是
Gym102341B Bulbasaur 首先最大流转最小割，其中割为割点。考虑固定右端点 $r$，$f_{s,i}$ 表示 $r$ 处只有只有 $s$ 中的点可以连通，左端点为 $i$ 的最小割。明显具有单调性，交换答案和状态。$f_{s,i}$ 表示最小割为 $i$ 的最右左端点 $i$。转移时取 $\max$ 即可。 Gym102900F Fountains 考虑确定了选择的 $k$ 个区间后怎么计算 $\sum\max$。将 $k$ 个区间按照区间和降序排序。每个区间 $(l,r)$ 都相当于给网格未染色的 $\forall (x,y) x\le l,y\ge r$ 染色。这个过程形成了一个优美的轮廓线。可以对它 DP。合法轮廓线的数量很少且难以编码，可以使用 $umap$。 CF1519F Chests and Keys $\forall \sum_{i\in\mathrm{S}}{a_i}\le\sum_{j\in N(\mathrm{S})}{b_j}$ 一眼霍尔定理的样子。按照 $a,b$ 的大小拆成几个点之后，题目就是要找到一组完美匹配，最小化若 $a_i$ 和 $b
D. Split Plus K 记最后相同的数为 $t$，则不难发现对于每个数 $x$，操作都形如 $t+y=x+k$，直到这个数变成 $t$，若这个数的操作次数为 $y$，则有 $(y+1)t=x+yk$，整理得 $x-t=y(t-k)$，其中 $y\ge 0$，将其改写为 $x-k=y(t-k)$，其中 $y\gt 0$，这样不难发现最优解时 $t-k$ 为所有 $x-t$ 的 $\gcd$，且所有 $t-k$ 同号。 E. Multiple Lamps 既然按下所有按钮，最终只会有编号为完全平方数的灯亮，所以可以数据分治。 $n\ge 20$ 全部点亮 $n\lt 20$ 注意每一种最终的点亮情况可以反演出按钮情况，所以可以枚举最终亮的灯。 F1. Small Permutation Problem (Easy Version) $a_1 \gt 1$ 或 $a_n \lt n$ 时无解，启发我们注意到差分只存在 $0,1,2$ 三种，开始分讨 $\Delta=a_i-a_i-1$，并记 $i-a_i=t$。 $\Delta=0$：前 $i-1$ 个数不存在 $i
yrq
