CSP-S 2019 游记 - Noble

# ~~性感选手，在线爆炸~~ ## DAY -20 手出了问题，莫名在抖。。。感觉要坏事。 ~~帕金森警告。~~ 医院做按摩一直做到考前第二天。 ## DAY 0 早起收拾东西上火车，早饭买了德克士打包。 然而上车之后睡着了，早饭【并不是】十点半才吃的。 恰完饭打开电脑去西欧拉货。 我noble就是被卡知识点，爆零，也不会复一下习。 包的大巴一开始去错旅馆了。。。 下午一点左右入住燕大~~宾馆~~招待所。 午饭在宾馆饭店吃的山药牛柳，他们盐不要钱的吗，怎么能放那么多？ 试机时候发现有vscode，兴致冲冲的建了个mfc工程然后忘了updatedata函数。。。最后百度的，在线丢人.... 然后打了线段树，lca（lnoi）试机。lca代码改成旧词的时候炸了，60分，想不通。 感觉不是好兆头。 晚上ztb讲了考试注意事项，中心思想就是多去厕所。 ~~下水道：我想不通。~~ ## DAY 1 6：30起床去恰饭。早饭没啥可吃的。。。。 起床到恰完饭一直在用手机玩命补gcd，exgcd，逆元，线性筛和tarjan。（~~真香~~）~~幸好一个都没考。~~ 做大巴前往180人大考场，有点晕车。日常开考前突然想上厕所。 密码：认真思考。好常规的密码。。。。 ### 开题 #### T1： 看了看，发现第i位是0/1只与k和第i+1位有关，对于最高位，视为更高一位为0就行。 直接逆推回去，过大样例跑路。 键盘依旧贼不适应，t1打了半个小时，日常丢人。 #### T2： 括号匹配可以用栈做，这题一眼出了。。。。 先写了个序列做法，和暴力拍了一下。 一边拍一边把序列做法改到了树上。 上树之后出了几个小锅，修了一下。 懒得不行，过大样例跑路。 大样例无端恶臭。 #### T3： 还有两个小时，~~感觉ak稳了~~。 担心今年又人均300。t1t2感觉比去年还简单的说。 t3肯定可以a掉，要加油啊。 ..... 一个小时后，wdnmd闸总。 去年t3只知道二分答案，然后啥都不会了。 今年t3只知道贪心去走，然后啥都不会了。 这怎么这么似曾相识啊。 跟去年一样上了个厕所，一样没效果。 两个省二afo，拜拜您呐。 ~~csp和noip俩省二能不能当双省二用。~~ 死磕到剩40分钟没出正解，被迫rush10分暴力。 没过第二个样例，想不通。。。 200滚了（还没对拍），想哭。 ### 收卷 出考场听说没几个人会，稍稍放心一丁点。 出考场知道原来输入格式和我以为的格式正好是反着的...... 大巴上高一学长说链的部分分贼好写差点给我吓死，然后说完做法我立马给他hack了。。。。~~md闸总~~。 下午坚决不测程序，上了下luogu发现大家都在吐槽t3，忍不住去看了t3正解。~~看完放心多了~~，这是人写的？ ~~震惊，清明十二响正式成为温暖题。。。。~~ 晚上和我妈去附近新开的商场拿生日蛋糕（我生日撞上day1..），许愿csp不爆炸，day2成功翻盘。 然而**Day2没有翻盘，只有翻车**。 ## DAY 2 去考场，依旧有点晕车。 密码忘了是啥。开考前又想上厕所。 ### 开题： 过了一遍三道题，稍稍有点慌。 #### T1： 写了一面草稿纸，感觉出作法了之后去看了t2。 开始写的时候发现推得是假做法。 及时想到了答案可以是全集-不合法。 而不合法的dp可以搞出来。dpi,j,k表示做了i个菜，j原料k次就行。 过不了100%，想到了bzoj内个1kb内存众数题，发现那个结论在不存在那种数的情况下不成立。。。。（成功跑偏）。 就这样没想到记录差值，1.5h，84分滚粗。 #### T2： 数值很大，没法记录，但是知道最后一段划分的开头和结尾就可以直接求出规模，n^3dp显然。 然后感性证明，因为是平方代价，尽可能多分，同时最后一段尽可能小最优。 这样立方复杂度变平方。 n^2显然过不了5e5，发现因为a>0，所以最近的一个合法转移一定最优（因为最后一段更小的情况下，段数不会更少）。 设fi为i段结尾最小代价，实际上是求满足dpj<sumi-sumj的最靠右的j,移项可得dpj+sumj<sumi,动开值域线段树nlogn。 感觉不太好写。。。发现sumi是单调递增的，而dpj+sumj可以用单调栈转化为单调的，线性做法到手。 然后发现大屏幕上保证nlogn数据范围答案longlong不爆才意识到这题轻松爆精度。。。。 awsl，12分写高精度有点亏，nlogn分数跑路搞t3正解去。 //据说最后12分普通高精还过不去，如果是真的，这12分wdnmd。。。。 平方优化到线性我用了一个小时 然后t2民间数据n方全都88，官方估计也这个分，day2就这样成功爆炸。。。 #### T3： 到t3就不剩啥时间了，先打上40分暴力。 暴力一遍过了，很走运。 开始推正解，还有一个半小时左右，慌得一批，感觉是算贡献，只推出了使x成为重心，在上方删边的做法，在子树里删边没推出来。。。 还剩10min时rush了链的暴力，不负众望挂了。 只在linux编译了确定不会ce，文件名都没来得及查。。心脏病发.exe **彻底翻车**。。。。 中间还肚子疼上了个厕所，十多分钟。。。。顺便diss一下某个没冲水的大哥（不知道是谁）。 ### 收卷 在火车上继续去欧洲开货车，老年玩家.exe。 准备下车等停车时候想了几分钟，发现t3子树里删边和在上面删边做法基本一样，wtmsb。考场上还是太慌了。 听说考场上zbk最后5分钟A了，orz。 zbk ak ioi 下车没回学校，住在石家庄市区，第二天去医院看手。 ## DAY 3 在医院检查，两个检查都明天才能做。 下午去了隆兴寺玩，挺不错的。 ## DAY 4 to n 住院了，现在还没出院。 爆炸的不轻，至少有25分白送的暴力没拿，脑壳疼。 按照民间数据，不出什么大意外应该能400+。苟进前十。 不过没卡我知识点没考数学还是比较走运的。 机房好像又退役了不少，今年真的香火不旺。 顺便给后来人提个醒，注意自己会不会对旅馆床品过敏，千万别过敏了休息不好导致第二天爆炸拿胸牌。 ## PS： 为啥游记现在才写？ 祸不单行，住院那天电脑坏了，昨天刚修好。 ~~这次依旧吃了黄焖鸡，但是只吃了一顿。~~ ~~顺便求一个 颈椎病康复指南 的pdf。~~ 希望学考不挂。 ## 12.1 官方数据d1t2爆int挂了20分，wdnmd 还被卡常了20分，md闸总，i7开了20个线程评测吗？ 心态爆炸。