2020-2021 ACM-ICPC, Asia Nanjing Regional Contest

发表于 2021-10-20 更新于 2021-10-25

链接

打垮了，又被 Clovers 带飞了。

签到题。

设每做 $k$ 个处理一次，那么有代价 $w=nk+m+\frac{w}{(1-p)^k}$，移项得 $w=\frac{nk+m}{1-(1-p)^k}$，容易发现这是一个单峰函数，直接三分即可。

诈骗题。首先当然用总方案减去不合法方案。也就是现在要统计不存在这样一个矩形的染色。

手模一下发现 $n=6,m=6$ 很难构造出来，打个暴力发现真的无解。

容易发现 $n>8$ 时只有 $m=1$ 有解，所以特判 $n,m$ 中有一个 $1$ 的情况，对于其余 $n,m\leq 8$ 直接爆搜即可。

复杂度 $O(能过)$。

吉司机线段树板子题，没什么好说的。

构造题。打一个 checker 可以发现最长直径往往会成为限制。换句话说应该构造一张图使两点间最长距离尽可能长。

第一想法显然是绕圈圈，但这样只能达到 $15%$ 的成功率，因为这种情况下墙的数量太多了。关注到题目只要求四联通构成树即可，所以先往左上再往左下这样走更优。可以得到 $30%$ 的成功率。

考虑随意取一个生成树，此时度数大于 $\frac n2$ 的点至多只有一个，不断调整直到满足条件。注意此时可能会出现另一个度数大于 $\frac n2$ 的点，但这两个点一定相邻，特判这条边即可。

实际上考虑正常生成树，不过每次加入要求度数不能超过 $\frac n2$，可以发现随机序列下正确率不低，多 shuffle 几次就过了。

考虑总共只有 $2n$ 个点，暴力两两判断能否连边，如果可以连边就连单向边，边权为其斜率。这样可以得到一张图，而答案就是其最小瓶颈路。

直接二分答案然后 dfs 即可。复杂度 $O(n^3+n^2\log n)$。

嘴巴一下，没有写过。

考虑最后实际上是选择一个矩形，使得所有点在矩形严格上下左右方向，代价是矩形周长减去到某个端点的曼哈顿距离。

考虑枚举下边界，维护每个上边界对应的左右边界之差。可以发现下边界上移过程中的代价是限制左右边界不能小于某个值，可以发现对应到上边界就是删去某些上边界，可以用 set 维护。

具体细节有一点恶心。

考虑求出点双。分类讨论：

细节有亿点恶心。