那年 @ 今日

摘要

纪念现役 2 年 OI

本站 @ 碎碎念

一路踏着星光走来,2018 四川省选也结束了,奖学金尘埃落定,看到 Siyuan 大佬一式 40 分,LMOliver 怒切 D1T2,XRY 努力学习文化课。看到 Mr_spade《我亲爱的朋友们》,心底突然划过一道彗星微茫的光,燃起朝霞映衬的春花。

首站 @ 初心

我的起点是一本老旧的《C 程序设计》,不知什么原因,就开始喜欢上编程。不知是哪里来的毅力,拿着一个小的 B5 本子,对着书上的讲解就是抄写,打下了结实的语法基础。那时根本不知道编程还有竞赛的路子,只想创造属于自己的作品。初一的时光在那时就是漫长的,虽然现在想起来是极短暂的。

看完了旧书,又花一些精力从 C 过渡到 C++,那时每天中午在机房写程序,是最惬意的时光,也因此完全无从回忆。

“二十余年如一梦,此身虽在堪惊”,大概没有这么夸张,但也足以说明了

次站 @ 洋洋

记得后来就接触到了七中的陈洋洋老师,洋洋是个很温和的老师,带着我和 GAvin 学语法,当然我就是复习了。

然后就讲到了开启我自闭大门的算法——DFS。那堂课我是深深得记得,拿着讲义,对着不到 20 行的模板代码,慌得一比,质数环问题一脸懵比。第一次体会到突破知识瓶颈的煎熬的过程,然而这只是小小的坎,面对后头的路子根本连坎也算不上吧。

不记得是怎么抢救过来的,只知道学完那堂课,仿佛埋下算法的种子,生根发芽。心里对编程的态度多了一份学习。紧跟着 DFS 的就是 BFS,大概又煎熬了一两节课吧。

大概就是在这个时期,又买了一本《挑战程序设计竞赛 2》,那时看这本书就是眼花缭乱目不暇接,大概看自闭了十几次吧

叁站 @ 洛谷与 NOIP

本校的信息老师推了洛谷,让我们做题。正是两年前的 4 月。于是我就干了大家遇到新 OJ 都会干的事,切掉了 A+B。

春风拾拣蒲公英,播撒希望于四方;朝露浸润生命种,风华散就参天荫。算法之路大概就是如此展开。

9 月,初二

就是在今年的国庆,上了洛谷网校的集训吧。不过基本上没怎么认真听,想的是屯课件后面啃(然而至今未补)

随后的 NOIP 自然而来,出生牛犊不怕火,取了普及一。那是大概是背包 DP 自闭期,完全不会 DP 吧。洋洋带我们继续学,然后就遇到了第 3 个自闭期——最短路。从 Floyd 到迪杰到 SPFA,大概只有无脑跪 % 的份了。

记得当时因为不会背 pair 套 queue 的定义,于是最先学会的是 spfa(Floyd 大概比较友好,不考虑),直到后来不知道什么时候才学会迪杰。这时洋洋就带着我们刷普及减的模拟赛,然而达不到 200 分……

就是在这个时候,大概 12 月份,GAvin 帮我们开了 typecho 的博客。有了自己的博客,自然时刻都想着放点什么东西上去。

寒假颓了一个月吧,然后春夏继续跟着洋洋走,记得在这个季节从红橙题过渡到了黄题吧

这个时期好像还写过贪吃蛇和 2048

也是在这个时期,GAvin 带我认识了 Linux 系统,从虚拟机开始,一步步摸索。大概是在期中的时候,买了 USB3 的 64GB 的 U 盘,成功折腾出了 U 盘装 Linux 系统。最开始装的自然是 Ubuntu18,在那时这玩儿好像刚出,一开始卡得可怜。于是有了 linux,那么 bash、vim 之类的也全部来了。带着初心折腾,带着兴趣摸索吧

把玩了两三个月,又发现了国产的 Deepin 系统,桌面美上天,果断切换,还装了 Windows & Deepin 双系统。而且 Linux 也能驱动独显,大概除了 IDM 和 Microsoft Office 之外的事情,我都是用 Deepin 做的吧

首坎 @ ZR

没错,就是这个令人战栗的组织,让我半个暑假沉迷自闭无法自拔

接下来的内容是我在那是集训完以后写的总结

从自信到自闭 ·ZROI2018 暑期集训总结

这个暑假来到 ZROI,感觉个人水平提高了很多,人脉也扩大了许多。

柒月

首先进行了 CD 班摸底考,当时 rk23,rating1607,然而当时认为题很难,感觉整个集训要崩……

果不其然,接下来 Scape 哥哥接连 3 天的数论轰炸,感觉自己被虐得体无完肤。当时看 Scape 起的标题叫幼儿园数论入门,然后就一天讲了 EXGCD+ 逆元 + 中国剩余定理,第二天就讲线性筛 + 欧拉定理,还有阶,原根,BSGS 一连串不知道是什么的东西。然而带着第一次体验集训的兴奋感,我居然没有自闭!而且在这小兔子实践系列下的刷题我也没自闭!

终于第三天讲小学组合数学入门,总算稍微熟悉了一点。然而 Scape 半个小时讲完小学奥数基础后,开始讲二项式定理……Lucas 定理……容斥原理……卡特兰数……斯特林数(至今不会)……Polya 定理……于是,我学会了自闭!

接下来是数论的模拟赛,Day1rk13,rating+46,主要考的异或,感觉良好。没想到 Day2 居然 rk2,rating+167,感觉信心回归了。

终于逃离 Scape 的魔爪,然后就是可爱的 mjy 老师给我们讲 XY 之力,总算是吃下一颗定心丸,稍微轻松地学了一天的 XY,精力充沛,还 A 了人生第一道黑题……

然后是美国 OI 竞赛前 10 的罗 hk 老师为我们上课,讲了两天的贪心,感觉不错,渐入佳境……

接下来是 tqy 大佬讲图论,讲到自闭……

捌月

8.1 打了一场骗分赛,骗分拿 rk4,rating+76. 领悟了 Scape 奆奆的教诲:打 OI 赛,不是看你能 AC 多少道,而是看你能不挂多少道。

8.2 打了一场 ACM“菜鸡互啄杯”,我,GavinZheng 还有一个北京划水的 HTX 组队,结果除了 Siyuan 小姐姐的外卖小哥队,我们 C 班第 1,爽得一逼

接下来是 wlp 老师讲图论,总结一点就是 tarjan 很伟大,很牛逼,然后自闭……

mjy 老师给我们讲简单 DP,结果勉强听到状压,写题的时候成功自闭……

第二天讲数位 DP……全程自闭……

然后是一场令人窒息的 DP 模拟赛……5 道题,强行打了两道题的正解,然后就自闭……rk14,rating-14.

终于讲到数据结构了!然而线段树树状数组树剖前缀和轮番轰炸,最后自闭于平衡树……

打了一场数据结构的模拟赛。第一题打了模板结果卡输入……我 TM 就 cin 了一个字符啊!100 变成 40……T2 面向数据编程,T3DP 居然拿了 61……rk12,rating 居然勉强 +5……我恨 iostream

然后讲后缀数组……一个下午的时间都用来理解 mjy 的代码……居然没有自闭!

然后是 AC 自动机,趁着昨天没有自闭的光环,被我强势图解,还投稿了一份洛谷日报~

接下来 mjy 老师继续讲杂题,半自闭自动机系列……

然后是 mjy 的毒瘤模拟赛,rk23,rating-104……探索海底系列

接着 zky 的毒瘤模拟赛,T1 卡输出……100 变 0……rk7,rating 居然 +32,原因:一共 44 人参赛,26 人爆蛋……哈哈哈,于是 zky 的 Day2 模拟赛只有 27 人报名……

终于,第二场 ACM,Siyuan 家族团队前五占四席,然而我,GavinZheng,Xry 组队 “Siyuan 小姐姐吊打集训队” 屈居第五……不过还是不错,鼓励鼓励

然后,又回到 Scape 哥哥的数论……一发莫比乌斯反演 + 迪利克雷卷积成功让我自闭……

第二天的数学期望,自动自闭(最近才弄懂)……

第三天,简单容斥?休克……

最后讲 DP,然而之前 mjy 都讲过,于是就自闭了

又一场综合模拟赛,rk12,rating+36.DP 本来 70 被卡成 20,原因不明……

晚上 glx 的毒瘤模拟赛,T1 数组没开够,100 变 60……rk12,rating-8.

最后的亦可赛艇杯,只因 T1 题看错,没写暴力,不会期望,没敢打……rk31,rating-194……变成 1649,退回原点……

然后,文娱表演完了,就结束了。

一些小梗

知乎 - 饮水思源二三事

思源小姐姐系列

小兔子实践系列

身败名裂系列

结语

来 ZR,感觉见识了很多国内顶尖优秀的 OIer,也意识到自己的渺小与蒟蒻。路很长,只有一步一步踏实地走过,才能走到顶尖。

——2018.8.25

现在再来简单总结一下,大概就是,“忆昔午桥桥上饮,坐中多是豪英” 吧

ZR 暑假集训是生硬而尖锐地炸开视野,巨大的信息冲入脑中。自闭了一个暑假,就是用此后的时光去斩破浮现的瓶颈。膜拜天下第一的曾经天下第一说过,“来这里集训不是让你全部学会,是告诉你还要学些什么”

学无止境

上道 @ 修行岁月

仿佛取经的漫漫长路吧。暑假完了就是 NOIP,每周是 ZR 的提高十连。最后拿了提高一。这个时期就是回嚼知识的时期,完善博客,码题。就是在这个时期吧,过掉了提高组一大部分知识点,包括简单数论,Tarjan 图论,各种 DP 优化,一些数据结构之类的。打了几场 CF。

成就感来源于不断增长的博客文章数吧

这次国庆是到的重庆参见 ZR 的集训。大概内容不记得了,只记得订酒店的时候和家长有一次冲突吧。然后好像自己还拿了一次 RK1 来着

今年寒假没怎么颓,前几天到四中蹭资源,后面到金华跟着 ZR 集训。到金华是只有一个人出远门,GAvin 没跟着去。什么事情都得自己料理,母亲也很关心我吧。不过 Parker 也去了,虽然他去的是提高。

这次集训倒是好好和 HUHAO,HDP,XRY 交流了一番(一起颓得很开心),然后又自闭地很惨了吧。也是在这个时期悟到一个道理,就是适当的颓废还是能调动积极性的,不能闷着头学。

3 月的青岛省选集训,XRY 没来,我和剩下两位继续开心地颓 MC 吧。这次又认识了 zyb,xy,wqy 等众多大佬吧。最后打完最后一场比赛,100 分居然 RK5,Rating 又跳回来了

那年今日 @ SCOI2018

以下是《SCOI2018 游记》

Day0

早上 7:20 从学校出发前往电子科大,下午打了一个小时的笔试(duck.ac/beibishi)=duck.ac/ 被鄙视)

下午到宾馆折腾了一下午的 manjaro deepin,然后一发不可收拾地果断放弃 Deepin 转投我大 Arch。yaourt 大法吼啊(虽然已死)

然后,就折腾到了凌晨 2 点。

我要飞~

成绩: 97

Manjaro 入门点睛

关于系统安装:如果是 UEFI 启动的话要用 GPT 做启动盘(不过貌似仍要开传统模式才能加载启动盘)

如果要双系统,一定记得设置一个 500MB 的 FAT32 挂载 boot/efi 做 UEFI 启动

如果有 Nvidia 独显,开机的时候记得在 quiet 参数后加一个 nouveau.modeset=0,等系统更新完了,安装了大黄蜂驱动后就不用担心开机卡死的问题了

关于输入法,fcitx 安装中文输入法的时候要把其他的什么 qt,gtk 之类的软件包一起装了

关于 vim,要使用 clipboard,装 gvim

关于微兔锐,用 yaourt 安装的话貌似开机不能自起,用官网脚本安装后可以

Day1

凌晨 2:00 睡,早上怎么提神?emmmmm 洗澡算吗

昨天折腾到凌晨 2 点,早上起来是真的自闭。到考场还有点晚了,大部分都开始噼里啪啦地敲配置什么的。

开 T1。emmm 欸?样例为什么要 9 回合啊……不是 6 个回合就走完了吗……T1 不可做啊窝还是太菜啊

5 分钟后……

开 T2。欸?换根法 DP 可以淦 20 吧……怎么还区间询问啊……正解是树剖吗……我先淦 20 再说吧

1 小时淦完暴力后

啊……好像还有 15 分的主席树啊……太难写啦……skip

开 T3。欸怎么这么球形空间啊……数论题吧……哇 30 分暴力怎么比 T2 还良心

推了一会 DP 式子,有一个向下取整的可以用数论分块做,齐次幂的前缀和可以线性预处理,DP 的状态转移空间是根号的。

开 hash 表可以过 50 吧……unordered_map 不能用咋办啊……手写板子吧

大概 3 个小时淦了两个暴力……

看 T1。emmmm……哦!好像是魔改汉诺塔啊

1 个小时打完

欸……这个 30 好像不起作用啊……还是要高精才行啊……

1 个小时码了高精的板子

最后 10 分钟了啊……自闭了啊

面试

欸?无领导小组讨论是啥啊……

啊……国民党失败的原因啊

历史没学好咋办啊

评委:5 号同学你怎么一直不发言啊

sshwy: 我大概是自闭了吧

sshwy: 我大概是在划水吧

出成绩

wc……T1 高精炸了啊

钟 dalao(雨田):高精不是过了吗

sshwy: 压位高精?

钟 dalao: 不用啊

sshwy: 不是汉诺塔吗

钟 dalao: 是汉诺塔啊……要找规律啊

sshwy: 不能直接上吗

钟 dalao: 不知道吧。反正我 A 了(人家 120)

sshwy: zblzbl

T2。emmm 怎么多拿了 5 分啊行吧

T3。怎么暴零了啊……下次开数据分治吧

可怜的 sshwy 大菜鸡: 75=50+25+0

Gavinzheng 认为很猛的成外妹子:165

美酒在手美人环绕的 Gavinzheng: 90

钟爸:100

唉……我真是太菜了啊……继续颓吧

正经的总结

其实感觉自己心态炸了,一心想要得分。当时 T1 没读懂,就先打了 T2 的 20 分;打 T3 的时候觉得 30 分暴力太少了,打算一口气淦 50 分,结果反而爆 0;回来做 T1 的时候突然读懂题以为可以 A,结果没有考虑清楚复杂度,白写了 1 个小时的高精;这 1 个小时我可以吧 T3 再拿个十分走的。

不过放松心情并不是颓的理由,只是告诫自己以平常的心态来对待竞赛。毕竟学竞赛不是下注,以一年的文化课时间赌一个一本约。再说目前局势动荡,竞赛这条路是否走得了,走得远,还是未知。

摘下厚重而残缺的帽子,我们都是本真同源的灵魂

Day2

凌晨 4 点睡……唉

T1 啊……20 分暴力吧

T2 啊……欸?30 分暴力的复杂度怎么不大对啊(其实是考场状态没对,其实没有卡那么紧)去做 10 分的暴力吧

然后推了大概半个小时的 T2,结果没有结果……

T3 啊……哇线性基没学啊又少 20 分暴力啊……只有 20 分啦

期望:50

Sshwy 的 Day2 定律

每次打 Day2 的时候,sshwy 总是会在开考 5 分钟的时候肚子不舒服,于是 5 分钟读完三道题后就奔厕所,顺便想题

emmmm

估计是吃华莱士 KFC 的原因?都是在电子科大附近点的外卖……

总结

还是年少轻狂啊

其实到 Day2 的时候已经没那么紧张了,感觉进入了一个玄学的状态吧。左边 7 中的大佬 Day1 就 130,Day2 考完还听他说把 T1 切了。自己的路还很长,大概都是未知数吧。也许明年又会杀出黑马,也许以后竞赛就灰了。

不过,念念不忘,必有回响。也许模拟退火,旋转卡壳,幻想乡,各路神仙博客什么的,以后就忘了,但学习竞赛的那一份初心,将恒常在。“优秀 OIER 的价值从来都是由自己体现,而非由用的算法体现。” 优秀的之所以优秀,是一份初心与信念,阳光与泪水所映射出的表象。拼搏一定不是随波逐流的,但一定是年轻的。

正所谓,不忘初心,方得始终。人活在碎片构成的时光中,也依靠星星点点的憧憬与敬畏,走向前方。

SCOI,有缘再会!

——2019.04.14

那年今日,正是此时吧

抱着 “闲登小阁看新晴” 的心态吧

花开花落 年复一年

初心不改 青春常在


  转载请注明: Sshwy's Blog 那年 @ 今日

 上一篇
容斥原理入门 容斥原理入门
摘要 啃论文系列~ 考容斥原理本身的题不多,容斥原理常用于某个算法部分的求值。 2019.6.16 编入精选文章。 入门 某班有 a 歌人擅长唱歌,b 个人擅长画画,c 个人既擅长唱歌也擅长画画,问有多少人至少有一种擅长? 发挥你聪明的大
2019.04.25
下一篇 
集合的整数表示 集合的整数表示
摘要 整理一些集合的小操作 对于大小为 的集合,要求我们表示该集合的任意子集,借助于整数的二进制表示,可以按以下方式编码为整数 f(s)=\sum_{i\in s}2^i位运算借助位运算来进行集合的运算。一系列例子: 意
2019.04.20
  目录