前言

今天是 CSP 测试，考前的最后一场测试。考得还可以，题目也非常好，很有趣。在这里总结一下，也相当于给 CSP-S 打打气。今天涉及到的内容有 [[dfs]]，[[基环树]]，[[可持久化线段树]]，[[分治]]还有 [[dp]]。
link

题解

今天考试，拿到了 260 pts，切了两道题，其实还可以再多暴力拿 30 pts，也是很可惜的。

T1

这道题就是 dfs，一边 dfs 一边修改。要注意一些细节，比如说走过的路就不能放障碍了。比较容易。

T2

这道题相对来说也没有什么比较难的地方，把染色拆分成两个操作，拆边和加边，先考虑树的情况怎么做，发现基环树只会影响环上的边的操作，思考环上的情况有什么不同。会发现只有当环都是一个颜色或者修改后都是一个颜色才会和一般的树的操作不同。

T3

这道题看起来也还行，考场上想到了一半，舍弃了 30 pts 的暴力分，我也不知道我怎么想的。正解是离散化用可持久化线段树来维护的 a 值，我是用的可持久化平衡树，都差不多，只不过看起来可持久化平衡树要慢一点，我都是卡着时间过的。

那么究竟应该怎么做呢？思考按 b 排序，然后我们就能想到一个的暴力。就是对于每一种长度，我们枚举 b 的位置，然后用一开始就建好的平衡树或者说线段树查询前几小的和然后取 min。

这道题最开始我猜测这个是单峰的，想用三分，但是后来发现不是。在最后 5 分钟我意识到 b 的位置可能是单调的，但是还是不会。后来看了题解，发现确实是单调的，也比较显然。那么怎么去做呢？题解给出的答案是分治，仔细一想，确实很对，先得到中间那个树的答案，另外的就分在两边了，非常 interesting。积累经验。

T4

这道题比较复杂，但是仔细研究一下可以发现这道题相当于在绍兴一中那个男生让女生排队的那道题的操作是一模一样的。不过问的问题是不一样的。但是这两道题的移动本质上来说是一样的。这也是我考完试后才发现的，挺有趣的。不过题解比较复杂，我也不怎么看得懂，还需要再理解理解。[[题解/绍兴一中 2023/7.1 测试#T2|绍兴一中 7.1 测试 T2]]。

后记

可以看到还是和高二有一些差距，我们要奋起直追，勇往直前，不怕困难，坚定理想，坚定信念，努力拼搏！