CSP2019 游记

    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。

    乱搞完之后,想打一点有意义的板子,于是就打了一个复杂度为 O(ke)\mathcal{O}(ke) 的 优 秀 最 短 路 算 法(

    然后搞 tarjan 求割点,打到一半的时候被两位奆佬叫回去了 qwq。

    回到酒店,先在 hh 的房间 happy 了一会,随后就去吃饭了。嗯,田螺真香。

    有意思的是在饭店里遇到教练与省里的各位教练聚在一起侃侃而谈,以及身后一桌的 OIer 聚在一起互膜/膜某人/装弱还是挺触动我的,就觉得,无论未来的路怎么样,也要坚持学 OI。

    饭后走了一会,有意思的是在路上遇到了一个可以 24 小时提供一条龙服务的店,才了解到一条龙的正真含义,突然想起 knh 前一个月问我要不要一条龙服务,给我整乐了。

    不过多久就回到了酒店,在酒店大厅遇见了 zlx 和 cjy 两位奆佬,于是凑过去问:“一起定一个三人间如何?”,后来才发现 ta 们早就订好了 QAQ。

    不知道晚上怎么睡,于是我串遍了所有同学的门,感谢 dalao-zzy 给我的赞助,让我度过这个不眠之夜,然后 …

    我们来到 hh 的房间 happy,发现只有我一个蒟蒻在研究如何对拍,其他的各位奆佬全在写板子,有点鸭梨。

    不过多久,教练召集开个小会,研究考场上的解题策略,诸位大佬积极分享自己的见解,只有我这个菜鸡尴尬地聊到了时间复杂度的分析:

    大家可以根据数据范围猜一猜算法之类的,例如:

    • n=10n = 10:全排列。
    • n=20n = 20:状压 dp。
    • n=100n = 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%95\% 的数据:k≤263−1k \leq 2^{63} - 1。
    对于 100%100\% 的数据:1≤n≤641 \leq n \leq 64,0≤k<2n0\leq k < 2^n。

    然后就意识到要开 unsigned long long 了,接着去搞 T2。

    因为预感今年 T2 比较毒瘤,就仔细地看了一下题面,发现 T2 确实有点恶心人,刚开始只想到 O(n2)\mathcal{O}(n^2) 的暴力。

    后来深入分析了一下求解的复杂度高的原因,其实是匹配过程中,经过了许多太多没必要经过的(已经与其他括号匹配过的)括号。

    于是自然就想到了一个优化方案:记 lst[u]lst[u] 表示 uu 到 root\mathrm{root} 的路径上最长的以 uu 为右端点的合法括号串的左端点的编号。特别地,如果 lst[u]=0lst[u] = 0,则说明 uu 到根的路径上没有以 uu 为右端点的合法括号串。

    那么这样,从当前节点一直用 lst[u]lst[u] 向根跳,就可以在找左括号的过程中,过滤掉许多无用括号了。

    花了 20 分钟打了一下,测一下第一个样例,OK 啊。接着测第二个样例 … 输出 119 是个啥玩意。

    又开始思考自己哪里锅了,仔细想想,发现自己没有锅呀,除非题意理解错了?

    于是打了个暴力跟自己的程序拍了一下,发现 … 一模一样啊,到底哪里错了?

    突然想起教练昨天的话:

    不要一直死磕在一题上。

    于是就去康康 T3 …

    什么神仙大毒瘤?想了一个贪心思路,却被我自己否认了,接下来想的几个贪心都被自己给否认掉了。

    最后发现,还是 10 分好打啊,于是打了一下 10 分的大暴搜,还差点打挂掉了。

    再回头康康 T2,突然发现:

    如果 A,BA, B 是合法括号串,则 ABAB 是合法括号串。

    草!

    然后随便调一下就过了刚刚没过的两个样例,然后看 T3 的部分分 …

    部分分也这么没有人性了?实在看不出链和菊花图与普通树有何区别(赛后发现 T3 在 luogu 黑了?大毒瘤!)。

    从 10:50 开始,在考场上绝望地凝视时间一点一滴的流过。

    最后 10 分钟,觉得有点闲,就去玩小恐龙了。

    大概是在最后一分钟的时候,我先是望向身旁的老哥,发现他的得分情况跟我差不多吧,然后再看向旁边的妹子,发现 … 她貌似 T1 没写出来,好惨。

    随后就到了 12:00 了,几家欢喜几家愁阿,有抱怨的,有跳舞的,但是后者为极少数人。

    问了问身边的巨佬,发现:

    1. 学长们都会 T1 和 T2,T3 都有思路,然后打挂了。
    2. 队友们都会 T1,T2 都有思路,然后打挂了,T3 弃疗了。

    这样一想,感觉自己成绩海星。

    赛后估分:100+100+10=210100 + 100 + 10 = 210。

    自己的程序被成功回收了,比较开森。

    感觉这个分数明天暴力就有省一了阿,接下来就是稳住 pj 和 tg-day2 了。

    然后回到酒店恰个饭,就去八中迎接 CSP-J2 了,很快就到了八中的门口,见到自己的学弟学妹们。

    觉得自己临时抱佛脚没有啥子用了,就去祈祷今年别出像摆渡车啊,魔法阵啊这样的题。

    依旧爬五层楼来到了考场门口,害。

    2:10 左右就进了考场,发现八中的考场真是 … 一言难尽啊。

    六个人一张桌?还有电脑分辨率是个啥?键鼠比时代还差?

    旁边的老哥时不时抖腿,还时不时乱发牢骚,我真的是 … 太难了。

    随后又是听那个:

    考生允许带进考场的物品有,笔,准考证,身份证,饮用水,食品 …

    不过多久就到了 2:30,康康题目:

    T1 的文件名 title 是去年的 T1 文件名,居然连改都没有改(偷笑)?乱做了一下就去康 T2 了。

    T2 给我的第一反应是二维偏序?但是貌似并没有这么毒瘤,emmmmmmm。

    分析了一下,貌似暴力可行 qwq,再乱加点 sb 优化就过了大样例 …

    T3 看着都像完全背包,但是仔细想想发现自己想不出模型来,于是去康康 T4。

    T4 题面多么花里胡哨啊,但是貌似就判断一下有没有 11 到 xx 长度为 kk 的路径就行了,这貌似可以转化成一个奇/偶最短路的问题,花了 3030 分钟乱搞了一下,过了大样例,十分快乐。

    回过头来看 T3,发现实在没有满分的做法,于是去想想部分分,发现:

    • T=1T = 1 不就是输出 mm 吗?
    • T=2T = 2 不就是完全背包吗?
    • N=1N = 1 不就是股票那题吗?

    就这样骗了 4040 分,又一次看着时间一分一秒地流逝,自己却不会打剩下的分,wtcl。

    打开附件的游戏夹 …… 空?唉,连扫雷都不让人玩了,有没有人性啊 qwq。

    马上就 18:00 了,天空黑鸦鸦的,像极了那时的我。

    出去问了问,发现同机房有两位巨神 AK 了,wtcl。

    等待自己回收情况时,与诸位大佬谈了谈做法,发现我 T4 少判断了起点与其他点的联通性问题,不知道能拿个几分吧。

    赛后估分:100+100+40+玄学=[240,340]100 + 100 + 40 + \text{玄学} = [240, 340]。

    自己的程序被回收了,嗯嗯,分数海星吧,然后就是回酒店了。

    帮教练提了一下电脑包,就与众多 dalao 一起去恰饭了。

    …

    为啥还是昨天那家,虽然还挺香。

    然后田螺换成了钉螺?嗯,还不错。

    恰饭的过程中讨论了成绩的事情,发现我 tg 成绩好突出啊 233333,那接下来就稳住 day2 不爆吧。

    回酒店的过程中听说教练又要召集开小会。

    到了酒店 … 才知道是谈论一些关于成绩与比赛经验的事情。

    发现自己估对了,民间数据还真是 210210 了,这个成绩在全省貌似能排很前面,day1 区分度好低。

    210210 考的跟学长差不多?惊了惊了,然后窝就有一个外号叫做 “学长 cjt” 了,这个外号比较诡异。

    然后貌似队友们考的都不是很理想吧,就去安慰了一下,希望大家 day2 都可以稳住吧。

    小会开完,窝准备回房间自己再测一遍,然后在 knh 的房间发现 ta 在快乐元气,然后窝就与 knh 和 zzy 一起快乐元气了,一直快乐到了 23:00 左右,大家都准备去美美地睡它一觉吧,就回到了各自的房间。

    然鹅窝却不是很想睡,心情比较激动吧,这是今年 CSP 在 fz 的最后一个怀柔之夜吧,想把这份美好刻画在脑中,铭记在心里,月光洒在床前,我凝视着,久久不能入眠 ……

    Day 2

    还是 day1 那个时候醒来,day1 好像没有 dp,感觉今天会出三道 dp(结果考了两道)。

    于是把背包复习了一下,于是就去恰饭了。

    来的比较早,食堂人很少。

    领到了 3 根油条和 1 杯豆浆,愉快地恰了起来。

    然后越来越多的巨佬来到食堂,发现外校貌似人均 210210?感到恐慌。

    然后互膜了一小会,就准备去考场了。

    一路上忐忑不安,想想如果 day2 爆零了,太可怕了太可怕了。

    按照惯例买了一瓶快乐水,走了一小会就到教学楼门口了。

    然后又见到一群巨佬互膜的场景。

    然后又是爬变态的五层楼梯到了考场,然后坐了下来。

    草稿纸变小了,还换成了白色,比较舒适。

    依旧是昨天的妹子和老哥 … 问了一下情况,发现窝旁边的老哥 day1 拿了 235?

    TQL!TQL!TQL!

    然后登 FrC,创文件夹,看见文件里每题的样例都是四五个,预感窝要 100−100- 了。

    8:30 开场,窝一时脑抽,先开了 T3 … 先拿暴力分 40+15+20=7540 + 15 + 20 = 75。

    O(n)\mathcal{O}(n) 求重心差点挂了,然后特殊性质 A 乱搞一下就有了,B 花了几分钟推了下式子,看了一下自己写了 5K 的 T3,感觉很稳。

    手打了几组样例,大概在 10:00 的时候发现没什么毛病,于是就去开 T1T2。

    害,真是 dp。

    奈何窝语文不好,直到考试结束也只理解了 T1 的 a[i][j]=1a[i][j] = 1 的题意,只拿了个 2424 分。

    直到 11:30 才去打 T2,又脑抽没有去考虑 dp,只打了 12 分的爆搜,害。

    第三次绝望地看着时间流逝,自己却没法拿到剩下的分。

    12:00 出考场,感觉人均 200+200+,就只有我这个菜鸡估分 24+12+75=11124 + 12 + 75 = 111。

    结果发现队友貌似比我惨很多,于是就没有继续发牢骚了。

    • CSP-J2 理想得分:100+100+40+100=340100 + 100 + 40 + 100 = 340。
    • CSP-S2 理想得分:100+100+10+24+12+75=321100 + 100 + 10 + 24 + 12 + 75 = 321。

    海星海星。

    然后与 dalao 们交流了一下,发现 T2 的 O(n3)\mathcal{O}(n^3) 的 dp 巨好想,还巨好写,怎么说 T2 都可以拿个 36 分啊,说不定我还可以优化出 O(n2)\mathcal{O}(n^2) 的,拿个 6464 分的,害。

    然后就是。

    赛后拿到自己程序,测了一下 …

    luogu 评测结果:

    • CSP-J2:100+100+40+0=240100 + 100 + 40 + 0 = 240。
    • CSP-S2:100+100+10+12+24+40=286100 + 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 是多测没有清空 visvis 数组,B 是少打了一个有关根节点的项。

    算是比较不错,但是好像明显可以做到更好更好更好,留下了许多挂分的遗憾,难忍心中的悲伤,哭了一小会。就这样,pj2=、tg1= 了吧。

    而且我居然忘记在“附中”和“时代”合影留念了,害。

    但遗憾比起收获,还是小的小的多。

    2019.12.01

    查到自己成绩了。

    • 普及 340340,省 rank15。
    • 提高 286286,省 rank90。

    欸!PJT4 有分了?CCF 没有在 Linux 环境下测我的 T4?哦豁。

    算是对我初一的练习一个优秀的答卷吧。坐标 FJ,两张 1= 多快乐阿。

    想想自己才初二,还有很长的路要走呢 …

    接下来就是念好文化课,继续练 OI 了。

    CSP2020 rp++!

    嗯,明年还去 pj。

    表示非常想去省冬体验一把,但是教练可能不会带我们去省冬。

    END。