【VP记录】CodeTON Round 5 (Div. 1 + Div. 2) A ~ H 题解

打得依托答辩，写出了

tag[x] += tag[x<<1];

状物

A

吃了一发罚时 /cf

感受一下，感觉只需要比较 $\sum a_i$ 和 $\sum b_i$ 的大小即可。

官方题解给出的证明是 $x-y,y-x$ 相当于 $x-min(x,y),y-min(x,y)$ 所以正确性显然。

B

由于是按位或操作，所以可以直接贪心。

C

显然有 $f_i = min(f_{i-1}, \max \limits_{j=1}\limits^{i - 2}[a_{j+1}=a_i](f_j+i-j)$。

所以把每个不同的 $a_i$ 的最大的 $f$ 值记录下来简单处理即可。

code

D

上难度了。挺不错的一题。

首先观察样例，手玩一下，发现答案的上界显然是从 $n$ 到 $1$ 的最短路。原因显然。考虑怎么构造，如果你手玩的足够仔细，你就会发现他大概是怎么样才会不选某一个点。发现其实你只有当一条只有一边有点被选的边选的次数顶满了才会舍掉那个点、边。于是我们考虑按照所有点与 $n$ 点的距离排序。从当前方案中每次删掉当前距离最近的所有点。这样做正确性还是相当显然。

code

E

赛时居然没调出来。

首先有一个很强的性质可以通过观察得到，就是选的所有三角形一定不交。

注意到 $k \leq 10^5$，提醒我们或许可以考虑设 $f_i$ 表示前 $i$ 行被覆盖完的最小代价。发现由于三角形不交，所以我们当前一定是这样子放三角形：

所以转移只需要枚举当前三角形的上角顶在了哪一行即可。

先考虑不放三角形的转移，非常好转移，把代价拆开直接转移即可，但我还是写了直接线段树优化。

然后考虑不放三角形的转移。发现每个区间要加上的代价不一样，拆不来。貌似没思路了？事实上，$n \leq 10^5$，所以你直接在线段树上区间加即可！

code

F

好题！

考虑题目中带有绝对值，直接做貌似不太好消掉这个绝对值。

人类智慧的一步是钦定所有黑点的重心为根。回顾重心定义，发现删掉重心之后的最大连通块大小 $\leq {n\over2}$。于是我们成功去掉了绝对值。考虑怎么放黑点才可以是的答案最小。拆一下贡献，发现每一个黑点会产生到根的距离乘二的负贡献。按距离根节点记录排序即可。

code

G

参见 link

H

感觉 1 不好看，所以不妨使 $x$ 在 $[-0.5,0.5]$ 范围内随机。这样所有的限制都变成了相加小于或大于等于零。

注意到对于 $x+y \leq0$ 而言，若 $|x| \geq |y|$ 则相当于 $x \leq 0$。所以我们只需要关注每个值的绝对值大小关系即可。直接暴力状压 DP 暴力检查计入一个数是否合法复杂度 $O(2^n n^2)$，稍微预处理一下即可变为 $O(2^nn)$

code