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$ 。
于是这部分,枚举每一位的变化,很容易实现。
- 如果变成一个后面会出现的数
可以发现,这样的更改会影响到的区间是
Problem B
Unsolved.
Problem C
Unsolved.
Problem D
Unsolved.
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.