2021 icpc败犬记

拖了好久的2021 icpc赛季记录，大概拖了一年多吧，真是让人不甘的赛季啊
这个赛季的网络赛与gym训练我们队都表现良好，队友目标都是冲金，但是只能说真的还是缺了点实力和运气吧。。

沈阳站
这是直到今日我仍然最不甘心的一场，也是我认为必金的一场。开场10min我先看了M, 直接秒了，感觉就是直接在$SAM$上贪心走最大字典序就完了，但是又感觉既然要用$SAM$做，肯定没有这么简单，随后我等待了20min后发现还是没有人过这题，而我又也有一些细节不太确定，比如这样做的复杂度是对的吗。

随后我就先打算想别的题，我和coming讨论了一会B的做法后让他去写了，然后就是这场的噩梦来了，在coming写B的时候。我思考了好一会，终于确定了M的SAM加堆的做法，告诉队友手上握了一道中后期题，告诉他们这场能冲金，我最后上。然而$coming$的$B$突然$TLE$了，并且经过多次调试后仍然无法通过，他自己也找不出问题，我过去看他的代码也没发现问题，我还怀疑过是他递归写死循环了，经过多次$re,tle$的尝试后，我们终于确定是被卡常了，问题在于我们想的办法是常数较大的建图30次的做法，复杂度是对的，但是常数大而且只有1s被卡常了。由于我们一直认为复杂度是对的，所以没思考建图次数更小常数的做法。

在这题足足T了2个小时后，我和coming毫无办法，都绝望了，这时我提出把vector换成邻接表试试，再不行就放弃了，结果一发通过了。这题足足卡了我们2个小时，心态完全被搞爆炸，通过之后只剩下一个半小时了，我们赶紧去跟榜，coming迅速秒了H，我和夜幕讨论后发现L就是个傻逼容斥。
我一看这就是个非常典中典的O(n^2)的树形背包，只需要写好转移时枚举的子树大小就就能严格O(n ^ 2), 这时夜幕推出了I的公式，但他不会写高斯消元，让上机写I(队内一般我来写这种数学题)。这时候只剩下最后1h了，我们确定了剧本。我把L的做法喂给coming后让他去写，并强调了枚举的方法怎么做才能保证O(n ^ 2)， 我来写高斯消元，如果顺利的话，最后我再把后缀自动机写了，1h过三题直接金。剧本很好，可惜3题一题都没过，时间太紧张了加上一些小问题。coming之前很少写树形背包，可能是我转述不清楚导致他的合并写法还是不对，一直T，但我此时在调试I，夜幕的矩阵系数手算算错了导致我一直得到一些很奇怪的答案，我们轮流打印上机，但最后还是一题都没过，赛后我查看coming代码的时候才发现他树形背包的合并是不对的，夜幕也发现矩阵手算的系数算错了。

最有希望的一场就这样没了，不甘啊…被卡常2h后，3题的做法我都会的情况下，只剩下一个小时一个都过不了，如果没有被卡常2个小时，我们至少多出一个半小时，我可以一个人把DP, SAM都写了，夜幕也可以去验证矩阵的系数。如果我去写树上背包，如果我10min开场就相信自己最初始的做法直接上机秒了那道SAM，可惜一切都结束了。这也是我们队第一次打铜，rk108, 从来没想过我们会打铜，去年少训练一年都是2个银，从来没有想过会因为卡常而铜…

上海站
沈阳后我们萎靡了很久，大家都没做题，因为上海站是诸神黄昏，所以我们完全没有抱任何希望，赛前也没有做题训练，开场我们迅速过了4题签到，随后coming进J，我和夜幕进K，coming提出bitset维护J的做法，我思考了一下发现很可行，但是这个trick我和他都知道，但是从来没用过bitset, 调试的过程中浪费了很多的时间。我和夜幕在K坐牢了很久后，我突然发现H过了很多人，我过去一看感觉就是个Kruskal生成树，基本上这种都是建树倍增直接做，在我没思考清楚的情况下，我把coming拉过来讲做法，但是建树后我自己突然有些细节讲的不明白，感觉自己卡住了，难道不是Kruskal板题。我思考了一会提出了一个启发式合并优先队列的2log做法，其实本质上就是和kruskal重构树的做法是一样的。通过H后我们三人一起构造，但是KM都构造不出来，6题银。

意料之中，毕竟是上海站，我从没想过能在这站冲金，再加上最后的两题都是构造题，我们队我和coming都是构造废物，全是夜幕负责构造。如果最后2题是图论/ds/字符串或许会有些机会吧。

对于一些中后期的思考，因为信心不足，赛场上紧张心态的原因。我总是没法思考完全部的细节，即便就是正解，也会开始质疑自己的想法。这也是我在两场中暴露的最大问题。

ECFAINL
我们认为我们没有EC的可能，三人都去实习，直到突然说有名额，7月份三人都在实习中请假参赛，不过由于7个月没写题，状态都很差吧。最后又是B的字符串正解被卡常，中途我们把unordered_map换成手写的哈希表，结果由于太久没写题，三个人都没看出来是指针清空为0导致re了，赛后3min才看出来，错失ec银牌。

2021 icpc的败犬记就这样结束了。队友都有新的生活与去向，而我也是半退役状态了，最近接了个提高组讲课，以后可能看心情更新博客，偶尔会单挑一些gym的比赛和以前的笔记发出来。