ICPC Nanjing 游记

· · 生活·游记

前情提要：高中生打星队伍，人生中第二次 ICPC 区域赛。

本来目标是金牌的，但是银了，有点难过 /ll

开场先随机看题，A 是一个交互，很快有了一个大概的思路，但是发现细节不是一般的多，先丢掉。看到很多队伍过了 C，于是看 C，发现是简单的 5min 1AC。

然后瞬间 F，I，K 三道题都有队伍过了，我看 K，队友两个人一起研究 C，发现 K 不合法的情况只有几种，感性理解一下车第一步的时候卡不死马就基本上卡不死马了，于是只要枚举马的第一步即可，49min 1AC。

我在写 K 的时候另外两个队友讨论出了 F，于是快速写掉，其中因为没有判 -1 挂了一发，但是还是非常快速的通过了，59min 2AC。

这个时候我们的排名来到了全场第 22 名，信心大增，但是突然之间三线卡题，一位队友在看 I，我和另外一位队友在看 E，首先会了一个 O(n^3) 的朴素 dp，队友说如果能做到 O(n^2) 可以轻松通过长剖优化到 O(n)，但是不知道如何优化，另外一个队友也卡在了 I 题，因为 I 是一个期望题，我们三个人刚刚好都不擅长，然后就倒闭了，于是一起看 E，发现直接差分 dsu on tree 就做完了，队友写了一下，期间犯了一个比较唐的错误，147min 2AC。

然后发现 G 过的人比较多，于是三个人研究了一会，发现似乎维护一个凸包就是对的，队友写挂了 3 发，实际上是因为建凸包写挂了，好在比较快的调对了，198min 4AC。

后面因为 I 不可做，M 看出来是一个 NTT 但是大家都不会，所以双线开题 B 和 H，队友有一个 H 的做法，我和另外一个队友将 B 转化为 xa_i+yb_i+c\le 0 之后就不会做了，听讲题的时候发现这个东西就是半平面交的板子。

然后我们看 I，队友看 H，我们 I 设计了一个和正解完全相同的 dp 状态，但是不会转移，所以倒闭了。队友最后 rush H，但是有一个贡献没有算全，所以也倒闭了。最终 5 题小罚时收尾，排名第 66。

稍微总结一下：感觉打的挺差的，首先是没有人会 I 这个简单题，其次是前面浪费太多时间导致 H 没有调出来，如果 H，I 过了之后 7 题应该是可以能进金牌区的。