图
题意
给出一张 \(n\) 个点，\(m\) 条边的无向图。每个点有一个点权 \(a_i\)，每条边有一个边权 \(b_i\)。设这 \(m\) 条边组成的集合为 \(E\)，对于一个边集 \(S\)，定义其“导出点集” \(nxt(S)=\{ x|\exists e \in S,x是e的一个端点 \}\)。
再给出一个整数 \(k\)，求 \(\max_{|S| \le k} \sum_{x \in nxt(S)}a_x-\sum_{e \in S}b_e\)。
\(1\le n,m\le 100,1\le k\le 10,0\le a_i,b_i\le 10^8\)。
题解
考虑二分图怎么做。容易建出网络流模型：源点向左部点连两条边 \((S,i,1,a_i),(S,i,\infty,0)\)，右部点向汇点连两条边 \((j,T,1,a_j),(j,T,\infty,0)\)，左右部之间连 \((i,j,1,-b_{i,j})\)。跑费用流即可。
一般情况下，最后答案的导出子图一定是一棵树，则一定是二分图。注意到 \(k\) 很小，而我们要求的只是 \(S\) 中的每条边两端点异色。于是可以对每个点随机黑白染色，正确的概率为 \(\frac{1}{2^k}\)。重复 \(w\) 次，正确的概率为 \(1-(1-\frac{1}{2^k})^w\)。\(w\ge 10000\) 时可以接受。
拼图
题意
对于正整数对 \((a,b)\)，定义一次操作将其变换为 \((\min(a,b),\max(a,b)-\min(a,b))\)。
设 \(f(a,b)\) 为最小的操作次数，使得某一个数变为 \(0\)。
给定正整数 \(n\)，求 \(\sum_{i=1}^n\sum_{j=1}^nf(i,j)\)，对 \(998244353\) 取模。
\(1\le n\le 2\times 10^7\)。
题解
变换形成树的结构。对每个点求其子树大小。
结论：\((a,b)\) 子树大小即为 \(1+2\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=1][ai+bj\le n]\)。
证明先鸽。
记 \(d_i\) 表示 \(i\) 的因数个数，\(sd\) 为 \(d\) 的前缀和，则
于是 \(O(n\log n)\) 解决。
反思
从结果看，这两题都不难，在稍微看了几眼题解后就足以自己想到解法。思维难度中等偏高，同时不是大代码题，这样的题目应该是我在省选赛场上追上他人的关键。但实际上我的水平还略逊。思维题将是接下来重点训练的方向。同时也要增加量的积累，多见套路。
从过程看，我还缺少两种能力：写乱搞的勇气，猜结论（或者打表观察结论）的勇气。前者可以让我过掉前一题的水数据，后者可以得到后一题的结论，推式子则是简单的。