2020 杭电多校训练第 1 场

rank solved A B C D E F G H I J K L
46 6 . . . O O O . . O Ø Ø !

D

Solved by XLor (00:26:04).

讨论 $n=1,2,3$ 的情况,在 $n>3$ 时,必须是 $abc$ 循环的形式,只有 $3$ 个回文子串。

E

Solved by ytriayggg (00:53:46).

考虑斐波那契数列的通项公式,二次剩余后就是等比数列求和。

F

Solved by XLor (02:34:01, +1).

首先按度数分块,每个点在分块求 $MEX$。

具体地,更新时,如果是小点,则暴力更新每个邻居的信息,时间复杂度是 $O(\sqrt{n}T_1)$。查询时,首先枚举周围的大点更新信息,$O(\sqrt{n}T_1)$,然后使用 $O(T_2)$ 的时间查询,总体时间复杂度是 $O(q\sqrt{n}T_1+qT_2)$。

每个点的信息再进行分块,修改的时间复杂度是 $O(1)$,维护每个值的出现次数和块内个数,查询枚举所有满的块,再枚举未满的块,查询的时间复杂度是 $O(\sqrt{n})$,总体时间复杂度是 $O(q\sqrt{n})$。

I

Solved by XLor (01:52:29, +1).

给了很多对称轴在 $y$ 轴上的二次函数,对顶点位置从上到下排序。最上面的开口最小的先获得第一,然后是底下开口更大的,但是可能会存在底下的把上面的覆盖掉。使用单调栈,维护开口大小(加速度)和成为第一的区间。

J

UnSolved by ytriayggg (+5).

K

UpSolved by XLor.

观察到答案就是对每个前缀求最后面的 Lyndon Word。对原串做一次 Lyndon 分解,对每个 Lyndon Word 计算答案,显然这个区间内的每个位置的答案只会在区间内。进一步考虑 Lyndon Word 的结构,是一个 Lyndon Word 循环多次之后接上其前缀接了一个更大的字符,对于位置 $i$,如果 $j$ 位置是答案,那么 $j$ 要么是 Lyndon Word 本身,要么就是 Lyndon Word 的前缀正好同时覆盖了 $[j \dots i]$。

L

UnSolved by XLor.