20231017-20231029训练赛简要题解

因为 Timeline 都忘了，所以弄个简要题解吧

20231017-noip-22

NOIP 三道黑

T1 rescue

设 $f_i$ 为救出来的概率为多少，得倒着做，转移复杂度 $\mathcal{O}(n^2)$。

改改状态，设 $f_{i,j}$ 为第 $i$ 天后剩余的总能力为 $j$ 时未来救出来的概率时多少，时间复杂度 $\mathcal{O}(1000n)$。

此外不能用 $1-f_i$ 表示活着的概率。

T2 dance

将 $a_i$ 从大到小处理，将影响到的区间都 $+1$，将问题转化成了第 $x$ 个版本的 $[l,r]$ 的最大值是多少，主席树即可。

T3 tree

bitset 优化构造

T4 dye

折半搜索 + 容斥 + 高位前缀和

20231018-noip-23

T1 flandre

贪心，答案为排序后的某个后缀

T2 meirin

不是数据结构题而是神仙式子转化，这里空太小我就不写了

T3 sakuya

把期望转化成概率，然后预处理一下后做树形 DP。

T4 scarlet

根号分治，需要维护区间加 $\mathcal{O}(1)$，区间和 $\mathcal{O}(\sqrt{n})$ 的序列分块，用差分维护区间加。

20231019-noip-24

T1 gcd

从大到小枚举答案，然后一边统计可整除的数，当 $\geq k$ 的时候直接输出即可。

T2 mathematics

带边权并查集板题。

T3 assemblage

直接按边权从大到小或从小到大加边，然后用一个并查集 $\mathcal{O}(1)$ 维护加边后的贡献。

T4 dedescription

转化成在平面图上用树状数组维护的问题。

20231027-noip-25

T1 gugu

设 $f_{i,j}$ 为到 $(i,j)$ 的方案数，直接 DP，到矛盾点直接跳过（不要直接 puts("0"); 了……）。

T2 bread

先把上下两行的等差数列求出来，往被修改的列的 $sum$ 加上，还有竖向的等差数列直接等差数列求和公式，最后统一做前缀和维护出来，剩下的直接暴力去填即可。

T3 substr

用一个栈在 KMP 时维护当前的 $f_i$，匹配了就把模式串都弹出来，然后栈里剩下的就是答案。

T4 excalibur

可以证明，要么只删一个奇数度的点，要么只删两个相连的均为偶数度的点，那么直接枚举每个点然后再枚举每条边即可。

T5 dance

P7298

20231028-noip-26

T1 sbt

题意说了有单调性，直接二分

T2 gft

设 $f_{i,j}$ 为前 $i$ 个格子中有 $j$ 个被染了奇数次，剩下的被染了偶数次。

时间复杂度 $\mathcal{O}(nm)$

T3 mg

主席树

T4 ball

set + 启发式合并或左偏树

20231029-noip-27

T1 array

看清题目，两边的不能交换

题中的操作相当于交换两边的差分数组，直接排序后比较是否相同即可。

T2 lis

贪心，遇到必须交换的连续段再 reverse，最大的那个直接反过来。

T3 box

预处理出每个位置最多走到哪里推不动箱子，然后两个方向的 DP 即可。

T4 subway

将问题转化成是否存在一条线路从 $x$ 中的子树出发到 $y$ 所在的子树，求出 DFS 序后转化为序列问题，主席树即可。