CCF CSP 202109 @ HNU 游记

此处所指的是大学组的 CSP,举行于 2021 年 9 月 19 日。

暴力出奇迹,骗分过样例。

暴搜挂着机,打表出省一。

NOIP 名言

又是一年 CSP 时,抱着当年 OI 攒下的一点点老本,以 “过 150 就算赢” 为目标,本着暴力出奇迹的原则,参加了学校统一组织的考试。

关于考场

考场在湖南大学前进楼机房,设备可以说是很有年代感了。目测 17 寸左右的低分辨率显示器,2C2T 的 Pentium E5700 CPU, Windows 7,再搭配上 Orwell Dev-C++ 5.11,整个简直像是上个时代的产物。由于远古的 TDM-GCC 4.9.2、调用 STL 时的糟糕体验和层出不穷的 bug,每次用 Dev-C++ 调试,我都想打人…… 如果觉得 Visual Studio Code 不开源,哪怕装个 VSCodium 也好啊……

哦,顺便提一嘴,Orwell Dev-C++ 是有正统续作的,由 Embarcadero 开发,终于能用了:

Embarcadero/Dev-Cpp

Java 环境好像也没有 IntelliJ IDEA,Python 好像也只能用 IDLE,所以 C++ 环境也不算差?

还行啦,CPU 再烂也是独占的,起码比信息院机房的瘦客户机好用多了。

第一题

逐个输入,每个数都加入最大值,遇到比上个数大的就加进和的最小值。画图好理解。

第二题

先试了暴力方法,$p$ 从 $1$ 到 $10000$ 循环(没必要也千万不要把数改成 $0$),直接统计大于 $p$ 的数的区间数,70 分,TLE 三个点。

然后尝试搜索的思路,类似于暴力思路的改进,仍然是搜索大于 p 的区间数,但不会搜索整个数组,而是在上一个 p 所划分的区间内搜索。比如 1 3 5 3 6 0 2 8,$p=1$ 时划出 1 3 5 3 6 和 2 8,然后分别在这两个区间内继续搜索 $p=2$ 的情况即可。

误以为区间数是随 $p$ 先上升后下降的,试图用 BFS 控制搜索深度,幸亏 BFS 手生,没写完就发现并不是我想的那样(狗头保命),遂停止。

换用熟悉的 DFS,结果仍然 TLE 三个点。原因是每次搜索,$p$ 的步进都是 $1$;事实上,仍然使用上个例子,$p=2$ 得到区间 3 5 3 6,区间最小值是 3,那么 $p=3$ 的区间数 + 1,然后直接搜索 $p=4$ 的情况即可,不必再搜索 3 的情况。

DFS 优化完成后可以达到 100 分。

第三题

阅读理解越来越难了,做完前面的还剩 2 小时左右,估计读都读不完。

没做。

第四题

骗得 20 分。有 20% 的数据,每个卡的爆率相同,易得期望就是 $n$。

还有 20 分比较简单,不知道为啥暴搜没过,5 个牌还会 T,真是……

第五题

瞄了一眼,似乎需要可持久化的数据结构,但有一个点没有操作 2,也许可以暴力存储历史数据。即便如此还是没写出来,放弃了。

总结

暴搜流派 yyds!