初赛1
首先注意到打倒最大的那个人就赢了，所以之前要不断打与自己相同的来增强能力。
所以我们的算法就是贪心的选取当前能到达的最大的能力值（存在与其相等的）
然后这为什么是正确的呢？假设这样打不到$boss$，那么一定是出现了一个无法逾越的鸿沟
，现在这么早来到这里还过不去，再迟点儿就不用说了。
算法绝壁是每次$O（n）$。
考虑如何判断一段区间是连续的。首先最大值和最小值相差k，然后这其中的每个数都出现了一次。
那么考虑所有的k区间，用倍增求最大最小，然后出现了一次我们可以离散化后记录一下。
还有一种解法是这其中的每个数都不相同，用$hash$实现。也很兹瓷的样子。
傻逼题随便二分
傻逼题随便线段树
傻逼。。。好吧，我是傻逼。。不会做弃疗
计算几何？弃疗。。。
初赛2
首先我们要知道曼哈顿距离和切比雪夫距离的转化：
$$max(|x1-x2|,|y1-y2|)=|\frac{x1+y1}{2}-\frac{x2+y2}{2}|+|\frac{x1-y1}{2}-\frac{x2-y2}{2}|$$
变换一下字母就有
$$|x1-x2|+|y1-y2|=max(|(x1+y1)-(x2+y2)|,|(x1-y1)-(x2-y2)|)$$
对于这道题我们可以考虑转化一下，变成切比雪夫距离。
那么在曼哈顿上移动距离$1$相当于在切比雪夫上斜着移动一格。
显然答案具有单调性。那么不妨设当前二分的答案为$mid$。
那么XXX在$T$时刻必须处于$i$点周围边长为$2*mid$的一个正方形内。
所以说任何时候XXX的可行区域都是一个矩形，每次加入一个正方形求交。
一旦出现交为空说明无解。
根据样例稍微思考下可以知道只会在整点或者两个整点的中点。
所以一开始全部乘2即可。
傻逼MST，我就是不用prim你来咬我啊
傻逼bfs
这种含有等式的问题可以考虑列方程。
所以我们枚举首和尾，计算中间那部分合法不合法即可。
为了避免精度问题可以先乘以$1000000$然后转成整数做。
刚开始想偏了，想了一个线段树做法，就是用线段树来维护f[i][j]表示前i个已经不降，第i个<=j最少需要改变多少。
这个暴力的$DP$。应该也是可以过得。
后来发现我傻逼了，补集转化一下，修改较少的，不就是留下最多的？留下的必须是不降的，不就是$LIS$？
QAQ
为了做此题还去A了 BZOJ1367
卡内存卡的我真恶心，本来就打算用线段树合并水过的。。。
有一个结论就是
评论 (0)
