ACM-ICPC 2019 亚洲区域赛 南昌站

（写于2019年11月11日，由于原博客弃用，故转至 AcWing）

Day1

由于上半年邀请赛已经来过，所以一路上都挺顺畅的，就是酒店订的有点偏僻，周围没什么吃的，就直接打车去校内吃。当时已经过了用餐券的时间，就在食堂内随便买了一点东西吃（再加上教练给我们买的一个柚子）

接下去就是热身赛，A题很顺利过了，B题题面没写需要将答案对 1e9 + 7 取模，导致一开始我很高兴的抱着高精度的板子上去一顿乱敲（队友在干嘛？？？坐在旁边吃柚子？？？我......（廉价劳动力无疑了！）。之后在答疑里面发现这一点的时候，已经WA了几发~后来lzh发现一个性质，看不下去我那丑陋的代码，就亲自敲敲敲过了（我好菜呀~）而且在这之前，lzh已经过了C（我连看题的资格都没有，他就过了~我好菜呀~ 至今未知C题题意~）

最后剩下一道D，删除一些边使图上不存在环？？？又是似曾相似的题？？？但是又没带板子？？？无奈之下我决定敲个 Tarjan 的板子改一改，测样例手推一下发现满足题意，但今天没 special judge？？？（所以之前C题输出8位小数WA了，10位小数AC也是因为没有 special judge ~~~）可题目最后明确说了需要 special judge！！！是把题目搬过来的时候忘了把 special judge 的代码搬过来嘛？？？但为什么还是有这么多人AK了？？？

赛后得知，这题将从标号小的点连向标号大的边放在一起，将标号大的点连向标号小的点放在一起，再输出两个集合中数量少的~~~

如果数据是这么出的，那么第五个样例咋回事？？？

群里说那是随便写得一种情况！！！

所以它并没有在测试数据里......

我们......

去食堂，用餐券换了晚饭，味道就那样吧~然后感叹了一句银川站这一点还是挺好的，吃的喝的可以随便换（虽然味道也不是很好~

之后买了点面包当明天早饭，就回酒店了，三人间没了？免费升级成套房？两张床的那种~ 只能按老规矩，掷骰子，小的单独一张床。610一开始就掷了个2~都感觉没了的时候我最后来了个1！！！（从银川站到南昌站，一共掷了三场骰子，正好一人赢一次hh

向酒店再要了一床被子之后开始愉快的备战（打游戏）

三个人都说要看一下虚树（因为武大校赛的时候，他们有个出题人说比较喜欢这个玩意儿，这一场又是武大出的题，所以......）结果，三个人都在打游戏，打着不同的游戏~~

终于，他们两个开始干活了，一个找了一些虚树的题面+代码+题解，另一个再整理些别的板子，明天一起印出来。（此时我继续打游戏~~

最后打游戏打累了，就洗个澡先睡了（后面具体发生了啥，我也不清楚~~

Day2

一大早在朦胧中听见610接了教练的电话，然后又躺了一会，说7:30下楼~~

果然，前一天准备的早饭只有我一个人吃了，他们全是鸽子。下楼后，开了酒店的发票，打车去学校。教练把我们扔在打印店门口，自己去恰饭了，然后我们等了快半个小时打印店才开门~~嘤嘤嘤

印完之后就是赶去体育馆（有一说一，这两个人怎么体力这么好，走那么快，还不时跑两步~ 已经半年没运动的我跟不上啊，现在还能感受到当时的疲惫~嘤嘤嘤

最后坐下的时候离开场还剩大概五六分钟（所以为什么要走那么快嘛

开场后疯狂找签到题，C题题面短，就先瞅一眼，感觉可能得dp？？？过了几分钟发现L题过的人也挺多的，610就去读L，发现是个计算足球得分的签到题，上去敲敲敲，过了样例提交，WA？？？

lzh重新读题，发现有什么净胜分？？？这是啥？幸好这位神仙队友看过足球，改了改顺利过了L。（此时的我仍然在默默坐在一边死磕C题的dp，写了个四维的数组推状态转移方程，至今仍然不知道L的啥啥分是干嘛的~）（如果以后的题都是这种类型的话，我一定会逼着未来成为我队友的小学弟看各种赛事，至少要了解计分规则hh

十几分钟之后，个人感觉终于推出了像样的状态转移方程，抢过电脑一顿敲，连样例都过不了？？？他们貌似又讨论出了E题的做法？？？（队友强就是好！！！

不知道为啥，对于自己推的转移方程有种莫名的自信，就觉得是自己写炸了，debug了一会调不出来，就打印了一份代码，把电脑扔给lzh写E。

就在小姐姐把我C题的代码送过来不超过3分钟，我发现了，有两个方程在两种情况下都得转移，我直接特判掉了~~ 抢回电脑，把那两句话注释掉，再移到if的外面，过了样例耶(＾－＾)V

不记得还有没有测一个手推的数据，反正提交之后直接AC！！！

接下去lzh继续敲E，610给我讲E题题意再确认一下做法。嗯，整体上没问题，又口头讨论解决了一些细节。确认没什么毛病之后lzh继续敲敲敲，我在610的带领下，看了眼榜单，决定看G题。

要对 998857459 取模？？？这个数字怎么这么奇怪，为什么不是常见的 998244353 或者 1e9 + 7 ？？？

这个数字肯定藏了点东西！！！

上述是我第一直觉。

很快，lzh敲完了E，简单调试了一下顺利过了样例，提交，AC！！！（大佬tql）

趁着大佬去上厕所，我偷偷在电脑前坐下敲了个test，发现阶乘只要到2803以及之后的数字，取模之后的结果全都是0！！！

那么，对于 n ，这个数实际的操作范围直接从 50000 缩小到了2802！！！

很自然可以想到用 $O(n^2)$ 的复杂度直接处理出所有的结果，接下来就是对于 m 组询问，如何快速出解的问题。

最后发现貌似线段树可以处理~~ 诶，那不就是学校新生赛最后一题的线段树的询问嘛？？？lzh压中题了？？？ tql！！！

这时候午餐送过来了，汉堡 + 鸡块 + 香蕉 + 牛奶

这两个人又开始压榨我了，指挥我敲敲敲，然后自己吃吃吃 ┭┮﹏┭┮

终于敲完了，直接甩给lzh检查，自己开始吃吃吃~~

由于lzh看不惯我 $O(n^2)$ 暴力的方式，直接将这部分代码全改了，嘤嘤嘤~~ 然后测个样例，过了！！！ 提交 WA？？？

再一看，是我写的下标搞混了？？？改一改再交，还是WA？？？再看看，发现下标还是没理清楚，无奈之下lzh拿起来纸笔画了画，我们一起再理一理，改一改~再交，AC！！！（好吧，我承认，这题是我演了

接下来就是愉快的看榜，吃东西时间(((o(ﾟ▽ﾟ)o)))

此时距离比赛结束，剩下不到两个小时(｡ì _ í｡)

榜上除了我们已经过了的4题，还有B题过的比较多，再就是J，由于J题面比较短，决定优先读J。

四种元素？一定顺序爆炸？循环同构？？？貌似在我们的知识储备中…又想了几分钟，发现我们可能确实不可做，就去读B题。

乍一看图是二分图，再一看数据范围只有18，再读一读题面，暴搜？？？感觉可以写一写诶，要是过了就可以稳一稳银了！

再仔细读了读题，确定了一下搜索顺序，但感觉会TLE，再想了一会决定我先敲一遍这个代码，就算真T了还可以用来验算数据。

成功跑出了样例的答案，但lzh随手造了一组数据就让它T了o(////▽////)q

由于想不到更好的做法，只能尝试着剪枝优化一下。

先将矩阵存联通性改成了vector来存每个点与哪些点联通，再跑那组数据，肉眼可见出解加快！

但交上去还是T了. .

此时离比赛结束已不足一小时，当然也已封榜，封榜前的排名为90，如果不过这题，可能又只有铜. . .

我玄学性的在每次dfs刚进入的时候就计算一遍ans用来跟全局最优解比较，如果加上未来的最优情况仍不如现在的全局最优，则直接返回。(其实这种剪枝很常用，只是这题每次都需要重新开个循环计算一遍ans，一开始就没加(但赛后想了想，貌似也可以将这个ans当参数直接传. . .

跑一遍那组数据，瞬间出解！！！

满怀激动交上去，WA. . .

回到代码界面，三个人盯着这个剪枝看，又是lzh发现了问题(tql！)未来的最优情况，就是0. . . 也就是计算出当前结果后直接与全局最优比较！

貌似没啥问题了，再交一发

......它测了好久. .好久. .好久. . 我们都以为它又T了......

然后突然蹦出来一抹绿色，象征着生命的颜色！！！过了☆:.｡. o(≧▽≦)o .｡.:☆

所以测得慢只是因为测试数据多(((o(ﾟ▽ﾟ)o)))

此时离比赛结束还剩半小时左右的时间，看了看榜单，如果这个罚时放在封榜前可以上升到三十几o(≧v≦)o

只要封榜后达到5题的不超过60队，就能稳稳拿个银^ _ ^

还开题嘛，剩下半小时

看一看吧

那就继续看题，看了一两题发现短时间内都写不出来，我就愉快的写了个随机数交最后一题，虽然几乎为0的可能通过，但我仍然乐此不疲，最后一共交了56发随机数，毫不意外，全是鲜红的WA

这次能够愉快地看滚榜，看颁奖了，不用像邀请赛的时候那样灰溜溜地改了高铁时间跑路了

讲题 + 乐器表演 + 志愿者小哥哥小姐姐合唱，接着就是滚榜

人生当中第一次在现场看滚榜，不过这次滚榜中间部分有些无聊，都没几个队过题，当看到榜单更新到一百二三十名的时候，我们还在前面，就觉得银稳了，毕竟我们封榜后过了一题，排名还会再往上滚

第一次滚榜到我们是100名左右，过题，排名上升，直接到了42！

再滚一滚，最终排名60，领了块银牌☆^ _ ^☆

接着就是例行的拍照，教练高高兴兴请客恰饭，在高铁上一卡一卡地看完了 FPX vs G2 的第一局，当时就预感 LPL 又会捧回奖杯，毕竟我们都银了(｡ì _ í｡)

最后附上610的帅帅的学侄的照片(他们的教练是610高中时候的学长，话说他们也过了5题，只是罚时比我们多了差不多200分钟而已，可他们才两个高二一个高一呀，如果不是打星队伍，也有块银，哎，我们好菜啊) 以及我校第一块icpc银牌，也是第一次封榜后过题的成果！