CTU Open Contest 2019

Problem A

Solved by Kilo_5723. 00:36 (+5)

题意：求在所有由 $A$ 和 $B$ 组成的 $K$ 位数中，$C$ 出现的次数。

题解：如果 $C\neq A$ 且 $C \neq B$，则不会出现。

否则如果 $A=B$，则出现 $K$ 次。

否则，出现 $K \times 2^{K-1}$ 次。

Problem B

Solved by Xiejiadong. 02:34(+)

按照题目意思计算即可。

题目确实比较难理解，看着样例大概猜了猜。

Problem C

Solved by Kilo_5723. 03:04 (+3)

题意：求矩形和圆形的面积交。所有点的坐标和半径都是绝对值不超过 $1000$ 的整数。

题解：比较方便的做法是将原点重定位到圆心，把矩形分割成 $1 \times 1$ 的正方形并旋转到第一象限下半部分，这样正方形被圆切割就只有三种情况。

Problem D

Solved by Xiejiadong. 04:08 (+)

题意：删掉尽可能多的边，使得每个点都在源点到汇点的一条路径上。

题解：考虑最坏情况下，每个点都需要一条出边和入边（除了源点和汇点），也就是需要 $2n-2$ 条边。

但是图中存在的某些边可以减少这样的边，即本来需要 $a-$ 汇点 以及 $b-$ 汇点，但现在可以通过 $a-b-$ 汇点来减少所需要的边。

显然这样的一组关系可以减少一条边。

考虑把所有的点拆成入点和出点，于是在上述要找尽可能多的关系，其实就是二分图匹配。

Problem E

Solved by Weaver_zhu. 03:37 (+1)

Problem F

Solved by Kilo_5723. 02:05 (+1)

题意：给定数轴上 $n$ 个点，要移动点使得每个点间隔为 $k$，求最小移动距离。

题解：显然移动前后点的顺序不会变，则求出每个点如果不改变位置，其对应的起点位置，并对这些起点位置排序。由于每个点关于起点位置的移动代价都是 V 形的分段函数，可以证明最优的起点一定是所有起点位置的中位数。

Problem G

Solved by Xiejiadong. 01:33 (+2)

题意：找一个最长的子串，使得这个子串里面所有的字母至多只有一个出现了奇数次。

题解：因为只有 $20$ 个字母，考虑状态压缩。

出现偶数次和奇数次，考虑到可以使用异或来做。

而至多出现一个出现奇数次的字母，考虑直接枚举这个字母是哪个。

记录每一个状态的最先出现的位置，直接查找即可。

Problem H

Solved by Xiejiadong. 02:53 (+2)

相对比较大的模拟题。时间顺序比较难处理（主要是题目没讲清楚）。

Problem I

Solved by Weaver_zhu. 4:07 (+3)

Problem J

Solved by Weaver_zhu. 02:20 (+)