# CSP2019 游记 Author: Fanyi Pu Published: 2019-11-23 Canonical: CSP2019 参赛游记。 声明：本游记的所有内容均是在 CSP 结束之后写的。 都高二了，第一次正式出去玩，第一次写游记。 ## Day0 上午信心赛，然后 yk 就放了场 Day2，窝打到自闭了。 啥我 T2 打了个奇怪的贪心过了？？？旺仔和 zyy 竟然 T1 同时没开大数组同一个数组海星…… 听说如果这场把 RP 用光会导致 CSP 爆 0，窝怕不是药丸。 高二老年选手第一次参加~~NOIP~~CSP，是不是晚了点。 路上好多人都在奶今年原题大战。 先去学车想围观一下考场，然而不让进。 和[daifucong](https://www.luogu.org/blog/daifucong/csp-s2019-you-ji)住一个房间，感觉酒店环境一般，但也还算过得去。 听说那叫“维也纳三好酒店”，名字不错。 晚上 daifucong 勾引我打 cs1.6，尝试下然鹅被卡巴基佬删了，听说 dfc 那个也被 360 删了。 然后开始无所事事。 dfc 给我讲了 pkuwc2019 的 D1T1，然后我想了好久是不是药丸…… 自闭后开始背板，然鹅还没开始被就被 dfc 的茄子吸引过去了…… 10:00 准时睡觉。 ## Day1 闹铃到 6:50，结果 26 分就被野花的奇怪的“酒店自动叫醒电话”给吵醒了。 ~~为什么酒店还有这种服务，我怎么才能关掉它。~~ 早饭除了豆腐脑其他都一般。 特别是菜包和肉包是放在一起且一模一样的，awsl…… 大巴车刚开到酒店门口就被一群保安来住了，听说是出口贼小然后车开出去的时候擦破了一点什么东西。 结果发现花和 $\sum$ 的车已经开走了，于是我们被困住了。 于是到 8:10 还没出酒店。 然后好像一堆人下车，然后车就开走了。~~并不知道为什么~~ 上车赶到考场，居然还没开始。 赶紧开题。 首先发现了题面画风与往年好像不一样，明显是用 `tex` 写的。 这个输入输出文件的字体好熟悉啊…… 然而但结束跟 daifucong 聊天的时候才想起来这好像是 `noi` 的模板。 T1 直接模拟就可以了。虽然记得小时候偷看我爸的通技书的时候好像记得格雷码是有啥公式的。但反正这个东西直接做也不烦。 看 T2。看到“有多少个**互不相同的子串**是**合法括号串**”这句话有点慌，Day1T2 就考数数？ 冷静分析一下之后发现最上面的题意已经有提示了。我们考虑 $f_i$ 表示从根到该结点的答案，$g_i$ 表示以该结点为末尾的合法串的数量。$l_i$ 表示 $l_i\sim i$ 这一段是以 $i$ 为结尾最短的合法串（可能 $l_i=0$ 即不存在）。不难发现如果第 $i$ 个数是左括号是不用跳的，如果是右括号就让 $l_i$ 暴力往上跳，直到有一个左括号停止即可。有了 $l_i$，$f_i$ 和 $g_i$ 都可以转移了。 考虑到每个点只会被跳一次，所以复杂度是 $\mathcal{O}(n)$ 的。 感觉 T1T2 都很好写，就没有先去看 T3，先把 T1T2 写完了。 看时间还有两个半小时，感觉肝一道 Day1T3 没问题（ 显然首先是 $1$ 要移到 $1$ 号节点，然后发现链上，然后发现先要把链上点的出链上边外的边删掉，然后再删链上边，最后删 $1$ 所在节点所连出去的那些边。 大概实现过程是找链，然后把链上点的编号交换处理一下，然后递归处理下去。 然后开始码。 然后发现只有半个小时了。 开始自闭。 发现自己还没打过暴力。 当时居然没有保底，而去继续肝了，并不知道当时为什么会这么想。 其实这个代码改成链的部分分应该是很快的。 到距离结束还有大概 15 分钟的时候过了小样例。结果大样例死活过不去。 还有 5 分钟的时候发现权值忘记交换了。 我当时在写什么…… 药丸。 感觉要 100+100+0。 出来之后发现全人类都比我高。 吃午饭的时候： dfc：T1 输入 `64 2^64-1` 输出啥？ 我：啥为啥 $n$ 开了 $64$，我全开了 `long long`？？？ dfc：…… （过了一会儿） dfc：等等 $2^{64}-1$ 是不是应该输出 $1$ 后面很多 $0$ 啊？？？ 我：？？？ dfc：我好像最后一位是 $1$，我考场上以为这是对的。 于是发现只有我和 dfc 不会 Day1T1。 开始自闭。 （过了一会儿） dfc：T2 你拍了吗？ 我：没拍。 dfc：T2 大样例好像怎么都能过。 我：完了。 怕不是 $95+0+0$？？？ 后来 zyk 一直跟我说，不确定就算对，然而我还是很自闭…… 开始去酒店麻痹自我…… 然后吃晚饭的时候听说高一已经有两个小哥 T2 过了大样例然后去牛客上测 `WA` 成 $10$ 分了。 窝怕不是凉了。 继续回酒店麻痹自我…… dfc 先看了会儿茄子，然后开始~~黄金矿工~~抓猪，然后和我完了会儿坦克动荡。 饥荒真好玩…… 希望 Day2 能友善一点。 ## Day2 去考场的路上竟然一路顺风。 回忆一下昨天晚上，daifucong 奶了一口 CSP 是不会出现 $998244353$ 的。 然后开题就慌了…… 然后就发现左边小哥已经在扫雷了。 更慌。 先看 T1。显然是个容斥。然后那个 $\mathcal{O}(n^3m)$ 的 `dp` 很好想，分数挺高的。 然后看 T2，一眼瞥到样例。等等怎么最后一个样例输出这么长啊……回去围观了一下输出格式： > 输出一行一个整数，表示答案。 **这不是字符串题啊……** `本来就少的可怜的开题数 -= 1` 果断先看 T3。 众所周知 Day2T3 是不可做的。 但是发现 $\mathcal{O}(n^2)$ 暴力很好写。 于是会过去看 T2。题面写得不错，下一个。 先写 T1，然后发现写挂了。 想确定一下 `dp` 有没有推对，在草稿纸上写了一下这个 `dp`。 等等后两维不是可以放在一起吗？ 于是就变成了 $\mathcal{O}(n^2m)$。 然后发现巨好写。 然后就听说 T2 的前面 88 分不用高精，保证 $ans\le 4\times 10^{18}$。 说的好像我会做的样子。 然后发现 $\mathcal{O}(n^2)$ 很好想也很好写。 于是就写了个 $\mathcal{O}(n^2)$ 走了。 想想能不能在多几分。 感觉有单调性。 然后就不会了。 自闭，时间不多了，去看 T3。 先打了个暴力。 然后打了档链。 发现链的那档挂了。 调了一年，`len = (r - l + 1) >> 1` 海星。 然后发现想二叉树，并没有发现数据中给出的是满二叉树，以为只是每个非叶子节点都有两个节点。于是深度可能是 $\mathcal{O}(n)$ 的。 于是我再也没有想出来…… 惊慌之中检查了一下大样例。不错，目测都很强。 然后就结束了。 目测大概 $100+64+55$。 发现又是人人比我高。 sxd 好像想到了 T2 $\mathcal{O}(n)$ 然后发现被卡内存了。 然后 zyy 直接写了个 $\mathcal{O}(n)$**炸**内存了。 zyy：完了我只有 $500$ 了。 自闭了。 会家学文化课。 ## Day5 发程序了。 拿 zyy 的数据测了一发：$95+100+0+84+64+40=383$。 Day1T2 没挂。 啥我 Day2T1 只有 84？？？ 不过听说是被卡常，CCF 的机子是能过的。 啥我 Day2T3 链的那档挂了？？？ 去看题意，**存在**一个 $1\sim n$ 的排列 $p_i$。 没说是 $p_1\ p_2,p_2\ p_3$ 这样读入的啊。 完了我没了。 不甘心去洛谷交了一发：$95+100+25+100+64+55=439$。 怎么两个分数差那么大啊…… 去牛客上叫一发：$95+100+0+100+64+55=414$。 但愿 CCF 数据水一点啊…… ## Day8 周末了，用 `__int128` 补了一下 Day2T2，然后来写游记。 政治老师要我补作业，~~明明不选政治为啥还抓得这么狠啊啊啊啊啊~~。 自闭了，文化课真香。 ## Day ??? 成绩出来了：$95+100+0+84+64+55=398$。 Day2T1 果然被卡常了。 去学文化课去了。