【记录】MX 11.3 ~ 11.8

· · 个人记录

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 - 洛谷

一道扫描线，有以下做法：

P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands - 洛谷

和 CSP T3 有点像的题，考虑查询同时包含前缀和后缀，把所有串插入一棵 trie，同时把串反转插入另一棵 trie，每次查询相当于是正反串分别位于两棵子树，把正反串在相应 trie 上的 dfn 看作 x,y，相当于是二维数点问题，然后就做完了。

P2163 [SHOI2007] 园丁的烦恼 - 洛谷

P6801 [CEOI 2020] 花式围栏 - 洛谷

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 晚 限时训练

20251104限时训练 - Virtual Judge

比较简单的几个题：

A

直接维护每个数字出现次数，维护贡献即可。

B

考虑枚举 a^b 的 b，然后 check 一下就好了。

C

考虑分别维护出每种情况出现的方案数与贡献，乘起来即可。

D

考虑枚举行的区间，发现对于每个数作为最小值贡献区间多选一定不劣，于是维护单调栈和前缀和即可，相似的题还有奥林匹克楼梯。

E

上面写了，主席树上二分即可。

11.3 上午 限时训练

11.03限时训练补题 - Virtual Judge

T1

CF1006F Xor-Paths - 洛谷

看到数据范围，直接折半搜索在中点处合并即可。

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

Problems

首先一个比较显然的性质是 \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

最短路径 - Problem - QOJ.ac

首先有一个 trick，缺一分治，也就是需要统计去掉一个东西的贡献，例如删掉一条边维护连通性，此时可以考虑线段树分治解决。

看到这个，询问删除一个点的最短路，复杂度可以允许 n^3 \times \log n，考虑线段树每个区间 l,r 维护不走 l,r 内的点的最短路，对每个线段树节点进行 Floyd，在叶子节点对询问统计答案即可，时间复杂度 O(n^3 \times \log n + q)。

11.7 限时训练

20251107限时训练 - Virtual Judge

T1

P3243 [HNOI2015] 菜肴制作 - 洛谷

容易发现这是一个拓扑排序，但我们发现正着做取字典序最小不一定是最优的，于是反过来找字典序最大的，发现这个之后就很好做了。

T3

D - AB

找规律大分讨题，考虑最开始的情况，然后分讨往后扩展即可。

T6

E - Directed Tree

考虑这题要求实际上就是 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 了。