题目列表
Day2
CF1082C Multi-Subject Competition
对每个科目的人降序排序，做前缀和之后对每一列再降序排序。
不难发现这样做刚好就是答案。
P14154 [ICPC 2022 Nanjing R] 索道 / gym104128B Ropeway
和 zxh_qwq 拼起来就能过掉了。
对前缀 DP，\(f_i\) 表示选择 \(a_i\) 的最小代价，对后缀 DP，\(g_i+a_i\) 表示选择 \(a_i\) 的最小代价。
这个 DP 直接用单调队列优化即可。
不难发现每次修改都只会影响后 \(k\) 个位置，重算后 \(k\) 个位置的 \(f\) 值，和 \(g\) 拼起来就能得到答案。
QOJ7749 一个简单的 MST 问题 / gym104813D A Simple MST Problem
首先考虑 \([l,r]\) 中存在质数的情况。
不难发现只有边权为 \(\omega(x)\) 和 \(\omega(x)+1\) 的边才是有用的，直接和区间内的质数连边代价就不会超过 \(\omega(x)+1\)。
记 \(x\) 的质因数和为 \(f(x)\)，质因数乘积为 \(g(x)\)，质因数乘积为 \(v\) 的集合的点数为 \(c(v)\)。
因此按照质因数乘积从小到大考虑每个集合，将当前集合的点互相连成一个连通块，代价为 \(f(x)(c(g(x))-1)\)。
然后还需要对这个集合向外连边。若当前集合已经被之前的集合扩展得到，那么这个集合就不需要额外连接，代价增加 \(f(x)\) 即可。
否则，当前集合的一个点需要对区间内的质数连边，代价增加 \(f(x)+1\)。最后尝试从当前集合扩展得到其超集。
最后要减去质数多算的答案为 \(2\)，若 \(l=1\) 则只需要减去 \(1\)。
QOJ7746 冲啊，兔兔伯爵！ / gym104813A Go go Baron Bunny!
Ad-hoc。
还没补。
Day3
AT_abc182_e Akari
按行列把格子依照障碍物切成若干段，依次标记即可，\(H\times W\) 是不大的。
随便怎么做都可以。
QOJ7937 快速异或 (Fast XORting) / gym105465F Fast XORting
气死了，把数组大小从 \(262144\) 改成 \(262145\) 就能过了。
注意到全局异或至多进行一次，考虑先通过交换操作变换成一次异或操作能得到的形式。
不难发现异或操作是一个分组后邻项交换的形式，然后又发现左右两边是子问题，所以分别记录每一层换还是不换即可。
诶等会我这个是不是单 $\log $ 的。
QOJ7618 模式搜索
好诡异的式子啊。
考虑 \(t\) 的周期，设完整周期有 \(k\) 个，字符 \(i\) 在一个完整周期中出现 \(p_i\) 次，字符 \(i\) 在剩下的不完整周期中出现 \(q_i\) 次。
则有 \(bt_i=kp_i+q_i\)、\(p_i\ge q_i\)。\(p_i\) 和 \(q_i\) 是可以 \(O(1)\) 算的。
枚举 \(k\)，答案为 \(\max \min\limits_{i\in\Sigma} \left( \left\lfloor\dfrac{bs_i-bt_i}{p_i}\right\rfloor +1 \right)\)。
P13954 [ICPC 2023 Nanjing R] 红黑树 / QOJ7736 红黑树 / gym104821D Red Black Tree
slope trick。
一会补。