就是说,再来写一场
#### A - Golden Spirit
场A(-1)。
fjj写的,是个分讨题,具体细节我也不知道hhh没细想。
#### B - Labyrinth
场1A。
如果起点终点围城的矩形内没有黑洞,那就直接走。
否则一定存在一条最短路径使得经过黑洞四周的点,因此拿这些点分别做单源最短路即可。
效率: $O(168nm)$ 。
一定要看到是 $nm \le 200000$ ,不是 $n,m \le 200000$ 。
#### C - Rencontre
场A(-3)。
考虑如果已经选了三个点 $x,y,z$ ,那么最小距离相当于 $\frac{1}{2}(dis(x,y)+dis(x,z)+dis(y,z))$ 。
因此设 $f_{i,0/1/2}$ 表示 $i$ 点到 $0/1/2$ 集合内的点的距离和,换根 $\text{dp}$ 即可。效率: $O(n)$ 。
要边除边加,否则会爆 $\text{long long}$ 。
#### D - ABC Conjecture
场1A。
猜性质,只要判断 $c$ 是不是若干不同质数乘积即可。是就是 $\text{no}$ ,否则就是 $\text{yes}$ 。
因此先判掉 $1e6$ 内的质数,然后把剩下的数开方判断即可。
效率: $O(1e6T)$ 。
#### E - So Many Possibilities...
场未A。
考虑最后答案的形式,假设被砍死的人为 $j_1,j_2,...,j_k$ ,然后在第 $i_1,i_2,...,i_k$ 时刻被砍死,那么就是 $C_{i_1-1}^{a_{j_1}-1}\frac{1}{n^{i_1}}C_{i2-i1-1}^{a_{j_2}-1}\frac{1}{(n-1)^{i_2-i_1}}...C_{i_k-i_{k-1}-1}^{a_{j_k}-1}\frac{1}{(n-k+1)^{i_k-i_{k-1}}}\times$剩下的砍 $m-\sum a_{j_l}$ 砍不死的方案数 $\times k$。
于是分别做 $\text{dp}$ : $f_{i,S}$ 表示第 $i$ 轮,存活状态为 $S$ 的概率,转移就考虑砍不砍死就好了, $g_{i,S}$ 表示第 $i$ 轮,存活状态为 $S$ 的方案数。
效率: $O(2^nm^2)$ 。
#### F - Skeleton Dynamization
场未A。且不会。
#### G - Caesar Cipher
场1A。
线段树维护 $\text{hash}$ 和 $\text{max}$ ,然后如果 $\text{max}$ 达到 $65536$ 就直接暴力修改即可,这样的次数不会很多。
#### H - Message Bomb
场1A。
用 $\text{set}$ 搞搞就好了。
#### I - Sean the Cuber
场未A。不会。
#### J - Steins;Game
场未A。一定要去打表找 $\text{sg}$ 函数的规律,这样就可以做了呜呜呜。
#### K - Tree Tweaking
场未A,但是先开了这题就A了呜呜。
深度和可以看成子树大小和,而每次插入一个数,它到最后的子树大小是后继-前驱-1。
因此先把 $[1,L-1]$ 的点都插入后, $[L,R]$ 的点就会被分成几个区间,在每个区间里面做 $\text{dp}$ 就好了。
具体就是 $f_{l,r}$ 表示 $[l,r]$ 还未插入,且 $l-1,r+1$ 都插入了的最小子树和,枚举中间的一个点转移即可。
效率: $O(nlogn+(R-L)^3)$ 。
#### L - Clock Master
场1A。
可以猜到一个数要么分成若干不同质数的次幂,要么就是它本身。
然后去做背包就好了。