2020杭电多校

打星为 upsolve

Round 1

rank 524 (1/12)

棒子，我x你仙人.jpg

1004

签到

n>=3 都是 abcabacabc…

*1005

为什么你们都会二次剩余啊

考虑 fib 通项，将根号五用二次剩余化成常数

二项式定理展开，每一项等比求和

卡卡常，幂次对 MOD-1 取模

*1006

分块 好题

考虑将度数大于 \(\sqrt{n}\) 的点记作特殊点，易知特殊点最多 \(\sqrt{n}\) 个

由于其他点度数不超过 \(\sqrt(n)\) 询问直接暴力

同时维护特殊点的相邻点的权值信息，这里我用了分块来保证整体复杂度在 \(n\sqrt{n}\) 级别

修改一个点权值的时候只需要更新其相邻特殊点的信息即可，由于特殊点不超过 \(\sqrt{n}\) 个，暴力更新的复杂度也能保证

*1009

首先按 p sort一下，用单调栈筛出 a 单调递减的所有机器人

之后按照 p 递增的顺序考虑，维护一个可行的（有机会成为领先的）机器人的集合，可以发现这是一个下凸包

新加入一条线的时候，如果和最后一条直线的交点的横坐标（时间） > 最后两个直线的交点的横坐标，就踢掉最后最后一个直线

类似于维护凸包，最后栈的大小就是答案

小心维护 p a 都相等的点，即带入构建凸包，但不算答案

*1011

字符串，我的后缀自动机卡不过去

Round 2

rank 50 (6/12)

1001

按权值 sort 一下，从后往前并查集

1005

费用流，保留每个工人极值点左右 50 个点的机器，之后费用流

每次新加边增广就行，不用重新建图

1006

取个模数算一下，O(n) 验证

1007

二分答案 + dp

二分直径长度 limit，考虑 dp \(f[u][k]\) 表示 \(u\) 这颗子树选 \(k\) 个边反转时 叶子到 \(u\) 的最长路径的长度

合并时若两条路径 > limit 则不能转移，最后看 \(f[1][k]\) 是否有值

\(O(kn\log{n})\)

*1009

暴力

注意到对于每行一定经过偶数次，记录每次经过的 y 坐标，sort 后 \([y_{i}+1,y_{i+1}] (i = 0,2,4….)\) 就是这行经过的格子

然后暴力

1010

暴搜

1012

dp

观察答案为 \((r-l+1) + m - 2*lcs\)

考虑 \(f[i][j][k]\) 表示 \(S[1-i]\) 匹配长度为 \(j\) 的子序列，子序列在 \(T\) 串的结尾为 \(k\) 时子序列起点在 \(S[1-i]\) 中最靠右的位置

用前缀和做一个 \(O(n*m^2)\) 的 dp 即可