FUN WORLD

Statement nnn 个灯笼排成一排，第 iii 个灯笼具有 pip_ipi​​ 的亮度。每个灯笼要么朝向左，照亮左边编号为 [i−pi​,i−1][i − p_i​, i − 1][i−pi​​,i−1] 的灯笼；要么朝向右，照亮右边编号为 [i+1,i+pi​][i + 1, i + p_i​][i+1,i+pi​​] 的灯笼。 请你为所有的灯笼确定朝向，使得每一个灯笼至少被另外一个灯笼照亮，或判断无解。 数据范围：n≤3×105n \le 3 \times 10^5n≤3×105。 Solution 神仙 DP。 把可行性问题转化为最优性问题，设 f(i)f(i)f(i) 表示前 iii 个灯笼能覆盖的最长前缀。 转移考虑第 iii 个灯笼的朝向。如果向右，那么 f(i)={f(i−1),f(i−1)<imax⁡{f(i−1),i+pi},f(i−1)≥if(i) = \begin{cases} f(i - 1), &f(i - 1) < i \\ \max\{f(i - 1), i + p_i\}, &f(i - 1) \ge i \en ...

Statement 给你一个长度为 nnn 的序列 aia_iai​。问有多少 1∼n1 \sim n1∼n 的排列 pip_ipi​，满足 ∀i∈[2..n]\forall i \in [2.. n]∀i∈[2..n]，有 api−1×apia_{p_i − 1} \times a_{p_i}api​−1​×api​​ 不为完全平方数。答案对 109+710 ^ 9 + 7109+7 取模。 数据范围：n≤300n \le 300n≤300，1≤ai≤1091 \le a_i \le 10 ^ 91≤ai​≤109。 Solution 每个数去掉平方因子后，条件等价于没有两个相等的数相邻。 Algorithm 1 把相同的数分类，假设共 mmm 种不同的数，其中第 iii 种有 cic_ici​ 个。记 f(i,j)f(i, j)f(i,j) 表示填入前 iii 种数，有 jjj 对相同的数相邻的方案数；g(i,j)g(i, j)g(i,j) 表示将第 iii 种数拆分成块内块间均有序的 jjj 块的方案数。下面设 si=∑j=1icjs_i = \sum_{j = 1} ^ ...

Statement 有一个正 nnn 边形，顶点顺时针编号为 1∼n1\sim n1∼n。问用 n−1n-1n−1 条边连接这 nnn 个顶点，使它们连成一棵树，有多少种方法。 连边时有以下限制： 给出一个 n×nn\times nn×n 的 01 矩阵 AAA，Ai,j=1A_{i,j}=1Ai,j​=1 表示顶点 iii 和顶点 jjj 可以直接相连，而 Ai,j=0A_{i,j}=0Ai,j​=0 时则不能。保证 Ai,i=0A_{i,i}=0Ai,i​=0，Ai,j=Aj,iA_{i,j}=A_{j,i}Ai,j​=Aj,i​。 两条线段不能在顶点之外的地方相交，如不能同时连 (1,3)(1,3)(1,3) 和 (2,4)(2,4)(2,4)。 数据范围：n≤500n\le500n≤500。 Solution 计数 DP 的一般套路是要构造一个“不可划分的整体”。—— sol1 考虑区间 DP，因为如果 iii 和 jjj 有边，则 i+1∼j−1i+1\sim j-1i+1∼j−1 中不可能有连出去的边。 记 f(i,j)f(i,j)f(i,j) 表示 iii 和 ...

Statement 定义一个括号串的 000 级偏值为将该括号串修改为合法括号串需要的最小操作数。一次操作你可以在一个位置添加一个括号或删除一个位置的括号。 定义一个括号串的 iii（1≤i≤n1 \le i \le n1≤i≤n）级偏值为该串所有子串的 i−1i - 1i−1 级偏值之和。 给你一个长度为 nnn 的括号串 sss 和一个正整数 kkk，求 sss 的 kkk 级偏值。答案对 998244353998244353998244353 取模。 数据范围：1≤n,k≤1061 \le n, k \le 10 ^ 61≤n,k≤106。 Solution 下面的 kkk 在题面的基础上 −1-1−1。 将一个括号串修改为合法括号串需要的最小操作数，等于它不匹配的括号个数。 一个子串的 000 级偏值中，一个左括号有贡献，一定是没有与之匹配的右括号。右括号同理。 那么一个子串 s[l:r]s[l : r]s[l:r] 的贡献就是 (l−1+kk)⋅(n−r+kk)⋅f(s[l:r])\binom{l - 1 + k} k \cdot \binom{n - r + k} k ...

Statement 给你一个长为 nnn 的序列 aia_iai​，mmm 次询问，每次询问给出 l,rl,rl,r，求 min⁡i,j∈[l..r]∧i≠j{∣ai−aj∣}\min_{i, j \in [l.. r] \land i \ne j}\{|a_i - a_j|\} i,j∈[l..r]∧i=jmin​{∣ai​−aj​∣} 数据范围：n≤105n \le 10^5n≤105，m≤3×105m \le 3 \times 10^5m≤3×105，0≤ai≤1090 \le a_i \le 10^90≤ai​≤109。 Solution 离线询问并按右端点升序排序，在 rrr 右移的过程中维护每个 lll 的答案。每次 r−1→rr - 1 \rightarrow rr−1→r 时，要加入 ara_rar​ 和前面的数的贡献。 下面考虑 ax≥ara_x \ge a_rax​≥ar​ 的情况，ax<ara_x < a_rax​<ar​ 的情况同理。 用主席树找到 [1..r−1][1.. r - 1][1..r−1] 中最大的 xxx 满足 ax≥a ...

T1. 假期计划 枚举 B, C 就行，预处理前三大的 A / D。时间复杂度 O(nm+n2)O(nm + n^2)O(nm+n2)。 T2. 策略游戏 按照 B 中是否有正负数分讨即可。 T3. 星战 判断的条件就是每个点出度都为 111。 给每个点随机一个权值 vali\text{val}_ivali​，对于每个点 vvv 维护 sv=∑(u,v)∈Evalus_v = \sum_{(u, v) \in E} \text{val}_usv​=∑(u,v)∈E​valu​，并维护 ∑sv\sum s_v∑sv​。每次检查 ∑sv\sum s_v∑sv​ 是否等于 ∑vali\sum \text{val}_i∑vali​ 即可。 感觉不稳的话就多随几次。 T4. 数据传输 k=2k = 2k=2 的时候中途的点不会跳出 sis_isi​ 到 tit_iti​ 的链上。矩乘加速是显然的。 k=3k = 3k=3 的时候中途的点可能会跳出 sis_isi​ 到 tit_iti​ 的链上，但是可以发现出去的点一定是这条链某个点的邻居。进一步可以发现，这个点一定是链上某个点所有 ...

Statement 有 nnn 根竹子，第 iii 根初始时高度为 hih_ihi​。你需要依次进行如下操作 mmm 轮： 重复 kkk 次，从 nnn 根竹子中选出一根，将它的高度减少 ppp。若当前 hi<ph_i<phi​<p，则将 hih_ihi​ 改为 000。 对于 ∀i∈[1..n]\forall i\in[1..n]∀i∈[1..n]，将第 iii 根竹子的高度增加 aia_iai​。 请你最小化所有操作结束时，最高的竹子的高度。 数据范围：n≤105n\le10^5n≤105，m≤5000m\le5000m≤5000，k≤10k\le10k≤10。 Solution 考虑二分答案后如何 check。不好做的是 hih_ihi​ 会改成 max⁡{hi−p,0}\max\{h_i-p,0\}max{hi​−p,0}。 尝试将整个函数向上平移，函数就变成了 hi+Δh_i+\Deltahi​+Δ 出发到 mid\text{mid}mid，一路上 hih_ihi​ 均 ≥0\ge0≥0。 因为最后时刻是确定的，因此倒序考虑，变成了『有 nnn 根 ...

Statement 给你一张 nnn 个点的完全图，边 (i,j)(i,j)(i,j) 的边权是 w(i,j)w(i,j)w(i,j)。保证所有边权形成一个 1∼n(n−1)21\sim\frac{n(n-1)}21∼2n(n−1)​ 的排列。 请你对每个 k∈[1..n]k\in[1..n]k∈[1..n]，求出把 nnn 个点划分成 kkk 个点集的方案数，满足： 对于任意四个点 a,b,c,da,b,c,da,b,c,d 满足 a,b,ca,b,ca,b,c 同组但 ddd 不同组，有 w(a,b)<w(c,d)w(a,b)<w(c,d)w(a,b)<w(c,d)。 数据范围：n≤1500n\le1500n≤1500。 Solution 条件就是组内边小于组间边，也就是组内边的最大值小于组间边的最小值。 所以按边权从小到大加边，可以发现一个结论：一个连通块可以单分为一组，当且仅当这个连通块在加边的时候，变成了一个团。 因此按照 Kruskal 的过程，维护当前连通块是否是团。到这里应该可以得到指数级的 DP。 比较显然的是，合法连通块一定是 Krusk ...

T1. 排水系统 拓扑排序 + 高精。 T2. 字符串匹配 题意：给你一个长度为字符串 SSS，求对 SSS 的划分个数，使得 S=(AB)iCS=(AB)^iCS=(AB)iC，其中 (s)i(s)^i(s)i 表示将 sss 复制 iii 遍拼接，A,B,CA,B,CA,B,C 均为非空字符串。 多组数据。T≤5T\le5T≤5，∣S∣≤220|S|\le2^{20}∣S∣≤220。 枚举倍数调和级数是 O(nln⁡n+26n)O(n\ln n+26n)O(nlnn+26n) 或者 O(nln⁡nlog⁡26)O(n\ln n\log 26)O(nlnnlog26) 的。 扩展 KMP 可以做到 O(n)O(n)O(n)。 T3. 移球游戏 题意：有 n+1n+1n+1 根柱子，前 nnn 根柱子上每根有 mmm 个球。所有 n×mn\times mn×m 个球共 nnn 种颜色，每种颜色 mmm 个。 你可以对当前局面进行以下操作若干次： 将某柱子顶端的球移到另一个柱子的顶端。 最后使得将相同颜色的球最后全部放置在相同柱子上。操作过程中需要满足： 原来的柱 ...

Day 1, T1. 卡牌游戏 题意：有 nnn 张牌，第 iii 张牌正面写着数字 aia_iai​，背面写着数字 bib_ibi​，初始时正面向上。请你选择 mmm 张牌翻面，使翻面后所有朝上的数字极差（最大值减最小值）最小。 m<n≤106m<n\le10^6m<n≤106，1≤ai,bi≤1091\le a_i,b_i\le10^91≤ai​,bi​≤109，保证所有 ai,bia_i,b_iai​,bi​ 互不相同，ai<ai+1a_i<a_{i+1}ai​<ai+1​。 答案一定是翻牌的一个前缀和一个后缀，即牌 1∼l1\sim l1∼l 为背面，l+1∼r−1l+1\sim r-1l+1∼r−1 为正面，r∼nr\sim nr∼n 为背面。 而且，最优解时一定不会出现 i∈[1,l],ai>bii\in[1,l],a_i>b_ii∈[1,l],ai​>bi​。同理也不会有 i∈[r,n],ai<bii\in[r,n],a_i<b_ii∈[r,n],ai​<bi​。这是因为翻前缀是要使最小值增大， ...