OI回忆录

高一成功退役(窝湖南的)

小学

我第一次接触信息竞赛是在小学,那个时候跟着我们雅礼的另一位教练上了一个学期的信息,但是可能不太喜欢那个老师吧,就短暂的跟信息再见了

后来一年跟着现在的雅礼教练上了信息课,突然发现自己很喜欢这个玩意,就待在机房直到初中,但其实一直很菜还喜欢玩游戏

初中

初中我的信息都比较惨,三次距离提高一等分别差$$1pts,5pts,9pts\dots$$(一直在退步…尤其是初二,是因为tpy去掉了HN一丢丢名额…)

我初一初二比较叛逆,不太愿意读书,再加上初中学校的一些矛盾,导致一直有些颓废,本身对信奥当时虽然很喜欢但是也没有报太大希望说初中搞得很好,就凉凉了

初三是希望可以拿到提高一等,这样可以保证自己可以升学。但很不巧我考场上出现了一堆小错误怒丢165…于是又一年凉凉

很幸运最后直升到了雅本,接下来就开始高中的Oier颓废生活

高一

CSP2019

Day0

感觉自己要退役,一整天都慌得一批,下午提前跑回家搞了一下午+一晚上的颓,越搞越慌,睡前还看了会儿板子

也不知道为什么,9:30睡的觉,脑子里一直想着第二天的考试,头晕乎乎的,2:30才睡着,心里想着凉了凉了

诶考后一问好多人都没睡好…

Day1

早上好早就到了考场,因为前一天没睡好挺不舒服的,还感觉有点拉肚子,早饭味道也很烂,种种暗示着我真的要GG

看到题目,T1一道数学题,T2一道树上问题,T3也是树而且感觉挺复杂的,感觉不太妙啊

先确定开题顺序123,刚刚看T1没什么思路,内心一脸懵(D1T1就不会,这可咋办)

接下来看了几眼,觉得就是对于第 $i$ 位 $mod\ 2^{i+1}$ 后是前 $2^{i-1}$ 或后 $2^{i-1}$ 都是0,否则就是1

一看数据范围有 $n=64$ 那这样的话最后两个都会爆 $unsigned\ long\ long$ 啊,咋办凉了凉了

定睛一看,觉得最后两个不用 $mod$ 所以没啥问题,只要后面两个特殊处理一下就好了(诶考完同学们都用的 $xor$ 好慌感觉自己做法跟其它人都不一样啊)

T2觉得可以记一下后缀和,设 $)$ 为 $+1$ , $($ 为 $-1$ 就可以了,只要后缀最小值为 $0$ 的都可以造成一的贡献,从上往下推就可以了

觉得可以拿线段树维护一下,然后查询套一个二分(线段树上本身就可以二分啊啊啊,为什么我不写???),这样是 $n\log_2^2n$ 的,当时测了一下极限数据 $0.5s$ 感觉很稳,谁知道考完最后四个点被卡掉了…

这个时候一看时间才 $10:00$ 那今天很稳嘛,肝T3!!!

接下来 $2h$ 啥都没干,写了个链的然后发现写挂了,人均 $210$ 就我没有…

今天睡得很舒服,恩D2翻盘!!!

Day2

今天解压密码 抓紧时间 哇听起来就不是什么好事,难道今天题还毒些???

T1计数T2数学T3计数哇这真的全是数啊…

T3看起来还是不太可做,T2感觉是道DP?(当时没仔细看题,以为是一道斜率优化原题),不慌不慌慢慢来

我数学不太好呢,T1就感觉不会容斥,冷静分析一波后成功设出了状态,恩 $O(mn^3)$ 有 $84$ 优化之后再想吧

T2这时才发现本来看错题了,恩那先写份暴力看有没有决策单调性什么的,码完 $O(n^3)$ 就开始打表

首先猜了一个贪心的做法,好激动啊 $O(n)$ 呗,一敲完样例都过不去,冷静分析一波觉得这是错的咕咕咕

接下来发现每次更新都是一个后缀,只要拿一个线段树和二分记录一下就好了,恩 $O(nlog_2n)$ 很稳

又才 $10:00$ 呗,不会 $T3$ 还是不会吧

决定 $T3$ 不仔细想了,写完暴力想办法让 $T1$ 做出来,花了一个小时写完 $75pts$ 暴力

剩下一个小时啥都没干…

考后自测 $100+80+10+84+88+75=437$ 恩还行…

总结

今年 $CSP$ 好难啊咋办…凉了凉了,感觉自己好菜啊…能不能水进冬令营啊咋办…