CSP-S 2023

发布时间 2023-10-22 00:23:37作者: WrongAnswer_90

Day 0

中午 12 点多出发,车上一开始 lgx,larry76 和 dwt 在打雀,我在旁边看,后来上手两把,我和 dwt 噶噶自摸,larry76 表示没有任何游戏体验,最后他甚至点了个一炮双响,我还是七对子。打的非常爽,感觉 rp 要掉光了。

晚上吃饭,感觉比学校食堂好吃。

去试机,幸运的抽到了 win10,嘎嘎好用,但是键盘键位有点阴间,试了试 debug 能用,打缺省源的时候发现忘了好多东西,非常可怕,回去一定要复习复习。

回去已经快九点了,去 lgx 屋打了个最大流,欧拉路和费用流,然后看 lgx 颓了一把铲铲,轻松 rk1/kt/kt/kt。

11 点多回自己屋,随机看板子,12 点了完全睡不着,感觉是早上睡到九点加车上睡了半路导致的。帮 dyyzy 调树剖,快 1 点才睡的。

Day 1

早上 7:20 起,吃完早饭就回屋了。李说想去海边看看可以 9:30 去大厅集合,但是完全不想去。在屋里又看了一会板子,然后和 lgx 口胡 CSP-J 的题,发现不会 T4,非常不牛,感觉没救了。(话说今年 -J 强度太高了吧)

看 lgx 打金铲铲,直接三星五费剑魔,一刀 20000 多群伤,有点太猛了。

吃中午饭的时候会了T4。

中午继续复习,开始背快读咋写args还有编译命令。睡得非常香,buff 已叠满!

下午进考场,有些紧张,手心一直在出汗。监考人员说不让动机器但是一车人都在打缺省源,同流合污,2:30 前一分钟左右打好了缺省源加拍子的模板。

开题!

T1 什么垃圾,直接暴力枚举,唉我测,怎么样例不过,唉我测,读错题了,快 3 点才调完,好浪费时间啊,感觉没救了。

看 T2,不太会,一开始甚至写的区间 DP,用 bitset 优化到\(\mathcal O(\dfrac{n^3}{32})\) 。又想了一下,发现 \(\mathcal O(n^2)\) 是简单的,枚举终点,向前扫,维护一个栈,当前字符和栈顶相同相同就弹栈,否则入栈。合法当且仅当栈为空。

但是以为难度递增,T2 只拿 50 不太甘心,去看 T3。

什么鬼,T3 放大模拟?看了看 T4,感觉不太会,时间似乎还够,直接开 T3。

写了一半 T3 发现又读错题了!

当时非常难受,已经快四点了,实际拿到的分数只有 150 分,看着写了好几十行的 T3 假的 code 比较崩溃。

T3 不敢继续写,T4 不敢开,T2 也不会,很想当场睡觉,但是知道肯定是不能摆的。

出去洗了把脸,冷静分析了一下,目前只有 T1 的 100 加 T2 的 50,T4 也没来得及思考,接下来开题不当很有可能直接崩盘。深思熟虑后还是决定重构 T3。

读好题,理清思路后 T3 意外的好写,写了 30 分钟,调了 20 多分钟,大样例过了,瞬间舒了口气,这时才五点不到,感觉心情好多了。

接下来看 T4,理性分析,推推性质,发现可以二分答案,转化为设计一个排列,使得儿子的标号大于父亲并且任意点的标号小于等于一个 \(need\)\(need\) 可以二分求。瞬间会了菊花,觉得链也是好写的,这时候其实也在犹豫是写暴力还是拼正解。觉得前面已经有250 了,直接飘了,冲正解!

又想了几分钟,发现父节点在儿子前面的限制可以转化成一个约束:把子节点排序,父节点的值和,但是这样好像是一个充分条件,必要性不会证,犹豫了一下,决定写写试试。

写了 30 多分钟,样例一二一遍过,样例三死活过不去,开了 int128,样例三过了!

心脏怦怦跳。

样例四。

文件。

运行。

1.3 秒。

fc tree.out tree.ans。

回车。

找 不 到 差 异!

当时整个脑袋嗡嗡的,有点不敢相信真的切了 T4,上个厕所冷静一下。回来把 T2 50 分补了,还剩将近半个小时,感觉非常赢。

想过挂拍子,但是 T1,2,3 都没啥拍的必要,T4 拍子又巨难写,遂摆烂,继续检查。T4 1.3 秒感觉不是很稳,实际上可以推一个巨大困难多系数二元一次不等式来避免内部的二分查找,消去一只 \(\log V\) 但是时间实在来不及。只能希望 CCF 机子快一点。

检查了好几遍文件输入输出和文件夹,感觉没啥问题直接交上卡点走人。

出考场给 lgx 打电话,他切了 T1,3,T2 只打了 \(\mathcal O(n^3)\) 的 35 分暴力,感觉有点可惜。modinte 和 dwt 都轻松 AK,太恐怖了。

在大巴上听说 T2 有 CF 的原题,非常不牛,没见过套路,感觉输麻了。

估分 \(100+50+100+100=350\),云斗上测的没问题,感觉很稳。dwt 和 modinte 都挂大分,lgx 甚至 T1 挂了20,听说 dwt T4 写了神秘线段树,被卡 TLE 了,有点可惜,他 T3 好像也挂了,希望他们几个 NOIP 不要失误。

忽然发现 T3 数组开成了 \(101\),可能会被极限毒瘤数据卡掉,祈祷 CCF 数据别太狠。

总的来说,这场比赛真的和过山车一样。开题顺序的一念之差,可能直接导致崩盘。T4 能猜出结论并拼出正解也有很大的运气成分。T2 没见过套路感觉还是做题少导致的。希望官方数据不要挂分了。。