AHOI2019退役记

$DAYquad -1$:

连作业都不写了来刷题。。。

希望能长点$RP$吧。。。

反正也是抱着退役的心情来考试。。。

我要是到了周日还不出长门我就退游!!!

$DAYquad 0$:

早上一起来就开始收拾东西。

什么乱七八糟的都无脑塞进包里:扇子,草稿纸,等等。

结果到了火车站才发现忘记带六神花露水了。。。

感觉还没被$AHOI$弄疯就先被蚊子弄疯了。。。

十二点半的火车,竟然只有站票。。。

但是上车之后好歹找了个座位坐下。

右边是一妹子,左边。。。感觉像个大学生啊。

因为我瞄一眼他的手机,发现他在看$C++$入门级的讲义。

关键是他的代码好短啊。。。感觉我只有$NOIP2017$写过这么短的代码——小凯的疑惑。。。

然后我就不知不觉地睡着了。。。

一觉醒来——咦?右手手臂好麻啊?

一看,妈耶?!

右边的妹子靠在我的手臂上睡着了!!!

对,没错,你没有看错——靠在我的手臂上睡着了!!!

#%@#@!&@%&@##@!#@%mmp。。。

幸好我没有跟同学一起出去,不然他们拍下照片,我的清白就。。。

不过小姐姐长得蛮好看的,戴个黄帽子,找个人形容一下:《碧蓝航线》里的胡德姐姐。。。

过了一会儿她醒了。。。

然后我们尴尬地对视了一眼。。。

然后就没有然后辣!

然后接着睡觉。。。

睡了一会我不想睡了,于是醒来看风景。

一路煎熬到合肥。。。

火车的终点站是合肥。

其实,我的$OI$生涯的终点站也是这里了。

出站,上车,一切如往常一样。

到了合肥一中,找到$JL$,拿了狗牌,去试机。

然后$JL$告诉我今年的秩序册换成电子版的了。

啥?不收钱就不印秩序册?啥道理?

算了去试机。。。

这。。。显示器怎么是正方形的啊?

看的好不舒服。。。

而且座位和显示器之间还有一段距离,是不是知道我看不见然后故意刁难我啊喂?!

还有这键盘怎么这么不顺手,这个$diagdown$键怎么在$shift$的旁边啊?

反正是各种差评。。。

算了,将就一下吧。

开始敲$K-D Tree$。

结果突然发现我左边的妹子手速好快啊!(一定是和我一样单身N年。。。)

不管她了,敲敲敲。

再写个暴力拍一下。

等会儿,对拍程序咋写的来着?

完了,不会。。。凉凉。。。$GG$。。。

算了,人工拍!

不知不觉试机时间到了,于是出考场。

然后$JL$又告诉我今年$AH$有试题讲评了。

啥?$AHOI$从来没有过讲座,今年竟然有讲评了?

反正去听一听,玩一玩,划划水啥的。。。

晚上就吃个饭,打打板子就睡觉了。

$DAYquad 1$:

早晨起来,吃个饭,然后走向合肥一中。

$7:30$准时到,然后告诉我要$7:40$才能进去。

于是在外面和$JL$预测今年考什么题。

他说:“今天肯定有至少一道$DP$。”

我:“$T2$肯定是线段树加上啥玩意。”

他:“$AC$自动机可能会考,但是可能性不大,后缀数组应该不会考。”

我:“$FFT$应该不会考吧。还有你讲不考后缀数组,那就是一定要考了。。。”

这是个神$flag$。。。

。。。。。。

到了$7:40$,进考场。

坐下,开始敲起始源。

顺便把文件夹啥的都搞搞好。

发现文件夹名:

$xor$?异或?去年$T1$好像也是异或。。。

$string$?字符串?不会真的被押中了吧。。。

$software$?软件?$NOI2015$?树剖?

坐等发密码。

密码是什么啊:$0cdceee809db$

不知道,先开题面。

第一面着实把我吓了一大跳:

怎么$T2$给了$8s$啊?!不会是什么毒瘤字符串吧。。。

怎么内存都是$1GB$啊?!怎么还要开$O2$优化啊?!

一脸蒙彼利埃。。。

看$T1$。

这题好眼熟啊?!

这不是可持久化$Trie$乱搞就好了么?!

于是我又双叒叕(you shuang ruo zhuo)切了$T1$?!

等一下!有个严重的问题!

可持久化$Trie$怎么写的来着?

完了!不会啊!早忘光了啊!

$NOIP2018$之前我写这个玩意就像写$a+b$一样。。。

这就是老年过气$OI$咸鱼的下场?

只能写暴力?

退役$2$个月,啥都忘了啊!!!

完蛋。。。凉凉。。。$GG$。。。认栽。。。

写暴力吧。。。

暴力还不好写,前缀异或和,$n^2$枚举左右区间然后丢进堆里完事,$10min$解决。

开$T2$。

什么乱七八糟的字符串啊?

还有这个支配是个啥意思?

算了,开$T3$。

题目名:骗分过样例。

预测$Day2$有一道题:暴力出奇迹。。。

第一句话:“这是一道传统题。”

我@#%#^#&@&#^&@*#mmp。。。

然后看完题面。。。这不是提交答案题么?!

出题人强行把提交答案题出成了传统题。。。

$day2$那道题不会是交互题出成传统题吧。。。

摘自知乎:

那我打表不就好了?

然后看到一句话:“文件大小不超过$100K$。”

这。。。算了,好好分析数据。。。

第$1,2$个点是快速幂没得说。。。

那个$1\_998244353$都把模数搞好了。

赶紧敲好。

那,第$3$个点是。。高精度???

我突然想起很久以前的一个$flag$:

所以!我决定!跳过!

我才不会告诉你我不会写。。。

然后这个$1wa\_998244353$是写挂了的快速幂吧。

好像是溢出了$int$。

那个$2p$是判断质数吧。

$nleq10^{18}$?

这个。。。线性筛不行了。。。

没事,我还有$miller rabbin$!

选10个质数,然后费马小定理。

但是那个$2u,2g$是个啥?

还有,这玩意怎么打不开样例啊?

我还重启了一次。。。

$2u$有正有负,这个应该也是搞什么玩意。

$2g$不知道是个啥。

先丢一边不管。

嗯?怎么还有$1?$这种点?

难不成是模数不知道?

这我怎么弄啊?

我这个大智障竟然没想到暴力枚举这个质数,我只知道这个模数应该在$100W$附近。。。

于是$GG$。。。

回头看$T2$。

突然明白这个支配是个啥意思——这不就是边嘛!

那不就是:

假如$A_i$连有向边连向了$B_j$,并且$B_j$是$A_k$的前缀,那么我们就可以在$A_i$后面接上$A_k$。

如果所有的边形成了环,那么说明可以无限接下去,就是$-1$。

没有环,就求最长链就好。

关键是那个前缀怎么搞。

这。。。不是后缀数组乱搞么?

于是我又双叒叕$A$了$T2$?

等一下!还是那个问题!

后缀数组怎么写的来着?

完蛋。。。凉凉。。。$GG$。。。认栽。。。

写暴力吧。。。

$SAM$是更不可能的。。。

$AC$自动机?

算了,反正分数最重要。

我竟然连$AC$自动机都记得,不记得后缀数组。。。

简直无语。

算了开码。

好长啊。。。

中间出了一大堆锅。。。感觉不是在码题,是在补锅。。。

然后翻数据范围的时候看到了这样一段话:

十二省联考命题组温馨提醒您:

数据千万条,清空第一条。

多测不清空,爆零两行泪。

良心出题人。。。

然后赶紧清空数组。。。

我好像在$NOIP2018$也干过类似的事。。。

弄了半天终于过样例了。

但是这个最大的样例怎么$RE$了啊?!

算了,不管它。

回头看看$T3$。

然而还是什么也没发现。。。

就这样闲到了结束。

出来和$JL$投诉——$T3$有毒。。。

稍微讨论了一下就回去吃饭。

估分大概是$60+40+?$。

结果睡到$2:30$才醒,急匆匆地赶往合肥一中听讲座。

 结果赶到哪儿才发现一开始是广告时间。。。

害我急出一头汗。。。差评。。。

而且这个广告是一个刷题网站,我都懒得听的,有洛谷在,其他都是辣鸡!

按照洛谷的服务,洛谷说第一,没人敢说第二,第三差着十万八千里!

我对洛谷就是这么自信!

然后过了一会儿开始讲题。

然后这个时候我突然反应过来——$T3$那个$2u$是筛莫比乌斯函数$mu$!

我怎么这么智障啊!!!

听王子聪讲题。

$T1$果然可持久化$Trie$乱搞。。。

$T2$果然后缀数组+最长链。。。

$T3$果然$2u$是$mu$。。。

丧心病狂,丧尽天良的出题人。。。

$T2$是王队长出的,$t3$是于老师出的。。。

$T2$的后缀数组标解跑了$2.5s$,然后验题的杨老师用$SAM$跑了$5s$。。。

于是这个题的时限就变成了$8s$。。。

$T3$那个$1?$果然是模数未知,而且要暴力枚举模数,然后检验。。。

那个$2p$竟然是原根?

原根是什么都不知道的蒟蒻听的一脸蒙彼。。。

讲题人说:“正解好像写了几十$K$的样子。”

我@#%^&*#&*@#&*#@&*mmp。。。

题目中说可以打一部分表。。。所以就成这样了。。。

然后就讲完了。。。

分数也出来了:$0+0+17$。

啥玩意?我又双叒叕挂了$80+$分?

于是去申诉。。。

结果依旧没分。

回来自己测,结果发现我$T1$的确考虑到$long long$的问题,但是我的手写读入出锅了!

inline int read(){
    ...
}

于是这题就爆了。。。555。。。

$T2$是$MLE$了。。。然后发现我这个大智障把$AC$自动机的空间开到了$900+M$。。。

这不是铁定$TLE$么?!

老了。。。真的老了。。。

不是技不如人,但是只能甘拜下风。。。

晚上一直在忧伤当中。。。

$Day2$加油!

话说我还是没有出长门呢。

明天再不出长门我就退游了!

$DAYquad 2$:

昨晚被蚊子折腾的要疯了。。。

关键是只有一只蚊子。。。

早晨起来,像昨天一样吃饭、洗漱、去考场、和$JL$交谈。

反正今天至少两道$DP$。

反正省选的$DP$我都不会。。。

反正我只能写写模拟退火啥的骗骗分。。。

然后进考场。

昨天的代码竟然没删?!不用再敲起始源了!

然后准时发密码,开题面。

第一面又把我吓到了。。。

啥啥啥?$T3$竟然$1.5GB$?!$T2$竟然只有$1s$?!

算了,看$T1$。

什么乱七八糟的题面描述啊?!语文弱鸡表示啥都看不懂。。。

看了半天终于明白了。。。然而只会暴力。。。

一通敲完看$T2$。。。

这题面。。。这是《流浪地球》吧啊喂?!

还有这玩意不是最大独立子集么?

然后手玩样例玩炸了。。。回头一看——我把题目看错了。。。

原来是要每个点分在不同的集合里。。。

这。。。先写个暴力。。。

然后开始搞链。

发现只要把两端的点搞出来,从大到小一一匹配就好。

结果我这个智障不知怎的把排序给注释掉了,然后怎么搞都不对就很烦。。。

然后发现那个$nleq2 imes 10^3$很好搞,暴力枚举点,求$LCA$即可。

然后调了很长一段时间终于过样例了。

看看表——$10$点多一点。

继续看$T3$。

这。。。怎么还是《流浪地球》啊?!

还有这个题是个什么鬼啊?!

算了写暴力。

然后连暴力都写不对就自闭了。。。

改了半天终于过样例了。。。

然后大样例就$GG$了。。。

然后转头回看$T1$。

怎么看都像网络流。。。

但是那个容量限制很烦人。。。

又感觉像背包。。。

但是怎么有$4$个有交集的背包啊。。。

无奈之下再搞$T2$。

感觉就是个贪心。

但是子树合并并不会搞。。。

这时候想起了模拟退火。

当时觉得蛮可行的,于是开码。

然后码着码着感觉越来越不对劲——我怎么分了这么多类啊?!

还有,我怎么写了个$Splay$维护模拟退火啊?!

$300+$行写的我想吐。。。

然后感觉不可做了,赶紧删掉。。。

至今那个$subtask2$还在那里。。。

然后就是各种调暴力以及优化的暴力。

终于,$12:30$,结束了。

一切都结束了。

不知,该伤心,还是,该高兴。。。

中午吃个饭,然后就在阶梯教室小睡一会。

下午讲题。

结果$JL$先开车溜了是什么鬼。。。

$T1$果然是极其变态的背包。。。

$T2$果然是大贪心。。。

$T3$并没有看出来是个啥。。。

$T1$的背包很恶心,反正不是我这种菜鸡能想到的。。。

而且出题组说:“此题并不难(指 std 900 行”

“哪有 900 行啊”

“才 858 行”

确实,“选手的命要没了。”

出题人的恐怖意图:

在这样一场毒瘤的比赛中

这道题目无疑是出题人无私的馈赠

大量精心构造的部分分,涵盖了题目中所有涉及的算法

你可以利用这道题目,对你是否能够进入省队进行初步的检查

经典的模型、较低的难度和不大的代码量,能帮助你把分数收入囊中

出题人相信,这个美妙的题目,可以给拼搏于省队的追梦之路上的你,提供一个有利的援助。

哎,这都是些什么乱七八糟的玩意。。。

$T2$的链上的贪心可以直接扩展到树上。

但是还要啥$set,priority\_queue$维护。。。蒟蒻无能为力。。。

这个题本来是叫“清明十二响”的。。。

但是怎么念怎么奇怪,于是改成了“春节十二响”。。。

并且为了和$T3$配合,改成了《流浪地球》题面。。。

清明十二响,编程火葬场。北京震轰轰,OI一场空!

$T3$就更恶心,全程除了暴力阶段都处于掉线阶段。。。

断线重连$ing......$

重连失败。。。

中途好像听到了一些数据结构:可持久化线段树啥的。

但是可回退化版本栈是个什么乱七八糟的牛鬼蛇神???!!!

表示并不会。。。

而且出题人的标解$800+$行,其中$500+$行是写了什么可回退化内存池。。。

哎,技不如人,甘拜下风。。。

出分了。。。$T2$成功搞到$60$分。。。

下午在火车站待了$2.5h+$,又在火车上站了$1.5h+$。。。腰酸背疼。。。就差腿抽痉。。。

于是,$AHOI2019$游记到此结束。

其实我应该是可以把$Day1$的前两题$A$掉的。

但是老年咸鱼。。。没办法。。。

所以,也就这样了。

顺带提一句:我退游了。

我的$OI$生涯到此结束。

AFO

原文地址:https://www.cnblogs.com/Yangrui-Blog/p/10657046.html