划水记
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})$ 做法感觉是显然的。赛时 $01:30$，感觉自己一题不会了，给大家表演一个最后 $3.5h$ 一题不过。去想 T5 & T6，T6 不知道为何一点想不到矩乘，逆天做法感觉不好写，发现榜上一群人过了 T5，后背发凉。想了二十分钟才考虑到了前缀和 & 对层次 DP。然后我从上往下的做法也是与众不同的逆天，共坑了我一个小时。换到了蓝气球，但是这一排已经好几个蓝了，再次遥遥落后。T6 写了逆天做法，再次被坑一个小时。去想 T7，看错题了/fn。看对题意后再次一眼秒了多线程背包和决策单调性，并重复感叹题目质量。此时已封榜，看到 T9，感觉很有流的意思。然后惊恐地发现昨天没有准备 dinic 代码块，被迫手敲一遍。随便二分一下，集合划分建个图就过了，还有几分钟，不想看 T10，遂摆之。
发现过 $9$ 题有小星星组打铜的风险。这必须得怪 T5，T6 的巨大耗时。
下午随便听了会儿报告，打了会儿 gen。
晚上正片开始，OI 生涯第一次观看滚榜。rk $92\to 34$，表演一个封榜后狂切两题。最终被滚到了 $49$。非常恼火，这下真要打铜了。
科目三，戏剧性的。
没有打铜，戏剧性的。
怎么打银了，怎么 qjm，tyx 也打银了，银银怪，嘤嘤嘤。
hgh $10$ 题打金了，即将获得巨额奖金。
正片开始，人类历史上第一次正式赛颁发铁奖，见证历史！打铁环节，震惊我 2023 一整年。
抽奖，最后一秒被滚下去了，特别恼火。
Day 2 (2024.01.01)
参观百度大厦，听百度吹。送了个小礼品，有趣。
题解
A
给一个 $n\times m$ 网格，其中有一个 S 和若干个障碍 '#'。要求选一个矩形使得边框上没有障碍但有一个 S。$n,m\le 3000$，旋转网格得到四种情况分别求解，每种情况只考虑 S 在矩形上边框。对于每个位置维护处向右和向下最多的延伸距离，使用 ST 表维护 S 所在行的向下延伸长度。即可枚举左下角，统计是否合法。
B
有 $n\le 5000$ 个颜色，一个时间段 $[S,T]\subseteq [0,10^9]$，$m\le 10^6$ 个限制每个为颜色 $x$，在 $[l,r]$ 不能被选中，且限制区间不交。求每个时间点都选一个颜色的方案数。首先离散化，记录每个左闭右开区间，对其离线区间修改即可简单统计。
C
给一棵大小为 $n\le 10^5$ 树，要求维护在子树 $v$ 内每一个点 $u$ 的权值加上 $a^{d+dist(u,v)}$，其中 $a$ 是常数，$d$ 是每次修改给定的值。并支持查询单点权值。不难有 $a^{d+dist(u,v)}=a^{dep_u}a^{d-dep_v}$，这样只要子树加后半部分的值即可。树状数组 + dfs 序。
D
$n\le 1000$ 个点，给定每个点的后继转移，问从多少个点出发可以终止而不成环。签到题，数据范围可以暴力跳，不难发现如果能终止一定会在 $n$ 步内完成。
E
给定了一个序列 $a_{1\cdots n}$，其中 $a_i \in [0,n-1]$。定义一种树为好的，当且仅当 $\forall dep_i\le a_i$，两种树不同的，当树的形态不同，或者一个点的儿子排列的顺序不同。这是我过的题中最有思维的一题。首先需要考虑对一层进行 DP，可以从上往下，或从下往上 DP。我的做法是先前缀和 $p_i$ 为 $\sum_j{[a_j\le i]}$，从上往下，$f_{i,s,x}$ 为考虑到前 $i$ 层，已经用了 $s$ 个点，第 $i$ 层有 $x$ 个点。转移时，枚举下一层的点数 $y$，有 $f_{i+1,s+y,y} += A^{s+y-p_i}{p{i+1}-p_i}\binom{y+x-1}{x-1}f_{i,s,x}$，其中排列数为新增可以确定的点的位置贡献的系数，组合数为无标号的树计数，插板法分配父节点。处理到每一层都统计一次答案即可。
F
给一个无向图 $n\le 100$，可能有重边自环，询问不超过 $20$ 次， $u$ 到 $v$ 间长度恰好为 $k\le 10^9$ 的路径的边权和的最大值和最小值。正解是矩阵快速幂板子题，但是我没想到。意识到 $k$ 很大，中间很长一段一定是反复走一个子环或者往返一条边时，就可做了。$f_{i,j,k}$ 表示长度为 $i$ 的 $(u,v)$ 路径的极值。询问时枚举中转点 $k$。$(u,k)$ 和 $(k,v)$ 的部分可以一次背包求出。假设 $x$ 为在中转点徘徊的长度，若 $x$ 为奇数则必须是自环，否则可以是往返某条边。
G
有 $A,B,C$ 初始值都为 $100$，有 $q$ 次询问给定 $D$，需要求 $A\cdot B\cdot (C-D)$ 的最大值。有 $n\le 3000$ 种商品，费用为 $c_i$，能提供的总费用为 $m\le 3000$。效果为将给定的 $t_i\in{A,B,C}$ 增加 $w_i$。数据范围很有 $O(nm)$ 的感觉，莫名想到皮配，多线程背包和背包合并。对于 $A,B,C$ 分别处理花费不超过 $c_i$ 代价所能取得的最大值，对 $A,B$ 进行合并，有花费不超过 $c_i$ 代价能取得 $A\cdot B$ 的最大值。这样每次询问可以枚举花费在 $C$ 上的代价。注意到决策单调性，即 $D$ 增加，$C$ 一定不会减小。分治 DP。这样总复杂度就可以 $O(m(n+\log{q}))$。
H
有 $n\le 2\times 10^5$ 个集合，集合总大小不超过 $2\times 10^5$，每次给定 $(x,y)$，询问期望意义下随机抽多少次集合可以抽到同时包含 $(x,y)$ 的，若不可以则输出 $-1$。首先若同时包含 $(x,y)$ 的集合数为 $x$，则答案为 $\frac{n}{x}$。转为计数题。这个题简直典中典快把根号分治写在题面上了。记一个分治阈值为 $B$，钦定 $(x,y)$ 中出现次数多的数为 $x$，若 $c_x \ge B$，符合条件的 $x$ 不超过 $\frac{n}{B}$ 个，对每个都可以 $O(n)$ 预处理。若 $c_x \lt B$，可以对每个点都处理出出现过的按照顺序的集合编号，双指针查找重复。总复杂度为 $O(\frac{n^2}{B}+nB)$，$B$ 取根号就有 $O(n\sqrt{n})$。
I
有一张图有 $n\le 500$ 个点，每个点是一个银行，有 $a_i,b_i,c_i,d_i$ 四个参数。警察局有 $p$ 个警力。小偷决定只偷一个点，若点 $i$ 驻防了 $x$ 个警力，有以下三种情况。
- $x\le a_i$，小偷可以偷走 $c_i+d_i$。
- $a_i\lt x \lt b_i$，若所有 $i$ 的邻点 $u$ 的驻防 $x_u$ 都不小于 $a_u$，小偷可以偷走 $d_i$。
- $x\ge b_i$，小偷不可以偷。
求出小偷能偷的最大值。警方保证损失小于 $x$ 所需要的警力 $f(x)$ 单调。考虑二分这个 $mid$。处理每个点有三种情况。
- $d_i \ge mid$，驻防 $a_i$，或者驻防 $b_i$。
- $d_i \lt mid,c_i+d_i \ge mid$，一定驻防 $a_i$。
- $c_i+d_i\lt mid$，驻防 $a_i$，或者驻防 $0$。
建模最小割，两种驻防方案，第一种表示和 $S$ 连通的代价，第二种表示和 $T$ 连通的代价。那么第一种情况的点若与 $S$ 连通，则相邻第三种点一定不能与 $T$ 连通。这是典型的集合划分模型。比较最小割和 $p$ 的大小关系即可。
J
过了这个就能拿奖金了/fn
K
我太逊了。
L
我太逊了。
