ICPC 2018 亚洲区域赛南京站游记
Day 0
国庆六场模拟赛场场自闭，导致比赛前一周状态不佳。抱着打铁的心态随便整理了一下模板。本来打算当天就整理好并打出来的结果转念一想去南航找复印店应该很容易（好一个 FLAG）所以就咕咕咕了。晚上听 BinGoo0o0o 巨佬讲了一些很高深的树形背包问题的变形（貌似并没有太听懂 QAQ），然后和队友胡乱吹了一波水，就心安理得地滚回宿舍睡觉了。
Day 1
早上起不来啊…… 好困啊…… 结果头天都说要咕咕咕的队友来得都比我早。
高铁好评。尝试在高铁上用 Surface 最后 rush 一下模板，结果前面那个人突然把作为猛地往前一调我 Surface 就不见了…… 还好没悲剧。于是接下来我都没敢用电脑了，就看了一会儿小说。南航离火车站之隔一站地铁…… 然而我感觉在地铁站里面走花的时间比坐地铁还久。
一出地铁就看到南航方向飞来一架直升机…… 然后又来一架…… 然后又是一架…… 果然南航，好强啊。进学校看横幅才知道貌似刚好赶上了一个 “南航 · 昌飞” 直升机主题招聘日，并且打出了 “您的专机已就位！AC311 乘机体验，让我们带你一起飞” 的标语。虽然很想坐直升机，但转念一想身边两位队友就已经可以带我飞了，所以也没什么关系了。照片不出意外地拍残了：
一群人迷路若干次绕了一大圈才找到体育馆。报道时发现南航慷慨地给了三张 20 元的餐券。去南航的网红食堂 “航空餐厅” 吃了午饭…… 拿了一堆菜以为要超额度结果离额度差不少（后悔 QAQ）。反正南航的伙食我吹爆，又便宜又好吃，有这食堂还订什么外卖……
吃完饭后去体育馆就可以碰到电脑了。南航的体育馆好气派啊……
到现场发现高中大佬学长就坐在对面的位置 orzzzzz。看比赛手册以为是带 Unity 桌面环境的 Ubuntu 16.04 LTS，结果到手发现是 xfce 桌面环境的 Xubuntu，连 gedit 都没有。另外我们发现电脑巨卡 QAQ。Hanano 尝试在 Code::Blocks 里瞎写一些东西，然后发现有一定几率写一半电脑突然卡住，过几秒才好 QAQ。接着我们又发现，Code::Blocks 执行编译好程序的默认终端是 xterm，而 xterm 连复制粘贴都不行。我们尝试把其改成 xfce-terminal, 结果发现一改在 Code::Blocks 里保存代码的时候就会跳 Exception，然后一点 stop 就闪退…… 心态崩了 QAQ。
下午简短的开幕式完了后就开始了热身赛，还没有打印模板的我心里慌慌的。热身赛一开始，打开 PC^2，输入账号，输入密码，Invalid Password。再输一遍，Invalid Password。两个队友轮流输，Invalid Password。结果后面才知道主办方 PC^2 出锅了…… 那就看题吧。结果拿到题册一看，全都没有时限/空间限制？PC^2 上也没写，这可还行。Hanano 大佬一眼秒 B 题（分别按照 $x, y, z$ 排序并将相邻点间连边建图再在图上跑最小生成树即可）。Hanano 写完 B 题正感叹交不了题的时候，主办方突然表示解决掉 PC^2 的锅了：将每个账户的密码重置为跟账户名一样。可还行。刚交完 B 题，我们发现 PC^2 里看不到评测队列并且半天没等到结果，我就提议看看榜单。结果一开 Firefox，整个电脑就卡死了…… 我们等了十分钟后发现电脑还没反应就召唤来了现场志愿者小姐姐，接着志愿者小姐姐又召唤来了志愿者小哥哥，帮我们进行了强制重启大法，解决了这一问题。我背锅我背锅，再也不敢看榜单了呜呜呜。直到小姐姐送来了气球我们才知道 B 题过了，Hanano 好强啊 QAQ。
接下来 nbfynbfy 大佬很快也推出了 C 题公式，好强啊 QAQ。电脑恢复正常后 nbfynbfy 写了 C 题，我给 nbfynbfy 提供了预处理阶乘逆元并 $\mathcal{O}(1)$ 求组合数的写法后也 1 发 AC 了。接着在我卡 D 题的时候 Hanano 决定试试环境而本垃圾一眼秒 A 题，然后发现 A 题看漏了一个条件…… 然后就做不来了…… 于是我就去开 D 题了。
在主办方表示除 Desktop 以外其他地方存文件可以保留下来的时候，Hanano 就决定玩玩 vimrc 啦…… 他一顿操作猛如虎写下了自己的 vimrc，却发现无论如何也加载不上去…… 知道我查到可以使用 -u 指令加载自定义配置文件后，他才发现自己 vimrc 写挂了…… 然后搞了半天终于调好了，并保存在了非 Desktop 目录下，然后美滋滋地让我瞎搞 D 题。
我 D 题考虑如果使用类似树状数组的数据结构的话，区间修改是只跟左端点和右端点 $+ 1$ 有关的，因此可以考虑首先读入询问并离散化所有左端点和右端点 $+ 1$ 来把 $10^9$ 的神仙数据范围降到 $10^5$。然而写了一半才意识到区间修改实现有一处细节考虑错了…… 然后就凉了做不来了。一道题都没做，划了三小时水，好羞愧呜呜呜。
赛后群里 Claris 表示我只看了 A 和 D 不都是 BZOJ 原题吗…… 瑟瑟发抖（分别是 BZOJ 2345 和 BZOJ 1938）。A 题面出锅了…… 原题是 V 船可以随意乱走但是热身赛题面说的是 V 船必须与 Y 船按照同样的方式走…… 醉了啊。要是是前者题意的话就是一道大水题。听说主办方为 A 题准备了 $300$ 多个气球最后只发出了不到 $10$ 个，哈哈哈。而至于 D 题，大致是先要用一些数学变换把修改操作转化为可以用树状数组或是线段树维护的修改操作，再像我那样离散化区间端点…… 嘤嘤嘤我开了什么神仙题啊，不过有空还是想补补这道题……
Hanano 表示 NUAA 的餐券好好看啊想留一张。我觉得大佬说的很有道理，于是我们去吃了汉堡王…… 然而吃的有些慢，一不小心就把学长咕了，呜呜呜。晚上路过南航停机坪时顺便偷拍了一架直升机……
去了宾馆，终于不是一晚上 $30$ 元一人的那种了，感觉超棒。在宾馆里最后修改了一下模板就跑回南航里找打印店了（要是没有模板我怕是要被队友打死 QAQ）。南航好大啊 QAQ。找了半天才找到打印店。打印好模板后站在南航里跨公路天桥上看了一会儿车水马龙…… 感觉莫名平静，另外就是感觉我读了一个假大学。
Day 2
房间里开了二十度的空调还能有蚊子…… 也是醉了。
七点过爬起来后在酒店吃完早餐就上路了。回到体育馆一看，什么都没了（包括前一天调了半天写好的 vimrc），于是 Hanano 一气之下就决定用 Code::Blocks 了。不过还好，今天电脑基本不卡了，而且修改默认终端也不会报错了。
本来以为有倒计时的（连热身赛都有倒计时），结果比赛突然说开始就开始了。题册按照惯例也没有时间限制空间限制，主办方在 PC^2 里发了个 Clarification 才把时限告知参赛选手…… 不过貌似还是没有空间限制。前一天听学长说貌似 PC^2 不会返回 Memory Limit Exceeded，所以貌似可以放心大胆瞎搞？问题不大。
按照惯例，nbfynbfy 从头看， Hanano 从中间看（F 题信仰），我从后往前看。我一看最后一题，回文树？打扰了。此时 nbfynbfy 貌似一眼秒了 A 题并开始敲代码了。他火速敲完后说是一个裸 Nim 博弈，我简单晃了一眼题貌似是的就让他交了…… 然后 Wrong Answer。然后我脑抽地问了一句会不会是多组数据…… 然后又交…… 又一发 Wrong Answer。于是我又仔细读了一遍题，发现看掉一个条件…… 一次取石头只能取一段连续区间。给 nbfynbfy 说了后心态有点小崩，然后就留下他继续想 A 我先去看 B 题了（我博弈很菜的 QAQ）。看完 B 题后发现没什么思路，这个时候看了一眼榜发现怎么大家都会 A 题啊 QAQ，然后 J 题也有人过，于是我就又去看了看 J 题，发现没有什么思路，只知道质因数肯定是要分解的，于是本垃圾心态更崩了。这个时候 Hanano 拉着我一起想 C 题。简单想了想没什么思路，我就决定先去跟 nbfynbfy 搞 A 题了（此时已经过了一片了）。然而这个时候志愿者小姐姐突然送给我们一只红色气球。Hanano 问道是 A 题过了吗？我懵逼了，难道重测了？再三看了看 PC^2 里的评测结果和榜单确认我们还依然处于签到失败的状态…… orz 看起来是气球发错了 QAQ。nbfynbfy 问我 $k + 3$ 是不是必败态，我仔细想了想发现不是…… 然后我们很快发现先手必胜的情况好多啊…… 会不会一定是必胜呢？简单想了想发现只要先手一来从中间取一段使得剩下两段长度相同的连续区间，然后接下来对方怎么取就跟着怎么取就一定必胜了…… 不过还要特判一下 $k = 1$ 的情况，因为 $k = 1$ 且 $n$ 为偶数时先手无法搞出长度相同的两段连续区间。于是我瞎写了几行交上去终于 Accepted 了。签到花了四十分钟嘤嘤嘤，而且一来就两百多名，充满了打铁气息。
接下来我们赶忙去看 J 题。nbfynbfy 提出了一种复杂度 $\mathcal{O}(n\log{n})$ 的神仙做法但是给我和 Hanano 讲的时候我们都一时没有理解（nbfynbfy！），于是就让 nbfynbfy 将就 Hanano 写好的素数筛和质因数分解直接上了。nbfynbfy 一顿操作猛如虎便过了样例，然后交上去后 PC^2 表示 Time Limit Exceeded。于是我们一起看了看代码，我首先发现 Hanano 写的是 $\mathcal{O}(n\log^2{n})$ 的埃氏筛，于是要求改成线性筛再交一发…… 继续 Time Limit Exceeded。我心态有些小崩，明明都总算 $\mathcal{O}(n\log{n})$ 了怎么还不让过 QAQ。我把目光转向了质因数分解部分，发现 Hanano 写的是 $\mathcal{O}(\frac{n}{\log{n}})$ 的质因数分解（即试除终止条件为 primes[j] <= n），这勾起了我 Codeforces 上某场疯狂 TLE 一小时的惨痛回忆，于是顺手改成了 $\mathcal{O}(\frac{\sqrt{n}}{\log{\sqrt{n}}})$ 的质因数分解（即试除终止条件为 primes[j] * primes[j] <= n），这样一来预处理素数的范围也可以改小一点了，然后再交一发…… 竟然 Accepted！开心（这算卡常吗 QAQ……）~
我们看了一眼榜，发现 I 题过的人挺多的（另外就是发现自己还在铁牌区 QAQ），于是我就去看 I 题了。我题还没读完 nbfynbfy 就大叫一声二分图（好强啊 QAQ），我一看有道理不过这个直接二分图匹配不好做要用网络流。与 Hanano 讨论了建图后发现自己之前把一个人拆成两个点的建法存在 TLE 风险…… 于是自己就考虑直接超级源点到源点容量限成 $n + k$，然后源点到每个人边容量设成 $2$ 来建。于是我上去写这道题，Hanano 和 nbfynbfy 一起去看 G 题了。我敲了半天 Dinic 板子并写好后样例一遍过，然而提交却 Wrong Answer 了。我的第一反应是会不会模板抄错了，检查了半天也没发现问题。这个时候 Hanano 过来帮我看了一看表示我建图存在漏洞…… 不应该只设一个源点限制 $n + k$，应当建两个源点一个限制 $n$ 一个限制 $k$，因为前者可能导致实际上有多于 $k$ 人服药。我一想好有道理啊，然后改了改交上去就 Accepted 了。贡献了一发罚时好羞愧 QAQ，Hanano 好强啊。
接下来我们就一起去看 G 了，Hanano 和 nbfynbfy 貌似已经人肉打表并发现一个公式了（疯狂膜队友），Hanano 用电脑上的 Python 进行了简要验算后就开始尝试化简式子了，然而化简了好久貌似都有一些问题（in the meantime 本垃圾由于什么都不会就只好帮大佬队友做人肉验算）。最后 nbfynbfy 进行一顿化简后大叫，这不就是组合数 $\binom{n + 3}{4}$ 吗…… 我们验算了 $n = 1 \sim 5$ 发现全都是对的，然后 Hanano 就说不如偷个懒直接用 Python 随手写一个交一发试试看（直接用内置高精度就懒得算逆元了）。在等待 PC^2 返回结果时 Hanano 表示要是 TLE 了就好玩了…… 然后若干秒后真的 Time Limit Exceeded 了。一口好奶，真是笑死在现场。于是我们只好灰溜溜地又用 C++ 写…… 然后就 Accepted 了。队友太强了 ooorrrz！
此时我们过了四题，大概位于铜牌区。不过这时大概就差不多要封榜了。我们看 D 题和 K 题过的人比较多，就决定最后一个小时主要看这两道题。D 题我看完题目就有二分答案的想法，不过如何判断答案是一个问题 —— 以给定所有点为球心作半径为 $R$ 的球并判断这些球是否相交于同一区域。开始我以为只要这些球两两相交就可以了，但是 Hanano 写出来后发现第二个样例没过，在纸上画了画才意识到这样子是不行的。然后 Hanano 就感叹道有没有最小球覆盖的算法啊…… 此时 nbfynbfy 掏出了他携带的一大堆书，并在红书上真的翻到了最小球覆盖问题的模板，好强啊 QAQ。比赛前还一直跟他说带这么多书没什么卵用的我此刻也只能说真香了。Hanano 表示这个模板码风好辣鸡啊然后二话不说开始打模板。于是我和 nbfynbfy 就一起去看 K 题了。
在此期间发生了几件有趣的事情…… 突然我们的 PC^2 都被登出了，不久后主持人表示评测姬出了一些问题正在修锅。几分钟后主持人表示评测姬好了并且比赛会延长 $5$ 分钟。接下来，主持人幽幽地来了一句，大家不要提交大文件，刚刚就是有个队提交了一个一百多兆的打表代码把评测姬卡爆了…… 现场一片大笑哈哈哈哈哈。可是没过多久后我们的 PC^2 却又被登出了，主持人再次表示正在修锅，几分钟后主持人又表示比赛再延长 $5$ 分钟，也就是总共延长 $10$ 分钟。这次主持人没有表示出锅原因，赛后我才听说好像是某个队伍疯狂提交 rand 导致评测姬负荷量过大卡掉了。
我和 nbfynbfy 讨论了 K 题后发现一个很大的问题 —— 做不来 QAQ。于是我提议不妨去看看 B 题，然而对于 B 题我们貌似也没什么思路。看了看表只剩二十分钟左右了，感觉再开新题已经不现实了，于是我们开始就围观 Hanano 巨佬敲代码了。Hanano 火速敲完代码便遇到了一堆编译错误…… 结果发现全是手误。修完编译错误后一跑样例，发现样例全挂了，心态打崩。于是我立马让 Hanano 把他的代码打印出来然后三个人一起帮 Hanano 查错。我帮 Hanano 查出了两处手误后 Hanano 发现样例还是过不了。这个时候离比赛结束已经不到 10 分钟了。我再次反复检查了一遍 Hanano 的代码，并没有发现什么其它错误。这个时候 nbfynbfy 表示会不会是书上模板是 int 而我们应该用 double 的问题…… 然后 Hanano 立马改了改，发现样例过了，于是立马提交。不过看起来这个时候大家都在疯狂提交，评测很慢很慢。于是为了保险起见，我让 Hanano 把 eps 为 $10^{-4}$ 到 $10^{-7}$ 的代码全部都交了一遍。接下来剩下的几分钟我们也没什么事情干了，之后看着评测队列。然而，比赛结束后还是没有返回评测结果，咕咕咕 QAQ。
于是我们终于打开了午餐盒，开始边吃边等待评测结果。这个时候我打开了手机看到 Changer-qyz 发了句祝贺，然后我懵逼地表示我们还等着看自己的滚榜哈哈哈。然后大约十分钟后屏幕上突然跳出一行绿色的 Accepted，我们沸腾了，然后进入疯狂膜 Hanano 绝杀大佬的模式。奇怪的是后提交的反而被先评测了，我们立即打开手机进行拍照留念。
这感觉有点像今年 WF 上 PKU 队最后四分钟绝杀那道计算几何一样…… 只不过他们比赛中就知道结果了，而我们比赛后才知道。接下来屏幕上又弹了三次绿色的 Accepted，每弹一次我们就膜一次 Hanano。然而当我们稍微冷静下来分析一波时，才意识到这大概就是从铜尾翻到铜首的区别，拿比例算一算拿银还是凉凉。于是我们开始焦急地等待滚榜环节。在此期间我们不要脸地从隔壁队伍偷偷借来了一只 D 题的黄色气球插在自己队伍的牌子上并拍了一张照片。
听说由于 PC^2 炸了工作人员需要手动核榜，所以咕了我们一会儿（工作人员辛苦了 QAQ）。滚榜时屏幕上直接出现了最终榜单，并直接以滚动的形式播放（这可还行，重新定义了滚榜）。眼尖的 nbfynbfy 突然表示看到我们在银尾区，等到终榜再一次滚动到银牌区时我们才确认了这一事实，然后我们又进入了疯狂膜 Hanano 绝杀大佬的模式。简直两位大佬带我飞啊 QAQ。前一段时间的疲倦怠意仿佛在此刻一扫而尽，心中只剩下一种纯净的幸运感与快乐。
我们把绝杀大佬 Hanano 推上去领牌了并对他进行了疯狂拍摄（这里就不上图片了，逃）。
晚上以“去南京吃北京烤鸭，去北京吃南京盐水鸭”的心态去吃了北京烤鸭，然而吃的有些慢差点又把学长咕了。晚上直到到高铁上想听点音乐才发现本垃圾一不小心把耳机扔宾馆了 QAQ，可以说是乐极生悲了orz。接着就滚回学校赶作业了（貌似一不小心就欠了某大佬一顿饭，早知道不嘴贱了 QAQ）。