AtCoder Beginner Contest 126 题解
AC Codes
A – Changing a Character
B – YYMM or MMYY
C – Dice and Coin
D – Even Relation
给定一棵 $N$ 个点的树，每条边 $(u_i,v_i)$ 都有边权 $w_i$ ，你需要对树上每个点进行黑白染色，使得：
- 任意两个相邻同色点之间的边权为偶数。
$N\leq 10^5$ 。
由于只有偶数边会限制构造方案，所以我们只对偶数边建图，建完图后一定是一堆连通块，dfs二染色即可。
E – 1 or 2
$N$ 张卡片背面朝上放在桌上，每张卡片的正面有一个权值 $A_i(A_i=1,2)$ ，已知 $M$ 个条件：
- 对于任意的 $i\in [1,M]$ ，$A_{X_i}+A_{Y_i}+Z$ 是一个偶数。
现在你有一种魔法：每次花费 $1$ 元，得知 $A_i$ 的权值，询问最少需要几元得知所有卡片的权值。保证有解。
$N,M\leq 10^5$ 。
对于所有的 $(X_i,Y_i)$ 建边后，显然会形成一系列连通块，由于保证有解，所以对于每个连通块显然只需要进行一次查询。
F – XOR Matching
构造一个长度为 $2^{M+1}$ 的数列 $A$ ，要求满足：
- 数列由 $\{0,0,1,1,2,2,\ldots,2^{M-1}-1,2^{M-1}-1\}$ 这些元素构成。
- 对于任意一对满足 $A_i=A_j$ 的 $(i,j)$，满足：$A_i \oplus A_{i+1}\oplus \cdots \oplus A_j = K$。
如果不存在则输出 $-1$ 。
首先，容易观察出以下结论：
- 如果 $K=0$ ，那么只需要构造 $\{0,0,1,1,2,2,\ldots,2^{M-1}-1,2^{M-1}-1\}$ 即可。
- 如果 $K \gt 2^{M-1}$ ，那么无解。
最后剩下一种情况：$K\in[1,2^{M-1}]$ ，这个可以从一个经典结论入手当 $n\equiv 0\pmod 4$ 时 $1\oplus 2\oplus 3\oplus \cdots n = 0$ 。因此我们不妨构造：
$$\{0,1,2,\ldots,K-1,K+1,\ldots,2^{M-1}-1,K,2^{M-1}-1,\ldots, K+1,K-1,\ldots,2,1,0,K\}$$
这是因为 $0\oplus 1\oplus 2\oplus \cdots K-1\oplus K+1\oplus 2^{M-1}-1 = 0\oplus 1\oplus2\oplus \cdots\oplus2^{M-1}-1\oplus K = K$ 。注意这个等式只在 $M>2$ 时成立，否则无解。