PKUWC 2019 游记

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

持续更新。

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

歌曲推荐 - 《心愿》

学习 @GNAQ 大佬,在博客里推荐一些歌 qwq…

《心愿》 by 王泽 & 杨颖 & 乔媛 & 唐景莲

一首略有点悲伤的校园歌曲,记录了一代人的青春岁月。

不知不觉,这个博客已经有了 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

×