2020csp复赛游记

## 考前 考试前写了下堆线段树啥的板子然后早上睡了个懒觉，中午给自己灌了一批咖啡然后去考场了 ## 开考 提前$10min$给了密码，开始还想着今年$ccf$效率真高，结果全机房没人解的开 发现密码搞错了，搞的有点紧张 ## T1 $T1$题目看上去超级水，于是直接开写。 每次先一年一年跳，跳到少于$365$或者$366$了跳月份，月份跳完跳日。 然后写到公元后发现得特判，写到$1582$年发现又要特判。写完已经快$1h$了（这**签到题？？？）。然后测了下大样例，发现直接T飞起来了。 一看范围，$n<=1e9$,然后就又把$1852$年以后的每400年打了个包一起跳。以防万一开了$long$ $long$然后勉强（$0.7s$）卡过了大样例就没管了，复杂度$O$（$Q*1e4$）的样子（$1852$年以前跑暴力，$1852$年以后$mod400$年的天数以后跑暴力） 用时$1h$ $10min$的样子 ## T2 一看$c$最大$1e8$数组开不下，于是我考虑特殊性质。后来发现由于pi可能重复导致某些对应二进制位完全没在已经有的数字里面出现的数字可以选进去。 然后就直接写了$20$分的暴力。（由于$20%$的分$p_i$不重复所以我没管$c$，直接或一遍然后查询二进制下$1$的个数，最后求$2$的$1$个数次减去$n$） ## T3 看了下觉得$T4$更可做然后就去$T4$了 ## T4 看了$T4$直接上手贪心，然后写着写着发现$T2$总共就$1e6$组输入，可以排序跑二分，然后又回去写$T2$ ## 再写 T2 又认真读了题，发现$m$最大$1e6$可以排序然后二分查找于是就又重新写$T2$。搞了个数组存种类，然后必须选的或一遍把对应饲料$log_2n$二分查找存到数组里面。 然后把所有要求扫一遍，如果一个二进制位所有需要的饲料都在数组标记过就把这个二进制位统计到$cnt$里面。 最后输出$2$的$cnt$次$-n$ # 大样例好像只要把所有不需要任何要求的位置和已经有的位置统计下，求$2$的次方就行，所以最后一步有点慌。 那时候有点紧张，人有点晕，但是为了节省时间带进去的吃的也没去吃,写代码逻辑运算写错好几次，还是应该吃点东西的。 复杂度$O(nlog n)$ 写完差不多过去了$2h$ $50min$ (这时候隔壁那个初二的兴奋的喊了句他终于把$T1$调出来了) 回家查了下好像极限数据会爆$unsigned$ $long$ $long$。 为了防止爆炸我开了没开$long$ $long$开了无符号，结果没想到还是会炸。（我**） ## 再写T4 回到$T4$继续写贪心，维护一个小根堆一个大根堆（考前写的板子用上了$QwQ$），每次取两个堆顶相减，看是否会小于小根堆新的堆顶。小于的话输出当前数量，否则吃掉以后继续下一步。 小样例都过了以后去跑大样例，发现一半的数据小了$1$。然后去查代码，发现堆写挂了（$stl$的重载啥的完全不会所以堆只能手写），调了$10min$的堆。后来就一直在调大样例直到最后。 出了考场才发现不能贪心，大样例过不去不是因为我代码问题。 后来发现我的贪心原来是能过$20%$的分的，结果为了调大样例把这$20$分也搞没了。 于是$n=3$ $20%$的部分分也没了，$T3$的暴力分也没了。 预计 $100+90+0+$(玄学)$≈200$ ## 总结 还是有点小紧张，后面思路不清晰。 大样例过不了应该考虑思路的问题，死磕贪心导致T4爆炸。 然后在$T4$耗了太久，$T3$暴力也没写。 还是应该先打了暴力再调正解的。 ## 关于题目 ### 以下纯粹个人看法 很多人说今年$T1$很难，$T2$更像签到题。但是我觉得其实算法方面$T1$更简单（隔壁那个初二说他最后只做了$T1$,$T2$只写出来暴力）。毕竟$T1$是个纯暴力(虽然码量和用时确实惊人)。 $T3$、$T4$相对于前两题难度跨越有点大，前两题都挺水的结果后两题暴力分都没多少。 $T4$有那么亿点点迷惑性导致我调了一个多小时的贪心。 # 附 在写这篇游记的时候发现T2题目里有这么一句话 ``` 数据保证所有ai互不相同，所有的pi互不相同。 ``` 然后…… 我的二分白写了，复杂度被我从$O（n）$搞成了$O(nlog n)$。最后处理$p_i$重复的那坨东西但愿别对结果造成影响吧。 ~~所以其实我那20分的代码交上去就可以过的应该~~ # 赛后 评测(洛谷)$40+70+0+0=110$ $T1$三段的边界全挂了，只有40分 $T2$用了左移，后来把左移改成了卡速米。结果有个地方没改，然后爆了一半的数据。 --------------------------------- hz oier,感觉凉凉了