没错,由于某些 zszz 的原因,我是真的去不了了(指去不了 ZJ)
令人自闭的 ISIJ 终于结束了————From ycx's blog
经历了长达 5 天的高强度训练,每天都 7:30 起床下午 4:00 到家,打了 5 场 mns,没有切任何一道题,被虐了 5 次,直接自闭(
u1s1 我这状态参加个 P 的 NOI 哦,我这样要是不垫底我倒立吃碘锤行了吧
上午在家继续颓废,下午做了个核酸检测
tbh 我以前一直认为做核酸检测是一件多么恐怖的事情,今天亲自体验以后:就这?就这?
然鹅回来以后竟然感冒了!!!11
上午继续颓,下午打多校,然鹅悲催的是我们队除了我没有人打,所以只能单打独奏了……
切了 8 个,成绩显然优于去年,但还是被 ymx,sjc 的队以及 csy 的队吊打了……
晚上看笔试题库,并把去年和今年 UNR 的笔试题做了下,然鹅两年第一次提交都只有 96pts……
夜晚发生了一些 zszz 的悲催的事情,第二天的模拟改线上了,然鹅那时的我并没有意识到事情的严重性,还在想也就确诊了几个而已,会有啥事,结果……
平平无奇的一天,上午打了 mns,大概是 15 人中的 rk4,但还是被 ycx 神仙 dd 了(u1s1 ycx yyds ddw!)
下午吃了感冒药,困得不行所以没写什么题,直接颓掉了。
上午在家稍微写了点题,下午多校刚开 1h 就被通知要集体到某医院重新做核酸,于是带了道结论题坐地铁出发了,地铁上全程都在猜这道结论题的结论结果还是没有猜出来/wq,说明 wtcl(
面了 sjc、ycx、csy 等神仙,大家在一起口胡多校,口头 AK(大雾。
回到家后就开始码,但由于时间缘故未能把所有会做的题都切掉,最后是过了 7 个,再次被全题 dd。
晚上继续写题。
夜晚似乎有 CF,但为了调整作息没有打(
上午在家继续补题,补前一天的 CF,这好好的上分场没能参加实是可惜/wn
10:00 多钟教练突然通知不去了,因为到了余姚也是被疾控中心监控,就在 NJ 就地设考场比赛了。
下午继续写题,晚上看笔试题库。
晚上 11:00 上床睡了,未来几天 rp++
开 幕 雷 击
上午继续在家复习笔试题库+打了几个板子,中午突然被通知下午参加笔试,于是匆匆忙忙吃了个午饭睡了个午觉赶去考场了。然鹅这个午觉睡得不是一般得沉,12:10 躺到床上结果一睡睡到 1:50…………欸,我怕不是睡觉大王(
“下午 rp++,争取笔试不挂分”,在去考场的路上我还在自言自语,虽然最后还是挂分了/ll(浓 浓 的 讽 刺 意 味)
到了考场发现一车人在门口排队,第一眼 jgh,第二页 ryz,说是要登记个啥健康码的。唉,南京这疫情搞得真是,连考个试都要登记这登记那,不愧是你大 NJ(大雾
进去以后发密码条,我 JS-26,密码随机字符串,csy 刚好 JS-30(JS 总共 30 人参加 NOI),ymx JS-28,真就故意把我们几个安排在一起呗
ycx:选手编号按实力倒序排列(拿出自己的密码条一看,JS-29)
。。。。。。
还有一个细节是今天我和 ycx 都穿了短裤,其他人都穿了长裤,就这还被 ls 拿来开玩笑:“蚊子就喜欢叮你们的腿,因为你们的腿嫩”,弄得我和 ycx 满脸 xor(
15:00 进考场考试,考前 mol 了一发 ztr 还被神仙怒 D 了(
上来几题都很顺,结果到了第 10 题突然来个“丢失密码条扣几分”,艹我怎么不记得笔试题库上有这东西?然后我就在回忆来回忆去,几乎把笔试题库上所有区域都回忆了一遍,然并卵。就算 NOI2021 日程表上也只说丢失密码条会扣分,至于扣几分……tm 我知道个鬼啊。给了四个选项 0,2,5,10,0 分直接被排除,觉得 2 分不太可行就在 5 分和 10 分两个选项里蒙,不知道念了多少遍“释迦摩尼 脚绽莲花 菩提达摩 你真伟大 天上天下 唯我独尊 如来佛祖 太上老君 耶稣耶稣快显灵”后颠倒了 10 分这个选项,行,那就 10 分吧。
后面做得也都比较顺。
我做笔试总共用时 8min,其中第 10 题用时 6min,其余 49 题共用时 2min,多么不均匀的分配(London fog
还有一个细节就是 CCF 这个考试页面做得比较离谱,给人一种「提交完之后就不能修改答案的感觉」,因此我虽然 15:08 就答完了笔试但到 15:25,也就是考试页面提示还有 5min 比赛结束才提交,提交完之后发现可以改答案?!!大草,CCF hopping(
笔试 15:30 结束后大概 15:38 成绩就出来了,\(99\),果然 T10 挂了。艹这个面子场不 AK 怎么见人啊/ll,赛后问了下身边人,丢失密码条就是 5 分,这是 NOI 参赛者应有的「常识」,woc 这个大概去现场的人教练都会跟选手交代?艹那这波不是 \(\text{C}_n\text{H}_{2n+2}\) 了吗,再加上其他题都是 sbt,感觉全场都要 AK 了/ll,不过反正就 1 分而已,顶多就没脸见人了而已(
没过多久就是试机赛,试机赛是 NOI2020 Day 1 原题,我使用的 guide(感觉大家都是 gedit?反正我觉得 guide 比 gedit 好用,唯一的遗憾是 guide 没有括号补全,不过听说 guide 的 Tab 有时会出锅,有时也会卡死?不管了,反正如果卡死了再换 gedit 吧,upd. on 2021.7.25,听 LG 群里说 gedit 比 guide 好用,那明天用 gedit 试试看),随便打了打,T3 最后还交了个 100001B 的程序上去(虽然比赛结束后没有再次收集文件)就走人了。
听说有人交了个 114514B 的程序?nbnb/cy
5:00 出考场时直接自闭。
晚上继续打板子,8:00 多钟下楼跑了 7 圈 2800m 心情稍微好了点。
晚上 10:50 就睡了,可在床上一直翻到 12:20 才睡着。
平平无奇的一天。
早上 7:30 起床继续打板子,打完板子之后补了几个题解,补完题解后补游记(为什么要划掉呢?因为在游记中提补游记的内容就是套娃),顺便重新回顾了下 ycx 的 NOI2020 游记以及我的 THUSC2021 游记,别的印象倒不是太深,唯独有一句话让我印象非常深刻:
还有,dzd的sb性质又爆发了,本来说丢失密码条要扣5分
我直接无 fa 可说
晚上听了个讲座,讲如何缓解考前压力。
10:30 就睡了,明天 rp++
注:由于我 day1 按 7.24 来算的,所以今天虽说是 NOI2021 第一个比赛日但在我游记中却被算为了 day3(
CCF 的 sb 性质又爆发了,本来说 8:00 比赛,一推推到了 8:30,又推到了 9:00,9:10,最后 9:15 才开始考试(
下发文件的解压密码竟然是今天日期,hopping(
我一开始还在桌面上的 day1 文件夹中解压文件然后死活解压不出来,后来经监考老师指导才知道要到桌面上解压,说明我是菜鸡(大雾
点开下发文件一看,没有交互库没有 SPJ,三道传统题 hopping,点开题面看第一页,不愧是 NOI,三个 O2,可这个时限只开 1s 是怎么回事?莫非要卡常?(flag *1)说不定这个数据范围不是给卡常的呢?
看 T1,这个题面看起来非常 LCT。说好的 LCT 10 级算法 NOI T1 不涉及的呢?不愧是 CCF/qiang,这非常符合 CCF 的作风。不过我冷静地一想,这路径问题……或许不需要 LCT,可能树剖也能做。然后想着想着就想到了一个树剖解法,常数略有点大,要开两棵线段树,不过开了 O2 怕什么。然后就开始码,1h 时过了 4 个大样例,u1s1 在 Linux 下测大样例真是麻烦,还是 Dev-C++ 吼(
然后用测了下运行时间,这第五个大样例 \(n=80000\) 跑了 \(820ms\) 是怎么回事/jk,感觉非常危,要被卡常了/ll,可我又不知道这东西怎么卡常啊/wn,感觉每一句话都有用也没啥好剪的啊,顶多加个读写优化罢,然后就顺手写了个 read 和 print,还没用 fread 因为个人不喜欢那东西,然后 \(820ms\) 变成了 \(800ms\),心里还是非常不平但就把它放一边了。
看 T2,想了 ~20min,有点困,因此也没有什么特别好的方法,不过前 8 个测试点我似乎会做?然后开始码,因为不会用除了 C++ 之外的其他 IDE 所以写得比较慢,把前 8 个测试点对应的部分分写好大概已经 11:30 了。
上个厕所,途中边走边想这个题,突然感觉这个式子有点眼熟,逆序对个数的奇偶性,而且还相减……对!行列式,而且这个数据范围 \(100\) 似乎就是给 \(n^3,n^4\) 之类的复杂度的。对于 \(k=2\) 的情况就是那东西的行列式,这样 55 分就到手了,接下来想下面的性质 A,刚才看大样例时就感觉那数字有点意思,什么 \(3240\),什么 \(2304\),感觉是一堆数字乘在一起,然后手玩了一下 \(k=3\) 的情况,发现 \(k=3\) 时直接把两个行列式乘起来就行了,然后我就猜特殊性质 A 就是把所有行列式乘起来,证明不会。写了一下发现还真是,测了下大样例发现大样例 2,4 都过了,那没事了,结论应该是对的,这样 20 分又到手了,其时已 12:20。没时间想正解啦,感觉要 LGV 引理(flag *2),(讲个笑话,NOI 之前某场模拟赛让我知道了这个神奇的科技,于是准备 NOI 之前学完,结果鸽着鸽着就鸽掉了,考 day1 之前一天本来准备花一天时间学的,然后我就开玩笑般地跟自己说,这么 trivial 的东西早学晚学都一样,反正到正式考场上也不大可能派上用场,结果……),反正我(当时,现在写这篇游记时会了)还不会 LGV 引理就没有往下想了。
看 T3,抱着 T3 都是不可做题的心理,我并没有往正解方向想,其时说句大实话感觉这题难度远不及“不可做题”的难度,可是当时的我并没有意识到。不知道这个性质是干嘛用的,既然是不可做题那咱也大可不必花那时间分析了呗(flag *3),暴力非常好搞,直接 SCC 缩点一下即可,然后就开始写,当时我不知道 \(m\) 数据范围在 5,6,7 测试点中可能达到 \(6\times 10^5\),所以我以为 \(\mathcal O(mq)\) 能过,写好了过了大样例感觉它非常《稳》就没管它了,然后看 \(m=n-1\),对于 \(m=n-1\) 而言 \(k=0\) 就是送的,直接上个倍增好了,\(k=1\) 感觉要分点类,\(k=2\) 感觉要分更多类,可能还要建个虚树,不过思路并不算困难,这样一来我不就有 56pts 了吗?然后开始码,然鹅码 \(k=1\) 时大样例就 WA 了好多次,一会儿这边少考虑一个地方一会儿那边又少考虑一个地方,所以到 4h10min 时才过大样例。于是 \(k=2\) 就直接没时间搞了…………靠前说好的要留至少 40min 对拍的呢?现在看来刚好。
然后就开始拍 T2,造了几个数据给我的三个 subtask 相互对拍,没有排出错误来,T3 又造了树的 \(k=0,1\) 的数据给我的三个 subtask 相互对拍,然鹅我一开始 sb 了外向树造成内向树了,导致我树的 subtask 的程序全输出 \(0\),直接把我吓死,后来才发现是我 generator
写错了,虚惊一场……那看来是没啥问题了吧,然后就开始卡 T1 的常,造了三组 \(n=m=10^5\) 但树的形态是父亲在 \([1,i-1]\) 中随机生成的数据(主要我懒得,也没时间写 prufer 序列了),事实证明这样造出来的数据非常菜(和我一样),发现跑得甚至比大样例还快,希望 CCF 也用脚造数据(,最后查了查文件就交卷了。
估分 \(100+75+44=219\)。
赛后发现 ycx 没有想到 T2 的行列式,以为行列式算出来的是二分图匹配个数,事实上二分图匹配的个数应该是那矩阵的积和式…………ymx 似乎会 T3?orzorz,终归还是 ddw,不过似乎没有调出来?不知道真的假的()他告诉我们 T3 那个性质是说把原图 SCC 缩点后得到的是一棵外向树。。。。艹我为什么现场没有想到?不然我不就又多了 20pts 了吗。csy 给我们证明了下为什么 T2 直接把行列式乘起来可以过特殊性质 A,我直接 mod mod mod。ycx 说 T2 \(m\) 可以高达 \(6\times 10^5\),然后我就直接挂掉了……然后我又一个激灵,事实上我那个做法根据之前“把原图 SCC 缩点后得到的是一棵外向树”这个性质,复杂度是 \(nq\) 的,因此又不会挂了()所以大概就 T1 可能被卡常?问题不大(
回家吃了个饭就回去查成绩了,过去发现一车神仙在颓 .io
,csy 给我们推荐了个什么 splix.io
,似乎还挺好玩的。就这样 1h 时间白白浪费了…………
5:00 ls 通知我们去查成绩。“马上可能会心肌梗死————ycx” 进去发现成绩没有下发到我们每个人的桌面上,只有数据,T3 测试点 5,6,7 \(m\) 只有 2000,竟然放 \(mq\) 过去了,差评。。。。。测了下 T1 的第 20 个点,1.028s,/jk/jk/jk 那估计要被卡常了,又测了下第 19 个点,0.7s,没事了,又重测了下 #20,这下又变成 0.992s 了……什么鬼啊,《超时 0.005s 算超时吗》,不过据说现场 IO 速度比我们考场的机子快?希望没事。
然后就下发成绩单了,我一分没挂,\(219\)。T1 #20 跑了 0.840s。不过据说一车神仙 AK 了?T1 211 AC,T2 53 AC,T3 43 AC,洛谷上三个紫题,真·NOI 难度。还有一车人因为卡常去申诉,包括但不限于 ztr 神仙、jt、ycs,似乎 ztr 最后 T3 阿了,mol。
晚上学 LGV 引理。
早上 7:00 起床补了昨天 LGV 引理的 blog 并做了道毒瘤题
按照惯例下午打多校,不出意外又被 dd 了,而且这次被 dd 得不是一般得惨,其他队都是七八题,我就 5 个题……
傍晚补刚才多校的某道卡常妹妹题。
d a y 2 直 接 翻 车(虽然 day 2 翻车已经成为我的传统艺能,不论是 CSP-S 2019,还是 NOI 2020 网络同步赛,又或是其他一些譬如 JSOI2021 之类的比赛,都出现了 D2 被一些我 D1 dd 的人吊打的人 dd,不过这次已经是我作为非正式选手的最后一场比赛了,难道你这次翻完了还想在明年 JSOI 或者 NOI day2 赛场上翻一遍?确实得引起重视)
先说几句负能量的话吧,不想看的可以不看。
tm 就你这大常数你指望你以后不会被卡常?
tm 就以为你 day1 比身边几个人略有领先你 day2 就能降低紧迫程度?
tm 在赛场上当你花了很多时间死杠一道题却无果的时候,你难道不知道回过头看看其他题目?打过这么多比赛这点技巧不懂?
无话可说了,考场上不知道脑子在想些什么。
如果你不继续给自己上点紧箍咒,继续保持最近这段时间懒散的状态,那恐怕 NOIp 2021 还是药丸,你就等着退役吧。
从明天开始写题一定控制常数,不要再对“抢最劣解”一类的行为不以为然甚至感到自豪了,否则就吃 \(114514191981019260817998244353\) ton 碘锤吧。。。。
下面进入正题,由于心情不好,可能写得略有点简略:
上午 8:00 开始考试,可由于 NJ 接受解压密码时间有点晚所以我们到 8:10 才开始(
今天解压密码竟然不是 20210728,hopping(
上来抱着“打打暴力也能 Ag”的心态看 T1,发现有 24 分暴力分,上来先把 24 分暴力写了,看 T2,发现暴力分给得也挺多的,先把最暴力的 20pts 写了。
然后想 T1 正解,这一看就没啥正解的做法,因此考虑乱搞,首先想了一个不知道能拿多少分的乱搞,就是每次随机将字符串的 \(256\) 位分成两组,每组 \(128\) 位,那么我们假设每次选的 \(k\) 个位置都在其中某一组内,然后用个 vector 或者哈希之类的结构维护一下另外 \(128\) 与询问串相同的字符串组成的集合————由于字典随机生成,这个集合大小对于询问串而言是常数级别的,然后对这样的字符串算一波贡献即可。
算下概率,对于某个 \(k\) 单次随机正确的概率大概是 \(\dfrac{\dbinom{128}{k}·2}{\dbinom{256}{k}}\),那么对于 \(k=2\) 随机 \(40\) 次单次出锅的概率就很小了,\(k=3\) 随机 \(60\) 次,\(k=4\) 随 \(100\) 次……以此类推,这样不就能多很多分了吗?
然后就开始码,码到一半突然发现,wtm 就是个 sb,这个不用每次都恰好随 \(128\) 位,事实上如果我们假设划分出来的两组的大小为 \(x,y\),并且如果我们这 \(k\) 个位置完全被包含在第一组的 \(x\) 个位置中,那么 \(x\) 太小的问题是,每次随机的概率太小,随机次数太多,\(x\) 太大的问题是,满足另外 \(y\) 位与询问串对应的 \(y\) 位相同的字符串太多,需枚举的字符串太多,而显然 \(x=128\) 还没有大到枚举次数太多的地步,因此我们完全可以调大 \(x\),减少随机次数。
想了想把 \(x\) 调到了 \(192\),写了写发现 \(2^{64}\) 哈希冲突概率还是小了,又调到了 \(224\),发现 \(2^{32}\) 又小了,紧接着又调到了 \(232\),…… \(2^{24}\) 可能差不多了吧,算了下随机次数,单次询问获得正确结果的概率大概是 \(12\%\),然后随个 \(80\) 次获得错误结果的概率就降到了 \(10^{-11}\) 了,然后就在原来写的 \(24\) 分暴力+玄学部分分的基础上继续码,码了好久,大样例倒是过了,发现代码乱得根本调不动,而且常数也大得上天,\(n=4\times 10^5,m=1.2\times 10^5\) 的数据要跑 10s,空间复杂度也出了大问题,一开始使用哈希表模数挑得比较大(\(123457\))空间卡成了 396MB,后来改成 \(65537\) 才变成了 366MB 比较稳,然后非常自闭……其时已 11:40 我却连个 T1 都没搞好。回去看 T2,30min 胡了个暴力 30pts 心态才稍微好点,把 T1 稍微卡了卡,把询问全部存下来然后根据 \(k_{\max}\) 调整询问次数,这样卡了卡大概看了看,可能能过十七八个点,此时已经 12:30,又去 T3 胡了个 12pts 的暴力,然鹅我暴力又调了好久原因是我一个 int
型变量开成 bool
了,调完已经 12:50 了,已经写不动其他题目了。
稍微拍了下 T1 T2 就结束了。
估分 \(72+50+12=134\),自闭。
出来发现大家都会 T1,ycx 和 lxr 也随的,csy 和 sjc 写的似乎是靠谱的做法,然后大家 T2 都是 50,个个 150+,我 tm 直接垫底。
回家自闭了一会儿。
回来以后发现各路神仙都在颓废,其中我们打 generals.io
使用账号名为 \(1004535809\)(话说我有个 CF 号就叫这个名字来着的,csy:下次见到了就叉),NTT 模数 hopping,某一场比赛甚至遇到了 wjz,还有个人叫 wlzhouzhuanismyson
,估计是 Froggy(?),真就 OIer 窝里斗呗。
15:20 查分数,T1 卡成 60 了,T2 45 不知道为啥 WA 了一个点,T3 12 没挂,\(117\),直接垫底/ll/ll
T1 还 WA 了两个点,莫名其妙。
ycx 162,lxr 146,ymx&sjc 154 全部 ddw。
总分 \(99+219+117=435\),Ag 走人
没啥好说的了,摸了会儿就走了。
回家途中遇到 jt,发现他 day2 也崩了,T2 写了正解,正解调对了可暴力写错了,所以只过了除了前 4 个点外的另外 16 个点。
jt:“我要是因为这 20 分丢了 jxd 我就 ***”
回家继续自闭+补游记,下午 5:00 出名单,我夏令营选手 rk15,orz lxr \(437\),rk 14,ycx \(438\),rk 13 ddw %%%
Au 分数线 \(498\),jt \(487\),真的为了这 \(20\) 分丢了 jxd,惨。可他才高一,希望他高二能够进 jxd 吧。
orz ztr \(621\) JS rk 1 dd djq by \(20\) pts,ix35 神仙和 djq 一样?orzorz。yht 和 dxm 分也一样,\(577\)。csy \(546\) 达 Au 分数线了,nbnb,祝贺 csy 神仙进队拿到 Au %%%。ymx 似乎炸了,不过终归还是 ddw,过去一个赛季除了 day1 没有任何一场比赛翻车。
回忆了一下,tm D2T1 \(k=1\) 时我以为一次随机就能搞定因此将随机次数设为了 \(1\),要不然我就不至于挂成这个死样子了,更何况多了这 \(4\)(或者 \(8\))分 wtm 就能 dd lxr 和 ycx 了,可惜我就因为这么几分惨遭被 dd 的命运/ll,无比懊恼。
稍微评价下这次的题吧:
再稍微总结下这次比赛的发挥:
15 岁祭。
不知道今天现场有什么活动.jpg
好吧确实没啥活动。。。
下午打了场多校,终于不再垫底了,吊打了 team0014
到这里,NOI2021 是真的结束了,想必在现场的选手们也已经踏上了回家的列车。
总之,令人自闭的 NOI 是结束了,下面一场 OI 比赛就是 3 个月后作为正式选手参加的 CSP-S 2021 了。
现在非正式选手翻一次也就算了,将来作为正式选手,可能几年的 OI 生涯就会因为一场比赛的翻车而告终。
不过只要我们足够努力,就能够最大程度上减少翻车的可能性。
卷起来吧,tzc!
手机扫一扫
移动阅读更方便
你可能感兴趣的文章