D
给定 $n,D_1,D_2$ ,要求构造一个在 $2n\times 2n$ 的网格中选出 $n^2$ 个点的方案，是任意两点间距离不为 $\sqrt{D_1}$ 或 $\sqrt{D_2}$
由题有 $|X|=4\times N^2$ ，要求 $|S|=N^2$ ，即，需要找到 $\frac{1}{4}$ 的点
容易想到当需要 $\frac{1}{2}$ 的点时，(即只有一个禁止距离时，$|S|=2\times N^2$) ，此时用二分图恰好达到目的
即：对于 $A,B\in X$ ，若 $|AB|=\sqrt{D}$ 则连接 $AB$ ，最后得到图 $G$ ，要求 $G$ 独立集且包含至少一半的节点，显然这是二分图
考虑图 $G$ 是否为二分图(考虑到欧几里得距离涉及到平方和，从数论角度)：
设 $|AB|^2=4^k\times D$ ，只考虑 $\mod 2^k$:
$D\equiv 1\pmod{2}$
此时 $|AB|^2\equiv (A_x+A_y)+(B_x+B_y)\pmod{2}$ ，则 $A_x+A_y\not\equiv B_x+B_y\pmod{2}$ ，则，按照 $x+y$ 的奇偶性分为两组，有边相连的二点必定在不同组中，满足二分图
$D\equiv 2\pmod{4}$
同上易得 $A_x-B_x\equiv 1\pmod{2} \wedge A_y-B_y\equiv \pmod{2}$ ，即 $A_x\not\equiv B_x\pmod{2}$ ，则，按照 $x$ 的奇偶性分组也满足二分图
$D\equiv 0\pmod{4}$
同时易得 $A_x\equiv B_x\pmod{2}\wedge A_y\equiv B_y\pmod{2}$ ，此时按照 $(x\mod 2,y\mod 2)$ 分为四个等价类，有边相连的点一定在同一个里面，对一个等价类，缩放为 $\frac{x}{2},\frac{y}{2},\frac{D}{4}$ ，归纳结论成立
再考虑两个距离：自由组合即可，即，独立考虑两种颜色，进行不同染色方式
1 | const int N=610; |
E
给出 $n$ 节点的树和 $m$ 条树上路径，为每一路径定向，第 $i$ 条边 $(a_i,b_i)$ 的权值为：同时被某两条路径沿 $a_i\rightarrow b_i,b_i\rightarrow a_i$ 经过的条数，求最大权值和及定向方案
这是一个阴间构造题：
设经过每条边的路径数 $c_e$ ，则答案上界 $\sum_{\min\{2,c_e\}}$
归纳法证明：
- $n=1$ 显然成立
- $n>1$ ，设与叶子 $v$ 相连的边 $e$ ,点为 $w$
- $c_e=0$ 直接删去 $v$
- $c_e=1$ 将路径 $(v,x)$ 替换为 $(w,x)$
- $c_e>1$ 任意选择两条路径 $(v,a),(v,b)$ ，设两路径的交 $(v,c)$ ,那么 $v\rightarrow c$ 的所有边贡献都为 $2$ ，剩下的路径等价表示为 $(a,b)$
执行到最后一个点即可
1 | const int N=2e3+100; |
F
给出长度为 $n$ 的二进制数 $x$ 和长度 $m$ 的 $y$ ，进行 $k$ 次操作：设 $z=x\And y，x+=z,y+=z$ ，求出操作后的 $x,y$
暴力模拟啊嗯
从高位到低位每位重复模拟 $k$ 遍处理：
考虑 $(1,1)$ 进位时：
遇到两个数同一位不相同的情况 $(0,1),(1,0)$ 则暴力进位
而遇到连续的一段 $(0,0)$ 可以直接移过去，
栈维护下标从大到小(当前位置)的 $(0,1),(1,0)$
1 | const int N=2e6+100; |