ICPC2019沈阳站游记

· · 个人记录

生涯第一场ICPC，又一个银三可太tuosh了

成绩 银牌第三（23/200） AC：AHLDMK(按过题顺序排序）

2019/11/15 出发前夜

上完毛概还得做微机原理实验，tuosh!

做实验还没位置，只能合作，tuosh!

累得半死放弃前途刷夜，结果宿管阿姨不想早起给我开门，tuosh!

出去住宾馆，汉庭满了，tuosh!

另寻一家宾馆，108一天的房间就不到10平大小还摆着安全套，tuosh!

昏昏沉沉睡去。

2019/11/16 清晨

被唐神的电话叫醒，起来一看6:30我tm人都傻了。闹钟没响（也许是我按掉了然后再睡了亿会儿），队友打电话显示全部是正在通话中，tuoshtuoshtuosh

慌慌张张起来收拾好东西窜出宾馆，坐上出租车察觉到这个特殊的时间才想起来十有八九是夜间勿扰模式搞的鬼。

四十分钟奔到机场改签，1k没了，tuosh！下一班航班是12：55，热身赛赶不上了tuosh！

现在我在汉堡王tuosh地打字记录这tuosh的两天。

2019/11/16 下午 热身赛

飞机降落的时候才发现大地一片银装素裹，沈阳刚下过雪。迈出舱门就只感到一股寒气袭面而来，好在衣服穿得足够厚，就是头和手冷。

火急火燎总归是赶上了热身赛的末尾，C题是给三个1000*1000的矩阵A,B,C判断是否有AB=C，元素值域是10^3。想到或许可以预处理乘法加速，不过没时间了。

2019/11/16 晚上

吃饭的时候和唐神讨论了\text{CSP Day1}的做法。回酒店先是切了\text{D1T2}，然后写了篇题解试图蹭一波热度骗一波赞：题解地址

大晚上闲的没事干溜出去转转，从酒店一路向西直到运河，然后向南拐进东北大学，最后原路返回。在路边找到一家烧烤摊，把队友拉下来吃了一波烧烤。

2019/11/17 现场赛

早起出门在酒店吃了早饭，qz爷在打印店打板子8:55才进场。开场一路顺风半个小时77分钟罚时怒切四道签到题，然后开始卡题。首先是假了F，我没注意到开始时间是可以变化的认为是裸的分数规划，直到样例过不去才发现问题。下来和唐神开始看K，看出来可以转换成整数拆分，但我们只有O(n\sqrt{n})的板子没有O(n\log{n})的板子。唐神上去敲了板子但是极限数据能卡到5s，过不去，于是一直在考虑如何打表，但发现其实并不能打表。接着又和qz爷讨论E，注意到在生成圆的圆心对大圆的圆心角顺时针变化时，每个点只会进入和离开圆一次。于是转化成在圆心角域上找一点使得尽可能多的区间包含这一点。但求离开和进入圆的圆心角位置是个大麻烦。我推式子推出来一个二元二次方程组，解不下去。二分倒是可以做但会带上一个log。qz爷和唐神一直在刚M但是未果。我上去写了E，本地测极端数据能到7s，时限0.5s，交上去果然T。之后一直在试图削减二分次数和进行常数优化，但并不能卡到时限以内。这时我下机让qz爷讲以一下M的题意，因为M过的人很多感觉并不是太难的算法。M题意是找三个不重叠的回文子串使得总长最长。我想了想提出了一个算法：枚举中间串的起点，贪心取以该位置为起点的极长回文串，然后在此基础上取中间串两边的最长回文串。队友感觉似乎很有道理于是qz爷开始上机码回文自动机。然而码完调试的时候却被一组"bcaabaa"hack了。但这组样例能用枚举中间串起点和终点加贪心的方式过过去但诸如"abaaaba"就会挂。但是码都码到现在了不交白不交。然后就过了，WTF？？？？全队同时黑人问号脸。然后qz爷把K题的代码卡了卡常，居然也卡过去了。然而此时已经临近终场，E也没时间卡下去了。

这场比赛就tm离谱，M题做法假，并且据说B和I也不同程度的有假的成分。滚榜出来是23名，又一个银牌第三tuosh。如果K和M能早点过或许就金了然而并没有。一队哥哥们也没出线，他们也被假的M题给卡掉了。

2019/11/17 归程

比完赛出去一看下雨，拖着箱子在泥泞的路上跋涉一公里之后总算找到了家还不错的馆子。不得不说东北的菜便宜是真便宜，量是真大。吃饱喝足打车去机场，坐了三个小时飞机回西安，然后又打的一个小时到学校。肚子又饿了tuosh。宿舍也没法回，外面店好像也全关了。只能窝在钱图码游记tuosh。不说了，马上翻出东南门去魏家凉皮弄点东西填肚子，tuosh