24OI 2023 8 月集训 做题记录

发表于 分类于

Day 1

60 + 100 + 70 + 0．

A. 蒙德

喜报：∑du=2m\sum d_u = 2m．

以一个点为中心的极大星图的贡献形如前缀加组合数，然后度数求和是 O(m)O(m) 的，暴力做就行了．

B. 璃月

每个数最多只能贡献 O(n)O(\sqrt{n}) 个点对，然后扫描线．内层数据结构上会产生 O(nn)O(n\sqrt{n}) 次单点加，O(n)O(n) 次区间求和，用个分块平衡下复杂度即可．

出题人没卡带 log⁡\log 的做法．

C. 稻妻

每个点双一定是简单环，然后不在点双里的边必须一直开着，对所有这些边取 min⁡\min．

对每个点双分开考虑，设大小为 kk，每个时刻需要有 k−1k - 1 个边开着，最小和次小可以轮班，然后对其他边取 min⁡\min．

这 b 题怎么卡常．

D. 须弥

有正数解   ⟺  \iff A4A_4 对应的点在 OA1→\overrightarrow{OA_1}，OA2→\overrightarrow{OA_2}，OA3→\overrightarrow{OA_3} 构成的锥体里．

然后就是计算几何了，狗都不补．

Day 2

100 + 65 + 30 + 60．

A. 坏蛋信使

签到题，场上只过了两个人，怎么会是呢．

场上我狂暴找规律过了这题．首先可以猜测答案的分母一定是 nmn^m，然后打了个 5×55 \times 5 的表，发现序列长度相同时不同交换次数的答案的分母可以递推．具体而言，设交换 ii 次时答案的分子为 aia_i，有 ai=(ai−1+ni−1)×(n−2)+nia_i = (a_{i - 1} + n^{i - 1}) \times (n - 2) + n^i．直接矩阵快速幂糊上去．

直接推也很好推！这里贺一下 ckain．

由期望的线性，可以对每个位置分开计算贡献．

每个位置的地位对等．

对于每个位置，考虑进行 mm 次操作后仍在该位置的信封仍在原位置的概率．

设 FiF_i 表示 ii 操作后仍在原位置的概率，有递推式：

Fi=(n2−(2n−1)n2+1n2)Fi−1+2n2(1−Fi−1)F_i = \left(\frac{n^2 - (2n - 1)}{n^2} + \frac{1}{n^2} \right) F_{i - 1} + \frac{2}{n^2}(1 - F_{i - 1})

可以求出通项．也可以矩阵快速幂求解．

B. 路由器

原．但是写挂了．

C. 进化

没写代码．\Huge\color{red}{\text{没写代码．}}

考虑辗转相减的过程，每个数对的祖先链是确定的．那么就相当于询问某个串是字符串集合里中的多少个串的前缀．

这个辗转相减的过程有一车重复的操作，于是压缩一下串，然后塞一起排序就行了．

D. 青蛙

66 维偏序，狗都不补．

Day 3

90 + 70 + 100 + 0．

A. 数字三角形

简单 DP，状态里记录一个前 kk 大就行了．

然而我写挂了，怎么会是呢．

B. 合作

排序，然后双指针扫值域．合法判定就是判断值域区间内的值的所有出现位置的并是否能够覆盖 1∼n1 \sim n．

C. 彩虹

枚举斜线和右下角，动态维护一下当前右下角对应的极大彩虹子矩形，判定颜色是否出现过需要拿个桶．

赛时写丑了，多带了个 log⁡\log，但是出题人 O(n3)O(n^3) 都没卡掉．

D. Flowfree

shaber 大搜索，狗都不补．

Day 4

40 + 90 + 92 + 50．

A. 消消乐

简单 DP，但是考试的时候脑子不清楚没写出来．

设 fi,j,kf_{i, j, k} 表示考虑了前 ii 个燃料，两个盘子颜色分别为 jj 和 kk 时的最大得分，枚举情况暴力转移．

评测的时候出题人后台开了个原神，导致一车人被卡常．

B. 猜猜乐

按照题意模拟即可．注意判空．

C. 跑步

首先有一个简单的 DP，可以求出每个点的答案．

考虑每次修改权值时影响 DP 值的范围，发现在每一行上都是一个连续的区间，且行与行之间区间的左右端点单调不降，那么拿两个指针扫一下就行了．

D. 树

一眼点分治．

Day 6

100 + 0 + 100 + 60．

A. 爱

按题意模拟即可．

B. 我推的孩子

没写代码．\Huge\color{red}{\text{没写代码．}}

如果两人能走的最长链都不和两人间的简单路径相交，那么直接计算然后比较大小即可．

博弈过程中，两人肯定都沿着出发点间的简单路径走，并且若脱离这条路径能获胜的话就脱离．脱离后二人的决策就无关了，可以直接比较．那么预处理一下从链上某个节点出发能走出的最长链，然后模拟博弈过程即可．

C. 阿库亚

按题意模拟即可．

D. 露比

打个表，比对系数可知位置 xx 上答案的表达式为

∑i≤x(k−1+x−ik−1)ai\sum_{i \le x} \binom{k - 1 + x - i}{k - 1} a_i

由于 xx 在询问时给定，直接维护是困难的（自由度分析？），考虑让我们维护的东西和 xx 无关．

考虑逆用 Vandermonde 卷积，有

原式=∑i≤x∑j≤k−1(xj)(k−1−ik−1−j)ai=∑j≤k−1(xj)∑i≤x(k−1−ik−1−j)ai\begin{aligned} \text{原式} &= \sum_{i \le x} \sum_{j \le k - 1} \binom{x}{j} \binom{k - 1 - i}{k - 1 - j} a_i \\ &= \sum_{j \le k - 1} \binom{x}{j} \sum_{i \le x} \binom{k - 1 - i}{k - 1 - j} a_i \end{aligned}

后面那个 ∑\sum 是一个固定的前缀和形式，于是采用树状数组维护即可．

注意计算上标为负数的组合数时的讨论．

Day 7

20 + 0 + 55．

A. 救火

诡异模拟费用流．

挂个类似题目的链接，如果联赛没退役的话就补．【UER #8】雪灾与外卖．

B. 风纪委员

由于 n=∏pin = \prod p_i，那么有 xpi≡qi(modn)⇒xpi≡qi(modpi)⇒x≡qi(modpi)x^{p_i} \equiv q_i \pmod{n} \Rightarrow x^{p_i} \equiv q_i \pmod{p_i} \Rightarrow x \equiv q_i \pmod{p_i}．

CRT 合并即可．

C. 下棋

观察到长度为 2k2^k 的空白连续段可以以 11 的代价弄掉，那么答案就是每个连续段的 popcount 求和．

注意特判端点．

Day 8

100 + 30 + 100．

A. 阳光明媚

不能求逆元，直接矩阵快速幂即可．

B. 树天

有一个堆的做法，套个启发式合并暴力上树即可．

C. 雾天

按题意模拟即可．

Day 9

10 + 20 + 25．

A. 数列

由于 ≤\le 号具有传递性，故只需考虑相邻两项大小关系的限制．

对于两数 xx 和 yy，其二进制最高不相同位贡献了大小关系，若不对的话则必须翻转那一位．

那么直接记 ci,0/1c_{i, 0 / 1} 表示第 ii 位上钦定为 00 或 11 的位置个数，若两个都有值显然不存在方案，剩下能填 00 就填 00．

B. 多云

将商店看作点，商品看作边，这是带权最小点集覆盖，挑战 NPC．

考虑搜索，若钦定当前点不选，那么与其相邻的点都必须选，然后卡卡常就跑过去了．

C. 字符串

CNOI 风味遗产．

有个很显然的 DP，配合二分 hash 可以拿到 70．

考虑根号分治，长度大于 L\sqrt{L} 的串只有不超过 L\sqrt{L} 个，这部分二分 hash 配合线段树区间取 min⁡\min 转移；长度小于 L\sqrt{L} 的串使用两个 trie 分别处理前后缀转移．

时间复杂度 Θ(mLlog⁡m)\Theta(m \sqrt{L} \log m)，貌似使用压缩 trie 技术能去掉 log⁡\log，但是不是很懂．