---
tags: Programming Contest
---

# AtCoder Beginner Contest 126 題解

## 心得

練習

## A, B, C

ʕ•͡ᴥ•ʔ

## D. [Even Relation](https://atcoder.jp/contests/abc126/tasks/abc126_d)

從節點 0 開始 DFS，遇到長度為奇數的邊，就變色；偶數的邊，顏色不變。

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append((v, w))
    G[v].append((u, w))

color = [-1 for _ in range(N)]
color[0] = 0
stack = [(0, -1)]
while len(stack) > 0:
    u, p = stack.pop()
    for (v, w) in G[u]:
        if v != p:
            color[v] = (color[u] + w % 2) % 2
            stack.append((v, u))

print('\n'.join(map(str, color)))

## E. [1 or 2](https://atcoder.jp/contests/abc126/tasks/abc126_e)

把這些卡片與 x, y 關係畫成 graph，就會發現所以等價這個 graph 中有幾個連通單元，因為每個連通單元都只需要使用一次 magic 來確定其中一個節點的奇偶性，該單元中其他節點的奇偶性就可以推出來了。實作使用 Disjoint set。

class DisjointSet:
    def __init__(self, N):
        self.par = [-1] * N
        self.sz = [1] * N

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return None, None
        if self.sz[a] > self.sz[b]:
            a, b = b, a
        self.par[a] = b
        self.sz[b] += self.sz[a]
        return a, b  # tree a merges into tree b

    def same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, x):
        return self.sz[self.root(x)]

N, M = map(int, input().split())
disjoint = DisjointSet(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    x, y = x - 1, y - 1
    disjoint.unite(x, y)

roots = set([disjoint.root(i) for i in range(N)])
print(len(roots))

## F. [XOR Matching](https://atcoder.jp/contests/abc126/tasks/abc126_f)

$K > 2 ^ M$ 的情況是不可能組出來的，xor 無法從 $0, 1, \cdots, 2 ^ M - 1$ 組出比 $2^M - 1$ 還大的數字。

建構的方法為：$[2^M - 1, \cdots, 2, 1, 0, K, 0, 1, 2, \cdots, 2^M - 1, K]$，利用 xor 滿足交換律的特性，將 $K$ 擺在最中間，然後在左邊與右邊對稱填入數字，最後再補一個 $K$ 在最右邊。

兩個 $K$ 之間的數字 xor 起來也會是 $K$：

$$
\begin{align}
&0 \oplus 1 \oplus \cdots \oplus (K - 1) \oplus (K + 1) \oplus \cdots \oplus (2^M - 1 )
\\
&=0 \oplus 1 \oplus 2 \oplus 3 \oplus \cdots \oplus (2^M - 1) \oplus K
\\
&=(0 \oplus 1) \oplus (2 \oplus 3) \cdots \oplus ((2^M - 2) \oplus (2^M - 1)) \oplus K
\\
&= \underbrace{1 \oplus 1 \oplus \cdots \oplus 1}_{2^{M-1}\text{個 = 偶數個}} \oplus K
\\
&= 0 \oplus K
\\
&= K
\end{align}
$$

$2^{M-1}$ 是偶數的推論僅當 $M > 1$ 時成立，所以 $M = 1$ 時要特別處理。

from collections import deque


def solve():
    M, K = map(int, input().split())

    if M == 1:
        if K != 0:
            return '-1'
        return '0 0 1 1'

    if K >= pow(2, M):
        return '-1'

    A = deque([K])
    for val in range(2 ** M):
        if val != K:
            A.append(val)
            A.appendleft(val)
    A.append(K)
    
    return ' '.join(map(str, A))

print(solve())

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::