2017中国大学生程序设计竞赛-秦皇岛站补题记录

这篇日志仅仅记录一个菜鸡赛后补题的过程,哪里写得不对请各位指出。
题目按通过人数排序(但不代表题目难度)

L. One-Dimensional Maze

通过人数:247/355

要么把$[2,m]$的都变成L,要么把$[m,n−1]$的都变成R
时间复杂度:$O(n)$

C. Crusaders Quest

通过人数:234/428

枚举删掉字母的顺序,取得分的最大值即可。
时间复杂度:$O(1)$

E. String of CCPC

通过人数:221/603

可以发现,最多加入一个字符。先匹配CCPC的个数,然后将匹配到的中间的CP做上标记(变成$)若能再匹配CCCCCPCPC中任意一个则答案加一。
由于模式串很短,所以可以直接暴力匹配。
时间复杂度:$O(n)$

M. Safest Buildings

通过人数:196/605

可以发现概率关于距离递减,且在$≤|R−2r|$时取到最大值,所求即为$\max(x ^ 2+y ^ 2,(R−2r) ^ 2)$最小的那些点。
时间复杂度:$O(n)$

A. Balloon Robot

通过人数:87/173

容易发现,每次过题的等待时间不会超过$m$,所以我们就可以把转很多圈的情况等价成转一圈的情况。这样每次提交就只有两种情况,在第一圈得到气球,在第二圈得到气球,这个是由机器人的起始位置决定的。于是我们可以知道起始位置一定在某个过题位置,把这些过题位置排序,先暴力扫一遍得到第一个位置起始的总不满意度,然后向后递推每个起始位置的总不满意度。
时间复杂度:$O(p\log p)$。

G. Numbers

通过人数:75/502

从二进制最高位开始贪心,考虑当前位是否可以为$0$,如果不能为$0$就在当前位填入尽可能多的$1$。
C++高精度乘法用FFT常数太大,要压位,或者直接用java高精度。
时间复杂度$O(\log n * 高精度复杂度)$

H. Prime Set

通过人数:26/243

先考虑选出贡献为$2$的对,如果不考虑$1$和$1$配对,就是个显然的二分图匹配。对于剩下的数字,先看有没有$1$和$1$因为这个贡献是$2$,然后再去找贡献为$1$的。
时间复杂度:$O(n^2)$


后面的题目太难了我也没补╮(╯▽╰)╭

捐助作者