此处所指的是大学组的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开发,终于能用了:
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!