专栏文章
11.3 ~ 11.8 总结
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minb85xk
- 此快照首次捕获于
- 2025/12/01 23:34 3 个月前
- 此快照最后确认于
- 2025/12/01 23:34 3 个月前
11.3 ~ 11.8 集训记录
做题记录
P14362 [CSP-S 2025] 道路修复 / road（民间数据） - 洛谷S T2，场上只写了 的做法，把所有边预排好序就可以少一只 ，可以通过。
反悔贪心，场上想了一会发现只会有一组不合法，所以反悔贪心就行了。
比较难实现的题，思路比较清晰。
首先发现 不同的部分一定与 不同的部分相同，另一个限制是， 的公共前缀是 公共前缀的后缀，同时后缀是公共后缀的一段前缀，于是考虑搞到 trie 树上，对于每个询问相当于查询有多少合法 使得 位于 的子树内，相当于给定若干个矩形，查询每个点被多少个矩形覆盖。
一道扫描线，有以下做法：
- 莫队
- 离线到右端点， 从左向右扫的过程中维护 的每个 的答案，设 表示上一个和 颜色相同的位置，则 决定这一段要不要新染色，区间 rmq。
- 考虑对每个点维护 表示上一个相同颜色位置，如果这之间有更小的数则需要染两次，考虑把所有需要单独染色的区间重新编号，询问变成了查询区间颜色数，离线扫描线算贡献即可。
和 CSP T3 有点像的题，考虑查询同时包含前缀和后缀，把所有串插入一棵 trie，同时把串反转插入另一棵 trie，每次查询相当于是正反串分别位于两棵子树，把正反串在相应 trie 上的 dfn 看作 ，相当于是二维数点问题，然后就做完了。
三个比较简单的扫描线题。
首先考虑一个 的做法，建出主席树，发现符合单调性，直接二分答案 check 即可，大常数，但也能过。
考虑直接在主席树上二分，每次查找区间后缀是否有 个数合法，这样就是单 ，跑得飞快。
11.4 模拟赛
T1
简单计算几何，但是出题人没有卡精度，其实可以两边同时平方一下，这样就可以避免浮点数运算。
T2
模拟赛 T2，观察到最后贡献的是一段区间，记录区间长度以及最后一个数是什么，转移即可。
T3
首先考虑次数是好算的，因为原本连接的边一定不会再动他，设 表示 连接的对角线数量，次数就是 。
接下来考虑方案，手模一下会发现，这些原本连接的对角线会把整个多边形分成若干个块，每个块内的方案数是独立的，发现各个三角形之间的顺序形成了一棵树形结构，那么最后方案数也就是对这棵树的拓扑序计数。
考虑树的拓扑序数量是 ，现在问题在于如何维护 。
注意这样一个结论，对于以 为端点的一段区间（多边形上一段弧），它所包含的三角形数量，也就是 为 ，于是我们需要考虑如何维护。考虑设 表示不经过 的区间 的 的乘积，那么每次询问就是 。难点在于如何维护 ，考虑加入一条对角线相当于是对两端的所有点都乘上对面弧的贡献，删除相当于是乘上逆元，区间修改单点查询，可以差分一下变成单点修前缀查，树状数组维护即可，注意实现的时候梳理好区间端点，细节比较多。
T4
这场模拟赛总结下来，前面简单题花费太多时间，而且被卡题了，但是 NOIP 时间比较长，所以要抓住时间做事情，做好时间分配。
11.4 晚 限时训练
比较简单的几个题：
A
直接维护每个数字出现次数，维护贡献即可。
B
考虑枚举 的 ，然后 check 一下就好了。
C
考虑分别维护出每种情况出现的方案数与贡献，乘起来即可。
D
考虑枚举行的区间，发现对于每个数作为最小值贡献区间多选一定不劣，于是维护单调栈和前缀和即可，相似的题还有奥林匹克楼梯。
E
上面写了，主席树上二分即可。
11.3 上午 限时训练
T1
看到数据范围，直接折半搜索在中点处合并即可。
T2
首先不难想到建图之后把强连通缩起来，这样同一个强连通内的点对之间都是模糊的。
接下来需要注意到一个性质：对于每个序列相当于图上的一条链，而一条链上同一个强连通内的点是连续的。
考虑到这一点之后，我们就可以直接维护答案，对整个的区间进行前缀和，每次查询把整个区间的贡献和两个端点处的贡献加起来即可。
T3
考虑每个正方形格子的左上和右下是没有影响的，所以可以从对角线切开，发现对于同一斜线上的三角形，他们的方案数是斐波那契数列，预处理出来，并且统计一下中间整块的贡献就做完了。
下午和同学 VP 了一场 CCPC？感觉 J 题还不错。
发现找到一个偶数度数的点，我们认为他是天赋异禀的，然后从他开始进行配对即可。
另外有一个性质，发现只会被分割成若干长度为 和 的链，且只有一条长度为 的，可以考虑枚举这条链。
11.6 模拟赛
进场看题之后感觉 T1 应该不难，但是 T2 应该需要组合数推式子，感觉 T3 是个简单题 \lh，T4 应该不好做。
看到 T1 之后想了几个贪心发现都不对，尝试刻画限制条件，发现限制条件的顺序没有确定好，没有想到正解的维护方法，去看了看 T2，发现这个东西可以根号分治，但死活想不出来 怎么做，于是看了 T3。
最开始想了一个显然不对的做法，只使用前缀和后缀的点的 Floyd，但是其实可能会从左边走到右边再回去。
又想到了分治 Floyd，其实是正解，但是场上不知为何写挂了，耽误了很多时间，又去想了前两个题无果。
以后在做出前两题之前尽量不花很多时间开 T3，注意策略。
T1
首先一个比较显然的性质是 ，考虑 还有什么限制，发现如果一个人的助攻和进球都特别多，就可能不合法，于是发现 ，很好理解，其他人最少进它助攻数量个球，他进了进球数，所以是 。
考虑这东西并不好对每个位置都维护，所以还需要发掘性质。发现一个 能产生这种贡献的条件，一定是 ， 同理，于是我们只需要找出 的区间最大值的位置，对这两个位置计算贡献即可。
T2
容易想到根号分治，难点在于 的部分，这个需要大力组合数推式子并解方程，不擅长数学，不会。
T3
首先有一个 trick，缺一分治，也就是需要统计去掉一个东西的贡献，例如删掉一条边维护连通性，此时可以考虑线段树分治解决。
看到这个，询问删除一个点的最短路，复杂度可以允许 ，考虑线段树每个区间 维护不走 内的点的最短路，对每个线段树节点进行 Floyd，在叶子节点对询问统计答案即可，时间复杂度 。
11.7 限时训练
T1
容易发现这是一个拓扑排序，但我们发现正着做取字典序最小不一定是最优的，于是反过来找字典序最大的，发现这个之后就很好做了。
T3
找规律大分讨题，考虑最开始的情况，然后分讨往后扩展即可。
T6
考虑这题要求实际上就是 不能是 的祖先，对逆排列计数，二项式反演容斥即可。
11.8 ABC
比较简单的一场，E 把每个点拆成四个方向四个点，然后建边最短路即可。
F 考虑从小到大填数，已经填了前 个，当前填第 个，考虑可以填的数，设 表示对于 合法的 数量，那么对于 的贡献就是 ，最后去重一下，总方案数是 ，其中 表示数字 出现的次数。
11.9 模拟赛
进场先看了题，T4 直接处理 A 数组求最大子段和可以有 ，暴力分不少，T3 应该是困难题，部分分这么多，找一找好打的打一下，T1 看着像换根，T2 感觉像 trie 树，类似的题被创飞好几次了，再研究一下。
看了 T1，大约 40min 的时候想到可以换根，维护每个点子树内到它路径全为 的数量，拆位换根就能知道每个点作为根的贡献，枚举统计贡献即可。
T2 想了很久，想到一个 的做法，写出来发现假了，又想了想 的东西，感觉实现太困难了没有写。
T3 写了一个比较好写的暴力，然后去看了 T4，写了 的线段树维护最大子段和。
T1出现失误，实现的太拉导致自己最后剩下的时间很少，T2 没有想出来，最后没有专心开一个题，主要问题不少，但是今天场上用 NOILinux 虚拟机测了 CE RE 等问题，发现 freopen 是有返回值的 /lh，还以为是 CE 了。
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...