2019 十二届ACM河南省省赛总结

赛前：
拉着nyx刷了不少的专题，国庆还专门刷了将近20道的博弈论和概率期望，从上次省赛回来自己已总结了不少的模板，学了不少的东西，虽然这次都没有用上，毕竟为这次省赛准备了不少。
然后就是错过火车，全体改签，这个我有责任，没有估计好时间。然后到了黄淮学院，志愿者非常热情，在前两天就一直联系我，给我们说各种去学院的交通方式，还有我们的报道流程。然后就是在火车站和程老师碰面，坐公交车到驻马店市体育馆，报道注册。这次省赛竟然是在体育馆比赛，这个也非常赞。
然后就是下午的热身赛，题目比较简单，好像很多队都AK了。也有不少队被AK了，因为不少人把座位号当成帐号，登错了。

主要讲一讲正式比赛吧
我们先把纸质题目分成3份，一人看几题，我先拿到ABC题，全部都是DNA序列的字符串题，又回到高中生物的感觉，A题好像就是个字符串匹配。暴力，B题没怎么看，去看了C题，应该也是一个字符串匹配+比较的暴力题。q学长想到D题的做法，直接上去敲，快敲完了，发现题目的描述，不知道有没有什么特殊的情况。再看看榜好像没有人过，就先放下了，A题有人过了，就直接敲A题去了。直接AC。然后就是C题，AC，看看榜B题有人过了，q学长去看了看B题说：可以做，类似一个最长公共子序列+贪心，就敲去了。其间了lxx翻译出来G题，我们想了想直接强连通缩点,然后最小链覆盖？好像不用最小链覆盖,直接统计入度为0的点就ok了。当时把想法给q学长说了，我们看了看榜，没有人过，q学长说不要先开这题，跟榜就稳了，当时一直是榜单前10吧，然后B题WA了，我推了个反例，发现必须全部dp，发现这题并没有那么多的人过，就放下这个题了，J有人过了，lxx翻译了一下，我直接推了个公式J题就AC了。
这个时候F题有人过了，lxx也把F题翻译出来了，我突然想到一个这个题和骨牌覆盖问题类似，二分图匹配，我只知道这个题，和做法，并不知道具体的实现，说来也巧，图论我就二分匹配没有刷专题，然后我把想法给q学长说了，他觉得也是这个，看了看榜单，发现南阳理工学院有个队开始就把F题过了，但是A题没有过，并且就过了F题，而且发现不少排名较后的队过了这题，排名较前的没有过，然后我们商量是不是暴力可行？，我推了一个反例，发现并不可以，但是好像二分图匹配复杂度太大，他就翻模板去了。这个时候我看nyx他们队，还没有过题，暗暗为他们捏了把汗。因为赛场上每个队平均都有1~2个气球了，新生也有一个气球了。
q学长看了看模板，发现有个模板复杂度可行，然后上去敲，不知道是不是模板的问题，还是建图的问题，样例过不了，然后就是换模板，这个时候这个题已经耽搁1个小时了，nyx他们已升起2个气球了，换模板还是推不出样例，我看着我们从榜单第7一直掉到30几。这个时候发现D题过了不少，q学长就把D题的代码特判了一下交了，WA了，然后又改了改交了，AC。这个时候差不多还有1个多小时2个小时的样子，这个时候q学长又看F题去了，我看B题去了，因为这个题有点像寒假牛客网有道题，我当时是补了的。我就直接推了个状态转移方程。应该是没有问题，我上去敲了出来：

样例过了，提交WA。然后q学长又去敲F题去了，我以为状态方程错，又改了改状态方程，样例都推不出来了，q学长代码一直推不出F题的样例，只能准备开E题了，当时我们看nyx他们4题了，而且他们F题过了，我马上让q学长不用敲二分图匹配了，因为我一直拉nyx刷的图论，我们都没有刷二分图匹配，所以他们肯定不是二分图匹配做的，
然后q学长看了E题发现应该可以做，就敲了E题去了，让我一直想一下F题的贪心，我实在是想不到这题怎么贪心，因为贪心就是错的。后来q学长敲到一半发现E题做不了，准备贪心写F题，从周围没有连通的点进行匹配，然后还有20分钟左右，WA了一发，改了改直接提交了，一直在队列中，我们计算了一下，过了好像能够银首还是金尾？，然后还有几分钟，我又去看了看D题,还是过不了样例，总感觉哪不对，又不知道是哪，一直到比赛结束，nyx过来问我们几题，我马上问他们F题怎么做的？
贪心啊！
你们怎么贪的？
优先与右边匹配！
我听到顿时心态崩了：你看，这个样例贪心过不了啊？
nyx看了看：的确是过不了，但是我们A了。
我，q学长，lxx：？？？？？。

比赛结束几分钟了，我们F题返回结果出来了，还是WA。

赛后
F题用二分图的思路没人过，过的应该都是贪心的思路。虽然正解是二分图匹配。
而且只有一个队过了G题，虽然大家的思路都是：强连通缩点统计入度为0的点，但是只有一个队过了G题，隔壁学校的大佬到题解分享会上替大家发了个言，并且希望公开代码和数据。
我们拿了个银，nyx他们因为一来就卡D题，直到最后也没有过，因为罚时太高，拿了个铜，小萌新2题也拿了个铜。
然后就是照相留影，回学校。没有金牌，没有继承去年的荣光，我们败的一塌糊涂。

想起之前自己的每一场比赛的flag都没有实现过，去年的区域赛的flag是拿牌，结果：青岛打铁，焦作打铁。蓝桥杯的flag拿省一，结果：省二。CCPC省赛flag是拿金，结果：银首。我想了想反正自己的flag都不会实现，那这次的flag就定成拿银吧，这次终于实现了…

接下了就是认真准备区域赛了，我真的担心我们17的队员打不到名额，我准备拉着nyx先把没有刷过的专题刷一遍吧，crz和dyw刷其他的专题，这样至少不会死的太难看。

后记：
当时我推的D题的状态方程没有问题，就是dp数组没有边界初始化，就是少了个方框的内容，好久没有写dp了，一直在刷图论，如果当时我能看看自己最长公共子序列的代码，也许能够发现自己没有初始化，但是没有如果啊啊啊啊啊啊啊。最后附上自己D题的正确的代码和吃瓜链接:如何评价2019河南省第十二届ACM省赛？