蓝桥杯省赛贷款 AK 游记

· · 生活·游记

省流：C++ A 组河北省第三。

赛时

前一晚睡的时间挺短，早上又没吃早饭，本来以为没啥影响。

开赛之后发现两道填空和前两个大题都是签，不过由于太饿，磨了一个小时吧。

然后树那题，题目没看懂，跳了。

后面一题，首先双模哈希肯定可以做，但我怕自己写挂。

然后研究 kmp 写法，发现这玩意不是字符串匹配，而是 0 和 1 匹配，反正没想到咋做。

然后突然想到 \text{01trie} ，手玩了一会想到每个点开个 set 维护，但是问题是你没法 lower_bound 出来 set 的元素是第几个。

然后发现，把 set 换成 vector，按左端点顺序插入，每个 vector 里的元素也是顺序的，这个就可以直接 lower_bound 了。

写这题代码写一半睡着了，反正写的也特别慢吧。

然后做倒数第二题，我一看这玩意不就只用把 1 压起来就行了嘛，其他的数字直接暴力不超过 \log 个就 \text{overflow} 了。

龟速写完了，然后突然看到数据范围可以取到 0。

想都没想就给判 \text{overflow} 的地方多加了个判 0。

掉头回去看树的那题，发现把每个点的深度算出来然后瞎搞搞就行了。

这时候还剩 1h，以及最后一题，看了半天题目脑子昏了，想着睡一会吧，做不出来也无所谓了。

醒了之后感觉这个东西也太像线段树优化建图了，而且又像差分约束。把两个东西都回忆了一下之后，发现就是两个东西套起来，然后直接开写，最后二十分钟写完了。测了一堆手玩的样例发现没问题，直接交了。堂堂下班！

赛后

出来之后在几个群里讨论了这场题目，怎么好像 AK 了，然后就不想了。

结果是，晚上不知道为啥，突然想起来倒数第二题如果远端有 0 的话，答案应该是 0 而不是 \text{overflow}。当时以为这题要挂完了。

然后预期一直很低吧，感觉拿个中位省一差不多了，就不想这个东西了，也没心情写游记。

出分

5/9 下午数据库课，突然收到短信说出结果了，我就去微信查了下，省一，还行。

晚上吃晚饭的时候看到了总榜，rank3，出乎意料啊，既然 rank3 了我说我自己 AK 了是不是也没啥问题（）

于是乎来写了个贷款 AK 的游记。