6.1 ~ 6.30 做题总结

· · 个人记录

有题解的题挂链接,没题解的题简要说明思路。过水的题不记录。

难度评价系统来自 https://www.luogu.com.cn/article/u98dxgp0。贺个图:

【2-】P14012 [POCamp 2023] 枫树 / Maple Tree

题解:https://www.luogu.com.cn/article/e200mkjv。

【1+】P3488 [POI 2009] LYZ-Ice Skates

题解:https://www.luogu.com.cn/article/ijtsm6q9。

【1+】ARC163C Harmonic Mean

题解:https://www.luogu.com.cn/article/6t2xyx39。

【2】P7840 「C.E.L.U-03」重构

题解:https://www.luogu.com.cn/article/sp98gzmn。

【3】CF1091E New Year and the Acquaintance Estimation

题解:https://www.luogu.com.cn/article/szfu472f 里面有。

【0】AGC006A Prefix and Suffix

找后缀 = 前缀的最长字符串即可。

【1】AGC006B Median Pyramid Easy

考虑令 p_{n-1}=x-1, p_n=x,p_{n+1}=x+1,剩余位置按照顺序填。这样在 n-1 层上一定会出现两个相邻的 x,并且两个元素可以传递到第一层。

【2】AGC006C Rabbit Exercise

对于一个点 x,其关于位置 y 对称后的坐标是 2y-x,与相对位置无关。

写成期望递推的形式,记 f_i 为当前状态下,左起第 i 个点的期望坐标,那么

f_i \gets \dfrac{1}{2}(2f_{i-1}-f_i)+\dfrac{1}{2} (2f_{i+1}-f_i)

整理一下就是 f_i \gets f_{i+1}+f_{i-1}-f_i。根据经典结论,这个操作就是交换差分。

记 f 的差分数组是 d_i,记录一下一轮操作后 d_i 的末位置,得到一个置换。快速幂优化置换乘法即可。

【2】AGC006D Median Pyramid Hard

考虑二分答案 x 并使用 01 转化的 trick,即我们只关心每个元素与 x 的相对大小关系。故将 \le x 的元素记为 0,>x 的元素记为 1。

形如 00 或 11 且离中心线最近的块就是第一行的元素,根据这个就可以 check 了。

【3】P2148 [SDOI2009] E&D

记两堆石子 x,y 的 SG 为 \text{SG}(x,y),打表发现 \text{SG}(x,y)=(x-1) \text{ or } (y-1) 在二进制下最低的 0 的出现位置,异或起来即可。

【2】CF138D World of Darkraft

坐标系旋转 45\degree,走斜线变成直线。然后将棋盘黑白染色,两部分分别算 SG。转移模拟题意即可。

【1】CF317D Game with Powers

每个集合独立,且集合大小 \le 30。记搜打表出 SG 函数以后异或起来。

【3】CF1442F Differentiating Games

考虑 DAG 上的情形,必须 SG 两两不同才能区分,则构造完全 DAG 转化为 nim 游戏。

在完全 DAG 下挂若干点,结合策略窃取论证,可以用三种结果区分目标点在 DAG 下节点所挂集合的所属情况。

贪心找点然后调整即可,可以说明次数是对的。

【2】P13356 [GDCPC 2024] 图

题解:https://www.luogu.com.cn/article/q8p78mga。

【2】AT_utpc2020_j Merge and Decrement

题解:https://www.luogu.com.cn/article/rgl351av。

【2】P12703 [KOI 2022 Round 2] 外环路

三度化后点 / 边分治更新最短路。

【4】AT_utpc2022_e Parallel Swapping

【1+】CF1217D Coloring Edges

使用拓扑排序判环,显然无环时 k_{\min}=1。

如果有环,我们断言 k_{\min}=2。考虑如下构造:对于边 (u,v),若 u<v 则染黑色,否则染白色。正确性使用反证法,即假设存在同色环,则环上点的编号递增且不会回到起点,矛盾。

【1】CF1438D Powerful Ksenia

注意到操作一定不会改变整体异或和。于是求出 m=\bigoplus \limits_{i=1}^n a_i,m 即为最终异或和。若 n 为偶数则必有 m=0,否则无解。

我们尝试给出奇数情况的构造。注意到若 a_i=a_j,则一次操作后有 a_i,a_j \gets a_k,这启示我们先令 a_n=m 再对 1 \sim n-1 顺次操作。

考虑增量维护前缀异或和。令 i=1,3,\cdots,n-2,对 i,i+1,i+2 操作,从而让 a_{i+2} 变为前缀异或和并继续传递。传递到 a_n 后再返回来操作即可。

对于 n 为偶数的情形,我们考虑删去 a_n 转化为奇数情形。这是由于 m=0,也即 a_n 必然与前面的数相等。

操作次数 n-1,复杂度 O(n)。

【1+】P9820 [ICPC 2020 Shanghai R] Mine Sweeper II

注意到将地图取反后空地价值和不变。证明考虑每一对八连通格子,取反以后贡献不变。

考虑将 B 修改为 A 或 A 的补图。根据鸽巢原理,两者之间必有一个的修改次数 \le \lfloor \frac{nm}{2} \rfloor。

【3】QOJ1429 Hit

首先将区间端点离散化,将值域映射到 1 \sim m。

考虑二分答案 k。对于一条数轴,我们用一个 01 串表示这个位置是否放置整点,并对其做前缀和,记为 p_i。则 p_i 满足如下限制:

这是一个差分约束的形式。考虑如下建图:

建超级源点 S 连向每个点,则 k 不合法当且仅当图中存在负环。以 S 为源点跑出最短路,p_i 即为所求。至此复杂度 O(n^2 \log n)。

考察这个差分约束图的形态,以第一组样例为例:

我们注意到,负环只可能由向左的 -1 边和向右的 +k 边构成。进一步,我们考虑求出 k 的下界。

我们使用朴素贪心,在每个线段都至少包含一个点的约束下最小化点数,并求出一条线段所包含点数的最大值 k'。维护这个贪心是简单的,按右端点升序排序以后顺次扫描,如果当前线段没有点就放在右端点,树状数组支持单点修改区间求和即可。

设贪心得到的点为 x_1<x_2<\cdots<x_{k'},这些点在图上形成了 k'-1 条向左的 -1 边 x_i \to x_{i-1},且 [x_{i-1},x_i] 除端点外不相交。可以说明,必然存在 u \le x_1 \land v \ge x_{k'} 使得 u\to v 存在 k 边。这样一来,x_{k'} \to x_{k'-1} \to \cdots \to x_1 \to u \to v \to x_{k'} 就是差分约束图的最小环,边权和为 k-(k'-1)。

根据负环的定义,得到 k 的下界为 k'-1。又由贪心算法给出了 k 的上界 k',故 k \in \{k'-1,k'\}。复杂度 O(n^2)。

至于之后咋做,我还不会。

【2】LOJ6267 生成随机数

题解:https://www.luogu.com.cn/article/xg2oodr3。

【4】QOJ7977 彩虹航线

【3】QOJ18404 Dangerous Data

题解:https://www.luogu.com.cn/article/i8embwqy。

【3】QOJ17760 Telepathy

题解:https://www.luogu.com.cn/article/r6ln11nt。

【1】AT_wtf22_day1_a Save the Monsters

题解:https://www.luogu.com.cn/article/52ank0ac。

【2】QOJ141 8 染色

A 和 B 先不断删去度数 <8 的点,得到新图 G'。只要 A 给 B 提示了 G' 的 8 染色,B 是容易按逆拓扑序贪心构造的。

记 G' 的点数为 n',根据握手定理 2m=\sum d_u \ge 8n',得 n' \le \frac{m}{4}。

如果每个颜色占 3bit,总的 bit 数就是 \frac{3}{4} m =3.75 \times 10^5,只能获得 41.3pts。

我们注意到 2 染色是容易的。考虑将 8 种颜色两两分组,然后传递 4 个组的标号。bit 数为 \frac{1}{2}m 符合要求。

可以证明,每一组在 G' 中的导出子图都是二分图,因此可以黑白染色,于是 B 就得到了 G' 的 8 染色。

注意精细实现,否则会被卡常卡空间。submission。

【2】P13011 【MX-X13-T6】「KDOI-12」能做到的也只不过是静等缘分耗尽的那一天。

题解:https://www.luogu.com.cn/article/yumpahmx。

【2】P8394 [BalticOI 2022] Boarding Passes (Day2)

【4】P8124 [BalticOI 2021] From Hacks to Snitches (Day1)

【2】CF1292E Rin and The Unknown Flower

【1+】P16536 [THUPC 2026 决赛] 流光解密

题解:https://www.luogu.com.cn/article/23lwa3rh。

【2】ARC148D mod M Game

站在 B 的角度思考问题。考虑将数两两配对为 (a,b),满足 a \equiv b \pmod m,A 拿走其中一个,B 就拿走另一个。

另一种情况时,当 m 为偶数,还有 a \equiv b +\frac{m}{2} \pmod m 合法,这样的对必须有偶数对。

这是 B 获胜的充分条件,我们猜测这是必要的。

问题转化为判定是否存在合法匹配。做法就是统计 2a_i \bmod m 出现次数的奇偶性,必须全部为偶数,以及用全局和限制一下。

【3】P10004 [集训队互测 2023] Permutation Counting 2

题解:https://www.luogu.com.cn/article/44ak4e9i。

【3】LOJ566 「LibreOJ Round #10」yanQval 的生成树

【4】P10611 故事结局

【2】CF1311E Construct the Binary Tree

【0】ARC222A Colorful Intervals

幽默题,卡了我 10min。

答案有一个显然的下界,即所有区间长度的 \max,我们把这个值记为 k。

断言下界可以取到。构造式证明是 1,2,\cdots,k,1,2,\cdots,k,\cdots,任何长度 \le k 的区间都符合要求。

【1+】ARC222B Circular RPS

枚举三种手势赢了 x,y,z 个人,可以列出若干不等式,最大化 x+y+z。

这是一个线性规划,直接解或者放到三维空间中都是容易的。一车 corner case。

【1】ARC222C 2 Directions vs 4 Directions

最优解一定形如:一条从上到下的路径,两行之间 x 坐标差为 1。A 堵住路径的两侧即可。

前后缀 DP 合并即可。O(n^2)。

【2】P12204 [COI 2022] 委员选举 / Povierenstvo

题解:https://www.luogu.com.cn/article/enhtc5t4。

【2】CF1061F Lost Root

题解:https://www.luogu.com.cn/article/9swhotpl。

【2】CF618F Double Knapsack

题解:https://www.luogu.com.cn/article/6yo7njlc。

【1】CF1498E Two Houses

幽默交互题 0 次询问。

给了入度,求出所有 SCC,然后随便做。

【1】CF1779E Anya's Simultaneous Exhibition

首先,要找的点集即为竞赛图缩点后链头 SCC 的点集。

直接问到每个点的出度,然后就能得到入度,用入度就能求所有 SCC。

【3】P3561 [POI 2017] Turysta

题解:https://www.luogu.com.cn/article/akorqiuf。

【3】P11164 [BalkanOI 2023] Permutations

题解:https://www.luogu.com.cn/article/somcbl4c。

【3】P14002 [eJOI 2025] Navigation

题解:https://www.luogu.com.cn/article/kauev85l。

【4】P14463 【MX-S10-T4】『FeOI-4』呼吸之野

【1+】P9000 [CEOI 2022] Measures

题解:https://www.luogu.com.cn/article/ezxm938f。

【4】ABC249Ex Dye Color

【3】P12636 [UOI 2020] Array Reduction

【2】ABC267G Increasing K Times

题解:https://www.luogu.com.cn/article/2kc5wkre。

【3】QOJ17160 Multiset Variance

题解:https://www.luogu.com.cn/article/mjw9rzg8。

【2】P7962 [NOIP2021] 方差

题解:https://www.luogu.com.cn/article/d670r3be。

【1】QOJ12212 Best Subsequence

题解:https://www.luogu.com.cn/article/urnr9tmc。

【1+】P14068 [PO Final 2022] 搭塔 / Legobyggartävlingen

题解:https://www.luogu.com.cn/article/5y6jl6xd。

【1+】P13649 [NOISG 2016] Panda Ski

题解:https://www.luogu.com.cn/article/dqptl5be。

【3】P12508 [ROI 2025 Day2] 程序员的日常

【4】QOJ6509 Not Another Range Query Problem

【2】P11647 【MX-X8-T6】「TAOI-3」俄罗斯蓝猫

题解:https://www.luogu.com.cn/article/2evhhjtz。

【3】QOJ11544 Colored Blocks

题解:https://www.luogu.com.cn/article/jspdsxil。

【2】ARC076F Exhausted?

题解:https://www.luogu.com.cn/article/ls0gn0br。

【4】CF1408H Rainbow Triples

【1+】CF1437E Make It Increasing

题解:https://www.luogu.com.cn/article/trgnp8hb。

【1+】P14394 [JOISC 2016] 俄罗斯套娃 / Matryoshka

首先用 Dilworth 定理对偶成最长反链,发现是最长非严格下降子序列长度。

按 r_i 降序排序,写一个 DP 出来用树状数组转移。每次查询实际上是 2-side 矩形求 max,扫描线即可。

【3】P1861 星之器

题解:https://www.luogu.com.cn/article/dgzqyy7m。

【1】CF1110E Magic Stones

题解:https://www.luogu.com.cn/article/2i28wba9。

【1】P6976 [NEERC 2015] Distance on Triangulation

平面图,多次询问最短路,允许离线,套路地考虑分治。做法是每次找到分治中心,从分治中心向两侧跑最短路,更新跨过中线的所有询问,并将中线同侧的询问递归处理。网格图分治、Halin 图分治。

对于本题,由于边权均为 1,直接从分治中心向两侧 BFS 即可。只要考虑如何找分治中心。

类似边分治,我们枚举当前连通块的所有边,并计算删去这条边后,形成的最大连通块的大小,然后取最大连通块最小的边为中心。

视 n,q 同阶,分治树一共 O(\log n) 层,总复杂度 O(n \log n)。

【2】P8392 [BalticOI 2022] Uplifting Excursion (Day1)

题解:https://www.luogu.com.cn/article/z7xcvlwl。

【3】P15653 [省选联考 2026] 星图 / starmap

题解:https://www.luogu.com.cn/article/l5o0n321。

【1+】ABC304Ex Constrained Topological Sort

题解:https://www.luogu.com.cn/article/ik9jkjta。

【1+】ARC145D Non Arithmetic Progression Set

题解:https://www.luogu.com.cn/article/k32za18a。

【2】P9499 「RiOI-2」change

题解:https://www.luogu.com.cn/article/paa60yzi。

【2】P8494 [IOI 2022] 最罕见的昆虫

题解:https://www.luogu.com.cn/article/vpl09tti。