蒟蒻的CSP 2019游记

## $\text{2019.10.19}$ 非常早就起床了。再复习了一遍初赛知识。 上午参加了CSP初赛。因为我所在的考场没有限制使用电脑上其他软件的要求，所以和组合、计数有关的题都用了Dev-C++。后面的看程序判断正误/不全程序简直就是一脸懵。 其中有一个并查集的程序有漏洞，首先没有判`u==v`，其次在合并的时候没有清空$cnt$数组。导致当场有两道题，其中一道是判断`cnt[i]`是否恒$\le n$（没掉进坑里），另一道是时间复杂度，被坑了。 因为全部是选择题，所以选了一些看起来比较顺眼的选项，就直接提交了。 考后，群里有同学说他周围的人人均$90$，我自测得了$79.5$，感觉过不了了，但是$\text{BJ}$以往的分数线都很低，去年只有$35$分，今年再高也高不到哪里去。然后我看到论坛里有人问$60$分能不能过，很多大佬都说“稳了”。因此我并没有对我能否进复赛有太大的把握。 ## $\text{2019.10.24}$ 成绩出来了，比我预测的低，$76.5$，但还是远高于$58.5$的晋级分数线。 全市（省）只有六个人阿珂，其中三个是我校的。~~我们教练没看懂那道状压的程序，只拿了82分，以致于有一个初一的分数都比他高。~~ ## $\text{2019.10.25\ \~ \ 2019.11.14}$ 这段时间的晚上加课比以前频繁了，基本上都是模拟赛。但是我的结果并不理想。~~但至少没有爆过0。~~ 11月2号打了一场月赛，比赛分直接加到了$51$，排名猛扎进前$250$。 11月7号CF上蓝了，开心（没错以前一直是specialist）。但晚上的牛客比赛爆零了，T1写的正解被同学忽悠了一遍，就改错了。~~然后同学**们**的T1集体爆0。~~ 11月9号又打了一场月赛，这次由于某些原因20:40才上线，所以非常仓促。T3正解没时间想了，直接打了暴力。最后$100+100+17+8=225$分。 为什么我们学校的期中考试要在11月11日这一周……~~9号月赛T3的“Y校”肯定是我们学校了。~~ 周三又打了一场月赛……具体就不多说了。 ## $\text{Day 0 (2019.11.15)}$ 今天一整天打了非常多的模板，~~打到怀疑人生~~   emm貌似混进了一些奇怪的东西 ## $\text{Day 1 (2019.10.16)}$ 考场上先用了一个小时建文件夹+对拍程序+T1，发现忘了对拍怎么写（为什么学校机房只有我的位置的电脑装不了linux导致无法练习linux对拍）（大哭） T2想了一个半个小时，写了一个$\Theta(\sum depth_i)$的暴力，具体是处理出dfs到第$u$个点时的括号串，定义一个数组$height$表示当前括号串的“高度”。从根节点往$u$的顺序，如果是左括号，当前位置的“高度”+1，果是右括号，先标记当前位置的“高度”，再将下一个位置的“高度”-1，然后再从$u$到根节点扫一遍，遇到高度小于$u$的节点跳出循环，不再往上搜；遇到高度和当前相同的，而且是左括号的，答案+1。为了优化，采用了回溯法。然后我发现可以用一个数组记录出当前能从后往前被访问到的每个高度的节点个数，也用回溯就优化到了$\Theta(n)$。 T3用`next_permutation`水过了10分。 考完听到神仙同学们说T2用什么倍增啊二分啊dp啊什么都有，还说样例特别水，不拍相当于爆零……感觉我的乱搞做法并不是太准，而我考场上手推了很久证明我的做法，但没有成功，但我还是觉得我的这种做法没有问题。 估分$\color{lightgreen}100\color{black}+\color{lightgreen}100\color{black}+\color{red}10\color{black}=\color{yellow}210$ 颓了一下午的洛谷+QQ，~~感觉非常anti-aoligei~~ 晚上再按照原来的思路打了一遍，测了一下T2的民间数据，竟然AC了，再提交到了牛客网上，竟然也AC了。看来这道题同学们想的都太多，如果是我的话最多也只给这道题评个$\color{green}\text{普及+/提高}$。 民间数据：$\color{green}95\color{black}+\color{lightgreen}100\color{black}+\color{red}10$ ## $\text{Day 2 (2019.10.17)}$ 一看T1和T2，一个小时之后发现都不会，就去搞T3。 T3写的40分暴力调了一个小时，55分又调了半个小时。看到快没时间了，直接写了一个T1的32分暴力。因为T3的75分看起来比T2的12分更加好写，就去写T3的75分。 又调了很长时间，发现式子推错了，又想不出来正确的推法。考试结束之后才想起来：原来我只想了只删最后一层的答案…… T2考崩了，预估$\color{orange}32\color{black}+\color{red}0\color{black}+\color{yellow}55\color{black}=\color{orange}87$ 两天加起来$292$，比去年还差，我太难了。 民间数据：$\color{orange}32\color{black}+\color{red}0\color{black}+\color{orange}40$ ## $\text{2019.10.18}$ 发代码了，我用我的考场代码交了一下洛谷自测，D2T3链斜挂了，就这样挂了15分。总分$277$。感觉省一没希望了，$\huge{\text{AFO}}$。