7.7

线上组队赛，队友：luomiao，305/400 pts，rnk 4/6。

• A 题枚举保留的矩阵，坑点是 \(k=0\) 时可以不保留矩阵。
• B 题简单构造，坑点是 \(n=1,m=1\)。
• C 题由于最小一半，可以用随机化，可以枚举模数再随机化判断，也可以随机两个数判断差的模数；也可以利用数量的限制优化枚举，如果模数是 \(m\)，则最多有 \(t=\Big\lceil\dfrac{10^5}{m}\Big\rceil\) 种不同的数值取模后相同，所以最大的一种值的个数最小为 \(\dfrac{n}{2t}\)，所以只需要枚举个数大于这个数的值。考场上因为刚才式子中 \(n\) 没除以 \(2\) 分没拿完，警告。
• D 题人类智慧构造，考场上骗了部分分。

这场考试前两题比较简单，但都有坑点，所以要注意想好整体情况后要考虑边界情况，卡你的极有可能是小数据。

7.12

线上组队赛，队友：AolinYu，5/9 题，rnk 1/6。

• A 题结论为 \(2\) 的不在同色联通块的边界的数量次方，考场死因不明。

对思维的考察比较多，但也有纯数据结构题目。对于数据结构的题，不要说废话，不要想多，但是也不要直接硬钢。

7.15

线下赛，170/400 pts，rnk 6~7/13。

• A 构造，但循环不好做，考虑递归去搞。赛时打了 \(n=10\) 的表，因为没有注意到 \(k\leq n\) 的限制没有得到 \(n=5,6\) 的分，构造题一定注意输出的格式和范围要求，警告。
• B 图论，赛时想写 SPFA 骗分，结果数据过水满分了。大概思路是 Bellman-Ford 算法，记录转移的点，每轮松弛结束后寻找负环，把修改负环上的点的距离。
• C DP。同时注意判断 \(n\) 为偶数的点。
• D 最小生成树的应用。

7.19

线上赛，435/500 pts，rnk 2/13。

• A 最短路计数。
• B 通过拓扑排序转化。赛时想出了一个时间复杂度严格 \(O(n)\) 但常数巨大的做法，所以当数据范围较大时要考虑常数，用常数小的方法，少用递归，访问连续。
• C 最小瓶颈树，跑 prim 即可。
• D 通过差分把原询问拆成 \(4\) 个询问，也可以直接 \(4\) 维莫队。
• E 很可爱的一道题。注意到小于 \(\sqrt {50000}\) 的质数较少，可以把每个数拥有的这些质因数压进一个 long long，然后记录剩下的最多一个质因数，就可以 \(O(1)\) 判断是否互质。同时，由于不同的出现数量是 \(O(\sqrt{n})\) 的，可以记录每个出现数量有多少次，并用链表维护出现的出现数量，就可以莫队直接维护、每个询问格外 \(O(\sqrt n)\) 计算。

7.22

现下赛，300/400，rnk 1/13.

• A 构造，比较经典。
• B 可以发现没有奇环的连通块的两个点的奇偶性不变，所以可以先求出多少连通块不是二分图，注意特判孤立点（不然样例为什么会有 \(4\) 个版本）。
• C 比较套路的线段树优化 DP。
• D 推式子。如果只考虑操作 1，考虑模 \(m\) 意义下环差分数组（即 \(a_2-a_1,a_3-a_2\dots a_1-a_n\)）个数，前 \(n-1\) 个随便放，最后一个要保证总和在模 \(m\) 意义下为 \(0\)，只有一种选法，则答案为 \(m^{n-1}\)；如果只考虑操作 2，考虑容斥，设 \(F_d\) 为有长度为 \(d\) 的循环节方案数，\(f_d\) 为最小循环节为 \(d\) 的方案数，则 \(F_d=m^d,f_d=F_d-\sum_{d'|d,d'\neq d}f_d\)，由于要去除循环同构，答案为 \(\sum_{d|n}\dfrac{f_d}{d}\)；合并后，\(f\) 和答案求法不变，\(F\) 同样考虑环差分数组 \(b\)，此时的要求是 \(m{\huge|}\dfrac{n}{d}\sum b\)，即\(\dfrac{m}{\gcd\left(m,\frac{n}{d}\right)}{\huge|}\sum b\)，所以最后一个数有 \(\gcd\left(m,\dfrac{n}{d}\right)\)，所以 \(F_d=m^{d-1}\gcd\left(m,\dfrac{n}{d}\right)\)。

不要硬钢构造题。