Codeforces 372 Div2
Title link and Code link
This time, I gained a lot from the two points of question D. It was my first time to do the tree divide and conquer of question E.
A. Crazy Computer
The meaning of the question is to give a sequence. When the difference before and after is greater than $C$, the result is cleared, otherwise +1, and the final result is asked.
B. Complete the Word
Given a string, find a substring containing 26 non-repeating letters, where ? can be replaced with any character.
C. Plus and Square Root
The meaning of the question is a game. The current number is $x$. You can add any multiple of $x$ on the basis of $x$, so that at the first $k$, etc., what you want to become is a perfect square number, and after taking the root sign, it can be divisible by $k+1$.
In each round, $k*k*(k+1)*(k+1)$ is constructed, so that after opening the root number, it becomes $k*(k+1)$, which can be divisible by $k$. Then in the next round, because of the factor $k+1$, you can continue to construct $(k+1)*(k+1)*(k+2)*(k+2)$.
D. Complete The Graph
The meaning of the question is that given a graph, the edge with a weight of 0 can be arbitrarily assigned a value greater than 0, and the shortest distance from $s$ to $t$ is required to be a fixed length $L$.
Seeing that this question can finally be solved in two parts, I really bowed down.
Divide the sum of all edges with a value of 0 into two parts. First, if they are all 0, then the shortest path is greater than the GG of $L$. They are all maximum values, and the shortest path is smaller than GG of $L$. The rest will be found to be equivalent to the length of the bisection on a certain side, and Dijkstra finds the shortest path.
E. Digit Tree
The meaning of the question is that given a tree, each edge has a number from 0 to 9, and then given a $M$, it satisfies $gcd(M,10)=1$. Now every two points on the tree can get a value $\sum_{i=1}^{k-1}d_{i}*10^{k-1-i}$ through the edge. Ask how many pairs of any two points on the tree can be divisible by M.
To divide and conquer a tree, first find the center of gravity, and then consider how many pairs there are that pass through the center of gravity.
Assume that the value of point u through deep search is 123, that is, when the center of gravity is the root, the depth is 3. Another point v has a value of 45 and a depth of 2. Then we can know that the values of the point pair formed by u and v are 12354 and 45321. Then assume that $A$ represents the value calculated from the root node, like 123, 45 obtained above, and $B$ represents the value obtained from the deep search of each node of the root node, like 321, 54. Then the condition for being divisible by M is,
$$
A_u\times 10^{d_{v}}+B_v\equiv 0\ mod\ m
$$
Just push it over
$$
A_u\equiv -B_v \times \frac{1}{10^{d_v}}\ mod\ m
$$
In this way, you will know what to record when searching deeply, and then use the center of gravity as the root, search twice before and after, and record the number of point pairs that pass through that point, and then continue to find the center of gravity and divide and conquer the solution.