这是又是一篇拖了很久的总结了。

为什么拖了很久，因为成绩又很烂，太菜了。

最后也给自己的ACM竞赛道路画上了句号。

一直没懂为什么区域赛可以高铁，EC就只能硬卧，emmm不过为了报销咱也不敢说什么。

热身赛就不多说了，因为忘了。

正式赛，基本算是我写的，所以锅也全是我的，罚时爆炸。

还是简单说一下一些题目吧。

A题签到，就推公式嘛，忘了当时好像自己哪儿推错了，21min才交题过的。

A

题目大意：给n×m的棋盘，共(n+1)×(m+1)个格点，问有多少条线段满足端点在格点上且线段中点也在格点上。

• 瞎搞搞推公式吧，忘了赛时怎么写的了。
• 现在想想大体思路就是：如果枚举情况就是，上下端点的行差必须是2的倍数，左右端点的列差必须是2的倍数，其他的就自己推吧。

接下来就是我为M题疯狂献上罚时的时刻了，真的交了无数发。一开始一直按贪心在想，也不知道咋出的锅，只知道把心态搞炸了。WA了5、6发之后终于发现可以暴力做，实在不想写了，把思路给队友说了让队友上吧，最后一共提交了10发吧，原地爆炸。

M

题目大意：两个数组$A$和$B$，从$A$里选择一些数$a_i$，若存在一组$(i,j)$和$k$满足$i^k=j$，且$a_i$和$a_j$都被选择，则减去$b_j$，问最后总分的最大可能取值是多少。

• 数据范围 n <= 100000，
• 因为2的p次方一定包含4的q次方，且$2^{18}>100000$，最多17项
• 若两数不存在次方关系，对于答案的贡献是独立的
• 所以我们对于每个数都枚举其次方项的取值情况，计算复杂度大概是$O(17*n\sqrt{n})$，当然好像不能这样算，$17$和$n$的复杂度是针对枚举2的情况，所以可行吧。

然后使队友开的E题，把原题目抽象成了另外一个模型，所以队友写了抽象模型的部分，后续我想了一个贪心思路，也是改了几次才AC的。果然每次想贪心都莫名其妙各种想不清楚。

E

题目大意：原题目忘了，抽象成的另一个模型是，起点和终点之间有多条路径，每条路径长度相同，即都由k条边组成，且每条边有最大流量，现在可以进行的操作是将某一条边流量+1，另选一条边流量-1，问使起点到终点流量max的最少操作次数。

• 首先最终的流量值是可以确定的，就是所有流量和除以路径长度k，向下取整。
• 然后+1和-1操作只需要考虑+1操作即可，因为总会有没用的地方进行-1即可。
• 然后每条路径有一个初始流量值，即路径对应k条边的最小流量值。
• 然后我们考虑每次增加起点到终点1的流量值需要的代价，每次选取最小代价即可。
• 代价很好计算，就是每条路径有多少条边的初始流量小于等于当前流量。
• 所以我们只需要对每条路径的k条边排序，每次比较选取最优路径即可。

剩下的一个半小时就是自闭时刻，另外还开了两道题C和H，但是都没有过，还有一道G是个大模拟，唉我队每次都没人碰大模拟，以后也没机会了。C题瞎推了下，找到一点规律，但是不会筛法就没办法了。剩下H题可以想一想。

H

题目大意：给定n个数的数组B和一个质数p，问能否从B中顺序选取至少n/2个数构成数组A，且满足存在q使得$qa_{i−1} \equiv a_i(modp)$，若存在输出最多能选多少个数，否则输出-1。

• 因为需要至少n/2个数，所以大概率会出现B数组中相邻两数都选，或者相隔一个数的都选。
• 所以我们把所有的这些情况即2n个q计算出来，统计个数。
• 考虑使上述两种情况尽可能少，即选择的数间隔为2，只能选出n/3个数，所以至少有n/6个数在之前计算的2n个q中。
• 剩下的就是枚举了，对超过n/6个的q都暴力计算一下，最多也就计算12个。

其实想到了相邻的会有很多，如果一个相邻的都不出现就只能全部都是相隔一个的，但就没有多考虑一步，有点可惜，赛后问隔壁队，人家随机算法做的，好像就考虑相邻的情况，然后随机balabala，咱也不知道了。

最后比赛结束，鼓掌撒花！

罚时报警，只能铜牌保报销了。

不管怎么说，菜是原罪。西安两日游结束，ACM公费旅游全部结束。

2019公费旅行路线：北京 - 西安 - 秦皇岛 - 南京 - 上海 - 西安

所以正规一点的一共参加了1场邀请赛，1场CCPC和4场ICPC，一共3银3铜，还是觉得有些可惜吧，因为还是希望拿个金牌，可惜没能如愿。不过很高兴结识两位队友，社会佩奇也一直在努力，继续加油鸭。