题解 - [Atcoder ABC 126] (C - F)
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
1 | 3 10 |
Sample Output 1
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
1 | 100000 5 |
Sample Output 2
1 | 0.999973749998 |
解题思路
式子还蛮好推的，照着做就行
就是注意下精度，本题要求到 1e-9
当然搞整除分块也不是不可以
代码参考
Show code
1 | /* |
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&w_2\\ \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
1 | 3 |
Sample Output 1
1 | 0 |
Sample Input 2
1 | 5 |
Sample Output 2
1 | 1 |
解题思路
如果边权为偶数，则两端点同色；如果边权为奇数，则两端点异色
代码参考
Show code
1 | /* |
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_{X_i}+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
1 | 3 1 |
Sample Output 1
1 | 2 |
You can determine all of \(A_1,A_2,A_3\) by using the magic for the first and third cards.
Sample Input 2
1 | 6 5 |
Sample Output 2
1 | 2 |
Sample Input 3
1 | 100000 1 |
Sample Output 3
1 | 99999 |
解题思路
一眼并查集，没啥好说的
代码参考
Show code
1 | /* |
F - XOR Matching
Problem Statement
Construct a sequence \(a= \{a_1, a_2, ..., 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 \(a_i\ xor\ a_{i+1}\ xor\ ...\ xor\ a_j=K\) holds.
What is xor (bitwise exclusive or)?
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.)
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 | 1 0 |
Sample Output 1
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 1 |
Sample Output 2
1 | -1 |
No sequence satisfies the condition.
Sample Input 3
1 | 5 58 |
Sample Output 3
1 | -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
代码参考
Show code
1 | /* |