回到了 Luogu，继续刷 COCI……
上午
事实证明后三题是可做题，前三题不大可做。
T1 P6405
开始码了一个相邻的树木连边，边权设为相等的时间，然后点边互换跑连通块算大小，默认恒等边与任意边相等。后来想了想这样恒等边一多就会挂。
1.5h，2k，2 pts
于是放弃
T2 P4811
老师真的觉得我们大多数人有做黑题的实力吗？
T3 P7119
这个每个房子必须靠边的条件看着挺有用的，限制还是挺大的。
然而还是想不到怎么处理。
RLY 说是记搜。但是我在肝 T1 就没细想了。
T4 P7177
开始想从起点跑一个 dfs 把每个点关于源点流量的表达式求出来。当发现次数是 \(2^n\) 级时转战二分答案。
几天来唯一简单题。
T5 P8046
效仿二叉树，构造 \(k-1\) 棵满 \(k\) 叉树，这样一个数的父亲的编号是它 \(/k\)。
树高只有 \(\log n\) 级，连倍增都不需要，直接往上跳。
T6 P7800
题意转化就是用给定线段覆盖区间。
明显是个 \(dp\)。要么按左端点排序，要么按右端点排序，状态就设为填满前 \(i\) 区间覆盖 \(1-j\) 格的方案。
如果按左端点排序，中间会有一段空出来的，而且这个右端点会有后效性。所以按右端点排序。
左端点固然可能不接上，但因为后面的右端点更远，该线段并不会有后效性。
这题与互质的性质压根没关系呀，然而自己开始想时一直在想能不能用莫比乌斯函数配合容斥套前缀和做到能好的转移。
评价：莫反学傻了。
下午
T1
讲题的学长用可撤销并查集实现。
把相同的时间从小到大排序，每次统一处理一个时间时同高的树。将这样的树在并查集中合并起来。那些恒相等的树预先合并。这样可以省去处理恒相等的麻烦，虽然在不恒相等的处理上比较困难。然而，每个不恒相等的关系只会需要考虑一次，这让我们选择采取这种方式。
这题并不难想，但代码实现较难。
T2
无人讲。
T3
这是个记搜。
注意到给定一个矩形，如果要求切出来的每块都要靠边，一定有一刀贯穿整个矩形。
否则，任意一刀，都有另一刀拦住它。这样循环绕下去，在中间会出现一个不靠边的矩形。
切矩形的唯一要求是切出的要靠边。所以记搜时记录当前矩形四条边的靠边情况即可。
评价：能否发现性质，能否大胆去搜，是能否解决这道题的关键。
标签：排序,T1,相等,8.18,端点,矩形,靠边,集训 From： https://www.cnblogs.com/purplevine/p/16598742.html