CSP2019 游记
希望能带来好运!
2024.11.04 upd:初中时期写的东西不清不楚的,希望可以博君一笑 QwQ。
2026.11.15 upd:优化了一下排版(但没有修改文章内容,纪念我曾经的文笔😂)。
Day 0
咕了一下午的文化课,坐上来福州的车(感谢 dalao-lzx 的资瓷),车上几度想要呕吐。
总算撑到了 “速 8 酒店”,在来酒店的路上还遇到了几位长汀一中的小哥,其中一位还向我打了一声招呼。
坐在酒店的大厅椅子上,想起没人与我拼房间,就十分蓝廋。
然后就见到了巨佬学长们,貌似对我的衣服很好奇(衣服上印了一份 “hello, world” 的代码),奆佬 changle_cyx 说:
你看,大括号不换行!
过了一会,教练来到了大厅,见到没人与我一起拼房间,就笑着对我说:“如果没人与你拼房间的话,就来和我一起睡吧♂,你想想一生当中能和我睡的机会有多少,还不好好珍惜?”
感到十分激(gan)动(ga),赶快附和一句:“明白明白,先过一会再决定吧。”
随后就是准备出发看考场了,一路上都在想 “一会试机要打啥呢 qwq”,走着走着就到了附中,过去报道后,惊奇的发现我居然在时代中学考试,极度难受,用不了习惯用的 dell 键鼠了,不过我竟然和 changle_cyx 和 xyz32768 两位奆佬一个考场,稍稍有了心里安慰 …
然后和诸位大佬一起走到了时代初一教学楼五层,爬楼梯就已经快要去世了,与 changle_cyx 和 xyz32768 两位巨佬一起找了三个位置坐了下来,电脑是联想的,敲了敲键盘,按了按鼠标,似乎海星。
文件夹里有一道 A+B problem,旁边的奆佬 xyz32768 说:
线段树打 A+B problem,简直板题。
然后突然想起来之前念念不忘的主席树,就用主席树乱搞一下 A+B problem。
乱搞完之后,想打一点有意义的板子,于是就打了一个复杂度为 \mathcal{O}(ke) 的 优 秀 最 短 路 算 法(
然后搞 tarjan 求割点,打到一半的时候被两位奆佬叫回去了 qwq。
回到酒店,先在 hh 的房间 happy 了一会,随后就去吃饭了。嗯,田螺真香。
有意思的是在饭店里遇到教练与省里的各位教练聚在一起侃侃而谈,以及身后一桌的 OIer 聚在一起互膜/膜某人/装弱还是挺触动我的,就觉得,无论未来的路怎么样,也要坚持学 OI。
饭后走了一会,有意思的是在路上遇到了一个可以 24 小时提供一条龙服务的店,才了解到一条龙的正真含义,突然想起 knh 前一个月问我要不要一条龙服务,给我整乐了。
不过多久就回到了酒店,在酒店大厅遇见了 zlx 和 cjy 两位奆佬,于是凑过去问:“一起定一个三人间如何?”,后来才发现 ta 们早就订好了 QAQ。
不知道晚上怎么睡,于是我串遍了所有同学的门,感谢 dalao-zzy 给我的赞助,让我度过这个不眠之夜,然后 …
我们来到 hh 的房间 happy,发现只有我一个蒟蒻在研究如何对拍,其他的各位奆佬全在写板子,有点鸭梨。
不过多久,教练召集开个小会,研究考场上的解题策略,诸位大佬积极分享自己的见解,只有我这个菜鸡尴尬地聊到了时间复杂度的分析:
大家可以根据数据范围猜一猜算法之类的,例如:
- n = 10:全排列。
- n = 20:状压 dp。
- n = 100:区间 dp,floyd。
……
会议很快就开完了,然后继续 happy!在房间里聊了一下 tarjan 的做法正确性,然后 hh 就给我们看一些很有趣的东东,例如新宝岛啊,影流之主之类的。
转眼就到了 11:00 多了,我与 zzy 一同回到房间,准备睡觉了,在床上有感写下 day0 的游记。
祝大家 CSP2019 rp++!!!
Day 1
日色入户,欣然起行。
居然 6:44 分才被太阳光照醒,先奶自己一口 “pj 没有 tg 来的理想”,然后开始盘算接下来要做些啥呢。
当然是临时抱佛脚拉!拿起蓝书狂记板子,小到快速幂,大到分数规划(虽然也不是很大),全给我复习了一遍,就 KMP 背的不是很熟练,开始祈祷别考 KMP 阿。
大概是 7:10 的时候,阿柯妈妈打我电话,叫我到酒店一楼的食堂恰饭。
粗略的看了看伙食 … 貌似只喜欢吃豆浆和油条,其他的 … 难以下咽阿。
强忍着内心的不满,渡过了这天早餐,随后教练就召集大家到大厅集合,准备迎接 CSP-S2 day1 了。
一路上总是不断地发着牢骚,说自己会怎么样怎么样怎么样,同时也祈祷着不要给大家垫底就行。
在便利店顺手买了一瓶快乐水,希望出来的时候会像喝快乐水的时候一样快乐。
不知不觉走到了时代,依旧爬那恶心的五层楼梯到考场门口。
大概是 8:10 分的时候,主监考就宣布进考场了,检查了一下准考证,身份证,笔,快乐水,就进去找到自己的位置坐下来了。
草稿纸惊到我了,是绿色的?尺寸与键盘差不多,还平放在键盘上?叫我这种菜鸡怎么打草稿?
考生纷纷入场,左手边是一位妹子,右手边是一位老哥,看起来挺强的样子。
8:20 就可以开始操作了,登上自己的 FrC,建好自己的文件夹。
看了下题的英文名 “code”,“brackets”,“tree”。
- 看见 “code” 的第一反应是:“难道是 KMP,给我奶中了?”
- 看见 “tree” 这个名字就弃疗了,CCF 一考树就很毒瘤。
- 唯独我看不懂 “brackets” 是个啥意思,就没想太多了。
接下去是监考念那些乱七八糟的考生须知:
考生允许带进考场的物品有,笔,准考证,身份证,饮用水,食品 …
终于熬到了 8:30 分开考,随着主监考发下密码文件,键盘与鼠标的声音逐渐多了起来。
然后就开始正常的答题时间了,草草的看了 T1,还以为是一道数论题,后面突然意识到是一道分治题 …
花了三分钟思考了一下递归求解的函数以及合理性,随后花了十分钟的时间打了一下,接着测样例 … WA 了 QAQ。
开始思考了我的代码哪里锅了,一分钟后:“woc,原来编号从 0 开始”,后面瞎搞了一下,过了小样例,接着测大样例 … WA 了 QAQ。
把 1 << (n - 1) 等等东西输出了一下,输出几个负数?然后才意识到没有开 long long …
过了大样例后再次审查了一下该题,发现该题数据别有用心:
对于 95\% 的数据:k \leq 2^{63} - 1。
对于 100\% 的数据:1 \leq n \leq 64,0\leq k < 2^n。
然后就意识到要开 unsigned long long 了,接着去搞 T2。
因为预感今年 T2 比较毒瘤,就仔细地看了一下题面,发现 T2 确实有点恶心人,刚开始只想到 \mathcal{O}(n^2) 的暴力。
后来深入分析了一下求解的复杂度高的原因,其实是匹配过程中,经过了许多太多没必要经过的(已经与其他括号匹配过的)括号。
于是自然就想到了一个优化方案:记 lst[u] 表示 u 到 \mathrm{root} 的路径上最长的以 u 为右端点的合法括号串的左端点的编号。特别地,如果 lst[u] = 0,则说明 u 到根的路径上没有以 u 为右端点的合法括号串。
那么这样,从当前节点一直用 lst[u] 向根跳,就可以在找左括号的过程中,过滤掉许多无用括号了。
花了 20 分钟打了一下,测一下第一个样例,OK 啊。接着测第二个样例 … 输出 119 是个啥玩意。
又开始思考自己哪里锅了,仔细想想,发现自己没有锅呀,除非题意理解错了?
于是打了个暴力跟自己的程序拍了一下,发现 … 一模一样啊,到底哪里错了?
突然想起教练昨天的话:
不要一直死磕在一题上。
于是就去康康 T3 …
什么神仙大毒瘤?想了一个贪心思路,却被我自己否认了,接下来想的几个贪心都被自己给否认掉了。
最后发现,还是 10 分好打啊,于是打了一下 10 分的大暴搜,还差点打挂掉了。
再回头康康 T2,突然发现:
如果 A, B 是合法括号串,则 AB 是合法括号串。
草!
然后随便调一下就过了刚刚没过的两个样例,然后看 T3 的部分分 …
部分分也这么没有人性了?实在看不出链和菊花图与普通树有何区别(赛后发现 T3 在 luogu 黑了?大毒瘤!)。
从 10:50 开始,在考场上绝望地凝视时间一点一滴的流过。
最后 10 分钟,觉得有点闲,就去玩小恐龙了。
大概是在最后一分钟的时候,我先是望向身旁的老哥,发现他的得分情况跟我差不多吧,然后再看向旁边的妹子,发现 … 她貌似 T1 没写出来,好惨。
随后就到了 12:00 了,几家欢喜几家愁阿,有抱怨的,有跳舞的,但是后者为极少数人。
问了问身边的巨佬,发现:
- 学长们都会 T1 和 T2,T3 都有思路,然后打挂了。
- 队友们都会 T1,T2 都有思路,然后打挂了,T3 弃疗了。
这样一想,感觉自己成绩海星。
赛后估分:100 + 100 + 10 = 210。
自己的程序被成功回收了,比较开森。
感觉这个分数明天暴力就有省一了阿,接下来就是稳住 pj 和 tg-day2 了。
然后回到酒店恰个饭,就去八中迎接 CSP-J2 了,很快就到了八中的门口,见到自己的学弟学妹们。
觉得自己临时抱佛脚没有啥子用了,就去祈祷今年别出像摆渡车啊,魔法阵啊这样的题。
依旧爬五层楼来到了考场门口,害。
2:10 左右就进了考场,发现八中的考场真是 … 一言难尽啊。
六个人一张桌?还有电脑分辨率是个啥?键鼠比时代还差?
旁边的老哥时不时抖腿,还时不时乱发牢骚,我真的是 … 太难了。
随后又是听那个:
考生允许带进考场的物品有,笔,准考证,身份证,饮用水,食品 …
不过多久就到了 2:30,康康题目:
T1 的文件名 title 是去年的 T1 文件名,居然连改都没有改(偷笑)?乱做了一下就去康 T2 了。
T2 给我的第一反应是二维偏序?但是貌似并没有这么毒瘤,emmmmmmm。
分析了一下,貌似暴力可行 qwq,再乱加点 sb 优化就过了大样例 …
T3 看着都像完全背包,但是仔细想想发现自己想不出模型来,于是去康康 T4。
T4 题面多么花里胡哨啊,但是貌似就判断一下有没有 1 到 x 长度为 k 的路径就行了,这貌似可以转化成一个奇/偶最短路的问题,花了 30 分钟乱搞了一下,过了大样例,十分快乐。
回过头来看 T3,发现实在没有满分的做法,于是去想想部分分,发现:
- T = 1 不就是输出 m 吗?
- T = 2 不就是完全背包吗?
- N = 1 不就是股票那题吗?
就这样骗了 40 分,又一次看着时间一分一秒地流逝,自己却不会打剩下的分,wtcl。
打开附件的游戏夹 …… 空?唉,连扫雷都不让人玩了,有没有人性啊 qwq。
马上就 18:00 了,天空黑鸦鸦的,像极了那时的我。
出去问了问,发现同机房有两位巨神 AK 了,wtcl。
等待自己回收情况时,与诸位大佬谈了谈做法,发现我 T4 少判断了起点与其他点的联通性问题,不知道能拿个几分吧。
赛后估分:100 + 100 + 40 + \text{玄学} = [240, 340]。
自己的程序被回收了,嗯嗯,分数海星吧,然后就是回酒店了。
帮教练提了一下电脑包,就与众多 dalao 一起去恰饭了。
…
为啥还是昨天那家,虽然还挺香。
然后田螺换成了钉螺?嗯,还不错。
恰饭的过程中讨论了成绩的事情,发现我 tg 成绩好突出啊 233333,那接下来就稳住 day2 不爆吧。
回酒店的过程中听说教练又要召集开小会。
到了酒店 … 才知道是谈论一些关于成绩与比赛经验的事情。
发现自己估对了,民间数据还真是 210 了,这个成绩在全省貌似能排很前面,day1 区分度好低。
210 考的跟学长差不多?惊了惊了,然后窝就有一个外号叫做 “学长 cjt” 了,这个外号比较诡异。
然后貌似队友们考的都不是很理想吧,就去安慰了一下,希望大家 day2 都可以稳住吧。
小会开完,窝准备回房间自己再测一遍,然后在 knh 的房间发现 ta 在快乐元气,然后窝就与 knh 和 zzy 一起快乐元气了,一直快乐到了 23:00 左右,大家都准备去美美地睡它一觉吧,就回到了各自的房间。
然鹅窝却不是很想睡,心情比较激动吧,这是今年 CSP 在 fz 的最后一个怀柔之夜吧,想把这份美好刻画在脑中,铭记在心里,月光洒在床前,我凝视着,久久不能入眠 ……
Day 2
还是 day1 那个时候醒来,day1 好像没有 dp,感觉今天会出三道 dp(结果考了两道)。
于是把背包复习了一下,于是就去恰饭了。
来的比较早,食堂人很少。
领到了 3 根油条和 1 杯豆浆,愉快地恰了起来。
然后越来越多的巨佬来到食堂,发现外校貌似人均 210?感到恐慌。
然后互膜了一小会,就准备去考场了。
一路上忐忑不安,想想如果 day2 爆零了,太可怕了太可怕了。
按照惯例买了一瓶快乐水,走了一小会就到教学楼门口了。
然后又见到一群巨佬互膜的场景。
然后又是爬变态的五层楼梯到了考场,然后坐了下来。
草稿纸变小了,还换成了白色,比较舒适。
依旧是昨天的妹子和老哥 … 问了一下情况,发现窝旁边的老哥 day1 拿了 235?
TQL!TQL!TQL!
然后登 FrC,创文件夹,看见文件里每题的样例都是四五个,预感窝要 100- 了。
8:30 开场,窝一时脑抽,先开了 T3 … 先拿暴力分 40 + 15 + 20 = 75。
\mathcal{O}(n) 求重心差点挂了,然后特殊性质 A 乱搞一下就有了,B 花了几分钟推了下式子,看了一下自己写了 5K 的 T3,感觉很稳。
手打了几组样例,大概在 10:00 的时候发现没什么毛病,于是就去开 T1T2。
害,真是 dp。
奈何窝语文不好,直到考试结束也只理解了 T1 的 a[i][j] = 1 的题意,只拿了个 24 分。
直到 11:30 才去打 T2,又脑抽没有去考虑 dp,只打了 12 分的爆搜,害。
第三次绝望地看着时间流逝,自己却没法拿到剩下的分。
12:00 出考场,感觉人均 200+,就只有我这个菜鸡估分 24 + 12 + 75 = 111。
结果发现队友貌似比我惨很多,于是就没有继续发牢骚了。
- CSP-J2 理想得分:100 + 100 + 40 + 100 = 340。
- CSP-S2 理想得分:100 + 100 + 10 + 24 + 12 + 75 = 321。
海星海星。
然后与 dalao 们交流了一下,发现 T2 的 \mathcal{O}(n^3) 的 dp 巨好想,还巨好写,怎么说 T2 都可以拿个 36 分啊,说不定我还可以优化出 \mathcal{O}(n^2) 的,拿个 64 分的,害。
然后就是。
赛后拿到自己程序,测了一下 …
luogu 评测结果:
- CSP-J2:100 + 100 + 40 + 0 = 240。
- CSP-S2:100 + 100 + 10 + 12 + 24 + 40 = 286。
对于普及,我 T4 的代码中出现了一个非常聪明的函数:
int add(int u, int v) {
ver[++ tot] = v; Next[tot] = head[u]; head[u] = tot;
}在 Linux 环境下遗憾爆 0,我直接喷血,这是要 pj2= 的节奏?
对于提高,我 D2T3 的特殊数据 A, B 都挂掉了,A 是多测没有清空 vis 数组,B 是少打了一个有关根节点的项。
算是比较不错,但是好像明显可以做到更好更好更好,留下了许多挂分的遗憾,难忍心中的悲伤,哭了一小会。就这样,pj2=、tg1= 了吧。
而且我居然忘记在“附中”和“时代”合影留念了,害。
但遗憾比起收获,还是小的小的多。
2019.12.01
查到自己成绩了。
- 普及 340,省 rank15。
- 提高 286,省 rank90。
欸!PJT4 有分了?CCF 没有在 Linux 环境下测我的 T4?哦豁。
算是对我初一的练习一个优秀的答卷吧。坐标 FJ,两张 1= 多快乐阿。
想想自己才初二,还有很长的路要走呢 …
接下来就是念好文化课,继续练 OI 了。
CSP2020 rp++!
嗯,明年还去 pj。
表示非常想去省冬体验一把,但是教练可能不会带我们去省冬。
END。