2023.8.17
今天没有失误。
硬要说有的话主要是以下两点：
-
B 题一开始根本没想过写，还是最后才稍微写了一点一眼错的结论骗了一点。
-
对自己的 C 题太过于自信了，没有想过重新写一份 cdq 的，而是一直在卡常。
然后收获有以下两点：
-
发现 huffman 编码学得不好，之前做过的原题都一点没有印象。
-
在做偏序问题的时候考虑能否把有相同量的两个维度缩成一个。
2023.8.19
T1
做太久了，一直在卡常，还好最后卡过去了，但是导致 T2 时间不够，得不偿失。
T2
一开始就感觉到了边数很多，只需要找一条哈密顿路径应该是很好找的，后面打 \(n\le 10\) 的表的时候发现 \(n=50\) 都可以轻松跑过，但是没想过竟然可以直接搜索。
后面想到了构造一个长度为 \(k\) 的串只使用 \(|a_i-a_{i+1}|\) 使得只需要处理 \(n\bmod k\) 的，但是脑子抽了没想到后面可以直接爆搜，结果就是八种余数只构造出四种，导致 \(t=1\) 的分看脸，多测全挂。
T3
没怎么看，是最大的失误，但是也从侧面反映出前两天学的东西不扎实（cdq，整体二分）。
T4
没开，甚至没打暴力，全程突出一个摆烂二字。
补题
T1
余数是一个很典型的根号分治的模型。
-
对于 \(x\le \sqrt{Size}\)，可以直接在修改的时候暴力维护，查询的时候直接输出。
-
对于 \(x> \sqrt{Size}\)，注意到如果把每个数写成 \(ax+b\) 的形式，其实只有 \(\lfloor\frac{Size}{x}\rfloor\) 个 \(a\)，相当于就是在每一段中查询最小的 \(b\)，但是同一段的 \(a\) 是确定的，所以转化为查找前驱。
现在有两种选择：
-
类似于值域分块的做法，维护每一块的后继和每一个数在块内的后继，修改时是 \(O(\sqrt{Size})\) 的，查询是 \(O(1)\) 的。
-
sqrt tree，可以直接做到 \(\sqrt{Size}\) 修改，\(O(\log\log n/\log\log\log n/1)\) 查询。
T2
注意到边数其实非常非常多，而只需要找到一条路径，则如果有解一定很多。
写完爆搜会发现相邻两个数的差不会超过 \(7\)，则直接爆搜非常快。
但是这不优雅，考虑使用同构串的方法做，比如长度为 8 的：1 6 3 8 5 2 7 4，就以这个为例。
讨论余数：
-
不用管，从 1 开始。
-
前面接上 1，从 2 开始。
-
前面接上 1 2，从 3 开始。
-
前面接上 1 2 3，从 4 开始。
-
前面接上 1 4 3 2，从 5 开始。
-
前面接上 1 4 3 2 5，从 6 开始。
-
前面接上 1 4 3 2 5 6，从 7 开始。
-
前面接上 1 4 7 2 3 6 5，从 8 开始。
T3
称 \(x_j\le x_i,y_j\le y_i\) 的两个点的关系为“\(i\) 覆盖 \(j\)”，发现点对 \((i,j)\) 产生贡献等价于 \(i\) 覆盖 \(j\) 且不存在满足 \(i\) 覆盖 \(k\) 且 \(k\) 覆盖 \(j\) 的点 \(k\)。
考虑排序的维度为 \(x\)，而在 cdq 内部做的维度为 \(y\)，用右边点当做右上的点，考虑存在所谓的 \(k\) 的情况：
-
两个左边点 \(k\) 覆盖 \(j\)，则 \(j\) 废了。
-
一左一右 \(k\) 覆盖 \(j\)（\(k\) 在右）。
考虑对于第一种情况，\(y\) 维度已经满足了，所以在加入点 \(j\) 之前，只需要把前面所有 \(x_k<x_j\) 的点 \(k\) 弹出去即可，用一个堆维护即可，并且可以实时维护一个建立在 \(y\) 上的树状数组。
对于第二种情况，考虑在计算以 \(i\) 为右上点的贡献时有一个点 \(k\) 被 \(i\) 覆盖，则假如左边一个点 \(j\) 被 \(k\) 覆盖，那 \(j\) 就不能用了，注意到 \(j\) 和 \(k\) 一定有 \(x_j<x_k\)，则只要 \(y_j<y_k\) 就不能用了，可以拿树状数组维护当前 \(x\) 坐标小于 \(x_i\) 的所有的右部点中的最大 \(y\) 值，不妨设这个值为 \(ymax\)。发现现在所有符合要求的左部点的数量相当于查询第一棵树状数组中 \((ymax,y_i]\) 的和。
总而言之这道题就以 \(O(n\log^2n)\) 的复杂度做完了（大概比单调栈好调，但是常数非常大）。
T4
因为全部为白点的做法和全部为黑点的做法完全相同，就只讨论全部变为白点的情况。
首先考虑在一条边上操作：从有边的两个点 \(u\rightarrow v\)，再从 \(v\rightarrow u\)，相当于对这两个点的颜色同时取反。
那么我们就能做两种东西了：
-
假如两个有边点颜色不同，可以把其中黑点移动到白点上。
-
假如是两个黑点，可以同时消除。
判断无解也比较简单了：
-
如果无奇环，则只需要判断黑点的数量的奇偶性即可。
-
如果有奇环，必定有解（在环上绕一圈就能把黑点的数量的值取反）。
然后基础的操作数是 \(2n\) 的（消除两个黑点需要两次操作），然后把黑点移动到一起的操作数也是 \(2n\) 的（移动一步需要两次操作，不走回头路把所有点聚在一起大概会遍历图上所有点一次），所以体感至少需要 \(4n\) 的操作。
但是在奇环上绕一圈也需要 \(n\)，所以大约是一个 \(5n\) 的东西。
其实在奇环上绕的操作并不是特别需要，可以考虑在移动过程中绕，就是 \(4n\)。
但是我不会做。
2023.8.24
打了分组赛，做了很多基础 dp 题。
牡牛牝牛
设 \(f_i\) 表示有 \(i\) 头牛，最后一头为牡牛的方案数。
则 \(f_i=\sum\limits_{j+k<i}f_j\)，用前缀和优化跑即可。
一模一样
考虑一个暴力的递推式子：\(f_{i,j}\) 表示消除第一行的前 \(i\) 各，第二行的前 \(j\) 个的方案数。发现可以这样递推：
-
\(f_{i,j}=\min(f_{i-1,j,f_{i,j-1}})+1,a_i=b_j\)
-
\(f_{i,j}=f_{i-1,j-1}+1,a_i\neq b_j\)
第二个式子可以简化为 \(f_{i,j}=f_{i-k,j-k}+k\)，而 \(a_{i-k},b_{j-k}\) 是第一个前面的相等的位置。
清洁机器
考虑机器人的数量 \(k\) 很小只有 \(10\)，可以得出一个 dp 状态：\(f_{u,x,y}\) 表示从 \(u\) 子树进入 \(x\) 个，清理完后出来 \(y\) 个的最小代价（假设这 \(x\) 个一开始就全部在 \(u\)）。
然后就是一个简单的背包了，复杂度为 \(O(nk^4)\)，跑不满，大概带个 \(\frac{1}{8}\) 的常数。
购买可乐
设 \(f_{i,j}\) 表示到第 \(i\) 个点，有 \(j\) 箱可乐的最小代价（不在第 \(i\) 个点购买），容易发现 \(f_{i,j}=\min\{f_{i-1,j-k}+(x_i-x_{i-1})j+C_{i-1}k\}\left(0\le k\le \min\left(F_{i-1},j\right)\right)\)，于是就有了一个 \(O(nk^2)\) 的暴力东西，然而是可以单调队列优化的就 \(O(nk)\) 了。
树上染色
树上背包的板子题。
送披萨饼
考虑一个区间 dp 的做法，和关路灯那道题类似：\(f_{l,r,cnt,0/1}\) 表示 已经处理（包括送和不送）过 \(l\sim r\) 的客户，现在呆在 \(l/r\)，还打算送 \(cnt\) 个客户的最大值（注意其实这里是倒推）。
最佳团体
首先有两条比较显然的处理方式：二分答案和分数规划。
假设当前有 \(ans=\frac{\sum p}{\sum s}\) 即 \((\sum s)ans=\sum p\)，事实上现在相当于一个平均值，假如对于每个单个的人的性价比都是相等的，则 \(s_ians=p_i,ans=p_i/s_i\)，现在套用刚才的二分答案，就定义一个数组 \(c_i=p_i/s_i-mid\)，我们的判定条件为 \(\sum c_i>0\)。
加法游戏
考虑将两个人的操作看作一种，即一个人做了 \(2t\) 次操作。这样看的话，就是一个简单的 dp 了。
赛道修建
考虑首先二分这个长度，然后考虑如何让长度大于等于 \(mid\) 的链尽量多。
考虑一个点要么与它的两个儿子合为一条链，要么继承它的一个儿子传到父亲那里，显然如果放弃儿子一条能够自己贡献的链而传给父亲肯定是不优的，那么先用儿子贪心再跑出一条不影响儿子匹配数的最长链传给父亲。
木棍分割
首先考虑二分出这个最大的最小长度，这个的判定就贪心地一直接在当前段的后面，一旦大于 \(mid\) 了就立刻换下一段，正确性显然。
其次，当二分出长度之后，考虑设状态 \(f_{i,j}\) 表示前 \(i\) 根分成 \(j\) 段的答案，有 \(f_{i,j}=\sum f_{k,j-1}(sum_{k+1,i}\le len)\)。这个可以用单调队列优化。
2023.8.26
可以说最大的失误在于前面 \(1.5h\) 浪费在 T1 上，间接导致 T2 没有时间检查挂了 \(70\)。
幂次分数和
看看样例会发现求的方案数是组合。\(f_{i,j}\) 表示的是用 \(i\) 个数组成 \(j\) 的方案数，有 \(f_{i,j}=f_{i-1,j}+f_{i,2j}\)，如果选择了 \(1\) 就是 \(f_{i-1,j}\)，但是如果不选那么以后都不能选了（因为是组合），所以考虑给后面所有数都乘个 \(2\)，就是 \(f_{i,2j}\)。
二叉索引树
\(cost(l,r)=calc(l-1,r)=sum1(l)+sum1(r)-sum1(premax(l,r))\)。
数位变化
不太会。
布置教室
对于任意一个班，先按照身高从小到大排序，发现一定是 \(1\) 和 \(2\) 一组，\(3\) 和 \(4\) 一组，\(2n-1\) 和 \(2n\) 一组。
考虑先把被另一种课桌区间包含的课桌去掉，然后排序就能满足当左端点单调的时候右端点也单调。
那么对于一种课桌的选择，我们对于任意的班级都会保持不变的安排顺序，即单调递增。
现在已经得到了单调性直接整体二分即可。
2023.9.2
边陲防务
首先考虑计算出距离每个点最近的关键点 \(f_u\)，那么考虑求关键点 \(x\) 和关键点 \(y\) 的最短路上一定有两个有边相连的点满足 \(f_u\neq f_v\)，所以考虑枚举每一条边，更新答案。
复杂度是 \(O(m\log n)\)。
路径异或
这种套路题一般都是统计一下从子树到根的各种链然后算一下非直链的贡献和直链的贡献。
但是直接弄不好做，发现操作是异或就二进制拆分。
可变地图
动态 dp 板子。
连边游戏
考虑下图的链接方式：