rank | solved | A | B | C | D | E | F | G | H | I | J | K | L |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
4 | 7 | O | . | O | O | . | . | O | O | O | O | Ø | . |
Type Systems 中文翻译
2020 ICPC 小米邀请赛决赛 D Rikka with New Year's Party 题解
题面
给定一个长度为 $10^5$ 的字符串,求同构意义下的本质不同子串数。
分析
考虑如何求一个串的本质不同子串数,实际上对他求一个后缀数组和 height
数组即可,进一步转化我们只要能对求出两个后缀的 LCP 长度,就能实现后缀排序。
将同构转化为距离上一次出现该字符的距离,可以发现每个后缀和整体的差别仅有 $26$ 个开始位置。
我们现在考虑如何求两个后缀的 LCP,首先两个字符的情况可以参考 2020 牛客暑期多校训练营第 1 场 A,我们将其扩展到更大字符集。
我们将这个串,用每种字符的第一次出现位置分割开来。如果两个串同构,那么这些位置必然也是一一对应相同的。
求 LCP 时,只需要一段一段考虑即可。
2020 ICPC 小米邀请赛决赛
rank | solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
54 | 9 | Ø | Ø | . | Ø | O | . | O | . | O | Ø | O | . | Ø |
2020 ICPC 小米邀请赛决赛 B Rikka with Maximum Segment Sum 题解
2020 ICPC 小米邀请赛决赛 M Rikka with Employees 题解
题面
给定一棵 $n$ 个点的有根树,初始时,每个点处于上班状态,你现在需要构造一个操作序列,使得每个点都满足一次,一个点满足当且仅当只有这个点的子树在上班,其他全在下班。
操作序列会维护一个栈结构,分为 $3$ 种操作:
点 $u$ 下班,加入栈中;
栈顶 $u$ 弹栈,$u$ 重新上班;
报告点 $u$ 处于满足状态。
其中 $2 \le n \le 10^5$,操作序列长度不超过 $9 \times 10^6$。
分析
对于一棵大小为 $n$ 的树,我们可以选择一条链(不妨选择重链),不断将外部的点删掉,可以用 $n$ 次操作,由浅到深将整条链都满足一次。之后,这条链就不在有用了,并且把树划分为一个森林,有多个等价的子问题。
思考一些暴力的做法,留下一棵树,其他入栈,对这棵树递归构造完成后(递归后满足子树所有点在栈中),需要去弹出下一个子问题的树,因为是栈结构,所以需要弹出栈顶的两棵树,再将做好的树入栈,以此类推。显然,这样一开始做的树就会被反复加入和弹出,不够优。
不妨使用哈夫曼编码以子树的大小作为频率值进行合并,在构造好的哈夫曼树上递归构造即可。由于哈夫曼编码的性质,每个点深度频率乘积的和,大约为 $O(n \log n)$ 级别,可以通过本题。
Grakn Forces 2020 题解
A Circle Coloring
每个点有 $3$ 种选择,一个点需要与前后不同,显然遍历一遍即可。
B Arrays Sum
注意到,每种数有多个并没有用,假设一共有 $n$ 种数。
考虑 $k=2$ 的时候情况,如果 $n \le 2$,那么一次操作就能完成,否则之后每次前面一部分填 $0$,然后构造下一个数。
因此 $k>2$ 也是类似的,第一步制造 $k$ 个,然后每次制造 $k-1$。
C Discrete Acceleration
直接对着题意模拟即可。
D Searchlights
注意到,被控制的区域呈现一种下降台阶的形状。于是,每个人,要么往上走,要么往右走,要么走到某个拐角处。
于是,每个人有很多种选择 $(x_j,y_j)$,表示他两个方向需要的步数。
按 $x$ 从小到大枚举,如果所有人都满足过了,在所有人 $y$ 的最小值,取最大值。
E Avoid Rainbow Cycles
注意到,对于每个集合,不需要真的搞出最大团,只要按顺序连成一条链,如果这个图有环,那么原图必有环。
因此题目要求的是,删除最小的边,使得原图没有环,也就是加入最多的树边。
做一个类似 MST 的过程即可。
F Two Different
考虑 $n=2^k$,我们可以每次将数组对半分,如果左右半边都分别被弄成了同样的数,那么我们通过左右两边一一对应,就能将整个区间弄成同一个数。
进一步,考虑 $n$ 的最高位,类似 ST 表,做两次即可。
G Clusterization Counting
给定一个无向带权完全图,每条边边权不同,求有多少种点集的划分方案,使得每个团内的所有边权小于该团所有向外的出边。
观察 Kruskal 建最小生成树的过程,每次合并两个连通块,新加入那条边的权值一定大于两个连通块内的所有边,于是我们可以合并两个连通块的 dp
值。
合并 dp
值只需要做一个类似卷积的过程即可。
特别地,如果某个连通块本身就是 $1$ 个团,那么其分成 $1$ 块的方案数 $+1$。
具体实现可以构造一棵 Kruskal 重构树,做树形背包的 dp
。
2018-2019 ICPC Northwestern European 区域赛
rank | solved | A | B | C | D | E | F | G | H | I | J | K |
---|---|---|---|---|---|---|---|---|---|---|---|---|
115 | 6 | Ø | O | Ø | Ø | O | . | O | O | O | Ø | O |
2020 ICPC Universidad Nacional de Colombia Programming Contest
rank | solved | A | B | C | D | E | F | G | H | I | J | K | L | M | N |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
13 | 11 | Ø | O | O | O | O | O | O | O | O | . | O | O | O | O |
2020 杭电多校训练第 9 场
rank | solved | A | B | C | D | E | F | G | H | I | J |
---|---|---|---|---|---|---|---|---|---|---|---|
45 | 3 | O | O | Ø | . | O | . | Ø | . | . | . |