2019ICPC区域赛南昌站

总结

肥宅很快乐这次差点就改名肥宅带伤上场(玩笑话)

这次比赛一开始三题还是非常顺利的，一路过关斩将1A。
遇到G题之后开始犯了难。
一度因为队友读错题和自己因为判无解wa4，然后怀疑题意读错开始重读题目。理解正确题意之后又wa2，忘记原因了。最后又发生了一发RE，然后可能用了太多的stl库，不知道RE的点在哪里，决定换一种稳妥的写法，最后AC，一共7次罚时。
B题队友觉得暴力可解，但我一度怀疑人生，这时候理解错队友说的题意，写了一份无效代码，心态有点崩，这点需要调整。在调整了一会儿心态之后，估算了一波暴力复杂度在3^n，加上剪枝本地测试之后稳过，选择提交，1A。

整个过程还是比较平稳的，但5题就算没有那么高的罚时也进不了金牌区，要拿到金牌还得提高自己水平并且让自己的做题速度再有一个提升。

题解

B

题意说明保证输入的图是个二分图，只存在$i$到$j$($i \leq j$)的边，并且每个$i$的出度不超过3，也就是最多3n条边。
暴力枚举右边每个点选择的左边的点，每次选择一个点之后位运算屏蔽掉不能和他出现在同一个图里面的点。如果发生某个$j$找不到能选择的$i$，那么退出。
动态维护每个点的当前权值和总和，如果超过之前的答案则剪枝退出。复杂度上限大约在$O(3^n)$，剪枝优化之后本地随便测了几个极端数据耗时不超过$10^{-3}s$。

G

给出一个1~n的全排列a，代表了一个序列b，还给出了一个MOD数，$b_i=(a_i!)\%MOD$。求b的最短子区间和$\geq$查询的x，保证x的范围不超过模数，但这个模数是一个合数，最大质因子是2803，也就是超过2803的阶乘对MOD取模后都为0，所以一共只有2803个非0数字，对着这2803个数字$O(n^2)$求出所有答案，并且维护数组，得到长度为$len_i$的时候能得到的最大区间和。这个数组必定是非递减的，然后每次直接在数组内二分答案即可。