模拟赛

· · 个人记录

3.14

CF1303D Fill The Bag

按⼆进制位从⼩到⼤贪⼼

CF1299C Water Balance

可以发现每一段的平均数是递增的，考虑用 单调栈 维护

首先，我们把序列中的每个数都看成一个长度为 1 的区间，然后从左往右弹入栈中。任意时刻如果将要弹入栈中区间的平均值不大于栈顶区间的平均值，就将栈顶区间弹出，与将要弹入的区间合并。这就保证了最后每个大区间的平均值是单调不降的

CF1304F2 Animal Observation (hard version)

不难写出一个 O(nmk) 的 dp，可以用线段树优化至 O(nm\log m)

CF1305G Kuroni and Antihype

建⼀个权值为 0 的点，并且默认⼀开始已经染⾊。

如果把所有按位与为 0 的点连边，边权为点权之和（因为按位与为 0，所以和就是按位或）。那么其实就是求⼀棵生成树，并且最后的答案是生成树边权之和减去 \sum a_i。所以就是求⼀棵最大生成树

从⼤到⼩枚举边权和 x，枚举 x 的⼦集 i，把点权为 i 和 x\oplus i 的点缩点并计算贡献。复杂度为 O(3^{18}\alpha(n))

3.16

P6148 USACO20FEB Swapity Swapity Swap S

预处理出 2^k 次操作的结果，快速幂即可

CF508E Arthur and Brackets

按题意模拟（贪心）

CF1284E New Year and Castle Construction

枚举 p，其余点按 p 极角排序（需要用向量叉积代替极角以避免精度问题）

题解

CF1303F Number of Components

我们发现新产生的连通块用并查集就可以求了，但是因为每次操作会把原先的连通块分裂，这部分很难算，因为并查集不能分裂，只能合并。

其实我们 倒着做撤销修改操作，原本的分裂就变成合并了，就可以用合并的方式求分裂的数量了

3.20

CF1566E Buds Re-hanging

进行一次将一个 bud 截下来再挂到一个叶子节点的操作后，总叶子节点数不变或 -1。既然不会增加，考虑先把尽可能多的 buds 取下来再合并

设最后有 x 块（包括根节点那块），合并一次会减少一个叶子节点，则答案为 tot-x+1

CF1566F Points Movement

首先去掉多余的部分：区间中已经存在一个点的区间，包含某一个区间的区间。剩下的部分就是一段点，一段区间，并且这些区间的左右端点一定都是单调递增的

我们再来思考一下一个点的行动轨迹是什么样的，不难发现无非以下两种：先向左走一段然后掉头走到它原来的位置的左侧，或者先向右走一段然后掉头。我们考虑以此为状态设计 dp

设 dp[i][0/1] 表示第 i 个点最终向左/向右走，前 i 个点的总路程。对于每一个点向右走的部分，可以将其 代价延后计算

dp[i][0]=\min(dp[i-1][0]+l_1\times 2,dp[i][1]+l_1)+l_2 dp[i][1]=\min(dp[i-1][0]+l_1\times 2,dp[i][1]+l_1)+l_2\times 2

3.21

CF1286B Numbers on Tree

随便构造

CF1303E Erase Subsequences

枚举 t 的分割点。然后设 dp(i,j) 表示如果取了第一次要取的前 i 个字符，第二次要取的前 j 个字符，至少需要 s 多长的前缀，然后根据最终状态判一下就可以了

CF1305F Kuroni and the Punishment

首先可以发现操作次数最多是 n，可以推出必有 一半及以上的元素 不变、加

1$ 或减 $1

所以我们在序列中随机找一个数 50 次，钦定它不变、加 1 或减 1，在它的因数中找答案即可

CF1307F Cow and Vacation

如果两个休息站距离 \le k，那么之间可以任意走动。所以我们知道每个休息站的控制范围是 k/2。因为 k/2 为奇数很麻烦，我们就在每条边中间加⼀个点，题目的 k 就变成 2k，控制半径变为 k。

我们把所有休息站放进队列， 扩展 k 距离。用 并查集 维护每个点属于哪个休息站，如果⼀个点属于多个休息站，那么两个休息站可以合并。

对于每个询问，先判断两个点距离是否 \le 2k（用倍增求 LCA）。否则让两个点各自往对方走 k 步(也是用倍增走，注意要判断是否越过了 LCA)，然后判断这两个点是否在并查集⾥属于同⼀个集合。 因为走 k 步如果走到某个休息站的控制范围了，那么肯定可以走到那个休息站。

3.22

CF1606D Red-Blue Matrix

先给每一行按照第一个数从小到大 排序，枚举行列的切割点，先预处理出四个方格的最值，即可 O(1) 比较

CF1606E Arena

设 f(i,j) 表示当前场上还有 i 个人，其中最大血量为 j 时，最后场上没有赢家的方案数

若 i-1\ge j，f(i,j)=j^i-(j-1)^i

若 i-1<j，f(i,j)=\sum\binom{i}{k}f(k,j-(i-1))\times (i-1)^{i-k}

CF1606F Tree Queries

首先注意到答案一定非负，那么对于一个 k 的 m 最大是 \dfrac{n}{k} 的，于是我们不妨考虑 根号分治

若 k\le \sqrt n，设 f_{i,j} 表示节点 i 在 k=j 时的答案，复杂度 O(n\sqrt n)

若 k>\sqrt n，一定有 m\le \sqrt n，记 g(i,h) 表示 i 子树里删 j 个点的最大儿子数，复杂度 O(n\sqrt n)

3.23

1-Trees and Queries

分类讨论

CF1296E2 String Coloring (hard version)

要通过相邻数交换使得序列有序，每一组 逆序对 必须要交换一次，考虑 最长下降子序列

CF1307E Cow and Treats

题解

3.24

CF1594E2 Rubik's Cube Coloring (hard version)

树形 dp，只考虑指定颜色后会被影响的点即可（可以理解为建虚树）

3.27

P7150 USACO20DECStuck in a Rut S 100/100

P7888 Distinct Subsequences 15/100

P7889 Eert Tuc Knil 15/100

3.28

P8568 JRKSJ R6 func 30/100 (60)

P8576 DTOI-2 星之界 15/100 (100)

P7920 Kubic Permutation 0/100 (35)

3.29

P7894 JROI-3 1÷0 65/100

P7877 SWTR-07 Spider Solitaire 16/100 (31/49)

P7470 NOI Online 2021 提高组 岛屿探险 35/100 (55)

第二个特殊性质可以考虑将询问变成修改，将修改变成询问