省选模拟赛Ⅱ

· · 个人记录

省选模拟赛Ⅱ

一、2023.12.23

1.车辆段

30/100

调了好久，结果是 Tarjan 求 LCA 出的问题，这个坑已经在 LCA 笔记中填上。

下文 “p 合法” 表示 p 的标准分解中，每一个质数的幂次均 \le d。

设 u 和 v 是 r 的子树中的点，且 u\le v，r 的答案为 \sum_u\sum_vf(a_u)f(a_v)-\sum_u\sum_vf(a_u)f(a_v)[a_u\cdot a_v 不合法] 。所有点的前半部分直接树形 DP 就可以求出，对于后半部分，我考试时是预处理出所有 a_u\cdot a_v 不合法的 u 和 v，则它们的 LCA 到树根的路径上的点的答案要减去 f(a_u)f(a_v)，这样 d 较小就会被卡成 O(n^2)。

需要优化求后半部分的过程。现在要让 r 的答案去掉不合法值。考虑往一个空集合一个一个添加以 r 为根的子树中的点 v，要找出 a_v\cdot a_u 不合法的 f(a_u) 的和，其中 u 是已经在集合中的点。全局维护 g(i)，表示集合中的点的 a 值是 i 的倍数的 f 之和。枚举 a_v 的质因数，用容斥解决（可以一并把前半部分解决）。

但这样计算复杂度 O(n^2)，还有容斥的约 2^6 的常数。再用 dsu on tree 优化一下就可以过了。

官方题解用的莫比乌斯反演。

2.涂装

题解

由于系数矩阵比较大，矩阵乘时写 A=Mul(B,C) 可能会堆溢出，覆盖其他局部变量，函数应改为取地址，或者用全局变量计算。 不是这个原因，实际上是矩阵大小开小了。

求 A^kB，其中 A 为 n\times n 方阵，B 为一维向量，不要每次询问都先求出 A^k 再算 A^kB，复杂度为 O(Tn^3\log k)。设 A^kB=A^{2^{k_1}}A^{2^{k_2}}\dots A^{2^{k_p}}B=(A^{2^{k_1}}(A^{2^{k_2}}\dots (A^{2^{k_p}}B)\dots ))，预处理出来 A^{2^i}，利用结合律从右往左依次计算 A^{2^i}B’，复杂度 O(n^3\log k+Tn^2\log k) 。

3.Metro Walk

25/100

最终停在每个点的概率不一样，不能简单用停在某个点 u 的次数 \times a[u]\div 所有点次数之和求期望（FeSO4）。

一道需要细致讨论的树上复杂 DP。

二、2023.12.27

1.环

将左侧的点按 a 从小到大排序。每个环可以看作左侧编号最大的点、它到右侧两点的边、连接这右侧两点的链组成。一条新链看作左侧一个点分别与右侧两条链各一个端点连边形成。不妨先假设链有方向。

设 dp[i][j] 表示考虑到左侧前 i 个点，右侧前 a[i] 个点时，有向链的个数为 j（右侧单点也看作链）的方案数。

添加左侧第 i 个点，则右侧新增 a[i]-a[i-1] 个点可供选择，枚举将哪些点算进链数，方案数 dp[i][j]\gets\sum_kdp[i-1][j-k]\binom {a_i-a_{i-1}}k 。再找两条链与左侧点 i，钦定第一条链的头部、第二条链的尾部与 i 相连，链数减少一，dp[i][j]\gets dp[i][j+1]\cdot (j+1)\cdot j 。

统计以 i 为左侧编号最大的点的答案时，所求链的数量即为上方第一部分 i 未与其他点连边时的答案，并去掉 i 与右侧单点形成的二元环。最后答案除以二。

三、2023.12.29

1.波斯菊

56/100

游老师评：“我看你思路还是很靠谱，只要不写挂，应该没问题。”还真就一语成谶。

DP 漏了一个转移，用自己子树内的点把自己子树走完的情况，还包括子树内的棋子走出子树再走回来。

2.芦荀花

20/100

瞎搞：遍历给定区间里的点时，如果所在点的子树都在区间里，下一个点就直接跳到这棵子树外第一个点，否则，保存这段子树中已经选中的区间。计算答案时，如果当前点父亲被包含在某个记录的区间中，则连通块个数不变，否则增加一。

3.豆蔻花

5/100

轮廓线DP

四、2023.12.30

1.跳跃

20/100

将一只青蛙一去一回转化为两只青蛙同向跳，由于起点不确定，逆序解决即从原来的终点开始往回跳。设 dp[i][j][k] 表示第一只青蛙在位置 i，第二只在位置 j，第二只比第一只多跳 k 步（k 可以为负）时的权值。

考虑优化。规定 |i-j|\le B（|i-j|>B 的状态一定能转化到 |i-j|\le B 的状态）。从位置 i 开始以某种方案跳一确定的距离，设 Ax+By=s，若要以另一方案跳同样的距离 Ax'+By'=s,x'\not=x，由于 x'=x+k\cdot\frac Bd,y'=y-k\cdot\frac Ad,d=\gcd(A,B)，需要将原方案的 \frac Bd 个 A 换成 \frac Ad 个 B，或反过来。可能的步数差为 O(\dfrac{\frac nA}{\frac Bd})=O(\frac {nd}{AB})。总状态数为 O(nB\frac{nd}{AB})=O(\frac {n^2d}A)，d 可以通过转化去掉。

实现时，可将后两维转化为 (x,y)，表示第二只青蛙比第一只多跳了 x 次 A，y 次 B，预处理出可行的 (x,y)，状态压缩成一维再 DP。

2.图论题

15/100

3.配对

五、2024.1.2

1.上古遗迹

20/100

没有多组区间询问的单调栈经典例题：Largest Rectangle in a Histogram。

分别求出 a_i,b_i（前者单调栈插入元素时求出，后者弹栈时求出），表示 h[i] 在 h[a_i,\dots,b_i] 中是最小值，且区间 [a_i,b_i] 不可再扩大，询问 [l,r] 中的答案就是 \max_{i=l}^r((\min(r,b_i)-\max(l,a_i)+1)h[i])。

详解见题解。讨论 l,r,a,b 的关系，分别用树状数组或李超线段树解决。

2.吞天得手

20/100

先 dfs 出选出序列的值，再枚举每个值所取的位置，能得到 70 分。