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)
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 (+)