仓库源文，站点原文

title: "题解 - [Atcoder ABC 126] (C - F)" categories:

算法竞赛
题解 tags:
算法竞赛
题解
AtCoder
数学
概率
期望
搜索
DFS
并查集
思维
构造
位运算
异或 date: 2021-02-02 12:06:09

C - Dice and Coin

Problem Statement

Snuke has a fair $N$-sided die that shows the integers from $1$ to $N$ with equal probability and a fair coin. He will play the following game with them:

Throw the die. The current score is the result of the die.
As long as the score is between $1$ and $K-1$ (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes $0$ if the coin lands tails up.
The game ends when the score becomes $0$ or becomes $K$ or above. Snuke wins if the score is K or above, and loses if the score is $0$.

You are given $N$ and $K$. Find the probability that Snuke wins the game.

Constraints

$1≤N≤10^5$
$1≤K≤10^5$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N\ K$

Output

Print the probability that Snuke wins the game. The output is considered correct when the absolute or relative error is at most $10^{-9}$.

Sample Input 1

3 10

Sample Output 1

0.145833333333

If the die shows $1$, Snuke needs to get four consecutive heads from four coin flips to obtain a score of 10 or above. The probability of this happening is $\frac{1}{3}×(\frac{1}{2})^4=\frac{1}{48}$.
If the die shows $2$, Snuke needs to get three consecutive heads from three coin flips to obtain a score of 10 or above. The probability of this happening is $\frac{1}{3}×(\frac{1}{2})^3=\frac{1}{24}$.
If the die shows $3$, Snuke needs to get two consecutive heads from two coin flips to obtain a score of 10 or above. The probability of this happening is $\frac{1}{3}×(\frac{1}{2})^2=\frac{1}{12}$.

Thus, the probability that Snuke wins is $\frac{1}{48}+\frac{1}{24}+\frac{1}{12}=\frac{7}{48}≃0.1458333333$.

Sample Input 2

100000 5

Sample Output 2

0.999973749998

解题思路

式子还蛮好推的, 照着做就行

就是注意下精度, 本题要求到 1e-9

当然搞整除分块也不是不可以

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_abc126_c AtCoder/abc126_c/0.cpp %} </details>

D - Even Relation

Problem Statement

We have a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge in the tree connects Vertex ui and Vertex $v_i$, and its length is $w_i$. Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

For any two vertices painted in the same color, the distance between them is an even number.

Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

All values in input are integers.
$1≤N≤10^5$
$1≤u_i<v_i≤N$
$1≤w_i≤10^9$

Input

Input is given from Standard Input in the following format:

$\begin{matrix} N\ u_1&v_1&w_1\ u_2&v_2&w2\ \vdots\ u{N-1}&v{N-1}&w{N-1} \end{matrix}$

Output

Print a coloring of the vertices that satisfies the condition, in $N$ lines. The $i$-th line should contain $0$ if Vertex $i$ is painted white and $1$ if it is painted black.

If there are multiple colorings that satisfy the condition, any of them will be accepted.

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

Sample Output 2

解题思路

如果边权为偶数, 则两端点同色; 如果边权为奇数, 则两端点异色

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_abc126_d AtCoder/abc126_d/0.cpp %} </details>

E - 1 or 2

Problem Statement

There are $N$ cards placed face down in a row. On each card, an integer $1$ or $2$ is written.

Let $A_i$ be the integer written on the $i$-th card.

Your objective is to guess $A_1,A_2,...,A_N$ correctly.

You know the following facts:

For each $i=1,2,...,M$, the value $A_{Xi}+A{Y_i}+Z_i$ is an even number.

You are a magician and can use the following magic any number of times:

Magic: Choose one card and know the integer $A_i$ written on it. The cost of using this magic is $1$.

What is the minimum cost required to determine all of $A_1,A_2,...,A_N$?

It is guaranteed that there is no contradiction in given input.

Constraints

All values in input are integers.
$2≤N≤10^5$
$1≤M≤10^5$
$1≤X_i<Y_i≤N$
$1≤Z_i≤100$
The pairs $(X_i,Y_i)$ are distinct.
There is no contradiction in input. (That is, there exist integers $A_1,A_2,...,A_N$ that satisfy the conditions.)

Input

Input is given from Standard Input in the following format:

$\begin{matrix} N&M\ X_1&Y_1&Z_1\ X_2&Y_2&Z_2\ \vdots\ X_M&Y_M&Z_M \end{matrix}$

Output

Print the minimum total cost required to determine all of $A_1,A_2,...,A_N$.

Sample Input 1

3 1
1 2 1

Sample Output 1

You can determine all of $A_1,A_2,A_3$ by using the magic for the first and third cards.

Sample Input 2

Sample Output 2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

解题思路

一眼并查集, 没啥好说的

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_abc126_e AtCoder/abc126_e/0.cpp %} </details>

F - XOR Matching

Problem Statement

Construct a sequence $a= {a_1, a2, ..., a{2^{M+1}}}$ of length $2^{M+1}$ that satisfies the following conditions, if such a sequence exists.

Each integer between $0$ and $2^M-1$ (inclusive) occurs twice in $a$.
For any $i$ and $j$ ($i<j$) such that $a_i=a_j$, the formula $ai\ xor\ a{i+1}\ xor\ ...\ xor\ a_j=K$ holds.

<details open> <summary>What is xor (bitwise exclusive or)?</summary> The xor of integers $c_1,c_2,...,c_n$ is defined as follows: - When $c_1\ xor\ c_2\ xor\ ...\ xor\ c_n$ is written in base two, the digit in the $2^k$'s place ($k≥0$) is 1 if the number of integers among $c_1,c_2,...c_m$ whose binary representations have $1$ in the $2^k$'s place is odd, and $0$ if that count is even. For example, $3\ xor\ 5=6$. (If we write it in base two: `011` $xor$ `101` = `110`.) </details>

Constraints

All values in input are integers.
$0≤M≤17$
$0≤K≤10^9$

Input

Input is given from Standard Input in the following format:

$M\ K$

Output

If there is no sequence $a$ that satisfies the condition, print -1.

If there exists such a sequence $a$, print the elements of one such sequence $a$ with spaces in between.

If there are multiple sequences that satisfies the condition, any of them will be accepted.

Sample Input 1

1 0

Sample Output 1

0 0 1 1

For this case, there are multiple sequences that satisfy the condition.

For example, when $a = {0,0,1,1}$, there are two pairs $(i, j) (i<j)$ such that $a_i=a_j$: $(1,2)$ and $(3,4)$. Since $a_1\ xor\ a_2=0$ and $a_3\ xor\ a_4=0$, this sequence $a$ satisfies the condition.

Sample Input 2

1 1

Sample Output 2

-1

No sequence satisfies the condition.

Sample Input 3

5 58

Sample Output 3

-1

No sequence satisfies the condition.

解题思路

首先我们注意到

$$ \forall k\in\mathbb{N}^+,\bigoplus_{i=0}^{2^k-1}i=0 $$

用数学归纳法证明即可, 或者考虑 Sierpinski 三角形

其次我们知道异或的逆运算是异或, 所以我们可以这样构造:

若 $K\geqslant 2^M$, 则一定无解
若 $M=1$, 则 $K=0$ 有解, $K=1$ 无解
其余情况我们可以这样构造

0 1 ... K-1 K+1 ... 2^M-2 2^M-1 K 2^M-1 2^M-2 ... K+1 K-1 ... 1 0 K

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_abc126_f AtCoder/abc126_f/0.cpp %} </details>