同样地，因为昨天基本没做题，并入今天的闲话。
昨天入手了人格解体，真的是非常优秀的作品，很喜欢！
打完 USACO Pt 组了，感觉比去年（指 USACO22FEB）的简单一些。去年只会做半道 T1，菜啊。
随便写一下 USACO 题解吧：
铜 T1：签到。
铜 T2：不会！随便猜了个结论过了！（贪心往后放）
铜 T3：不会！随便猜了个结论过了！每次暴力枚举一个合法的切分位置并操作。
银 T1：不会！随便猜了个结论过了！dfs 一下树，把要移动的位置之间的边建出来拓扑排序。
银 T2：不会！随便打了个表过了！可以发现每个位置相对独立，而一个位置胜利的条件是模 \(4\) 不为 \(0\)，最小步数分模四余数讨论一下，为 \(0,2\) 每一步都会取 \(2\)，\(1,3\) 一定是取与其余数相同的最大素数。
银 T3：把相同的段缩在一起，而我们又知道相邻差值的绝对值，也很容易判断相邻两个差值的符号正负性是否相同，就做完了。
金 T1：比较喜欢这种题。如果确定了哪些奶牛参加，我们一定是按照 \(X\) 从小到大喂冰淇淋。那么将所有奶牛将 \(X\) 排序后，找到最后一个喂冰淇淋的奶牛，其前面邀请的奶牛一定只喂冰淇淋，后面邀请的奶牛一定只给钱，因此前缀后缀分别做个背包就好了。
金 T2：直接 \(O(n^2\log n)\) 搞过去的。枚举点对靠左的点 \(p\)，计算出它到右边所有点的斜率，那么其合法右端点一定是非严格前缀最大值。由于只有单点加操作，我们可以用线段树暴力找到后面不再合法的位置并删掉。（我感觉维护笛卡尔树结构可以均摊，把 \(\log\) 去掉，但没细想）
金 T3：每次删掉最小度数的点，然后把这个过程时间倒流，并查集维护连通块大小就好了。
铂金 T2：可以发现操作过程形成了若干个团的结构，初始我们将每条边看成一个大小为二的团，而删去一个点不过是将其相邻所有边的团合并，启发式合并就好了，两个 \(\log\)。（听 hzr 讲能 \(1\log\)，膜拜 hzr）
84 USACO22DEC BREAKDOWN P
本场最难的题。
不妨讨论 \(k=8\) 的情况，其余情况做法是一致的。
首先有个显然的时光倒流，变加边。
折半，我们在外层枚举折半点 \(k\)，分别维护 \(1\) 到 \(k\) 与 \(k\) 到 \(n\) 经过 \(4\) 条边的最短距离。
两种情况是是一致的，不妨考虑 \(1\) 到 \(k\) 的距离怎么维护。我们再次折半，对于每个点，我们维护 \(1\) 到 \(x\) 与 \(x\) 到 \(k\) 经过 \(2\) 条边的最短距离，同样只考虑第一类距离如何维护：
加入一条边 \((x,y)\)，我们讨论其作为第一条边还是第二条边。若为第一条边，这类边只有 \(n\) 条，我们枚举每个点作为第二条边的中点，并更新距离；若为第二条边，直接更新当前边终点的距离就好了。
每个 \(k\) 的复杂度都是 \(O(n^2)\)，总复杂度 \(O(n^3)\)。
当时以为代码会很难写，写完才发现只写了 2k。
85 USACO22DEC PALINDROMES P
86 uoj#750. 【UNR #6】小火车
标签：12,21,17,T2,T1,枚举,维护,奶牛,log From： https://www.cnblogs.com/xiaoziyao/p/16995287.html