GDKOI2021口胡

· · 个人记录

因为在广东集训，我们都要参加 GDKOI2023 来试手。

听说 GDKOI2021 是三天，每天 4 小时 4 题，省选难度，并且没有大样例。（p.s. GDKOI2022 未举办）而且评测机似乎还是 g++ 4.8.4。

然后由于是非正式选手，我们会在纪中机房打，用的机子会统一是只有 g++ 4.9.2 的 Windows 神秘机。不过听说评测环境会是 NOI Linux 2.0。

反正是，纪中教练（Update: 由 Alpha 从教练那边讨来的）给了我们 GDKOI2021 三天的题面，然后手上也没有可以自己交的地方（没有 gmoj 帐号，注册也没用），因此打算开始口胡！

题面下载链接。

Day 1

A

给你一张 n 个点 m 条边的无向图，你要把点集分成两部分，使得两个点集之间的边的边数达到一半的总边数。数据保证有解。

保证无自环，重边按重数计。

考虑对点集增量。

每增加一个点，考虑其和已有的两个点集中谁的边数更少，加入那个点集即可。

复杂度 O(n+m)。

B

给定长为 n 的序列 a_1,a_2,\cdots,a_n，设 f_{l,r}=(r-l+1)\min_{l\le k\le r}a_k\quad(1\le l\le r\le n)，求出从小到大排名在 L 到 R 之间的各个 f 值。

这个，是不是，可以加进 XJCS，作为单调栈基础练习题啊！@devinwang

写个单调栈，建出笛卡尔树，我们就可以知道对于每个 \min a，其向左、向右扩展的距离。

然后我们考虑二分答案，对每个值 w 查询有多少对 l,r 满足 f_{l,r}<w；答案显然不超过 O(nv) 级别，因此只用 O(\log(nv)) 轮二分即可解出第 L 大的数对应的权值，以及有多少数小于之。

然后我们考虑下一个数怎么求：我们先把相同的 w 尽可能取空，这样我们下一个只用考虑 >w 的数。然后我们对每个 \min a 开一个对应了元素的堆，每次取出最小元素后把该 \min a 的下一项放入堆中。

这样就可以在 O(n\log(nv)) 的时间内解决该问题了。

C

给定一个长度为 n 的字符串 s，q 次询问，回答某个区间 [l,r] 内的最长回文子串长度。

神秘串串题，不会 PAM，爬了爬了。

考虑 manacher，我们对前一半区间考虑，相当于求出区间内 \min\{M_p,p-l\} 的最大值；后一半同理。

这个直接离线用扫描线 + 线段树维护哪边取到 \min 即可。在线也可以主席树。

复杂度 O((n+q)\log n)。

D

给出 n,k,A 和 k 个数对 (s_1,v_1)(s_2,v_2)\dots(s_k,v_k)，求出所有有 n 个叶子的如下二叉树的权值和：

  • 整颗树的权值定义为其各节点权值之积。
  • 叶节点权值为 1。
  • 枝节点均有 2 个儿子，且其权值由其左子树中叶子节点个数决定；即，若节点叶子个数为某个 s_i(1\le i\le k) 时，其权值为 v_i；如均不满足，则权值定义为 A。

对 10^9+7 取模。

数数题！

假设 n 的答案为 f_n。

f_n=\begin{cases}1&n=1\\A\sum_{1\le t\le n-1}f_tf_{n-t}+\sum_p(v_p-A)f_{s_p}f_{n-s_p}&n>1\\0&\textrm{otherwise.}\end{cases}

先判掉 A=0，此时的柿子很简单，直接暴力即是 O(nk) 的。

剩下的情况乍一眼不可做，因为是半在线卷积形式。

但这个做法我们感觉很不靠谱，毕竟常数太大了，而 O(n\log^2n/\log\log n) 的也不能用，用了也未必快。

考虑，设 h_n=A[\forall t,s_t\neq n]+\sum_t[s_t=n]v_t，g_n=h_nf_n。

则

f_n=[n=1]+[n>1]\sum_tg_tf_{n-t}

于是设 F(z)=\sum_nf_nz^n,G(z)=\sum_ng_nz^n，则

F=z+FG G=AF+\sum_t(v_t-A)z^{s_t}[z^{s_t}]F

我们推回了原式？

考虑怎么办。

假设后面的柿子已知，设为 G=AF+H。

则

F=z+AF^2+FH AF^2+(H-1)F+z=0 (F+\frac{H-1}{2A})^2=\frac{H^2-2H+1}{4A^2}-\frac zA F=\frac{1-H}{2A}+\sqrt{\frac{H^2-2H+1}{4A^2}-\frac zA}

后面的这个部分就是对一个非 0 项数 O(k^2) 的多项式进行开根。

这个容易列 ODE，做到 O(k^2) 递推出单项。

然后就可以通过递推，再反过来对 H 进行增量。

于是总复杂度即为 O(nk^2)。

Day 2

A

初始你有 0 颗星，你将参加若干轮比赛，当你有 i 颗星时胜率为 p_i，获胜加 1 颗星，落败减 1 颗星，0 颗星落败不会减星，问期望几轮变为 n 颗星，对 998244353 取模。

设 f_k 表示若初始为 k 颗星，则期望要几轮才可以结束。

容易发现

f_k=\begin{cases}(1-p_0)f_0+p_0f_1+1&k=0\\0&k=n\\(1-p_k)f_{k-1}+p_kf_{k+1}+1&\textrm{otherwise.}\end{cases}

稍作转化，即可依次推出形如 f_k=f_{k+1}+C_k 的柿子，于是就做完了。

使用离线求逆元，复杂度即为 O(n+\log{\mathbf{Mod}})。

本题亦可以用鞅的停时定理与势函数相关知识解决。

B

给定一张 n 个节点的有向图，每个节点 p 向 p+1（如果 p\neq n）和 a_p 连出一条边，你要支持 q 次如下操作：

  • 修改某个 a_p。
  • 查询一个节点 p 可以到达的编号最小节点。

允许离线。

唔，很困难啊！

容易发现 a_p<p 时才有意义，a_p\ge p 相当于没连。

注意到我们每个节点均可以到达一个后缀，然后这个后缀的起始点是单调的。

设 b_p=\max\{q|a_q=p\}，如不存在则认为 b_p=p。

考虑如果不带修改，则预处理的部分，可以从小到大依次考虑编号，把 (p,b_p] 的答案均用自己的答案更新。

如果一个位置 p 不会被任何元素更新，则说明 \max\{b_k|k<p\}<p。

于是问题就转化为对 b_p 单点修改，查询上一个满足 \max\{b_k|k<p\}<p 的元素，容易把后面这个东西描述成 (p,b_p] 加 1，容易线段树上二分。

复杂度 O((n+q)\log n)。

C

现在有 26 种左右对称的字符，我们不妨称为 \texttt a\sim\texttt z，每个字符依次有一个抄写时间 cost_c。给你一个长为 n 的字符串，你要依次抄写之。

由于你很聪明，你发现你可以花 C 的时间把已抄写部分的一个后缀「翻折」到后面的部分，从而避免对那些部分的抄写（注意最后一个字符可以被往后翻折，也可以直接在此处进行翻折，详见原题面）。

你要回答至少花多久才可抄完。

容易发现对每个前缀，答案是单调的；证明比较容易。

设 f_n 表示对一个长度为 n 的前缀的答案。

容易发现，我们总是从尽可能早的位置进行翻转（代价都是 C 嘛），或者从上一位的答案直接递推。

manacher 的同时维护一个单调队列，表示由谁翻转来的贡献即可。

复杂度 O(n)。

D

二叉堆可以通过倒序 O(n) 轮下滤操作构建，代码详见原题面。

给定一个 1\sim n 的排列 a，q 次查询一段区间 [l,r] 如果建出二叉堆，其某个位置 x 的权值，或者某个权值 x 对应的位置。

先看第一类查询。

当更新到当前点时，其权值为子树中的最大值。

然后每次看父亲与另一个子树最大值，模拟一下变化即可 O(\log n)。

然后考虑第二类查询。

我们从此值的位置向上考虑，每次模拟一下操作，即可 O(\log n)。

使用 ST 预处理 RMQ，总复杂度 O((n+q)\log n)。

Update: 假了，正解是 2\log。没事反正口胡。

Day 3

A

给定一颗 n 个节点的树，每个点有点权 a_i。

假设树上有一对路径 (x,y),(u,v)\quad(x\le y,u\le v)，设 f(x,y,u,v) 为所有同时在两条路径上的点的点权的 \operatorname{lcm}，求出所有 f(x,y,u,v) 的乘积，对 10^9+7 取模。

反向统计有多少路径对会统计到 p^c 的贡献，建出虚树直接计算即可。

即，点减边容斥，钦定某个点 / 相邻被选点对必定会被选择，求方案数；不被选的点表示其下某些点会和别的某些点匹配。

容易 O(\text{点数}\log n) 建出虚树并计算贡献。

由于一个数这样的因子个数为 O(\log v) 的，于是即可 O(n\log v\log n) 解决。

如果适当地对比较长的部分直接基排，并 ST 表实现 O(1) 查询 LCA，应该可以获得更高效率。

B

给定 n 个数对 (a_i,b_i)，一个区间 [l,r] 的正向贡献为 (\sum_{i=l}^ra_i,\sum_{i=l}^rb_i)，反向贡献为 (-\sum_{i=l}^ra_i,-\sum_{i=l}^rb_i)。

如果一个贡献的第二部分 >0，则称其优秀。

假设有若干贡献对 (A,B)，你要回答对每个 A，分别有多少贡献对满足 B>0。

不妨分别做前缀和，然后按 b 排序，那么我们发现我们可以把这个按 b 分成若干段，每个元素和之前的段之间的 a 之差有贡献。

直接分治 FFT 减法卷积计算贡献即可；也可以多叉分治。

复杂度 O(n\log^2n) 或 O(n\log^2n/\log\log n)。

注意答案可能会很大，要双模 NTT 然后 CRT 合并。

Update: 假了，分治下去没有变成更小的问题。正确的做法是分块 FFT。

C

对一个异或生命游戏，初始时有 n 个节点 (x_1,y_1)(x_2,y_2)\cdots(x_n,y_n) 存活，之后某一时刻某节点存活当且仅当上一时刻其四周恰有奇数个节点存活。

你要回答 L 至 R 时刻存活细胞数目之和，对 998244353 取模。

先考虑 n=1 的情形，则一个节点可以在 t 时刻存活当且仅当其有奇数种从起点被走到的方案。

假设起点 (0,0)，终点 (x,y)，时间 t。

则存在当且仅当 |x|+|y|\le t\land2|t-|x|-|y|。

方案数则为 \sum_a\binom{t}{|x|+a,a,(t-|x|+|y|)/2-a,(t-|x|-|y|)/2-a}。

化一下柿子。

\begin{aligned} &\quad\sum_a\binom{t}{|x|+a,a,(t-|x|+|y|)/2-a,(t-|x|-|y|)/2-a} \\&=\binom{t}{(t+|x|+|y|)/2}\sum_a\binom{(t+|x|+|y|)/2}{|x|+a}\binom{(t-|x|-|y|)/2}{a} \\&=\binom{t}{(t+|x|+|y|)/2}\binom{t}{(t+|x|-|y|)/2}\quad(\text{范德蒙卷积}) \\&=\binom{t}{(t+x+y)/2}\binom{t}{(t+x-y)/2} \end{aligned}

于是由 Lucas 定理，存活当且仅当 |x|+|y|\le t 且 2|t-|x|-|y| 且 (t+x+y)/2,(t+x-y)/2 均在二进制下为 t 的子集。

然后就是数个数。

任取 t 的两个子集 a,b 均可反向唯一确定合法的 x,y？

于是就建立了双射。

x=a+b-t,y=a-b

直接计数 \sum_{t=L}^{R}4^{\operatorname{popcount}(t)} 即可，容易数位 dp 算出每种 \operatorname{popcount}(t) 的方案数，从而做到 O(\log^2v)。

回到原题。

由于 n 很小，我们考虑容斥掉被多个同时统计的贡献。

x_1+a_1+b_1=x_2+a_2+b_2=\dots=x_n+a_n+b_n y_1+a_1-b_1=y_1+a_1-b_1=\dots=y_n+a_n-b_n

于是一样拆开 a,b 的贡献即可。

(x_1+y_1)/2+a_1=(x_2+y_2)/2+a_2=\dots=(x_n+y_n)/2+a_n (x_1-y_1)/2+b_1=(x_2-y_2)/2+b_2=\dots=(x_n-y_n)/2+b_n

（注意可能带一个 1/2，但奇偶性必须相同）

按 x+y 排序，则合法 a 递减。

然后枚举最小 a，可以推出其余 a 与之的差量。

感觉能数位 dp，但是没推过，咕了。

D

没看。睡觉去了。明天 GDKOI Day 2 RP++。