记录一下高三的日子。
Day0
打了一天的板子。吃完晚饭后去杭州，给我校所有选手都买了瓶饮料希望能攒 RP。
Day1
晚上被室友呼噜吵醒了，响得要死根本睡不着。
早上醒来肚子痛，在酒店上了一次厕所，进考场前又上了一次，debuff 拉满了。
考场左前方是 lhx。
开考先把三个题都看了一遍，T2 看起来是个什么比较暴力的数据结构，T3 感觉不太可做。
T1 稍微玩了一会就会了，很快写完过掉样例，只用了半个小时。
然后做 T2，仔细读了一遍题，发现图没有任何性质（甚至没看到 u<vu < vu<v），那复杂度至少是 O(nmw)O(\frac{nm}{w})O(wnm) 了，毛猜猜是什么四毛子状物。想到了一些传递闭包的神秘剖分之类的东西，可以在图上加点维护传递闭包，然后就要维护每个时刻的信息进行查询。尝试了一下，发现首先块长只能取很小而且没办法方便修改，然后尝试改进做法，搞了一会发现可以对每个块二分出 aaa 在范围内的集合，然后再二分出答案，这样块长就可以开到 www 了，修改直接暴力重构两个块，复杂度是 O(nqwlogw)O(\frac{nq}{w}\log w)O(w...
为啥这玩意没在 OI 中普及啊？
Description
有 nnn 种物品，第 iii 种物品的重量为 wiw_iwi，价值为 viv_ivi，一共有 cic_ici 个，求在总重量不超过 mmm 时的价值之和最大是多少。
形式化地，求：
max∑i=1nxivis.t.{∀1≤i≤n,xi∈Z∧0≤xi≤ci∑i=1nxiwi≤m\max \sum\limits_{i = 1}^n x_i v_i \\
\text{s.t.}
\begin{cases}
\forall 1 \le i \le n, x_i \in \mathbb{Z} \land 0 \le x_i \le c_i \\
\sum_{i = 1}^n x_i w_i \le m
\end{cases}
maxi=1∑nxivis.t.{∀1≤i≤n,xi∈Z∧0≤xi≤ci∑i=1nxiwi≤m
其中 1≤wi≤W1 \le w_i \le W1≤wi≤W
我们有一个 O(nlogn+W3logW)O(n \log n + W^3 \log W)O(nlogn+W3lo...
PKUWC
Day 1
早上 7:40 起床，爽睡了。
路上 wc 跟我说只有我没到了，仔细一问原来我听错集合时间了，这下爆蛋了。最后迟了大概 7 分钟才到。
报道完在边上随机游走，cyf 带着 zxx 来和 zyz 面基，我在旁边有点尴尬就偷偷润了。
在报道厅里面到了那老师和 Meatherm。还收到了 Mea 的徽章。大家都好帅啊。
开幕式没啥好说的。午饭还行，不是绍一食堂承包，应该没有卫生问题。
吃完饭回报告厅开了一会 Phigros，然后背了下板子，没记住。
进考场试机，配了下 VSCode。看眼试机题，怎么是我玉玉症题，skip。第二题不会做，懒得想了，默写了一下 NTT。
开始之后先看 T1，感觉不太会做。看眼 T2，数据结构。再看 T3，看着好眼熟，但是没啥想法。
继续做 T1，没啥想法，先猜了个 a>b+1a > b + 1a>b+1 的结论，交上去发现假了，有点急。仔细想了一下，发现本质上是构造一个 a+ba + ba+b 个点的图使得最大独立集只有 a−1a - 1a−1。
这数据范围铁 O(T(a+b)+(a+b)2)O(T(a + ...