PKUWC 2019 游记

谨以此文记录我的 OI 生涯的第一次向 PKU 冲刺的机会。

持续更新。

最近有人用脚本(或其他)方式在这个博客刷大量垃圾评论骚扰。我有一些内容想留给那位同学:

不知不觉,这个博客已经有了 10000 的访客数和 30000 的访问量,memset0.cn 也陪我走过了将近一个年头。
想当初的自己看到 rxz 哥哥的博客非常帅气,经历几番波折终于折腾出了自己的博客。
而那时候,这篇博客的内容也非常肤浅(大概也就初学线段树的水平 233),到现在学了越来越多的知识,能够写出稍微有点意义的题解了 qwq… 自己也从一个普及组选手,逐渐进化为一个打提高的菜鸡。

回首过往,浮想联翩。
如今 PKUWC 在即,也是决定我命运的其中一站,期盼着的未来,会是那个美好的结局吗?

100 篇文章纪念

memset0 的博文终于有 100 篇啦,要继续坚持下去哦…

(然后又偷偷从老博客里搬了几篇回来…)

2018 感谢有你

2018,感谢有你。

第一次写总结。由于 memset0 的语文一直处于垫底水平 + 停课半年没写过东西,请原谅一下我糟糕的表述,谢谢 qwq.

NOIP2018 爆零记

Day -1

注意这是 -1 天

上午照常模拟赛,考 NOIP 信心赛。

虽然是信心赛,但是题目好难。T1 洛谷原题,黑题难度 QAQ 。后两题稍微简单一点,但是如果开始刚了 T1 估计就来不及了。

我先开了 T2 ,推出了容斥,期望 $O(t \log n)$ 的 70 分。然后去开 T3 ,写了个 $O(n \times m \log n)$ 加卡常,期望 80 。最后开 T1 ,一遍写对了一个动态开点线段树,特判特殊情况拿到 50 分部分分。

考试成绩出来,诶 T3 怎么 A 了 QAQ 。T2 没有输出 STO yyb ORZ (无解情况)少了 15 分, T1 还是预测得分 50 分。算是涨了不少信心吧。

下午继续写板子,任务列表也清的差不多了。还有一些很难的算法感觉也不会用到懒得写了。

晚上老师讲竞赛时间安排和一些注意事项,同是说明天是 “ Open Day ” ,我们可以光明正大的地颓废放松 233 .

讲完之后感觉压力突然加大,本来以为很遥远的 NOIP 真的近在眼前了。真的,真的,好紧张。找学长哭诉。 lyc 哥哥特别好,特别温暖,给了我许多安慰 qwq。

Day 0

上午开始机房集体颓废,打 jokebird.com 爆踩全服。之后开始打球球大作战。也有人 5 人组队 LOL (第一局被对面五杀,第二局吊打对面 233)

下午继续颓废,看了点数论。

在赛百味吃完饭的时候遇见了 zx2003 学长,他给我们讲了一些他的故事,也给了我很大的鼓励。

晚上颓了一会会儿,然后手推 EXGCD 和 EXCRT ,虽说感觉不会考,主要还是熟悉一下推式子的感觉 QAQ 。

接着去楼上机房蹭 RP ,好紧张,又哭了 QAQ 。但是学长的安慰真的很有用(不然可能窝晚上心态就蹦了)。

睡觉的时候还是有点紧张,半夜睡不着。

Day 1

但是早上起来精神状态还是很好的。一路赶去学军紫金港路也很顺畅。

早点到校门口集合领准考证,我们有同学的准考证在校园里还没领但是要有准考证才能进场 233 。还好老师送出来了。我们初中几个还拍了合影。

进考场前最后膜拜了一次大佬。坐我左边的是一个超好的(不认识的)高三学长。当时我特别紧张,他安慰了我也给了我鼓励,也让我平静了一下心态。

开题,解压密码 Fei2Xue@Lian$Tian! 。学军体育馆可真冷。

T1 上手一个 $O(n ^ 2)$ 贪心过了大样例,然后用 ST 表优化成 $O(n \log n)$ 开始拍。

T2 一开始以为是 exgcd ,但又感觉不可能那么难。看了眼 T3 没思路,滚回来手玩了一下样例想到了个背包。一发过了大样例感觉很稳。

T3 先写了部分分,和状压暴力对拍。差不多写满 55 分部分分,正解的思路也有了。此时我可以写二叉树的部分分到 80 ,也可以直接写正解。经过了一番焦灼,还是写了部分分,毕竟写正解也有可能调不出来。

考完和同学 yy T3 ,发现了一个思维漏洞,不过很容易拍出来,而且我也立马想到了补救措施。不过如果这是考场就不一定了。所以感觉当初自己稳一点写了部分分也是挺正确的。

估分 $280 = 100 + 100 + 80$ ,考完听说 Sooke 、mocania 、 LJC00118 、 Isonan 都 AK 了。唉,毕竟技不如人,甘拜下风。

下午继续颓废,帮学长安 Flash Player 但是失败了,同时跟同学继续嘴巴 T3 。

晚上颓废 + 写游记,也不是很紧张了。

明天加油:尽人事,听天命。

Day 2

无论如何预感今天的题目会很难。跟同学开玩笑说今天写满暴力就好了,结果还真 tmd 暴力滚粗了。

解压密码和昨天连起来:“飞雪连天射白鹿,笑书神侠倚碧鸳。” CCF 的解压密码倒是一年比一年有创意了233。就是能不能不要出原题QAQ。

开 T1 ,一开始以为是一张图,没想到是一个树和基环树。等等,这一题当两题的画风,让我想到了栗栗的书架啊。先随手写了个树的情况,过了大样例,开始看 T2 。

T2 一眼以为是状压,一脸懵逼。还成功出现了“关于 T2 的题目解释请看 T1 的情况”(那放洛谷上怎么办 233)。本想枚举个数然后直接判断,结果第二个样例输出 144 瞬间懵逼。写了发状压枚举路径判断过了两个小样例。开始跑 $5 \times 5$ 的但始终过不去(为什么别人的状压可以跑 $7 \times 7$ QAQ)。发现了每次 $\times 3$ 的规律。

没办法,开 T3 ,44 分的 $O(n m)$ 暴力很好写,一遍过了大样例。开始想正解却没思路。目前已经有 $60 + 50 + 44 = 154$ 分了,还有两个小时多,先上个厕所冷静一下。

回来想继续优化 T2 ,但脑子里一直把枚举矩阵的 $O(2^{nm})$ 复杂度搞成了 $O(2^{n+m})$ 。结果当然是就算苦苦优化还是过不去大样例,白白浪费了半个小时。

接下去去看 T1 $n = m$ 的情况,由于 $m = n - 1$ 的情况可以 $O(n)$ 完成,我把 $n = 5000$ 的数据范围当成了 $n = 100000$ 最后强行想出来了一个 $O(n)$ 解法但已经又过了半个小时。还有一个小时感觉写不完这个及其麻烦的做法,赶紧苟了个成环的部分分。

只能看 T3 部分分。一条链上的情况考场里一脸懵逼毫无思路,考完出来却豁然开朗(mmp)。其实把 dp 的转移变成一个个矩阵放到线段树上区间查询即可。然而考场上我脑子里一片空白,什么也想不到。

回去检查 T2 , T2 的大样例好毒啊,不仅给的数据范围小,而且都是 $n = m$ 的,感觉有坑。检查了老半天暴力还有不到半个小时。发现 $n = 1$ 的情况不是每次乘以 $3$ 而是 $2$ 。赶快改过来(差点就没分了),捡回一条狗命。

最后时间照常检查文件,交卷。考完出来要了隔壁同学的 QQ 号,也算是一种缘分吧。

Sooke , Isonan 照样稳的一比 , $200+$ 。感觉考场 debuff 太严重了,真的脑子里一片空白。平时模拟赛可以拖一段时间交卷,大胆地去尝试正解,然而考试的时候不仅没拖延的可能,还要单独花时间检查文件等等,一下就丧失了去尝试正解的勇气。

最后期望得分 $189 = 80 + 65 + 44$

Day 3

出选手代码了,去洛谷上交了一发竟然 $ 474 = 100 + 100 + 80 + 80 + 70 + 44 $ ,激动的要死。

当然也有同学 D2T1 的 $O(n log n)$ 做法挂了,但还是比我高。

Day ?

CCF 官方成绩出了,只有 $ 454 = 100 + 100 + 65 + 80 + 65 + 44 $ ,原来 D1T3 的分支不超过三按照我的那种方法有可能在根节点三叉。

看来 WC 无望了,只能希望可以上 PKUWC 的初中线吧。

这其实是一个比赛啊啊啊啊啊!

反正考得超级辣鸡的!

这是我第一次参加ACM类的比赛,估计也是我的第一次写游记吧。
这次参加浙大校赛的,不光有他们大学生,还有各路中学生;同时,我也在队伍里面发现了小学生的踪影(就差幼儿园的了)。
整体的氛围还是比较愉快的,可能是因为三个人一起做题的关系吧,没有OI那么压抑。

这次比赛给了我们一点经验,也让我们看到了很多不足的地方(同时我现场领悟了如何数组模拟链表,thanks to fjk)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×