XIX Open Cup named after E.V. Pankratiev. Grand Prix of China

Problem A

Solved by Xiejiadong. 03:10 (+2)

题意：可以选择其中一个数 $a_i$ 改成数 $y$ ，使得 $|a_i-y|+\sum_{i=1}^{n}c_i$ 最小，其中 $c_i$ 表示 $a$ 数列更改以后前 $i$ 个数中不同数的数量个数。

题解：可以发现，更改只发生在原数列前缀不同数的数量个数增加的位置上，为了让答案变小，肯定不会产生新的数，分类讨论：

• 如果变成一个以前出现过的数

因为本来当前位置为新出现的数，于是可以使得从当前位置到当前位置上本来数的第二次出现位置的前一位整体贡献 $-1$ 。

于是这部分，枚举每一位的变化，很容易实现。

• 如果变成一个后面会出现的数

可以发现，这样的更改会影响到的区间是更改后数第一次出现的位置到原来位置上的数第二次出现的位置（不是合法区间就不会有贡献），同样贡献也是 $-1$ 。

假设本来第 $i$ 位上的数为 $a_i$ ，即将变成 $a_j$ ，$a_j$ 第一次出现在位置 $j$ ，$a_i$ 第二次出现在位置 $k$ ，于是对原答案的修改就是 $|a_i-a_j|+\sum_{i=j}^{k}i$ 。

绝对值不好处理，考虑拆掉绝对值。离散，分别维护前缀和后缀最小值，针对每一个 $a_j$ 查询符合要求的最优贡献 $a_i$ 即可。

Problem B

Unsolved.

Problem C

Upsolved by Kilo_5723.

题意：给出 $n$ 个点，用 $\lceil \frac{n}{2} \rceil$ 条直线将每个点都分到独立的块上。

题解：先用一条直线将 $n$ 个点均分成两半，然后两边各做凸包，每次取凸包公切线上的两点划分出去。

Problem D

Upsolved by Kilo_5723.

Problem E

Unsolved.

Problem F

Solved by Weaver_zhu. 03:18 (+6)

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.