CERC

Preface 新年第一训，直接被干出shi来 开局经典梦游2h2题不知道在干啥，后面抄个网络流板子也能抄错卡个半天 后面2h祁神来救场几何，结果因为一个特判地方没加绝对值WA到结束都没看出来 鉴定为全队太久没摸键盘导致的，寒假有时间得再多练练的说 A. Attendance 开场就开到的不可做题 ......

题目链接：[Cerc2007] robotic sort 机械排序 前置知识点：文艺平衡树 具体的我们会将序号下标作为平衡树的键值，这样一来每个节点其实就是数组中的每个位置，又因为这个位置是具有有序性的，所以我要找某个位置的当前值是可以在树上二分出来的，同时考虑平衡树的一段子树打翻转标记，交换左右子 ......

题目描述 The aliens from outer space have (finally!) invaded Earth. Defend yourself, or be disintegrated! Or assimilated. Or eaten. We are not yet sure. T ......

Kitchen Knobs 首先，一个 trivial 的想法是，因为每个旋钮如果上面的数字并非全部相同则其必有唯一最优位置，故直接扔掉那些全部相同的旋钮，对于剩余的求出其最优位置。明显此位置是一 \(0\sim6\) 的数。 因为是区间同时旋转，所以转成数之后就是区间加同一个数。 一个经典套路是差 ......

1ay 1D。 这是一个跑不过双 \(\log\) 的单 \(\log\) 做法。 考虑双 \(\log\) 做法是怎么做的。令 \(a_i(1\le i\le n)\) 为给定的 \(x\) 坐标递增的点序列，开一棵线段树维护区间上凸壳，第 \(i\) 次查询相当于在 \([i+2,n]\) 区间 ......

考虑霍尔定理和广义霍尔定理： > 霍尔定理：对于一个左部图为 $X$、右部图大小为 $Y$ 的二分图（钦定 $|X|\leq |Y|$），存在边数等于 $|X|$ 的匹配的充要条件是：对于左部图的任何一个点集，右部图中和它相邻的点集大小都大于等于它（相邻的点集指的是所有点出边的并集）。 * 证明：必 ......

简单题。 每个点 $(i,j)$ 二分处理出 $p_{i,j}$ 表示在这个点上面能放的**最大的集装箱大小**，这部分二分就可以做到 $O(n^2\log n)$。 然后就相当于选择一条从 $(A_x,A_y)$ 到 $(B_x,B_y)$ 的路径，使得路径上 $p$ 值最小的点最大。 这是经典套 ......