ec-final 2020 游记

挂个[校内传送门](https://www.cc98.org/topic/5065354) ## Day -21  去年因为时间冲突没打 ICPC，~~打了也进不了~~，偶然得知有奖励名额参加 ec 的机会。 由于时间不多，~~课表也不允许平时集训~~，新队还没训几场就到了 ec。  初训（双人，ec 2019） ## Day 0 有 div1，好耶 实际: 航班延误了不一定能打。 在机场被教了德扑，然而并不是很懂。 晚上九点多到了酒店，然而网速过差，连 CF 镜像都上不去，就跑路了，打了一晚上德扑，~~打完回房听 zzy 谈人生~~ ## Day 1 在 cjb 的带领下在校园随机游走，终于找到了签到地点。 下午开幕式，挺无聊的，一直在看省赛的实时榜。 这 I 怎么卡不掉人啊 女队 NB！ 开幕式之后是热身赛。 我看了 A 扔了个做法给 Heltion 写，在此期间主持人进行了令人智熄的一血宣读。写完 l1ll5 和 Heltion 讲了 B 题意，Heltion 感觉能做就上去写了。写到一半发现不对劲，我正好推了 C，上去写了，期间 Heltion 把 B 过了，但 C wa 了。最后发现是快读写挂了，~~被 Heltion 勒令不得使用 cin 以外方式读入~~，改过来就 AK 了。 随后进行了一个速的测，发现评测机带指令集一秒能跑 `maxint`，感觉很稳。 晚上回酒店开小会，交流一下注意事项，发现 trac 又挂了。开完会回房抄了一下 NTT 模数就睡了，不过楼下实在是很吵，半睡半醒又醒了几次。 ## Day 2 体验迷之操作。 不得带手机进入赛场，但要扫码才能进入赛场 放好行李之后，正式赛就开始了。 读了 A 感觉好像很签到，扔给 Heltion 去想。 Heltion 连续想了几个做法，又都叉掉了，这时榜上已经过了一大堆 F。l1ll5 看了 F 的题意，我想了下用 `set` 随便搞搞就可以了，让他去写。 在此期间我和 Heltion 交流了一下 L，Heltion 提出按素数来做，我想了下显然可以压缩全 $0$ 段再 dp。 A 最终顺利通过了，意外抢到了一血，但 F 题 T 了。我先是看了代码找了几个错，但还是一直 T，决定先扔一下这题，l1ll5 上去写 L。 我和 Heltion 讲了下 BD 的题意，Heltion 很快想出了 B 的 $O(n^4)$ 做法，然后自己证了一下复杂度和树卷积一样，会变成 $O(n^3)$。接着推了推 D，结论比较显然，我们确定了枚举边的思路并计算了答案式子。 但是 L wa 了。仔细思考发现，一段连续的 $0$ 会对答案有贡献，不过这个问题可以预处理掉。但这需要重构。 Heltion 上去写 B，然而刚运行就死机了，原因应该是递归爆栈。现场工作人员过来说要重启，然而重启之后技术人员过来说不能随便重启。 还好文件没丢。 Heltion 用 assert 防止爆栈并确定了问题的位置，我看了下代码找了几个错。 F 题还是没什么头绪，我估算了下大胆猜想是被卡常了。随了一组数据测了下，十分接近时限。我上机对 F 进行了重构，再交一发 wa 了，还不知道是原做法的问题还是改出了问题。 此时是 100 分钟，三分之一的时间过去，仍然只有一题。据场外消息，这时排名已经掉到了 200 名的打铁区。  我看了下 F 确定有一处改错了，上去交了一发。 终于过了。 随后，Heltion 定位了 B 的错误，再交了一发也过了。过了之后接着写 D 题。 l1ll5 想清楚了怎么改写 L，再考虑了一下边界的特殊情况，终于也交过了。 一分钟后，D 题通过。 40 分钟内连过 4 题，终于把局势扳了回来，稳定在金牌区。 在这期间看了榜，CGK 是比较可做的。G 题我和 Heltion 讨论过了，K 题是一个德扑题。 在之前 Heltion 上机时，我突然发现 G 的本质是一个区间 $a_i\to a_i+b_i$ 的问题，这有一个经典的矩阵做法。 等下机我和 Heltion 说了这个做法，他想了下发现向量求和不可做。他又再想了会，发现可以多维护两个维度实现这个问题，就上机了。l1ll5 初步分析了 K 的可能情况，我算了下发现只有同花顺一种稳赢策略，并和 l1ll5 确认了这一点。 然而，G 题 T 了，K 题 wa 了。 G 题 TLE 是在意料之中的事。$4^3n\log n$ 在 $5\times 10^5$ 的范围下无法通过是很正常的，但根据其上三角以及矩阵的特殊性可以进行优化。然而，一直都是 TLE。 最终，Heltion 上去把矩阵乘法完全循环展开，我继续确认 K 题的情况并分析 K 的代码。 在看 K 代码的过程中，我才知道 `A2345` 也是顺子，仔细想了下发现这是一个和前面都不一样的特例，需要特判。 240 分钟到了，封榜，此时 5 题 rk15。 封榜后，我改好了 K，交了一发过了，Heltion 也改好了 G，也过了。最后的目标只剩 C 题。C 题我们一开始分析了很多性质，但事实证明这些都没用。唯一有用的是 $n$ 越小越难做。 我和 Heltion 说那些 $2^n$ 的模数可能有大用，Heltion 想了下发现这可以直接归纳出方程，可以按位解出所有的解。而对于 $k\times 2^n$，可以忽略这个 $k$。 $25+12+6+3+1=47<64$，方程不够。 Heltion 想了下，可以直接暴力枚举剩下的自由元。但是带自由元的方程结构是很奇怪的，我想了下拿出了这次 ec 唯一用到的书 高等代数上册（？） Heltion 看了下方程结构，基本做法成型了。 在此期间，l1ll5 已经写好了 generator 和预处理的部分。我也把可能用到的逆函数写好并验证了。一切就绪，Heltion 上机冲刺最后的 C。在 Heltion 写代码的同时，我在旁边手动模拟了 l1ll5 的预处理，没有问题，同时 l1ll5 也在旁边看着现在写的代码是否有明显的问题。 修过了编译，测了一发样例无解。这时只剩几分钟了。 Heltion 立刻开始了紧张的调试，修复了若干个错误，直到最后那串 16 开头的数字终于出现在屏幕上。我们立刻开始找调试语句，全部删掉之后测了样例直接交了，我提醒把 $n$ 改小再交一次。 第二份代码交上去时，第一份代码的评测结果出了。 CORRECT。 ~~后来第二份代码因为没改干净，NO OUTPUT 了。不过这并不影响。~~ 一分钟后，比赛结束了。 刚结束就看到 cjb 走进赛场，说我们捧了浙大的第一个杯（是季军）。 ~~还捧了稀有的顽强拼搏~~  打完发现了一个史纲的 ddl，光顾着写观后感，闭幕式除了滚榜都没听。~~滚榜时才知道一个学校至多一个杯~~  闭幕式结束进行了一个神秘的采访，全程微笑默叹，基本上都是 l1ll5 在回答。结束后就块速赶往机场，甚至差点连饭都没吃。 ~~为什么最后吃了呢？因为又延误了~~ 起飞前交了史纲，但又发现另一个 24:00 的 ddl，还好 23:50 飞机落地交上去了。 后面留坑待填