2020 ICPC ShangHai Regional 总结

前言

咕咕了两天，觉得有必要写一下。

$Just\ Record\ it,and\ leave\ a\ memory$。

闲扯&热身赛

从热身赛前一天讲起吧，因为热身赛与四级在同一天，而且热身赛在上午，所以考前一天，一直在 ~~复习英语~~ [抱佛脚]，果然，有一大事，晚上就失眠了，早上5点就醒了，上午考完四级，听力懵逼过去了，中午提议和$wyy$一起去吃顿好的，结果就去了$kfc$，我请客吃了个大餐，[说好的AA呢?]，下午没事做跟上个星期天打比赛的主办方对线 [后来复审还是挺好的，进决赛了] 。然后随时间的推移来到了晚上的热身赛，晚上热身赛有点意思，热身赛一共有三个题，刚开题，$ycs$看到概率就丢了，我们直接快进到第二题，找了半天规律，乱搞了一个奇偶性的规律，后来发现有特例过不去，就又丢了，快进到第三题，发现跟之前在知乎上面看到的一个数学题有点像，下意识猜了个结论就是排序取中点，可惜的是没想到转换思想，$zyj$造数据给我整懵了，我也不知道这个题目坐标系是咋建的。哦豁，最后热身赛结束直接爆零了。后来看别人的$AC$代码，发现第一个题是概率问题，用组合数学化简一下然后暴力就可以了，我和$ycs$一直以为是概率$dp$，这题还可以用欧拉函数加速一波，估计是我们被上次的那个概率$dp$整怕了，哈哈。热身赛结束，我一看这一波爆零了，有点慌呀，平时我们训练的时候没爆零过呀，根据$zyj$的建议，我回去整理了一波模板，[后来这一堆模板成为了场外人员观战]。整理模板的时候，我发现我的博客都写的啥啊，全是我看不懂的，可能是我记忆力太差了，或是我太菜了，每一个模板都简单的回忆了亿下。噢，12点了该睡觉了。

正赛

按照约定好的，$ycs$主写代码，我和$zyj$辅助，~~我划水~~。比赛开始了，刷新了一波界面，发现有人过$G$题了，集体懵逼。上来我好像看了个$E$题，发现是个环题，丢了，很快我们便找到了签到的$G$，很快$ycs$就$A$掉了，虽然后来我也不知道咋做的，没仔细看那个题。于是开始读其他的题，发现$B,D,M$过的人比较多，我读完了$D$发现这个题是可做的，然后建议一起搞$D$，结果发现要讨论好多情况，我们直接取了几种情况乱搞了下，交了一发，恩，$WA$掉，发现这题有点复杂，就先丢了。然后看$B,M$，读完$B$题，我的第一眼发现题目明显的提示，不是直接签到题吗，然后细心的$zyj$告诉我这题不是这个意思，噢，我人傻了，发现没有啥思路，就丢了。最后决定先搞$M$，发现是个树题，有点类似今年$PAT$甲级那道文件目录？我的第一个直觉是$map$搞，发现没有什么比较好的方法写出来，后来在$zyj$的帮助下，发现只需要$dfs+$贪心的遍历就好了，最后就只剩下建图了，$ycs$决定用字典树建图，我好久没用字典树，自然有点懵逼，好在$ycs$巨巨临危不乱，历经两个小时，成功建树一发$AC$了，$tql$了。我要好好学字典树了。然后我准备想$B$，发现这个题这么多人过，必然是签到啊，最终发现了结论，冲了一波，噢，就是这么简单。$A$掉$B$后，我让$zyj$看$I$题，我和$ycs$看$c$，讨论一会儿，只推出来了个最高位，但是不知道怎么统计每位的贡献，事后发现这个题是个裸的数位$dp$，然后$zyj$读完题目了，给我们讲了一波，我发现要一层一层的算，但是具体怎么算没想出来，然后$zyj$给出最短距离的计算方式，此时$ycs$好像有思路准备写这题的代码了，此时比赛还剩$1h$，我问了下$ycs$，一个小时能不能做出来这个题，搞不出来就丢了，去做人过得比较多的$D$，$ycs$自信的告诉我可以，然后开始搞$I$了，因为我没有啥实现的思路，我在看一些其他的题，最后$ycs$写了个代码，发现过不了样例，然后我和$zyj$一直在帮忙找错，最后我发现这同一层贡献肯定是$2\pi r$的倍数啊，怎么里面没有$r$，然后告诉了$ycs$，果然就出错在这里了，然后还是我们还是不敢交，准备用$zyj$构造的样例再测下，然后发现有点不对？实际上写的是对的，$ycs$交了下就过了。过了$4$题还剩下$20$分钟，我提议最后在$D$上挣扎下，恩，就是挣扎下而已，事后发现有的情况不需要讨论，此题的正解是特判两种，然后二分下第三种情况。比赛结束了，看了眼排名，不算打星的队伍的话，发现有机会拿铜。恩，最后拿了块铜牌，还是挺好的。