专栏文章

Codeforces Global Round 28 官方题解

eenucai
题解参与者 14已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@miqqd8df
此快照首次捕获于
2025/12/04 09:01
3 个月前
此快照最后确认于
2025/12/04 09:01
3 个月前
查看原文

A. 凯文和湖景村

  • 提示 #1
    当我们选择连续的两个 33 删除时，这个数减少了多少？
当我们将 x33y‾\overline{x33y} 变成 xy‾\overline{xy} 时（x,yx,y 均为十进制数），真实值从 10p+2⋅x+33⋅10p+y10^{p+2}\cdot x+33\cdot 10^p+y 变成了 10p⋅x+y10^p\cdot x+y，实际减少了 99⋅10p⋅x+33⋅10p99\cdot 10^p\cdot x+33\cdot 10^p，容易发现 33∣99⋅10p⋅x+33⋅10p33\mid 99\cdot 10^p\cdot x+33\cdot 10^p，因此我们可以用若干次 −33-33 操作来代替删除连续两个 33 这种操作。
所以我们只需要判断 xx 能否通过若干次 −33-33 操作变为 00 即可，即判断 x mod 33x\bmod 33 是否为零。

B. 凯文和不归林

  • 提示 #1
    如果排列足够长，最多能有多少个长度为 kk 的子区间的最小值为 11？
整个排列中，最多只有 kk 个区间能包含 11，同理，最多只有 kk 个区间包含 2,3,…2,3,\dots，我们希望最小值尽可能小的子区间数量尽可能多，因此采用如下构造：
pk=1,p2k=2,…,p⌊nk⌋⋅k=⌊nk⌋p_k=1,p_{2k}=2,\dots,p_{\lfloor{\frac{n}{k}}\rfloor\cdot k}=\left\lfloor\frac{n}{k}\right\rfloor
对于剩余的位置，可以用 ⌊nk⌋+1∼n\lfloor\frac{n}{k}\rfloor+1\sim n 的所有值任意填写。容易证明这种构造的答案最小。

C. 凯文和月亮河公园

  • 提示 #1
    是否存在一个对于所有串，都必然会被选择的子串？
  • 提示 #2
    [1,n][1,n] 必然被选择，能否确定另一个串的长度？
  • 提示 #3
    注意特殊处理全 11 串。
为了最大化两个串的异或和，肯定想要最大化异或和的二进制位数，为了最大化这个位数，[1,n][1,n] 必然被选择。假设我们选择的另一个串的首位为 11，若不为 11 可以把前导零全部删去。
找到整个串从前往后的第一个 00 的位置，我们必然想让这个位置变为 11，而且不让更前面的 11 改变为 00。因此，设第一个 00 的位置为 pp，则另一个串长度为 n−p+1n-p+1，枚举另一个串的开始位置，线性计算两个串的异或和，取最大值即可。复杂度 O(n2)O(n^2)。
若整个串全部是 11，则选择一个 [1,n][1,n]，一个 [1,1][1,1] 可以被证明是所有选择中最大的。
有趣的事实：这个题可以做到 O(n)O(n) 复杂度。具体来说，观察到另一个串需要满足：长度为 n−p+1n-p+1，第一个字符为 11，所以左端点必须 <p<p，也就是说，另一个串的前缀 11 长度可以在 [1,p−1][1,p-1] 之间任意选择。我们希望原串的第一段 00 尽可能被赋值为 11，且第一段 00 后面的那个 11 不会被修改成 00，假设原串第一段 00 的长度是 qq，则选择的另一个串的前缀 11 的长度必然为 min⁡(p−1,q)\min(p-1,q)，容易快速定位到起始位置。
在筹备比赛确定题目过程中，我们认为 O(n)O(n) 做法对于 C 题难度来说过高，因此使用了 O(n2)O(n^2) 的数据范围作为使用的题目。

D. 凯文和里奥的回忆

  • 提示 #1
    可以忽略所有 rating 低于你的参赛者，这不影响答案。
  • 提示 #2
    你是 rating 最低的参赛者，所以你能解决的问题所有人都能解决，因此你在一场比赛中的排名只与你不能解决的最简单问题有关。
  • 提示 #3
    使用贪心算法解决该问题。
阅读所有提示。先删除所有 rating 低于你的参赛者，这样你就成了 rating 最低的参赛者。此时你能解决的问题所有人都能解决，不影响你的排名，可以将这些问题的难度看作 +∞+\infty。
此时，你不能解决任何问题，因此你在一场比赛中的排名是 (1+(1+ 在这张比赛中解决至少一个问题的参赛者数量 ))，即我们只需要关注每场比赛中的最简单的问题。
预处理出对于每个问题，有多少参赛者能够解决，设为 cic_i。可以通过将参赛者 rating 和题目难度排序后使用双指针或二分算法求出 cic_i。
接下来的问题是，给定 cic_i，你需要将所有 cic_i 分为 ⌊nk⌋\lfloor\frac{n}{k}\rfloor 组，每组 kk 个，最小化每组 cic_i 最大值之和。可以使用贪心算法解决，将 cic_i 从小到大排序，对于一个 kk，答案就是 (ck+1)+(c2k+1)+…(c_k+1)+(c_{2k}+1)+\dots，暴力计算复杂度是调和级数，算上排序后即为 O(nlog⁡n+mlog⁡m)O(n\log n+m\log m)。

E. 凯文和军工厂

  • 提示 #1
    可以观察到 mm 越大条件越难以满足，尝试找到 mm 的上界。
图总共有 2nm2nm 条边，而每种颜色构成一个森林，因此对于一种颜色最多存在 2n+m−12n+m-1 条边，那么总边数一定不超过 (2n+m−1)n(2n+m-1)n。于是得到条件：(2n+m−1)n≥2nm(2n+m-1)n\ge 2nm，化简得 m≤2n−1m\le 2n-1。
接下来我们只需构造出 m=2n−1m=2n-1 的情况即可解决本题。
事实上容易构造，由于每个右部点的度数为 2n2n，且颜色总数为 nn，令每种颜色的边恰好 22 条。则对于每个颜色而言，相当于选择两个左部点使其联通（我们忽略右部点的存在），最后经过 2n−12n-1 次连接，左部点需要形成树。可以发现只需要将左部点连成链即可，构造时只需要循环移动第一个右部点的颜色。例如对 n=4,m=7n=4,m=7 的情况，形如：
CPP
1 4 4 3 3 2 2
1 1 4 4 3 3 2
2 1 1 4 4 3 3
2 2 1 1 4 4 3
3 2 2 1 1 4 4
3 3 2 2 1 1 4
4 3 3 2 2 1 1
4 4 3 3 2 2 1
因此一种简单的构造方法是对于左部点 ii 和右部点 jj，其连边的颜色为：
⌊(i+j) mod 2n2⌋+1\left\lfloor\dfrac{(i+j)\bmod 2n}2\right\rfloor+1

F. 凯文和永眠镇

  • 提示 #1
    能否找到一种策略，使得只有 nn 个区间会可能被操作。
  • 提示 #2
    每次操作整个序列，可以使答案 ≤63\le 63。
对于 bb 序列建出小根笛卡尔树，容易发现，我们只会操作这棵笛卡尔树上的区间。
  • 证明：对于一个 bxb_x，找到其左侧最后一个 bp≤bxb_p\le b_x 的 pp 与右侧第一个 bq<bxb_q<b_x 的 qq，如果我们希望区间除以 bxb_x，那么操作区间不能包含 p,qp,q 两个位置，同时区间尽可能长肯定不劣，因此必然操作 [p+1,q−1][p+1,q-1] 这个区间。而这些所有区间就是笛卡尔树上的区间。
考虑在笛卡尔树上进行 dp，令 fu,if_{u,i} 表示只考虑 uu 子树内的所有位置，进行 ii 次操作之后，区间内 axa_x 的最大值最小是多少。合并时，首先需要对他的两棵子树进行合并，设为 ls,rsls,rs，则有转移：
fu,k=min⁡i+j=k(max⁡(fls,i,frs,j,au))f_{u,k}=\min_{i+j=k}\left(\max(f_{ls,i},f_{rs,j},a_u)\right)
然后再考虑在 bub_u 这个位置的除法操作，即：
fu,k+1←⌈fu,kbu⌉f_{u,k+1}\leftarrow\left\lceil\frac{f_{u,k}}{b_u}\right\rceil
由于一直操作整个序列可以做到 log⁡2max⁡(ai)≤63\log_2\max(a_i)\le 63 次操作，因此 dp 状态的第二维只需要定义 0∼630\sim 63，这样做的复杂度是 O(nlog⁡2a)O(n\log^2 a)。
这种做法的瓶颈在于对于两棵子树 dp 状态的合并。观察发现 fu,if_{u,i} 是单调不增的，因此对于 fls,if_{ls,i} 和 frs,if_{rs,i} 做 min⁡−max⁡\min-\max 卷积等价于对于两个序列做归并排序，可以将合并做到 O(log⁡a)O(\log a) 的复杂度，最终得到一个 O(nlog⁡a)O(n\log a) 的解法。

G. 凯文和圣心医院

  • 提示 #1
    左式能小于右式吗？
  • 提示 #2
    考虑式子中取到最值的位置，它们有什么性质？
  • 提示 #3
    考虑容斥原理。
  • 提示 #4
    二项式定理。
我们假设左式中取到最值的位置为 LL，右式中为 RR。
任意找出一个 L,RL,R，记和 LL 同行和 RR 同列的位置为 PP，则有 aL≥aP≥aRa_L\ge a_P\ge a_R 即 aL≥aRa_L\ge a_R。于是只要考虑 aL=aRa_L=a_R 的情况。
考虑两边同时取到最值的位置，记作 SS，那么 SS 中的位置既是这一列的 max⁡\max，也是这一行的 min⁡\min。于是对于两个 SS 中非同行同列的位置 P,QP,Q，容易得出和 PP 同行和 QQ 同列，与和 PP 同列和 QQ 同行的两个点也都能取到最值。归纳可以得到 SS 构成了一个子矩形。
不妨枚举最值 kk 和 SS 的大小 i×ji\times j，限制是 SS 的所有行剩下的元素 ≤k\le k，所有列剩下的元素 ≥k\ge k。使用容斥原理，不难得到：
ans=∑k=1v∑i=1n∑j=1m(−1)i+j(ni)(mj)ki(m−j)(v−k+1)(n−i)jv(n−i)(m−j)ans=\sum_{k=1}^v\sum_{i=1}^n\sum_{j=1}^m(-1)^{i+j}\binom ni\binom mjk^{i(m-j)}(v-k+1)^{(n-i)j}v^{(n-i)(m-j)}
朴素计算是 O(nmv)O(nmv) 的，无法通过。考虑化简：
=∑k=1v∑i=1n(−1)i(ni)∑j=1m(−1)j(mj)(ki)m−j((v−k+1)n−i)j(vn−i)m−j=∑k=1v∑i=1n(−1)i(ni)∑j=1m(mj)(−(v−k+1)n−i)j(kivn−i)m−j=\sum_{k=1}^v\sum_{i=1}^n(-1)^i\binom ni\sum_{j=1}^m(-1)^{j}\binom mj\left(k^i\right)^{m-j}\left((v-k+1)^{n-i}\right)^j\left(v^{n-i}\right)^{m-j}\\ =\sum_{k=1}^v\sum_{i=1}^n(-1)^i\binom ni\sum_{j=1}^m\binom mj\left(-(v-k+1)^{n-i}\right)^j\left(k^iv^{n-i}\right)^{m-j}
求和符号中很像二项式定理，考虑加上 j=0j=0 的项再减掉：
=∑k=1v∑i=1n(−1)i(ni)(∑j=0m(mj)(−(v−k+1)n−i)j(kivn−i)m−j−(kivn−i)m)=∑k=1v∑i=1n(−1)i(ni)((−(v−k+1)n−i+kivn−i)m−(kivn−i)m)=\sum_{k=1}^v\sum_{i=1}^n(-1)^i\binom ni\left(\sum_{j=0}^m\binom mj\left(-(v-k+1)^{n-i}\right)^j\left(k^iv^{n-i}\right)^{m-j}-\left(k^iv^{n-i}\right)^m\right)\\ =\sum_{k=1}^v\sum_{i=1}^n(-1)^i\binom ni\left(\left(-(v-k+1)^{n-i}+k^iv^{n-i}\right)^m-\left(k^iv^{n-i}\right)^m\right)
于是我们在 O(nvlog⁡m)O(nv\log m) 的时间内解决了该题。

H. 凯文和唐人街

  • 提示 #1
    考虑如何确定是否可以生成 0101 字符串 tt 。
  • 提示 #2
    尝试设计一个只需要记录有用变量的 DP。
  • 提示 #3
    使用数据结构优化，或优化转移复杂度。
假设对 0101 串 ss 执行若干次操作后得到 0101 串 tt，不难发现 tt 中每个元素一定对应 ss 中一个子集的元素的 max⁡\max。进一步观察可以发现这个子集一定构成一段区间，不妨写下 tit_i 对应 max⁡k=lirisk\max\limits_{k=l_i}^{r_i} s_k。
初始的串 t=st=s，因而所有 li=ri=il_i=r_i=i。假设当前的串 tt 长度为 mm，对应 l,rl,r 两个序列，考虑如果在 1≤p≤m1 \le p \le m 的位置 pp 执行了一次操作，得到的新序列 t′t' 对应的 l′,r′l',r' 两个序列。那么由于 ∀1≤i<p,ti′=max⁡(ti,ti+1)\forall 1 \le i < p,t'_i=\max(t_i,t_{i+1})，∀p≤i<m,ti′=ti+1\forall p \le i < m,t'_i=t_{i+1}，可以发现 ∀1≤i<p,li′=li,ri′=ri+1\forall 1 \le i < p,l'_i=l_i,r'_i=r_{i+1}，∀p≤i<m,li′=li+1,ri′=ri+1\forall p \le i < m,l'_i=l_{i+1},r'_i=r_{i+1}。如果只关注 l,rl,r 两个序列到 l′,r′l',r' 两个序列的变化，相当于删去了 lpl_p 和 r1r_1 两个值。
因此从 ss 序列出发做 kk 次操作，能生成的序列 tt 对应的 l,rl,r 序列，一定 ll 序列是从 1∼n1 \sim n 任意删去 kk 个值，rr 序列是 k+1∼nk+1 \sim n。
现在，不妨考虑如何判定 0101 串 tt 能否被生成，将 tt 反转得到 t′t' 后，相当于目标是寻找 n≥p1>p2>...>pk≥1n \ge p_1 > p_2 > ... > p_k \ge 1 使得 ∀1≤i≤k,ti′=max⁡k=pin−i+1sk\forall 1 \le i \le k,t'_i=\max\limits_{k=p_i}^{n-i+1}s_k。一个显然正确的贪心策略是按照 i=1∼ki=1 \sim k 的顺序选择 pip_i，每次都选择最大的可行值。
现在考虑进行 DP，设 dpi,jdp_{i,j} 为有多少长度为 ii 的 0101 串 tt，使得运行上述贪心算法后 pip_i 恰好取到 jj。可以认为必定 p0=n+1p_0=n+1，边界情况是 dp0,n+1=1dp_{0,n+1}=1。考虑从 dpi−1,j→dpi,∗dp_{i-1,j} \to dp_{i,*} 的转移：
  • 如果 s[j−1,n−i+1]s[j-1,n-i+1] 已经出现了 11，那么 tt 反转后的第 ii 位必须为 11，且必然 pi=j−1p_i=j-1 ，将 dpi,j−1dp_{i,j-1} 加上 dpi−1,jdp_{i-1,j}。
  • 如果 s[j−1,n−i+1]s[j-1,n-i+1] 未出现 11，tt 反转后的第 ii 位可以为 00，如果为 00 必然取 pi=j−1p_i=j-1，还是将 dpi,j−1dp_{i,j-1} 加上 dpi−1,jdp_{i-1,j}；如果希望 tt 反转后的第 ii 位为 11，需要找到最大的 pos≤n−i+1pos \le n-i+1 使得 sposs_{pos} 为 11，然后取 pi=posp_i=pos，将 dpi,posdp_{i,pos} 加上 dpi−1,jdp_{i-1,j}。
两类转移可以看作是无论如何将 dpi,j−1dp_{i,j-1} 加上 dpi−1,jdp_{i-1,j}。然后找到最大的 pos≤n−i+1pos \le n-i+1 使得 sposs_{pos} 为 11，对所有 j−1>posj-1>pos 即 j≥pos+2j \ge pos+2 的 dpi,posdp_{i,pos} 加上 dpi,jdp_{i,j}。
可以将第一种转移视作对 DP 数组进行了整体平移，然后第二种转移是求 DP 数组一段后缀和再执行一次单点加，记录偏移量后容易使用线段树在 O(nlog⁡n)O(n \log n) 执行所有转移。
答案即是所有 1≤i≤n,1≤j≤n1 \le i \le n,1 \le j \le n 的 dpi,jdp_{i,j} 之和，使用线段树维护时当然也可以 O(1)O(1) 求出当前的 dpidp_i 的每一项之和（需要将 dpi−1,1dp_{i-1,1} 这一项平移后下标不在范围内的置零）。
由于转移有着更好的性质，实际上可以不用数据结构仅仅更巧妙地使用前缀和 O(n)O(n) 解决该问题，但这不是必要的。

I1. 凯文和红教堂（简单版本）

  • 提示 #1
    讨论最左边和最右边的字符分别是什么，然后递归构造。
引理：假设最后填出来最大值是 mxmx，不同的数的个数是 cc，记 d=c−mxd=c-mx。那么 d=0d=0 或 d=1d=1。
证明：首先显然有 c≤mx+1c\le mx+1。假设 c<mxc<mx，观察填 mxmx 的位置则容易发现矛盾。
考虑序列 ss 中最左边和最右边的字符是什么：
  • 如果分别是 L 和 R，可以发现这两个位置的数一定都是 00，而除了这两个位置一定不能填 00。对于内部的位置，无论是 L 还是 R，都会将 00 统计为一种不同的数字。因此我们可以删去这两个位置，对里面递归做，在完成后给里面的所有数字 +1+1，并在前后各加入一个 00。
  • 如果分别是 L 和 L，首先左边的 L 一定是 00，假设右边的 L 写的是 xx，容易证明里面的位置不可能填 xx。对于内部的位置，无论是 L 还是 R，都会将 00 或 xx 统计为一种不同的数字。 所以和上一种情况类似地，还是删去两端后递归做，然后给里面的数都 +1+1 再填上 00 和 xx。需要满足 xx 的值是里面的不同数的个数 +1+1。此时要求 xx 在内部不能出现过，根据引理可以发现这个条件等价于，内部整个区间满足 d=1d=1。
  • 如果分别是 R 和 R，跟上一种情况相同。
  • 如果分别是 R 和 L，可以得到一种简单的构造是全填 11。同时我们发现，在这种情况下，无论填什么数字都不会出现 00，因此这个情况只能对应 d=0d=0。
我们把原字符串每次取出首尾字符后递归构造。
分析 dd 的变化，对于 LR 情况 dd 不变，对于 LL 或 RR 要求内部 d=1d=1，对于 RL 会使整个区间 dd 变为 00。
因此，考虑最外层的 RL，其外层若包含 LL 或 RR，则无解。
否则一定有解，且容易根据上述过程构造。
复杂度 O(n)O(n)。

I2. 凯文和红教堂（困难版本）

  • 提示 #1
    只有简单版本中两侧字符为 RL 的情况需要计数，事实上 RL 这两个位置上的数一定相同。
  • 提示 #2
    不妨设 RL 这两个位置填的数是 mm，枚举最右侧填 mm 的 R 位置 xx，和最左侧填 mm 的 L 位置 yy。
  • 提示 #3
    上述情况中 x>yx>y 的情况容易解决。对于 x<yx<y 的情况，分析出其满足条件的充要条件。
  • 提示 #4
    对于最终转化后的条件，使用 bitset 或卷积来完成计数。
根据简单版本，可以发现大部分情况解的个数并不多，因为对于 LR，LL 和 RR，对于里面的部分填完后，外层只有唯一的填法。因此如果没有一层是 RL，那么答案必然是 11。
接下来考虑有 RL 的情况，不妨假设 RL 是最外部的两个字符。
可以证明的是：这个 RL 中 R 位置和 L 位置填的数是相同的。具体证明在此省略，读者自证不难。
不妨设这个相同的值为 mm。接下来，枚举最右侧填 mm 的 R 位置 xx，和最左侧填 mm 的 L 位置 yy。讨论一下 x,yx,y 的关系：
  • 若 x>yx>y，可以发现 xx 右边的 L 都需要填 mm，而 xx 右边的 R 只有唯一的填法。对 yy 同理。对这种情况计算，我们可以直接枚举 mm，然后就可以确定唯一的 x,yx,y 位置，并检查是否满足 x>yx>y。
  • 若 x<yx<y，此时 xx 左边的 R 都只能填 mm，左边的 L 是唯一的填法。对 yy 的右侧同理。再考虑 (x,y)(x,y) 中间的部分，显然 mm 必然没有在中间出现，因此我们可以删除 xx 及其左边的 R，yy 及其右边的 L（也就是删除所有值为 mm 的位置），称得到的新序列为剩余序列。删除这些字符后，我们解决剩余序列，再对得到的数全部 +1+1，然后加入所有数为 mm 的位置即可。
    以下为一个初始序列的例子，其中红色的字符为 xx 和 yy，省略的部分是 (x,y)(x,y) 中间的部分。
    R L L R R L L R ... L L R R L m 1 2 m m 3 4 m ... m m 2 1 m\textbf{R L L R R L L }\color{red}\textbf{R}\color{black}\textbf{ ... }\color{red}\textbf{L}\color{black}\textbf{ L R R L}\\\textbf{ m 1 2 m m 3 4 m ... m m 2 1 m}
    以下为上述对应的剩余序列，∗* 对应原序列中 x,yx,y 的位置。
    L L L L * ... * R R 1 2 3 4 * ... * 2  1\textbf{L L L L }\color{red}\textbf{*}\color{black}\textbf{ ... }\color{red}\textbf{*}\color{black}\textbf{ R R}\\\textbf{ 1\ 2\ 3\ 4 * ... * 2 \ 1}
    在填完剩余序列后，需要分析加入所有数为 mm 的位置的条件：我们将剩余序列分为“左”、“中”、“右”三个部分，以 x,yx,y 的位置为分界线，其中左部分只有 L，右部分只有 R。则要求是，记“左中”部分的颜色总数为 c1c_1，“中右”部分的颜色总数为 c2c_2，那么需要满足 m=c1+1=c2+1m=c_1+1=c_2+1。同时还要求 mm 不在剩余序列中出现，该限制等价于对于“左中”部分和“中右”部分，都满足 d=1d=1。可以推出等价于剩余序列满足 d=1d=1。对于条件 c1=c2c_1=c_2，容易发现其等价于：记 zz 为左部分和右部分的个数较大值，则剩余序列最左边 zz 个字符必须全为 L，最右边 zz 个字符必须全为 R。
    这部分的最终得出的充要条件是：记 xx 左边有 aa 个 L，yy 右边有 bb 个 R，不妨假设 a≥ba\ge b，取出 (x,y)(x,y) 中间的字符串（不包含 x,yx,y），需要满足末尾有连续 a−ba-b 个 R，且去这 a−ba-b 个 R 后，得到的字符串满足 d=1d=1，即每次取出首尾字符时不存在 RL 的情况。由于 d=1d=1，因此若剩余序列满足该条件，则存在恰好一种填法。
最后仅需要对上述情况分别计数即可。x>yx>y 的情况容易 O(n)O(n) 统计，对于 x<yx<y 的情况，不妨 a≥ba\ge b，可以枚举 yy，计算出 yy 前面连续的极长 R 的个数 cntcnt，那么对 aa 的限制变成了 b≤a≤b+cntb\le a\le b+cnt。
  • 当 cnt=0cnt=0 时，aa 的值固定，但对应的 xx 可以在某一个 R 连续段中任意选择一个位置。我们发现由于 cnt=0cnt=0，也就是 yy 前面一个位置填的是 L，那么 xx 后面一个位置就不能填 R，所以 xx 只能取这个 R 连续段中的最后一个 R。
  • 当 cnt>0cnt>0 时，只需要枚举 xx 的值。容易发现每个 xx 只会被计算至多 22 次。
通过上述观察，我们总共只需要枚举 O(n)O(n) 组 x,yx,y 并判断其是否会对答案增加 11。也就是说，答案是 O(n)O(n) 级别的。
最后的问题是：每次给定一组区间 [l,r][l,r]，问这个字符串每次取出首尾字符时，是否存在 RL 的情况。
一种简单的解决方法是，使用 bitset 维护，例如从小到大扫描 rr，以 bitset 维护对于每个 l+rl+r，是否存在 RL 的情况。该做法的时间复杂度为 O(n2ω)O(\dfrac {n^2}{\omega})，可以通过本题。
如果使用分块卷积，可以做到更优的复杂度。事实上，如果继续深挖性质，可以做到 O(nlog⁡2n)O(n\log ^2n) 的时间复杂度（需要使用卷积），如果你对此感兴趣可以自行研究。

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...