Table of Contents
恭喜 PKU 连冠！太强了 Orz。。
- https://codeforces.com/blog/entry/134044
- https://github.com/SnapDragon64/ACMFinalsSolutions/tree/master/finals2024
Problem B. Bingo for the Win!
签到题。只需要枚举最后一张牌，然后看编号最大的有这张牌的选手即可。
（据说 o1 也会这个题 Orz。）
Problem C. Citizenship
签到题。要处理时间戳，代码肯定比上一题长。
Problem F. Friendly Rivalry
二分答案，然后 dfs 求出所有连通块，然后类似拔河那个题，看这些连通块能否凑成容量为 n 的背包。
最后单独构造一下方案即可。
Problem D. Doubles Horseback Wrestling
给定 n 组区间，问可以最多凑出多少对区间，使得可以从这对区间中各取一个数和为给定的 s。
挺有趣的题，首先一般的匹配算法肯定不行了，考虑扫描线贪心。最后每组区间中一定有一个数取 <= s/2，不妨我们从中间分成左右两侧。
假设所有左侧的区间都是单点，那么贪心策略显然，就对所有右区间进行扫描线，从大到小扫描，然后每次拿潜力最小，也就是左端点最大的区间即可。
考虑一般情况，那么需要在左右两侧同时向中间扫描，贪心策略不变。注意到现在有些区间可能会在两侧的事件中同时存在，因此需要开一个全局 used[] 数组记录一下，然后每次贪心要 while 循环，找到第一个没用过的区间进行匹配。
最后再把剩下来的元素两两匹配即可。
Problem J. The Silk Road . . . with Robots!
给定一个数轴，然后依次安排一些事件，表示某个位置刷新一个机器人，或者某个位置刷新一个收益为 c 的资源点，机器人可以花费 1 代价移动单位距离，问最大收益是多少。
这个题极易读错。。注意到每个机器人居然可以 reuse，那么地图上的资源点实际被这些机器人覆盖，每个机器人覆盖一个区间，机器人可以仅左、仅右，或者先左再右、先右再左四种方式构成区间。那么显然这个东西可以用线段树维护区间来动态 dp，转移类似矩阵乘法，难点是构造单点的状态，建议拆成区间和单点，2n-1 个状态来处理，可以写的非常对称。
Problem I. Steppe on It
这个题我也读错了，读成 k 个点然后距离和最小了，囧。
那么只要最大最小显然还是二分答案树 dp。
据说是 COCI 原题，https://www.luogu.com.cn/problem/P8314，囧，还是非常容易写错的。。。
Problem A. Billboards
无聊的几何题，每个赞助商有一个分段线性函数设置偏好，且只需要在它的评价下取一段函数值大于 1/n 的区间即可。
我们只需要贪心的每次在左边找最短的一块符合某个赞助商要求的区间即可。
Problem H. Maxwell’s Demon
封闭空间分成左右两半，初始有一些粒子，在边缘会完全弹性碰撞，中间的墙的某个位置有一个 door，到粒子运动到门时，你可以决定是否让它通过，当同一时刻有多个粒子经过门时，你必须同时决定它们是否能够通过。每个例子初始是红色或者蓝色，问是否能让所有红色粒子在左边，所有蓝色粒子在右边，如果可以，最短时间是多少。
发现难点主要是粒子同时撞到门的情况，假设不考虑这种情况，那么只要算出每个点最早撞到门的时刻即可。
现在考虑这些连携的情况，我们发现这些例子现在的状态纠缠在了一起，我们虽然没法在当前时刻立刻决定是否通过门，但是好消息是否通过对我们的计算影响不大，因为门的两侧的运动轨迹是完全对称的，粒子通过门与否不会影响这些例子下次经过门的时刻。
我们用 01 向量表达每个粒子初始是否需要经过一次门，那么问题就变成了，随着时间的推进，我们不断加入一些 01 向量，问何时当前向量组能够线性表示出初始向量，而这只需要维护一组 xor 向量基即可。
