CSP-S 2019 游记

### 2019-10-18 刷了一遍Noip2018提高组初赛，感觉挺难的qwq(去年我还在PJ呢) 我：啊啊啊啊啊啊！！！！！！完啦完啦完啦！！！！！！ 慌的一批…… ### 2019-10-19 一大早就去校门口了，走之前还去班里面和同学打了一声招呼。 上了车就拿着手机开始刷前些年的初赛题目(顺便玩了一下RS) 在赛场门前看了几位学长玩狼人杀，之后就去考试了。 仍然慌的一批 拿到考试卷了，真的没想到这次考试会这么简单qwq 之后就放慢速度压线做完卷子，被效率定义坑死掉到了96分 我到现在还在纳闷：难道效率算的是最坏复杂度吗？为什么不优化并查集是$O(n^2)$的…… ~~管这些干啥，进了就行了，哪来这么多废话~~ ### 2019-11-15 在和文化课对抗了数日之后，终于开始复习了！！！ 之后就是看了Noip2019提高组复赛，就睡觉了(?) ### 2019-11-16 Day 1 之前说是一起去，以为是坐车，之后倒成群结队地挤在地铁里 在电脑前眼睁睁地看着监考员两次写错密码…… 之后适应着灵敏度极高的鼠标把rar解压了 一看题 OMG第一题是来干什么的？一上来我就不会？ 盯着数据2分钟后我发现了一个天大的秘密： 答案的二进制和k很像！ 之后3分钟YY了一个$O(n^2)$算法 ``` A -> K的二进制表示法 for i from N-1 to 0 if(A[i]) for j from i-1 to 0 A[j]^=1 print(A) ``` 之后还AC了！ 实际上这道题有三种做法（指计算）： $O(n^2)$ 如上 $O(n)$ 直接枚举，计算每一位是1是0就行 $O(1)$ `print(k ^ (k >> 1))` (from @Vexalwig_Goodwcoffin ， 这是ta准备的一场比赛中的一道题目，于是就有了这个算法) 好的回到现场，$8:40$看了T2 什么题啊这是！括号匹配？树？ 根据我的表达式学习进度来看，括号匹配是没有问题的，但是树…… 上了厕所回来，想到了dfs+dp做法 直接开始dfs，暴力存放左括号比右括号多的个数，开了桶记录一下，再瞎搞一下就好了 由于每一次dfs中只有枚举儿子和$O(1)$的添加删除，之后就是$O(n)$的了 在小样例上输出$800+$，调了20min 之后就是喜闻乐见的RE时间，用了gdb调试才发现是垃圾电脑爆栈了 再打开大样例一看，这不是才******(太臭已屏蔽)个点吗？哪里爆栈了…… 然后就开T3了,此时是$10:00$ 什么鬼！？交换数字?删边？ 之后就开始使用贪心大法狂猜正解，4数据的样例中只AC了2和3 到了考试结束都忘记测试能不能骗到sub2和3 expect : 100+100+?(我的第三题代码正确性真的玄学) # 2019-11-17 自己去到了考试现场 顺利打开文件，把三道题都看了一遍，觉得只有第三题有思路。 我想到的是计算每个点对答案的贡献，要求的是快速计算一个节点的每一棵大小在一定范围内的子树个数，把复杂度乘上n 但是我只想到$O(n^2)$做法……到考试结束还有一个区间没推出来……………… expect:? 之后就是漫长的思考过程，在最后$1h$我终于开始敲代码（之前打了Bint模板） 第二题我用了错解贪心，打Bint和代码总共花20min,没调试就走了 expect:?(AC了前两个样例) 第一题的话……$O(m^n)$算法放上去，没了（没时间想骗分DP啊啊啊） expect:32 到了考试最后甚至伸个懒腰按到了T3文件输入输出那里，多输入了一个字符，还保存了……最后跟监考员斗智斗勇，最后的反馈是：没有大问题……最后改回来收上去了，但是还是心有余悸。 $\Sigma = 100+100+?+32+?+? $ $\ \ \ \ \ \ \ \ \ 100-100-25-32-0-0 \rightarrow\ 257\ \ at\ \ least$ 这个分数，在GD还有救吗…… 于是，一次重要考试炸了。 其实下午的国家体育测试也不咋地……