Contest Info

practice link

Solutions

A. Packets

签到题。

B. Reach Median

签到题。

C. Equalize

签到题。

D. Valid BFS?

签到题。

E. Trips

题目大意：给你一个 \(n\) 个点的无向图，开始时没有边，有 \(m\) 次询问，每次向其中加入一条边，然后让你选出尽可能多的点，使得这些点的导出子图中，每个点的度不小于 \(k\)。

题解：倒着处理询问，每次删掉一条边后，我们都把度数小于 \(k\) 的点删掉，并把删掉点后导致度数小于 \(k\) 的点也递归地删掉。剩下的点都可以选。

F. Maximum Reduction

题目大意：给你一个数列 \(a_{1},\cdots,a_{n}\)，和 \(k\ge2\)，每次操作把数列变成 \(a'_{i}=\max_{i\le j\le i+k-1}a_{j}\)，直到数列长度小于 \(k\)。每次操作的代价为结果数列的和。求所有操作的代价和。

题解：考虑每个数的贡献，该贡献显然只和左右第一个比本数大的数的位置有关。简单计数即可。

G. A Game on Strings

题目大意：一种游戏是这样的：开始时有一个串，每次操作选取一个串，选择该串的一种字母全部删掉，随后该串被分割成若干个字符串。不能操作者输。现在给出一个串，有 \(m\) 次询问，告诉你游戏的初始串是这个串的一个子串，问先后手谁胜。

题解：首先容易想出计算 sg 值的方法，但是暴力复杂度过高。注意到所有的“关键”字符串只有每种字母分割出来的字符串，以及它们的所有前后缀，只有 \(\mathcal{O}(n\Sigma)\) 个。如果我们巧妙地安排预处理的顺序，并且维护一些前/后缀和，那么就可以在 \(\mathcal{O}(n\Sigma^{2})\) 内预处理，\(\mathcal{O}(m\Sigma)\) 内回答。

复杂度 \(\mathcal{O}(n\Sigma^{2}+m\Sigma)\)。

H. Security

串串题，要用后缀数据结构，pass