F
这道题是一个远古（中学时想的） idea，没想到成大三老登了竟然还能用上。
判定问题
假设 $x$ 一定，那么球位于某些点的时候，A 是不败的，称这些点为胜点，其余点是败点。考虑如何判定每一个点的胜败。
一个点 $p$ 是败点的充要条件是：
$$ \text{与 } p \text{ 相连的胜点数量} = \deg(p) - \text{与 } p \text{ 相连的败点数量} \leq x. $$于是可以通过类似拓扑排序的方式，求出所有败点：
- 首先把所有满足 $\deg(p) \leq x$ 的点入队，这些点一定是必败无疑的。
- 取出队首，更新与该点相连的点 $v$ 的 $$ \deg(v) - \text{与 } v \text{ 相连的败点数量} $$ 的值，如果小于等于 $x$，则 $v$ 也入队。
显然，上述过程中，所有进入过队列的点就是败点。
最小化 $x$
一个显然的结论是：
$x$ 对应的败点点集是 $x+1$ 对应的败点点集的子集：
所以我们有一个暴力（但对正解有启发性）的方法：
- 首先对 $x = 1$ 做判定；
- 然后对于在 $x = 1$ 的判定过程中没有入队的结点，再看是否满足 $x = 2$ 时的入队条件，若满足则进行 $x = 2$ 的判定；
- 然后对于在 $x = 2$ 的判定过程中没有入队的结点，再看是否满足 $x = 3$ 时的入队条件，若满足则进行 $x = 3$ 的判定；
- 以此类推……
最后只需要记录每个点在 $x$ 等于几时入队，即为该点的答案。
优化
发现上述过程中的入队顺序等价于：
把所有节点扔到以
为关键字排序的小根堆中，每次取出队首并更新相关信息。
时间复杂度为 $O(m \log m)$。
如果把优先队列换成桶，并进行精细实现，可以做到线性复杂度。
K
这题是寒假里做关于 Sparse LPN 的一个定理证明时想到的，USTCPC 赛前听说缺题，突然感觉可以出成妙妙构造题。但是当时事情有点多，因此题面和数据都是 @Grand_Dawn 写的，感谢（
如下是该题的一个等价转换：
命题
设 $n \ge 3(d - 1)$，且 $V \subset \mathbf{F}_2^n$ 是一个维度为 $d$ 的线性子空间。那么，存在一个向量 $\mathbf{x} \in V$，使得其 Hamming weight 满足：
$$ d \le |\mathbf{x}| \le n - d + 1. $$证明
取 $V$ 的一组行最简形式（保证主元对应的列消的只剩下一个 1，可以参考 Menci 的写法）下的线性基 $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_d$。因为每个基向量中至少有 $d-1$ 个 0，所以可以保证每个基向量的 Hamming weight 满足：
$$ |\mathbf{b}_i| \le n - (d - 1) = n - d + 1. $$接下来讨论两种情况：
情况 1：
存在某个 $i$，使得 $|\mathbf{b}_i| \in [d, n - d + 1]$。此时，$\mathbf{b}_i$ 本身即满足结论。
情况 2：
对于所有 $i$，都有 $|\mathbf{b}_i| \in [1, d - 1]$，即每个基向量的 Hamming weight 都小于 $d$。定义如下的前缀和向量：
$$ \mathbf{x}_k = \sum_{j = 1}^{k} \mathbf{b}_j, \quad 1 \le k \le d. $$由于每个 $\mathbf{b}_i$ 的 Hamming weight 小于 $d$，所以相邻两个前缀和向量之间的 Hamming weight 差满足：
$$ \left|\, |\mathbf{x}_k| - |\mathbf{x}_{k-1}| \,\right| \le |\mathbf{b}_k| < d. $$又因为基底是行最简的形式，可以保证 $\mathbf{x}_d$ 至少有 $d$ 个非零位，即：
$$ |\mathbf{x}_d| \ge d, \quad |\mathbf{x}_0| = 0. $$因此，由于 Hamming weight 从 $0$ 增加到至少 $d$，且每一步变化最多为 $d - 1$，根据离散中值定理，存在某个 $k \in [d]$，使得：
$$ |\mathbf{x}_k| \in [d, n - d + 1]. $$所以存在一个满足条件的向量 $\mathbf{x} = \mathbf{x}_k \in V$，证毕。
算法
最终算法就呼之欲出了，先进行高斯消元，随后检查每个向量以及前缀异或和是否满足条件即可，复杂度 $O(\frac{n^3}{w})$。