2019-2020 ICPC, NWRRC

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

签到题

B

利用奇函数的性质,我们对称构造一个上升序列

把3.14分成25000份等长区间,直接爆搜就行了

C

D

E

多起点BFS, 考虑是按距离分层的, 如果某个距离某个点被访问了$$K$$次, 那么他就是要求的点

F

G

H

发现可以贪心分成一段一段的

然后对于$$n$$种不同长度段数总和是调和级数$$O(n\log n)$$

然后二分每段的边界就行

I

高度可以二分, 然后因为$$45$$度角的特殊性, 所有的约束都可以变成对中心点的值域约束

判断值域是否有解即可

J

答案是唯一的

我们考虑按顺序枚举终点, 从大到小枚举起点, 对中间的方案数计数判断即可

K

贪心把$$A$$的疆域填满

然后剩下的地方可能使用某些策略会导致一些空位没填, 那么各种策略都试试直到都填完即可

L

实际上$$k$$次方子串长度就是$$\frac{LCP(x,y)+(y-x)}{y-x}$$

然后在后缀自动机的parent树上做启发式合并

M

枚举中间那个数,前面扔进map,拿后面的查一下就行