CSP-S 2019 游记

## CSP-S 2019 游记 今天，CSP 2019 的大部分结果终于公布了。想一想，这也是我 ~~第一次参加 CSP-S~~ 第四次参加 NOIP 级别的比赛了，也许这就是最后一次了。总体来说，算是几乎超常发挥了吧，也基本没有什么遗憾了。 ### Day 1 也许是因为模拟考积累了信心吧，考前并没有很紧张，还是像历次 OI 考试一样，听着 01 社社歌和 Euphoria 到了考场外，简单收拾就进了考场。 #### D1T1 看到题目名，“格雷码”？这个东西我在《组合数学》中见过，当时还为它的巧妙感到十分震撼，并且还思考过如何写出按格雷码枚举子集的代码，想过“它有什么应用”，甚至还出了一道相关的题目。 马上就放了心——今年 D1T1 终于不是什么奇怪的思维题了。仔细看看题，虽然我没有思考过“第 $k$ 个格雷码是什么”的问题，但是由于构造规则不复杂，因此做法应该也不难。 按照模拟的习惯，我先写了一个暴力和一个数据生成器，再开始思考正解。正解想起来并不困难，不久我就把它写出来了，并且过了大样例和对拍。由于担心快读写得不好被卡，我还特意用了看上去最安全的 `cin`。总之这道题花了大概半小时，也许稍久了点，但是至少分拿得稳。 #### D1T2 看到题，先有了写部分分的觉悟（bushi。 首先是一个小思考点——对于“子串”，只需要考虑“以当前节点结尾的子串”（后缀）有多少个合法括号串即可。 接着我就开始推各种古怪的引理，期间想起了 Catalan 数推导过程中的“任何时候右括号数都不多于左括号数”之类的结论，好不容易才把条件转化清楚了。接下来又考虑条件的运用，又是一番折腾…… 结果似乎想得差不多，可以写了，写完发现根本过不了样例，代码实现也没有错……看来是式子错了，仔细检查，发现果然有问题。然后又开始一轮推条件，总算是改对了。至此已经浪费了很多时间了。所以，即使时间紧，还是记得 Think twice, code once，否则会浪费更多时间！ #### D1T3 时间已经不够了，绝对只能写部分分了。 拿到题，一开始还不想写 10 分的部分分，总觉得麻烦；但是思考一段时间都没有头绪，这让我不得不动手把 10 分的部分分写了下来。 接下来有两种情况——链和菊花，我选择了在前面的链。稍推一下，搞了一个似乎是正确的结论，然后写下去，再拿个数据生成器生成数据，过不了对拍。拿小数据检查，发现思路又错了…… 重新想了想，发现情况很多，遂想去写菊花，可菊花也没有头绪。也不剩多少时间了，感觉压力很大，就硬着头皮写链的情况，写到还有 5 分钟，决定放弃，直接交暴力。把前两题再过了一遍样例，就交了。 提交等待时间比较长，心里其实也有些崩溃。出了考场，好像大家都 AK 的样子？（雾）不过和同学交流，发现其实大家好像都不知道 T3 想考什么…… Day 1 考场估分 $100+100+10=210$，实际 $100+100+10=210$。 ### Day 2 Day 1 考完，心态确实有些影响，不过看到 T3 的题目颜色，似乎也放心下来了。 #### D2T1 拿到题目觉得可能是找规律之类的，可是仔细想想，并没有很有思路。 想到用容斥原理，又注意到超过一半的列至多有一个，所以就是一个简单容斥。 那么最主要的问题就是如何求“某一列选取超过 $\lfloor \frac{k}{2} \rfloor$ 的情况下的总方案数”。看复杂度，大概只能承受 $O(n^2m)$，所以 dp 要好好地优化才行。不过似乎总选取个数、选的“关键列”个数、选的“非关键列”个数，知二才能推一，于是似乎有两维，这样可就是 $O(n^3m)$ 了啊。由于时间有些来不及了，所以最后就写了这个方法，想着 84 分也差不多满意了。 这道题的正解其实也不难。最后我们只关心“关键列”比“非关键列”多多少，并不关心总共选了多少列，因此只要把这两者的差值作为状态，就可以压下一维，做到 $O(n^2m)$ 了。考场上没有想到，也还是思维水平需要提高啊。 #### D2T2 这大概是我 CSP（超水平）的一题吧。 首先想到的当然是 dp，然后总觉得这个转移方程太简单了一点，应该有各种各样的玄机。于是开始思考贪心。 首先想到的是“当断不当断”之类的思路，然后小样例就过不了，马上放弃。接着边想边去洗脸清醒，然后想到了“最后一个元素所在的段最小”之类的思路。自己也说不清楚这到底有什么道理，不过抱着试一试的想法写了写，居然过了大样例。我又谨慎地写了随机种子式输入，把超大样例也检查了，同样过了！于是愉快地拿走了 88 分。 然后这题确实是 rp 使然吧。 #### D2T3 这题暴力一看就很可做，马上把暴力写完。 接下来还是慢慢想链和完美二叉树的情况。我一开始注意到了“这些 $n$ 怎么有点奇怪”，但却没有深究那个完美二叉树的 $n$ 究竟是什么。 链的情况不是很难，写一写，就过了。还剩一些时间，我不停盼着把完美二叉树的部分也写了，但是遇到不少困难。 时间不太够了，我口胡了一个做法，结果过不了对拍。随意修改口胡的做法，还是过不了。 然后我看了看样例，发现这些 $n$ 怎么都是 $2^k-1$？终于发现那个奇怪的 $n$ 也是 $2^k-1$，也就是这是一棵满二叉树！这样树上每个点对答案的贡献只与深度有关，直接打表就可以得出答案了。可惜那时只有约 5 分钟了，我只能稍微整理整理文件，便提交了。 看来以后遇到不熟悉的数字，一定要花点时间弄清楚“这是什么”，一定会大有用处。另外用 vim 浏览一下大样例也是有好处的。 Day 1 考场估分 $84+88+55=227$，实际 $84+88+55=227$。两天估分都一分不差，可能我的程序还是比较沉稳（？）。 ### Day 1 && 2 总的来说，这次最重要的经验还是要调整好心态。这点和 GGOI 2019 是一样的。 另外就是要注意观察数据特点，遇到蜜汁常数要弄清楚“这是什么”；最后就是“大胆猜测，用对拍求证”吧。 #### 感谢 今年的 CSP 备战历经了一个月，在这段愉快的时光里，要特别感谢： - 一直支持我的父母和老师 - 一同奋战、相互扶持的 OIer 们 - Special thanks, 每天都陪在我身边、给我鼓励的 Hanakiko 愿我们明年的某个时候再会！