2021年8月模拟赛简要题解·上

醉后不知天在水，满船清梦压星河

2021.08.05

A. Sign

Sign

签到题，处理每条边贡献即可

code

B. Map

Map

考场上直接大力找规律找出来了，答案是 $\dfrac{\dfrac{(n-1)^t-(-1)^t}{n}+(-1)^t}{(n-1)^t}$

实际上列个 DP 式子就能推出来

然后忘了对 n 取模挂分

code

C. Path

Path

线段树优化建图裸题

code

D. 星系探索

星系探索

ETT 题，但是因为只用换子树和子树加，只用 Splay 维护括号序也是可以的

没开 long long 挂了50

code

2021.08.09

A. 龙妹妹喝牛奶

龙妹妹喝牛奶

单独考虑每个点被选上的概率是 $1-(1-\dfrac{(2x(n-x+1)-1)\times(2y(m-y)-1)}{n^2m^2})^k$

code

B.枯法者训练

枯法者训练

同余最短路板子，选定一个 mod ，把别的数字表示成 $x\times mod+r$ 的形式然后跑模意义下每个 $r$ 需要多少个 $mod$

选择最小的 $a_i$ 使得点数最少

code

C. 没名字

没名字

EX 的推柿子题

忽略掉解直线方程的部分 其实是我忘了而且懒得再推了

最后要找到 $Ax^2+By^2+Cx+Dy+Exy$ 的最小值，并且系数可以 $O(1)$ 维护

先对一个变量求偏导，接出来之后带入进去，就能得到一个一元二次函数，找到极值即可

不能直接解俩偏导是因为分母可能为零，图像上表示为一条直线都是最小值

code

D. 线段树

线段树

$O(n^3)$ 区间DP，问就是不可能跑满 + 常数极小

code

2021.08.13

A.殖民计划

殖民计划

没改，口胡了

前一半数据点暴力 dfs ，发现后一半数据点的边数和点数接近，建出 dfs 树后对每个非树边暴力分类讨论

B. DBW的黄金

DBW的黄金

考虑 $dp_{i,j}$ 表示第 $i$ 个人进贡 $j$ 黄金的方案数，有 $dp_{i,j} = \sum dp_{i-1,k} - \sum\limits_{k|j}dp_{i-1,k}$

观察下发现如果从 $dp_{1,p}$ 开始转移，每个数字都只会被他的素因数转移到它的指数次，并且与素因子具体是什么无关

所以设 $dp_{i,S} = \sum dp_{i,j}$ j 的质因子指数集合为 S

打个表能发现这个组合不超过 $200$ 就可以 $O(200^3\log n)$ 矩阵快速幂了

取模不充分挂分

code

C. 测试数据

测试数据

因为它只会问一个点的值，我们考虑一个点能被那些修改操作影响

把询问序列按 $S \to T$ 排列，发现这一个点向上跳，碰到有交集的区间就合并，最后查询这一个大区间的 $\max$ 即可

问题在于怎么快速的向上找到这个大区间

把左右端点分别考虑，左端点只想左右，右端点同理，所以我们把区间挂在线段树上，然后查询第一个碰到的区间就是他的上一个能合并的区间，按这个关系建树，树上倍增找到最大的左右端点即可

code

D. 电车

电车

贪心的考虑下坐车的顺序一定是先快再次快然后慢

所以快车站把区间划分成了几个子区间

考虑每个子区间里能坐慢车到达的点就没必要建站了，不然会浪费距离

在第一个慢车到不了的地方建次快车站，然后按照每个区间距离目标时间剩下时间的多少，优先给剩的贪心建站即可

code

2021.08.14

A. 世界线

世界线

卡空间屑题，分成两块维护前一半和后一半的连通性就可以避免空间爆炸

code

B. 欧拉回路

欧拉回路

欧拉定理 $v-e+f=2$

计算几何把所有交点算出来去重，然后算新增的边用欧拉定理即可

code

C. 光线追踪

光线追踪

一个矩形只会有下边和左边有用，而 $x,y$ 是独立的，可以分别维护

所以只用解决一维的情况，加入一条线段其实就是把它的左端点到右端点这一段斜率的线覆盖住了，所以先把所有的斜率离散化下来然后线段树上覆盖即可

精度需要 long double，挂分

code

D. 是否

是否

原题 AGC 的 Yes or No

考虑如果 Yes 多就尽可能选 Yes 是没问题的，按照还剩下的 Yes/No 数量为坐标轴建系，我们回答的路径就是一个不断靠近 $y=x$ 的路径

所以 $\max(n,m)$ 是必然能猜到的，主要是计算 $y=x$ 上能对几个

因为有 $\dfrac{1}{2}$ 的概率猜对，所以要统计经过 $y=x$ 的路径个数，即 $\sum\limits_{i=1}^{\max(n,m)}\binom{2i}{i}\binom{n-i+m-i}{n-i}$

code

2021.08.16

A. 地中海气候

地中海气候

先把 $S$ 中最后一个拿出来，就变成了插入 - 取出的循环，思考一下就能发现要贪心取最大值，用堆的就会 $O(nk\log n)$ TLE

发现其实最大值只能不断减小，因为如果下一个拿出来的比较大，下一个人会直接取走

所以用桶维护即可（顺便这题极致卡常，1s根本不过去，std都过不去）

code

B. 东非大裂谷

东非大裂谷

显然划分的链的两端一定是最大最小值，而且一定是单调的，所以记录 $dp_{x,0/1}$ 表示当前点是最大/最小值，而且因为是单调的，所以可以用差分得到最大-最小的值

code

C. 地转偏向力

地转偏向力

数据保证边长是 $5$ 的倍数，所以可以把它划分成若干 $5 \times 5$ 的小格子，然后爆搜 $5 \times 5$ 的各种方案，拼接起来

实际上挺难写的，没写

D. k子串

k子串

考虑一个大子串的 border 如果在大子串去掉头尾后自己也去掉头尾仍然是一个 border

也就是每次缩减答案至少是 $x-2$

反过来考虑每次向大拓展答案最多是 $x+2$ 类似 height 数组的复杂度，这样最多是 $O(n)$ 的

code