2021 ICPC 上海 流水账

终于摸到了人生中第一个icpc金,来写个流水账记录一下。

八点五十按照要求到了机房。
教练:你们可真听话,他让你们几点来就几点来啊。
(委屈)

正式比赛:
开局队友L签了E,另一个队友X签出了D,丢给我来写,我当即一个map<pair<int,int>,pair <int,int>>,发现本机要跑4s多,那个样例自测都T,冷静思考了一下卡了一波常数卡到2s多,然后感觉无论如何都卡不下去了,于是让出机器给队友L签G,队友写完代码一发提交 WA ,然后看了一眼榜发现已经被卷到了400多名。不得不说:这个上海站是真的卷,特别是前两小时大家的手速真的是太快了,完全卷不过。三个人你看着我我看着你看了五分钟,然后冷静分析出了G题代码没完全取模,改了改过了,然后我实在想不出什么解决方法了,直接上手写了个散列表,代码量+1k,本机0.4s,终于把这个签到题过了(upd:赛后发现oj上更慢了……)。看了一眼榜,hjh,已经卷到两百多名了,老年人手速真的跟不上啊。

这时跟着榜来到了这个I题和J题,我和队友X读完题感觉根本没想法,然后跑去读别的了,结果另一个队友L读完I之后直接给秒了,上机开写。

趁这个时间我和队友X把后面的题几乎全读了一遍,发现根本不会做。

队友:我怎么感觉这个M就是输出1/n^2啊?
我:不试白不试,不如试一下。

喜提一发WA。
然后又又又又自闭了,跟着榜又开了个H。

队友:这不是克鲁斯卡尔重构树吗?
我:这个跟重构树不太一样啊,这个权值会变的,这个可以离线的,直接做一遍生成树就好了balabalabala,诶等等,我们对每个询问都可以有一个 \(O(n\log n)\)的算法,我们可以离线,然后维护一下平衡树启发式合并,克老师的hdu多校出过类似的,只要用fhqTreap维护一下就好了。

队友把I题过了之后我上机写H,写写写,写写写,板子抄抄抄,然后发现连样例都过不了,再次自闭。

这时三个人三线程卡题了,于是进入了奢侈的机时调代码阶段,调调调,调调调调调调调,还是调不对。三个人分别举了个手加入上厕所队列,我们跟志愿者比较熟,可能进入了上厕所的优先队列。

队友:我M题有个新想法,不如我们来试试这样这样这样。
我:好。

改改改,交,又WA了。
H题调了一年,根本过不了样例,持续自闭中。

队友:我还有个新想法,我们这样这样这样,要是再过不了我真不会了。
我改完M之后提交,可以说是运气真的还可以,直接就过了。
从这个M过了开始,感觉一切都好起来了,我终于看出了H题的大问题,原来我直接用merge合并了两棵不同的fhqtreap。

我:平衡树启发式合并怎么写?
队友:你会不会把小的那棵树里面的每个结点都插入到大的里面去啊,这样也就两个log。
我:这样好像set就行了诶。?!那我写什么FhqTreap?(内心os:怪不得这个题他们都写这么快,原来都是set对吧)

终于把这个样例给过了,自信提交,又喜提一发WA。
我:???
队友:要不你把机器让出来,我们看看K题规律。

(打印机吐了三页纸)
队友:你怎么写了这么长。
(打印机吐出了第四页纸)
队友:…

我看看看看看,发现自己犯了一个睿智错误,pushdown的时候没pushdown tag 只pushdown了key,改完之后终于把这个H题给过了。

我(因为两本题册全被队友霸占手上根本没有题册):你们推出了那个B题的公式了吗?
队友A & B:没有。
我:?这个看起来就是先容斥一下,然后搞几个多项式乘一乘,你看这个998244353刚好是NTT模数。
队友:道理我都懂,但是推不出来。

看了眼榜,发现这个J过了一车人,三个人你看着我,我看着你,没一个会做的。

我:我来推推这个B。

队友L在用机器看K题构造的规律,然后队友X被我们拉着双线想题。

我:X佬X佬,如果我从一个 \(m\) 条边的环上选 \(x\) 条边,构成 \(y\) 个联通块的方案数是多少啊?感觉可以写一个公式直接推出来的样子,但是感觉很难写的样子,这个会不会要dp啊,或者要用polya之类的东西。数学水平实在是不够高啊。

队友X:孤立点算联通块吗?

我:当然算啦。

队友X:(无奈脸)$ x + y = m $
我:?怎么可能呢,这应该有很多种情况的,你看这样这样这样,再这样这样这样,就不满足了,如果我们设这些大小分别是xxxxxxx的话,那么他应该满足(式子写写写写写)
我:诶 大师 我悟了。

这时候两个队友大呼nb,原来是看出了K题的做法,直接给K题过了。
我:队友nb啊,我来试下这个B。

板子抄抄抄c,代码量+=2k。
我:好,样例过了,交一发试试。

又WA了。

我:我超 这都能错 不会是我式子错了吧,那我就真不会了。诶不会是这个容斥系数反了吧,不会吧不会吧。
队友:我们之前自己测的都是 \(n=4\) 的情况,用一个 \(n=3\) 的情况测一下看看。
(输出:\(998244347\)
我:… dbq我是傻逼(B题AC)

看了眼榜,封榜前终于来到了43名。
我:看看有没有机会再过一个,你们真的不会做这个J吗?

队友X:我感觉这个L挺签到的…
我:?这个L题封榜前只过了逆十字,你真的会做?
队友X:我觉得挺简单的a
队友L:反正不会J,不如来试试
于是全员梭哈这个L,梭哈了半个小时,啥都没梭哈出来,果然这种比赛最后半个小时就是垃圾时间。

比赛结束了,开榜,发现自己是36名。
我(心里一万只草泥马缓缓跑过):我超 不会吧不会吧 不会被卡成银牌第一吧。
队友:你快看我们上面有打星的。
三个人:ohhhhhhhhhhh。气势一概超过了旁边的出线队伍。旁边的大佬们像看傻逼一样看着我们。

原文地址:https://www.cnblogs.com/CzxingcHen/p/15616295.html