QD MX 模拟赛记录

题目列表

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。

一会补。