D Mi Re Do Si La? So Fa! 题意：给定串 SSS，询问其每个子串的完整循环节长度和。例如串 aaaa的完整循环节长度有 1,2,41,2,41,2,4 三种。∣S∣≤1×106|S| \leq 1\times 10^6∣S∣≤1×106。 解法：显然每个子串 S[l,r]S[l,r]S[l,r] 都有长度为 r−l+1r-l+1r−l+1 的循环节。考虑循环节长度不为子串本身的循环节长度：  其中红色块代表长度为 kkk 的循环节，那么如果串中存在子串有长度为 kkk 的完整循环节，那么对于该串覆盖的任意的分段点（如上图中的 ik,(i+1)k,(i+2)kik,(i+1...

B Fall Guys-Perfect Match 题意：给定 n×nn \times nn×n 的棋盘，每个格子有一个颜色 ai,ja_{i,j}ai,j​，保证每种颜色出现次数不超过 202020 次。问站在哪个格子，到达任意一个格子的曼哈顿距离的最大值最小。n≤1×103n \leq 1\times 10^3n≤1×103，颜色数目 m≤n2m \leq n^2m≤n2。 解法：最大值最小，考虑二分答案。首先将曼哈顿距离 ∣x∣+∣y∣|x|+|y|∣x∣+∣y∣ 转化为切比雪夫距离 max⁡(∣x∣,∣y∣)\max(|x|,|y|)max(∣x∣,∣y∣)，则二分一个切比雪夫距离 d...

C Cmostp 题意：给定字符串 SSS，qqq 次询问 SSS 的全部本质不同子串中有多少个子串的右端点落入 [l,r][l,r][l,r] 中的。 ∣S∣,q≤5×105|S|,q \leq 5\times 10^5∣S∣,q≤5×105。 解法：显然在 SAM 上可以将前缀 [1,i][1,i][1,i] 对应节点在扩展的时候找到，记该节点为 did_idi​。同时每个节点对应了 lll 个本质不同子串。那么问题转化为，∀k∈[l,r]\forall k \in [l,r]∀k∈[l,r]，dkd_kdk​ 到根节点的全部链的并上节点的 lll 之和。这是由于 dkd_kdk​ 对应的...

E Everyone is bot 题意：nnn 个人打算复读。一次复读的过程如下，每一轮，nnn 个人按照编号从小到大依次执行以下操作：如果这个人在前几轮已经进行过复读，他不会再次复读，否则他可以选择复读。如果某一轮没有人进行复读，那么复读的过程结束。 结束后选择复读的倒数第 ppp 个人会扣分，而其他的人会得分（第 iii 个人若为第 jjj 个复读的，则会获得 ai,j>0a_{i,j}>0ai,j​>0 的分数）。每个人最大化得分，问最终每个人的分数。1≤p≤n≤1×1031 \leq p \leq n \leq 1\times 10^31≤p≤n≤1×103。 解法...

J Jellyfish and its dream 题意：给定长度为 nnn 的环形序列 a0,a1,⋯ ,an−1a_0,a_1,\cdots,a_{n-1}a0​,a1​,⋯,an−1​，仅由 0,1,20,1,20,1,2 构成。若 ai+1≡ai mod n+1(mod3)a_i+1 \equiv a_{i \bmod n+1} \pmod 3ai​+1≡aimodn+1​(mod3)，则令 ai←(ai+1) mod 3a_i \leftarrow (a_i+1) \bmod 3ai​←(ai​+1)mod3。问能否经过若干次操作使得 a0=a1=⋯=an−1a_0=a_1=\cdo...

G Good red-string 题意：给定一个长度为 nnn 的串，仅由 r，e，d，?构成。问能够找到一种将全部的 ?转化为 r，e，d中的一种字符，使得最后的串由 n3\dfrac{n}{3}3n​ 个不相交的 red子序列构成。例如 reredd符合条件而 rederd不符合条件。保证 nnn 为三的倍数，n≤3×105n \leq 3\times 10^5n≤3×105。 解法：考虑对 e的约束条件：每一个 d前必须至少有一个 e；每一个 r后面至少有一个 e。因而仅针对这两条关系，可以用栈去安排出刚需的问号转化方法。对于剩下的问号，则从左到右的尽可能安排 red即可。最后检查一下...

B Bustling City 题意：给定一个 nnn 个点 nnn 条边的有向图，第 iii 个点恰有一条出边指向 aia_iai​。在每个点上恰有一个商人，一个时刻位于点 iii 处的商人会走到 aia_iai​ 号节点，问每个节点第一次有 kkk 个商人同时在该点的时间。n,k≤1×106n,k \leq 1\times 10^6n,k≤1×106。 解法：将图分成若干个连通块，每个连通块由一个环和树根在环上的内向树构成。首先考虑树上的点的答案（排除树根），对于节点 uuu，可以根据它的最大子树深度 hhh 得到一个长度为 hhh 的数组 fuf_ufu​，第 xxx 位表示第 xxx ...

L Lndjy and the mex 题意：给定长度为 nnn 的序列 {ai}\{a_i\}{ai​}，满足 ∑ai=n\sum a_i=n∑ai​=n。问由 a0a_0a0​ 个 000，a1a_1a1​ 个 111，……，ana_nan​ 个 nnn 构成的全部 n!∏i=0nai!\displaystyle \dfrac{n!}{\prod_{i=0}^n a_i!}∏i=0n​ai​!n!​ 个序列中，每个序列的全部连续子序列的 mex\rm mexmex 值之和。n≤1×105n \leq 1\times 10^5n≤1×105。 解法：显然直接求 mex\rm mexmex 是...

K Killer Sajin's Matrix 题意：给定 n×mn\times mn×m 的矩阵，要求在其中填入 kkk 个 111 使得每行每列 111 的个数均为奇数。输出一个合法方案或者报告无解。n,m,k≤1×105n,m,k \leq 1\times 10^5n,m,k≤1×105。 解法：（感谢 Oscar 提供的做法） 显然通过不断的交换列与行可以使得所有的 111 都安放在斜对角的矩阵中，且每行每列必然至少有一个 111，如下图的形态：  设每个满 111 矩阵的长和宽分别为 xi,yix_i,y_ixi​,yi​，则有 ∑xi=n\sum x_i=n∑xi​=n，∑yi=m...

K NIO's OAuth2 Server 题意：有 kkk 个元素和 nnn 个由这 kkk 个元素构成的集合 {Sn}\{S_n\}{Sn​}，问由这 kkk 个元素生成的全部 2k−12^k-12k−1 个非空集合中有多少个 TTT 集合满足 T⊆⋃k=1iSk\displaystyle T \subseteq \bigcup_{k=1}^i S_kT⊆k=1⋃i​Sk​，即由 iii 个集合能覆盖 TTT 集合，对于 i∈[1,k]i \in [1,k]i∈[1,k] 计算答案。k≤20k \leq 20k≤20，n≤1×105n \leq 1\times 10^5n≤1×105。 解...

I The Great Wall II 题意：给定长度为 nnn 的序列 {ai}\{a_i\}{ai​}，将其划分为连续的 kkk 段，每一段的花费为这一段的最大值，问 k∈[1,n]k \in [1,n]k∈[1,n] 的最小花费。n≤8×103n \leq 8\times 10^3n≤8×103。 解法：考虑 fk,if_{k,i}fk,i​ 表示前 iii 个数字分了 kkk 段的最小花费，那么朴素转移为 fk,i←k−1≤j≤i−1{fk−1,j+j+1≤l≤ial}\displaystyle f_{k,i} \leftarrow \min_{k-1\leq j \leq i-1} ...

G Magic Spells 题意：给定 kkk 个串 {Si}\{S_i\}{Si​}，问在每个串中都出现的本质不同回文子串个数。∑∣Si∣≤3×105\sum|S_i| \leq 3\times 10^5∑∣Si​∣≤3×105，k≤5k \leq 5k≤5。 解法：kkk 较小，因而可以考虑对每个串都建立一个 PAM，然后同时对 kkk 个 PAM 进行遍历，只向每个 PAM 都能扩展出来的字符出边走。整体时间复杂度 O(k∣Si∣)\mathcal O(k|S_i|)O(k∣Si​∣)。 #include <bits/stdc++.h> using namespace st...

F Matrix and GCD 题意：给定 n×mn \times mn×m 的矩阵，其中 [1,nm][1,nm][1,nm] 的数字均只出现一次，问所有的连续子矩阵的 gcd⁡\gcd gcd 之和。n,m≤1×103n,m \leq 1\times 10^3n,m≤1×103。 解法：考虑 O(nlog⁡n)\mathcal O(n \log n)O(nlogn) 的倍数枚举，统计有 fif_ifi​ 个连续子矩形其中全部的数字均是 iii 的倍数，再进行容斥，答案为 ∑i=1nmμ(i)fi\displaystyle \sum_{i=1}^{nm} \mu(i)f_ii=1∑nm​μ...

E Longest Increasing Subsequence 题意：构造一个长度不超过 100100100 的排列，使得其最长上升子序列个数恰好为 mmm 个。m≤1×109m \leq 1\times 10^9m≤1×109。 解法：为了保证 LIS 的个数，一个基础的构造是 2,1,4,3,6,5⋯ ,2n,2n−12,1,4,3,6,5\cdots,2n,2n-12,1,4,3,6,5⋯,2n,2n−1，这样可以使得 LIS 的个数为 2n2^n2n。同时此时的 LIS 序列长度为 nnn。最后添加一个最大值，作为全部 LIS 的终止。接下来考虑利用二进制拆分，如何填补更小的 2i2...