本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-09 13:20:19
11.3 ~ 11.8 集训记录
做题记录
P14362 [CSP-S 2025] 道路修复 / road（民间数据） - 洛谷
S T2，场上只写了 $80$ 的做法，把所有边预排好序就可以少一只 $\log$，可以通过。
P14361 [CSP-S 2025] 社团招新 / club（民间数据） - 洛谷
反悔贪心，场上想了一会发现只会有一组不合法，所以反悔贪心就行了。
P14363 [CSP-S 2025] 谐音替换 / replace（官方数据） - 洛谷
比较难实现的题，思路比较清晰。
首先发现 $s_1,s_2$ 不同的部分一定与 $t_1,t_2$ 不同的部分相同，另一个限制是，$s_1,s_2$ 的公共前缀是 $t_1,t_2$ 公共前缀的后缀，同时后缀是公共后缀的一段前缀，于是考虑搞到 trie 树上，对于每个询问相当于查询有多少合法 $s$ 使得 $t$ 位于 $s$ 的子树内，相当于给定若干个矩形，查询每个点被多少个矩形覆盖。
P7416 [USACO21FEB] No Time to Dry P - 洛谷
一道扫描线，有以下做法：
- 莫队
- 离线到右端点，$i$ 从左向右扫的过程中维护 $j \le i$ 的每个 $[i,j]$ 的答案，设 $pre_i$ 表示上一个和 $i$ 颜色相同的位置，则 $\min_{j = pre_i}^{i} a_j$ 决定这一段要不要新染色，区间 rmq。
- 考虑对每个点维护 $pre$ 表示上一个相同颜色位置，如果这之间有更小的数则需要染两次，考虑把所有需要单独染色的区间重新编号，询问变成了查询区间颜色数，离线扫描线算贡献即可。
P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands - 洛谷
和 CSP T3 有点像的题，考虑查询同时包含前缀和后缀，把所有串插入一棵 trie，同时把串反转插入另一棵 trie，每次查询相当于是正反串分别位于两棵子树，把正反串在相应 trie 上的 dfn 看作 $x,y$，相当于是二维数点问题，然后就做完了。
P10096 [ROIR 2023] 扫地机器人 (Day 1) - 洛谷
三个比较简单的扫描线题。
P7554 [COCI 2020/2021 #6] Index - 洛谷
首先考虑一个 $\log^2$ 的做法，建出主席树，发现符合单调性，直接二分答案 check 即可，大常数，但也能过。
考虑直接在主席树上二分，每次查找区间后缀是否有 $mid \le k$ 个数合法，这样就是单 $\log$，跑得飞快。
11.4 模拟赛
T1
AT_joisc2013_joi_poster JOIポスター (JOI Poster) - 洛谷
简单计算几何，但是出题人没有卡精度，其实可以两边同时平方一下，这样就可以避免浮点数运算。
T2
P9906 [COCI 2023/2024 #1] Kocke - 洛谷
模拟赛 T2，观察到最后贡献的是一段区间，记录区间长度以及最后一个数是什么，转移即可。
T3
P10230 [COCI 2023/2024 #4] Lepeze - 洛谷
首先考虑次数是好算的，因为原本连接的边一定不会再动他，设 $ind_i$ 表示 $i$ 连接的对角线数量，次数就是 $n - 3 - ind_i$。
接下来考虑方案，手模一下会发现，这些原本连接的对角线会把整个多边形分成若干个块，每个块内的方案数是独立的，发现各个三角形之间的顺序形成了一棵树形结构，那么最后方案数也就是对这棵树的拓扑序计数。
考虑树的拓扑序数量是 $\frac{n!}{\prod_i siz_i}$，现在问题在于如何维护 $siz_i$。
注意这样一个结论，对于以 $l,r$ 为端点的一段区间（多边形上一段弧），它所包含的三角形数量，也就是 $siz$ 为 $r - l - 1$，于是我们需要考虑如何维护。考虑设 $mul_i$ 表示不经过 $i$ 的区间 $l,r$ 的 $siz$ 的乘积，那么每次询问就是 $fac_{n - 3 - ind_i} \times inv_{mul_i}$。难点在于如何维护 $mul$，考虑加入一条对角线相当于是对两端的所有点都乘上对面弧的贡献，删除相当于是乘上逆元，区间修改单点查询，可以差分一下变成单点修前缀查，树状数组维护即可，注意实现的时候梳理好区间端点，细节比较多。
T4
P10209 [JOI 2024 Final] 路网服务 2 / Road Service 2 - 洛谷
这场模拟赛总结下来，前面简单题花费太多时间，而且被卡题了，但是 NOIP 时间比较长，所以要抓住时间做事情，做好时间分配。
11.4 晚 限时训练
比较简单的几个题：
A
直接维护每个数字出现次数，维护贡献即可。
B
考虑枚举 $a^b$ 的 $b$，然后 check 一下就好了。
C
考虑分别维护出每种情况出现的方案数与贡献，乘起来即可。
D
考虑枚举行的区间，发现对于每个数作为最小值贡献区间多选一定不劣，于是维护单调栈和前缀和即可，相似的题还有奥林匹克楼梯。
E
上面写了，主席树上二分即可。
11.3 上午 限时训练
T1
看到数据范围，直接折半搜索在中点处合并即可。
T2
P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking - 洛谷
首先不难想到建图之后把强连通缩起来，这样同一个强连通内的点对之间都是模糊的。
接下来需要注意到一个性质：对于每个序列相当于图上的一条链，而一条链上同一个强连通内的点是连续的。
考虑到这一点之后，我们就可以直接维护答案，对整个的区间进行前缀和，每次查询把整个区间的贡献和两个端点处的贡献加起来即可。
T3
AT_arc166_c [ARC166C] LU / RD Marking - 洛谷
考虑每个正方形格子的左上和右下是没有影响的，所以可以从对角线切开，发现对于同一斜线上的三角形，他们的方案数是斐波那契数列，预处理出来，并且统计一下中间整块的贡献就做完了。
下午和同学 VP 了一场 CCPC？感觉 J 题还不错。
The Hanged Man - Problem - QOJ.ac
发现找到一个偶数度数的点，我们认为他是天赋异禀的，然后从他开始进行配对即可。
另外有一个性质，发现只会被分割成若干长度为 $2$ 和 $3$ 的链，且只有一条长度为 $3$ 的，可以考虑枚举这条链。
11.6 模拟赛
进场看题之后感觉 T1 应该不难，但是 T2 应该需要组合数推式子，感觉 T3 是个简单题 \lh，T4 应该不好做。
看到 T1 之后想了几个贪心发现都不对，尝试刻画限制条件，发现限制条件的顺序没有确定好，没有想到正解的维护方法，去看了看 T2，发现这个东西可以根号分治，但死活想不出来 $k \le \sqrt n$ 怎么做，于是看了 T3。
最开始想了一个显然不对的做法，只使用前缀和后缀的点的 Floyd，但是其实可能会从左边走到右边再回去。
又想到了分治 Floyd，其实是正解，但是场上不知为何写挂了，耽误了很多时间，又去想了前两个题无果。
以后在做出前两题之前尽量不花很多时间开 T3，注意策略。
T1
首先一个比较显然的性质是 $\max(\sum a,\sum b) \le ans$，考虑 $ans$ 还有什么限制，发现如果一个人的助攻和进球都特别多，就可能不合法，于是发现 $a_i + b_i \le ans$，很好理解，其他人最少进它助攻数量个球，他进了进球数，所以是 $a_i + b_i$。
考虑这东西并不好对每个位置都维护，所以还需要发掘性质。发现一个 $id$ 能产生这种贡献的条件，一定是 $b_i > \sum a - a_i$，$a$ 同理，于是我们只需要找出 $a,b$ 的区间最大值的位置，对这两个位置计算贡献即可。
T2
容易想到根号分治，难点在于 $k \le \sqrt n$ 的部分，这个需要大力组合数推式子并解方程，不擅长数学，不会。
T3
首先有一个 trick，缺一分治，也就是需要统计去掉一个东西的贡献，例如删掉一条边维护连通性，此时可以考虑线段树分治解决。
看到这个，询问删除一个点的最短路，复杂度可以允许 $n^3 \times \log n$，考虑线段树每个区间 $l,r$ 维护不走 $l,r$ 内的点的最短路，对每个线段树节点进行 Floyd，在叶子节点对询问统计答案即可，时间复杂度 $O(n^3 \times \log n + q)$。
11.7 限时训练
T1
容易发现这是一个拓扑排序，但我们发现正着做取字典序最小不一定是最优的，于是反过来找字典序最大的，发现这个之后就很好做了。
T3
找规律大分讨题，考虑最开始的情况，然后分讨往后扩展即可。
T6
考虑这题要求实际上就是 $a_i$ 不能是 $i$ 的祖先，对逆排列计数，二项式反演容斥即可。
11.8 ABC
Tasks - TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431)
比较简单的一场，E 把每个点拆成四个方向四个点，然后建边最短路即可。
F 考虑从小到大填数，已经填了前 $i - 1$ 个，当前填第 $i$ 个，考虑可以填的数，设 $cnt_i$ 表示对于 $i$ 合法的 $i - 1$ 数量，那么对于 $i$ 的贡献就是 $cnt_i - i + 1$，最后去重一下，总方案数是 $\frac{\prod\limits_{i = 1}^{n} cnt_i - i + 1}{\prod\limits_x count_x}$，其中 $count_i$ 表示数字 $i$ 出现的次数。
11.9 模拟赛
进场先看了题，T4 直接处理 A 数组求最大子段和可以有 $25$，暴力分不少，T3 应该是困难题，部分分这么多，找一找好打的打一下，T1 看着像换根，T2 感觉像 trie 树，类似的题被创飞好几次了，再研究一下。
看了 T1，大约 40min 的时候想到可以换根，维护每个点子树内到它路径全为 $0$ 的数量，拆位换根就能知道每个点作为根的贡献，枚举统计贡献即可。
T2 想了很久，想到一个 $n^2$ 的做法，写出来发现假了，又想了想 $2^x$ 的东西，感觉实现太困难了没有写。
T3 写了一个比较好写的暴力，然后去看了 T4，写了 $25$ 的线段树维护最大子段和。
T1出现失误，实现的太拉导致自己最后剩下的时间很少，T2 没有想出来，最后没有专心开一个题，主要问题不少，但是今天场上用 NOILinux 虚拟机测了 CE RE 等问题，发现 freopen 是有返回值的 /lh，还以为是 CE 了。
鲁ICP备2025150228号