CSP2019游记

  这可能是我高中时候的最后一篇以OIer的身份写下的博客了。是时候滚回去肝文化课了。

Day 0

  下午抵达酒店,还是去年那家,去年就在修的路今年还没修好,对面就是电子科大。一切跟去年仿佛都没有什么区别,除了从2018变成了2019,除了多了一年爆零的经验,除了今年考的是跟NOIP没有关系的CSP。今年感觉要紧张一点,毕竟去年只是试试水,并没有真的要冲一等奖,但今年是最后的机会了,我不能错过。

Day 1

  我的邻座居然还是我去年的邻座。。。但是我的位置居然在机房的角落。。。

  算了,先看题。看了三道题感觉比较难。按习惯我先写T1,开始以为是个结论题,结果敲完之后试第二个样例时发现题读错了。然后我发现这个好像可以倒着模拟一下(其实我也不知道这算不算模拟),然后我写挂了。一看时间9:20,于是心态爆炸。慌乱中写了一个50分的暴力(后来发现是错的),赶紧去写T2。

  T2我忽然发现这题好像不是很难,貌似记一下每个点到根节点的路径上有多少个失配的(,再记一下有多少连续匹配的括号就行了。然后第二个样例又挂了。试了一堆小数据后终于找出了错,这是那组hack数据:

  8

  (())(())

  1 2

  2 3

  3 4

  4 5

  5 6

  6 7

  7 8

  然后我用了一个类似链表的东西维护了一下这个点之前失配的(,过了第二个样例,然后第三个样例RE了。。。WTCL,不会开栈,于是第三个样例只有咕咕咕了。不会开栈的邻座也RE了,他去找监考员求助,然后……就没有然后了。

  T2写完,形态稳了一点,于是滚回去写T1。事实证明考试的时候心态一点不能崩啊。心态稳了点后我很快就把T1调出来了。然后我去看T3,然后,这是什么鬼啊?(果然hzq大佬说的没错,求最小字典序的题基本都是毒瘤题(除了去年Day2T1))于是先写了一个暴力搜索,然后瞎写了一下链的部分。此时时间严重不足(T1浪费了太多时间),链那部分连样例都没试,估计是凉了。

  出考场后和同学对了一下,发现我T1好像有个细节写挂了,估计要扣掉5分。T3好像大家都没做出来,某位大佬肝了两小时都没肝出来(晚上教练查寝时我才知道那是道不可做题)。

  吃饭的时候不知道是谁(好像就是我)奶了一口明天三道DP。

Day 2

  早上起来猛然发现外面起雾了,而且还是特别大的那种,街对面完全看不清。有同学还半开玩笑地问我在去CSP的路上会不会被车撞死,毕竟这事写在了考前注意事项里(真·弥天大雾)。

  进考场后看题,我以为那个人奶中了。。。我DP很弱,开始自闭。

  T1先写了一个搜索。然后我开始思考记忆化,然后发现根本找不到一个合适的状态定义,只好跳过。

  T2看了一眼数据范围,4e7。。。O(n)?推了一下式子,发现跟斜率DP特别像。但是我斜率DP忘完了,尝试了一下考=考场现推,失败,又加上这道题比普通的斜率DP多了一个限制,于是我开始思考暴力DP,开始想的是O(n3)的,然后发现枚举分了多少段没有用,于是写出了一个O(n2)的DP。

  T3先写O(n2)的做法。树的重心我也忘得差不多了,于是又是一波考场现推,还好这个比较容易,推出来了。然后又写了一下链的那部分,还对拍了一下,55分应该比较稳了。

  时间还剩了一些,于是我继续想n≤40的暴力,还是考虑记忆化,然后又过不了样例。调到考试快结束的时候我才发现我的状态定义有问题。。。于是T1没了。

  出考场后和同学们讨论了一下,发现大家好像多没有切T1。然后T2可能是一道比较神奇的贪心,可能就像之前的国王游戏一样。。。

 

  差不多就这些了。我这不到一年半的OIer的生涯可能就此结束了。不过如果CSP考的还不错的话,我可能还会再回来的。

上一篇:CSP2019树上的数


下一篇:csp2019游记 公开版