CSP2019 游记

one last chance

Day 0

一觉睡到中午，感觉明天早上要起不来了。

吃过午饭，带着 wjyyy/ouuan/EternalAlexander 的 XR 抱枕冲到华科。

由于到的比较早，所以试机的地方还没有多少人，随便找了一排坐下。

然后华一和外校的到了，面了 ustze/EternalAlexander，然后惊奇的发现没几个认识的人了。

突然想到这是我参加的第一场没有 wjyyy/Dew/lbw/hyf/Vixbob/Edt 的 OI 比赛，有些伤感。

随便敲了点板子，对拍了一下，感觉没啥问题，除了键盘极其不习惯以及好久没用 Win7 了很自闭。

走的时候叫 EternalAlexander 把 ouuan 和他的抱枕都拿走了，zgjjj 带走了 wjyyy 的抱枕。

然后就回家了。

今晚要早点睡，大概十点？虽然好久没有用这么早躺下过了，鬼知道睡不睡得着。

CSP2019 rp++！

Day 1

果然混到两点还没睡着。

但是早上六点爬起来感觉精神状态还不错。

吃完早饭冲到华科，面到了 quank 和 KS。

然后就进场了。

进场之后先检查机器，打了板子码了快读，然后拿快读和 cin 的 a+b 拍了半天，感觉没啥问题。

然后发密码 Ren2Zhen0Si1Kao9?。

认真思考 2019？

奶一口明天 Zi9Xi1Da0Ti2!，好像短了点 2333。

然后看题：http://www.xht37.com/wp-content/uploads/2019/11/CSP2019-S2-day1.pdf。

T1 读完大概就知道是个简单模拟了，看了看数据范围，$n \le 64$，感觉有坑。

码码码，一测大样例，果然挂了，发现是 1 << n 的锅，改成 1llu << n 就过了。

然后造了一组最大极限数据一测，没挂，很稳，扔了。

开 T2，咋 T2 就来树啊。

读完题，感觉上就不太难，大概想了几分钟就会了：

考虑以每个节点为结尾的合法括号子串有多少个。

以 ( 为 $1$ ) 为 $-1$ 做一个树上前缀和，设点 $x$ 的前缀和为 $s_x$。

则以 $x$ 结尾的合法括号子串的开头 $v$ 需要满足：

1. $s_u = s_v$。
2. $v \to u$ 的路径上所有点的 $s \ge s_u$。

遍历一遍树，用一个 $c$ 数组记录从根节点到当前节点的所有 $s$ 出现的个数，同时用一个 $p$ 数组记录每一个 $s$ 上一次出现的位置。

那么对于一个点 $u$，以 $u$ 结尾的合法括号子串的个数应该为，在点 $u$ 的时候 $c[s_u]$ 的值（去掉 $s_u$ 本身）减去在点 $p[s_u-1]$ 的时候 $c[s_u]$ 的值。

前者可以直接加到 $ans_u$ 中，后者则需要等到回溯到 $p[s_u-1]$ 再从 $ans_u$ 减掉，用一个 vector 记录即可。

其中，更新 $p$ 数组时，需要用一个额外的变量记录更新前的值。

总时间复杂度 $\mathcal O(n)$。

思路理清后，代码很快就打完了，然而一测过不了样例一。

一查，最开始的时候要将 $c_0$ 设为 $1$，因为本质上这是个差分。

然后顺利过了样例一二，再测第三个样例的时候爆栈了。

举手问了下监考给不给开栈命令，发现不给，然后使劲回忆，好像是 -stack,--Wl=1073741824？

一开，CE 了。

然后慌了改成 -Wl,--stack=1073741824 就 ok 了（大雾。

嗯，大样例过了，很稳，扔了。

这个时候才过去不到一个小时，还有 2.5h 刚 T3？嗯，很稳。

然后就自闭了，T3 只能拿个 10 分。

出来的时候感觉要凉，这个 Day1 怕不是全场 AK，就我 210 T3 暴力滚粗。

然后一出来，感觉好像似乎或许这个 T3 没几个人 A 掉？

这样的吗...

这还是 NOIP 吗...

哦不是，这是 CSP...

吃饭的时候，C 的题解出来了：https://www.zhihu.com/question/351347604/answer/896344216。

啊，神仙贪心。

话说贪心怎么一年比一年考得难啊，想想曾经的「国王游戏」。

然后 T1 OI-wiki 上居然有：https://oi-wiki.org/misc/gray-code/。

看群里都在讨论 T2，据说那个大样例水得一匹，于是开始慌，我为啥不对拍一下啊，懒惰死了。

结果下午拿到了程序，牛客、信奥题库、洛谷、CSP.ac 都测了一下，都是 210，嗯，很稳。

顺便测了一下别人的程序，emmm...

Day1 考得还可以，但想到去年 NOI 的时候，也是 Day1 海星，Day2 就爆炸，心里还是有点虚的...

希望明天自己能够正常发挥吧。

CSP2019 day2 rp++！

Day 2

密码是「抓紧时间」。

题目：http://www.xht37.com/wp-content/uploads/2019/11/CSP2019-S2-day2.pdf。

开 T1，想了一会儿发现没啥正解思路，打了 64 就扔了。

开 T2，想了一会儿发现没啥正解思路，打了 36，输出了一下转移发现了些性质，就改成 64，然后又扔了。

开 T3，想了一会儿发现没啥正解思路，打了 75，然后又扔了。

这个时候过了不到 3h。

然后就开始在 T1T2 剩下的分中纠结。

然后考试就结束了。

下午测，还是那四个地方，$64+64+75=203$，一分没挂，一分也没多得。

问了下别人的分数，感觉全世界都吊打我。

这个 T1 就是一个极度简单的容斥，可是我脑抽了。

唉，还是技不如人吧。

两天加起来 $413$，没去年高，不知道能不能去 THUWC。

我已经高二了。

Day 3

中午才爬起来...

听说马上要合格考了，考政史地，全省前 $98\%$ 能过关。

看起来快要没学上喽。

测了下全湖北的代码，没测完，只测了一半，就感觉很凉...

jxl 535，ouuan 也铁定比我高。

某神仙和 ylh 看上去大概率比我高，如果 T1 数据不强的话。

一半就把我搞到第五去了。

我想去 THUWC，想上 THU；我想湖北前四，我想省队拿 A。

可能，就，都没了吧。

心情很糟，不写了。