题面

给定一个长度为 $10^5$ 的字符串,求同构意义下的本质不同子串数。

分析

考虑如何求一个串的本质不同子串数,实际上对他求一个后缀数组和 height 数组即可,进一步转化我们只要能对求出两个后缀的 LCP 长度,就能实现后缀排序。

将同构转化为距离上一次出现该字符的距离,可以发现每个后缀和整体的差别仅有 $26$ 个开始位置。

我们现在考虑如何求两个后缀的 LCP,首先两个字符的情况可以参考 2020 牛客暑期多校训练营第 1 场 A,我们将其扩展到更大字符集。

aaababccabdb

我们将这个串,用每种字符的第一次出现位置分割开来。如果两个串同构,那么这些位置必然也是一一对应相同的。

求 LCP 时,只需要一段一段考虑即可。

阅读全文 »

题面

给定一个长度为 $n$ 的数组,对于所有子数组求最大子段和。

其中 $2 \le n \le 10^5$。

分析

考虑分治,也就是需要统计跨越中点 $m$ 的贡献。

注意到,跨越中点的区间的最大子段和位置,它要么完全在左半边,要么完全在右半边,要么是中点往左右延申得到的。

我们在区间 $[l,m]$ 枚举左端点的位置,可以发现右端点从左往右移动的过程中:首先是一段使用完全在左半边,然后是一段左右拼接,最后是完全在右半边。

二分出 $2$ 个边界的位置即可。

阅读全文 »

题面

给定一棵 $n$ 个点的有根树,初始时,每个点处于上班状态,你现在需要构造一个操作序列,使得每个点都满足一次,一个点满足当且仅当只有这个点的子树在上班,其他全在下班。

操作序列会维护一个栈结构,分为 $3$ 种操作:

  1. 点 $u$ 下班,加入栈中;

  2. 栈顶 $u$ 弹栈,$u$ 重新上班;

  3. 报告点 $u$ 处于满足状态。

其中 $2 \le n \le 10^5$,操作序列长度不超过 $9 \times 10^6$。

分析

对于一棵大小为 $n$ 的树,我们可以选择一条链(不妨选择重链),不断将外部的点删掉,可以用 $n$ 次操作,由浅到深将整条链都满足一次。之后,这条链就不在有用了,并且把树划分为一个森林,有多个等价的子问题。

思考一些暴力的做法,留下一棵树,其他入栈,对这棵树递归构造完成后(递归后满足子树所有点在栈中),需要去弹出下一个子问题的树,因为是栈结构,所以需要弹出栈顶的两棵树,再将做好的树入栈,以此类推。显然,这样一开始做的树就会被反复加入和弹出,不够优。

不妨使用哈夫曼编码以子树的大小作为频率值进行合并,在构造好的哈夫曼树上递归构造即可。由于哈夫曼编码的性质,每个点深度频率乘积的和,大约为 $O(n \log n)$ 级别,可以通过本题。

阅读全文 »

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

阅读全文 »