最终得对抗自己

CQOI·2018 续命之行

Day [-n, 0]

去鸭梨各种考试各种崩溃, JeremyGuo和Ender各种艹翻全场(有一次甚至分居Rank1和Rank2!, JeremyGuo第一次使用神秘的自动AK机, 被出题人发现了…然并卵)。

自己也成老年选手了, 初二大佬ModestStarlight和初三清华爷Freopen对我各种碾压…我也不知道自己脑袋出什么批事了, 害怕, 神犇深夜查寝和我谈了好久——太执着?貌似神犇抓住了痛点…对题目难度预估太高导致总是一条思路走到死emm努力改正吧…但是这貌似已经成了一种习惯不是说改就能改的啊…

回到八中复习一周, 上午继续复习…看了一坨网络流题目, 稀里糊涂地想起来回文自动机还没有复习于是复习了一下..

晚上考试! 从6点考到11点全程暴力稳稳暴力分垫底。
没救了…

第二天上午继续考, 依然三道暴力, 拿完暴力分以为稳稳垫底, 然而? 貌似写正解的都爆炸了?

感觉自己就是个暴力选手了…感觉自己要退役了…没问题的NOIP那么高就算全大暴力应该也能压线吧(自我安慰flg)…

下午试机, 在神犇的SUV上睡了一觉(困), 去邮电大学试机, 连邮电都换新电脑了!qwq!i5 6400! 有钱啊! 各种羡慕(八中什么时候把7年前的奔腾换掉啊喂…)
键盘表示不很爽, Backspace依然只有一格然后旁边就是反斜杠, 各种误触, g键貌似又是地鼠, 猛艹一阵子后莫名其妙地好了。
旁边的小哥CQ-6竟然是西师附中高一选手!编号竟然有CQ-06!NOIP一定强强强(。 v 。)(老年选手羡慕的眼光)。

回家颓…打开正义联盟群发现自己因为魏启大陆wiki的*事get称号”鸽王”, 于是准备迁移wiki服务器, 倒腾到十点多, 早早睡了。

Day 1

上午

睡觉前一点都不紧张和NOIP时完全不一样, 然后…被子盖薄了凌晨迷迷糊糊醒了好几次?早上清醒过来感觉凉凉的, 没睡好…

吃早饭!鉴于上次CQOI悲惨的经历为了防止智商下线我一定得多吃点…

到达邮电大学, 冷qwq, 听神犇重新讲完考试策略就进考场, 啪啪啪地敲头文件, 对拍脚本, 写密码的黑板离得很近, cqcs? Computer Science? 成功解压。

打开题面, 画风突变, nodgd应该不会写这种风格的pdf吧, smg, 三道题都是1s+512MB?完全无法猜测题目类型啊。
看T1, 我曹, 感觉和CQOI2016的某模拟题好像, 我曹还真是模拟, 可A(开心!开心!有100pts了!), 这题果然签到分数只有两档, 30的纯暴力和100正解。
看T2, qwq, 矩阵树裸题??? 诶貌似根节点固定了, 第一题那么水这题不可能再送分了吧, 难道是一道扩展矩阵树定理之类的题目??
看暴力, 咦??还是只有30分纯暴力模拟和100分正解???
管他丫的看T3。
T3貌似计数…看数据规模, 发现N是1e7, M是1e8, A是45, 然后感觉这个计数很naive啊一定比第二题可做, 然而部分分为何还是那么诡异只有不能更暴力的暴力30分和100分正解???

出题人你怎么搞部分分的…

回头肛T1, 20min写完BSGS不带ex, 生成大数据发现map要跑0.8s, 考虑到评测机配置是四代i5, 有点怂于是手写哈希跑0.1s稳, 40min写完全规模对拍拍上了。
看T2, 稀里糊涂不抱希望地想了5到10min 智商下线 觉得这题很神, 一定是的! 于是果断放弃, 计划A掉T3然后回来写个暴力! 230在CQOI这个难度下应该很稳!
看T3,N是1e7, M是1e8, A是45。10min感觉就 好naive啊不是O(NlogA)可以松过去么 少年你的想法很危险…于是写了个循环做1e7次快速幂31次方, 不开O2发现得跑1.4s, 松松松10min后发现越松越慢, 然后劳资想起来本场考试好像一反常态地不开O2。

过不了。

但是这么快的算法可以拿很多分吧(图森破) 我终于明白为什么出题人部分分给的那么没梯度了…意思就是这个1.4s的算法还是只能拿暴力分对吧…淦。

^&^*&^#)*(冷静下…解题关键一定在于如何淦掉这个log!
10min后:实现技巧不可行, 换思路!
20min后:二项式展开推公式….
30min后:淦推不出来!
换个脑子….
于是花15min给第二题码了个无脑暴力, 回头继续肛T3。
10min后:展开乱搞不可行…推下幂的差分…
20min后:貌似有些规律! 这个数列差分A次后会变成常数数列!有希望!
30min后:淦…如果维护差分复杂度反而变高了。
woc搞不出啊部分分不让人满意啊这个A这么小但是完全不知道为什么啊开脑洞啊qwq!

咦, M只有1e8?(出题人没用科学计数法表示我一直以为那一坨有9个零)。

其中必有蹊跷!(qwq我上辈子造了什么孽脑啊)

原根!上!1e7规模的排序?松松桶排!上!
成功get:O(1)超级幂!

鸡冻٩(๑>◡<๑)۶ md, 1e8竟然要跑5s??你还是不是i5?你还有没有脸去见intel? 这一定是正解!松~~~ 30min松到3s 1h松到1.2s 指针遍历数组!循环展开! 还是1.2s, 松松你骗我 开O2跑一跑试试? 0.98s 智障出题人!竟然不开O2评测!愤怒! 关掉O2 1.2s QAQ

零点二秒。

人的一生中, 有12614400000个零点二秒。

零点二秒, 雨滴落入池塘, 浅浅积水上溅起的涟漪也不能走完它短暂的一生。

零点二秒, 仿佛什么也改变不了。

但是, 零点二秒。

猎豹冲刺6米

蜂鸟振翅16次,

声波传递72米,

而宇宙中最快的光,

则能在0.2秒内走完六千千米的路程。

而以光速运行的计算机核心,

i5 6400 四核2.4Gz四兆缓存未超频不带K,

能多进行三千万次的运算!

三千万次!

三千万次!

三!千!万!次!啊!!!

淦, 松不下去了。

时间还有1.5h, 身旁的高一小哥一点不慌愉快地玩扫雷, 但是我看他貌似只写了一道题啊smg, 我老年选手了我没有玩扫雷的资本啊慌!
放松一下身心…检查程序正确性, 5min码个暴力。
md, 常数没送下来, 正确性倒是被我松没了。

慌慌慌慌慌慌慌慌慌慌恍恍惚惚嚯嚯嚯, 脑袋一团乱麻, 或者说是一摊糨糊——哦不更恰当地比喻是一团乱麻和在一坨糨糊里搅来搅去…60min才查出个sb错, 我的天哪快速幂爆int了身败名裂啊!
想起来快速幂是复制第一题的, 赶快检查第一题代码, mdzz原来第一题我为了稳全部int都开成long long怪不得快速幂没有写强制类型转换…没时间松啦!

花10min拿1.4s的O(NlogA)算法和1.2s的O(M)算法组了个拼盘, 心跳加速整理+检查代码…
时间还有20min, 预处理个逆元然后把小于N/2的数据扔给O(NlogA)处理, 然后觉得自己那么智障于是来拍一下吧!

一拍, 出错了。

淦!我果然除了能清楚地认识到自己是个zz以外一无所成!

狗眼观察Debug!

狗眼瞎了!10min都没看出错!还有10min结束!

还有2min! 眼睛爆了我没处理0!的逆元!改改改!

拍上了…

下午

出考场, 神犇说不要讨论题目?管他y的, JeremyGuo:我应该300! Ender:第二题傻逼啊! SunIsMe:完了我第二题写错了一个地方(虽然拍了30min才拍出错hh), lsy不清楚, Hineven:????第二题那么水么?

玩脱了…大众分230, 劳资只有160pts…

爽啊, 排名爆掉, 退役预定, 心情不好, 下午到家郁闷郁闷郁闷, 父母说明天的题一定会上难度还有机会(蛤?), 复习吧算了不想复习…看番貌似又没有喜欢看的番。
反思了一下今天的考试策略…我™竟然还是把难度估计高了!难道今年CQOI那么水么?调整策略, 暗暗决定必须给每道题至少分配半小时。
想起来初中群上的承诺还没兑现, 看样子我是和鸽王脱不开干系了, 继续鼓捣树莓派装apache+php5+mediawiki, libiconv持续出毒导致php无法编译, 于是直接无脑 sudo apt-get install php5 , 还真的有!一直鼓捣到晚上终于成功, 内网穿透没时间整, 然后想到今天没考字符串和网络流于是看了看回文自动机版, 睡得很早, 10点半不到。

躺着又没什么睡意(明明考试那么消耗精力), 除非Day2AK逆天改命, 自己五年OI就这么退役了? 想到这里奇怪地一点感觉都没有。

Day 2

上午

早上去邮电大学, 家人做了饺子和煎饺然而我莫名其妙没有胃口只吃了5个…担心吃不饱考试半路会爆炸, 但是可能省选已经咸了吧也就没强迫自己多吃一些…

到门口, 吴老师正在立flag:今天的题目肯定比昨天难! Explorer表示吴老师的flag一直都是用来被拔掉的。然后我蜜汁自信奶了一口说今天一定没有字符串(???然而CQOI有三年都没考过字符串了), JeremyGuo:糟了我还没复习回文自动机!吴老师继续立flag:fft这种东西都不会考!CQOI还没考过fft呢!

进考场, 解压看题, mdzz又是全部512MB+1s, 出题人垃圾还是只给30+30+30裸暴力部分分mdzz! 搬原题搬板题什么垃圾态度!

令人怀疑他是不是先搬原题然后根据这个时限调整了数据规模啊…然后我一看第二题的名字就激动了!

九连环?差点笑出声, 我就写过一篇blog: 九连环问题与格雷码 , 随便你怎么考!

看T1, 咦咦咦这不是裸的状压?O(2^N*N^2)??N是20?复杂度算出来4个亿??按照出题人这尿性又要卡常?难道还有O(2^N*N)算法?管它y的。

看T2, 果不出所料…水题一道, 这个样例解释怎么那么熟悉啊难不成我在某博客上看到过, 出题人复制粘贴?

看T3, 感觉做过原题, 想了一会感觉很离线, 或者很分块但不会。

回头快速码完T1, 取模的模数是1e9+7?但是出题人没用科学表示法直接写了一坨0, 于是直接复制。

手造20的大样例一跑用了1.4秒, mdzz但是感觉没有更快的算法了先不管。

然后重新思考T2, 发现事情没有我想象的那么简单…高精度?压位貌似复杂度也不对?fft加速?
又是模板…
开了一波车40min写ntt加速压4位高精度码完调完。

时间才过去1h多点点, 精神恍惚, 感觉能AK!

重新思考T3…
离线询问+排序右端点扫一遍维护?5min后:不可能。
莫队暴力?5min后:不可能。
在线分块?20min后:我貌似get了O(Nsqrt(N)log(N))算法, 而且炒鸡难写!
1s怎么可能跑得过…按照出题人的尿性一定把后面70%的数据点都开满了一分不给…

不会看错题了吧?去阅读一下样例。

咦怎么只有一个k, 我还以为每个询问单独给出k!

…哈哈哈哈

…然后脑袋昏昏地短路了, 一开始想莫队竟然以为复杂度不对, 又绕了30min才绕回来发现sb题*1。

迅速码完+对拍+数据gen, 发现自己有个地方手残了改完才10点。

回头准备卡第一题常数, 但是鉴于昨天的经历认为卡常是没有前途的…于是准备思考O(2^N*N)做法, 重新阅读题面以及数据规模…然后…

我好想发现了一个惊天动地的大秘密!

N<20, 不是N≤20。

wtf!出题人你什么心态!六道题目就只有这一道题目数据规模写小于符号, 其他题目全部写小于等于你是不是皮!

…对对对我们要心胸宽广…出题人一定是在从不同地方复制原题的数据规模时不小心忘记统一符号了…

于是造了一组19的数据, 0.6s跑过。

在心里默念了几遍zz出题人平息自己的怒火, 想到第二题没拍于是写了个小数据的暴力拍上了。

总感觉有什么不对。

天哪!ntt乘法不能压4位会爆!
于是写了个不压位的高精度+ntt跑大数据, 果然错了!
不压位会超时!1.8s超时!出题人你对常数有多执着!
写压2位的高精度ntt, 和不压位的跑大数据!0.6s过了!

嘘….

重新检查数据规模以及边界情况, 没有问题, 第二题应该稳了, 顺便去看看对拍中的第三题数据规模…

冷汗…我的数组没开满…随手就写了个10^5比2^17小一点…吓屎, 按照出题人这尿性我怕是会爆零…

回头查第一题, 感觉这第一题那么简单怕是不会写错吧…但是还是写了对拍

拍出错。

wtf?flag要不要那么灵验???

检查…检查了30min才发现自己傻了忘记把状态取反…样例这么弱么…改完直接过。

开始拍, 拍上了, 看着三个黑框框和100%的cpu占用率感觉好安然。

还有一个半个小时, 昨晚的flag灵验了?好像AK了?

…今天的题这么水, AK也没卵用啊…

下午

除了lsy, 大家都表示AK了, 果然没差别的…

去吃饭, 大家一起怒斥出题人, JeremyGuo:你们发现第一题的模数是1e8+7而不是1e9+7没有?wtf我还真的没发现?要不要这么不要脸?还好劳资直接复制粘贴…

2点半出成绩, 出完成绩发现Day1T2暴力炸了只有5pts?但貌似全场暴力都炸的只有5pts了会不会数据有问题?然后Day1T3拿到NlogA的45分, O(M)一分没有…发现好多500pts+的大佬, 我这种450菜鸡得看rp了…

天哪, rank10, 压线入队。

qwq

lsy貌似爆炸了, 她是女生第二高, bs的女生比她高, 退役了。

今年bs很强啊, 我们bz进了四个省队, 也就是TheSocialists四人组…最开始, 信息竞赛只有我们四个人, 然后来了Farmer, Elaine, UISG103, Miracle, YUKI, Singularity, 结果到省选结束, 还是只剩我们四个人, 来奋力一搏的人都走了, 和最初没有区别。

Join the discussion

Your email address will not be published. Required fields are marked *