CTU Open Contest 2019

From EOJ Wiki
Revision as of 04:04, 24 February 2020 by WeaverZhu (talk | contribs) (→‎Problem E)
Jump to navigation Jump to search

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

暴力枚举答案