Hello everyone~ I am Tommy from Shanghai Jiaotong University. I am very happy to participate in the relevant proposition work of this CCPC regional competition. The lecture video at the closing ceremony was too sloppy (the preparation time was too short), so here are the solutions to all the questions. (and some backstory)

gym link : https://codeforces.com/gym/102832

It seems that there are repeated circles in the data of question J, and the validator is wrong, I apologize to the affected players TAT...

Some questions and solutions have not been written yet, so I will make up tonight~

Problem A Krypton

It can be found that except for the first deposit reward, the ratio of the remaining RMB to coupons is 1:10, so we only need to consider how much first deposit reward we can get at most.

Just enumerate all cases directly and violently, time complexity$O(2^7)$O(2^7).

It should be noted that this question cannot be greedy. (6+28+88+198+328 is better than 648)

Problem B The Tortoise and the Hare

Each time the rabbit will choose the closest$k$kOnly turtles interfere, in fact, this is the best choice.

We consider how to do a query, we divide the answer in two$t$t, then the total number of curses needed is$\sum_{i=L}^Rmax(a_i+t-(m-1),0)$\sum_{i=L}^Rmax(a_i+t-(m-1),0), and the total number of curses is$t*k$t*k,therefore$\sum_{i=L}^Rmax(a_i+t-(m-1),0) \leq t*k$\sum_{i=L}^Rmax(a_i+t-(m-1),0) \leq t*k

This problem can be transformed into using the weight line segment tree to cover the interval balance tree. We can divide the weight line segment tree into two, count the number of weights and the sum of the weights, find the corresponding point, disassemble max, and calculate The answer will do.

time complexity$O(n\log^2n)$O(n\log^2n), the space complexity$O(n\log n)$O(n\log n).

The practice of AC players on the field seems to be a clever division. (It seems that I am not very good at TAT)

Problem C Quantum Geometry

In this question, we need to understand what is called "quantum" geometry. At the beginning, a person can only see a wall, but he can decide his own route based on the current field of vision information.

Divided into two situations:

The first is that the wall you see does not block the end point, so just walk over it.

The second is the wall seen$AB$ABBlock the end point, then the first step must be from the starting point$S$SGo to a certain endpoint, may wish to set to go to$A$A.

go to$A$AThen there are two cases, the first is$A$Ago to$B$Bthen go to the end$T$T, the second is$A$Ago to the third point$C$Cthen go to the end$T$T. (Also a possibility$AC$ACwith$BC$BCnot blocked$A$Aarrive$T$Troute, just go directly)

In the second case, if$AC$ACwith$BC$BCblocked$A$Aarrive$T$Troute, then$C$Cmust be$AS$ASreverse extension cord and$ST$STIn the interval of , this area is related to$B$Bnothing to do$O(n^2)$O(n^2)preprocessing.

time complexity$O(n^2+q)$O(n^2+q).

Problem D Meaningless Sequence

Easy to find$a_n=c^{popcount(n)}$a_n=c^{popcount(n)}

Enumerate a fixed prefix, considering the number of schemes filled in the second half of the current situation arbitrarily.

Suppose the length of the second half is$L$L, then there is$k$kThe number of schemes of 1 is$C_L^k$C_L^k, to count the contribution to the answer.

time complexity$O(Len^2)$O(Len^2)

Problem E Defense of Valor League

Consider blasting. The time complexity is$O(n\cdot n!)$O(n\cdot n!), difficult to pass.

Notice that after making a decision, the order of the previous BP does not matter, it is only related to the set of heroes selected, so the number of essentially different situations is only about 900,000, and the memory search can pass.

Memorized search for this question needs to be implemented carefully: one detail is that the number of different options for heroes to choose is actually very small, and the value of all situations can be pre-processed.

Since this question guarantees a large input randomness, game search ALPHA-BETA optimal pruning can be considered.

Problem F Strange Memory

To be done

Problem G Monkey's Keyboard

To be done

Problem H Combination Lock

Each operation will change the parity of the sum of all current numbers, so the whole graph is a bipartite graph.

Alice wins currently only if the starting point is on any one of the largest matches. We only need to run the maximum matching of the bipartite graph first, then delete the starting point and run the maximum matching of the bipartite graph again, and judge whether the two answers are the same.

Both Hopcroft-Karp and Dinic can pass this question.

Problem I Kawaii Courier

set slave point$u$udepart, pass by exactly$k$kThe probability of reaching point 1 after one step is$p[u][k]$p[u][k].

Assume$A[u]=\sum_{i=0}^{+\infty}p[u][i]\cdot x^i$A[u]=\sum_{i=0}^{+\infty}p[u][i]\cdot x^i ,$B[u]=\sum_{i=0}^{+\infty}p[u][i]\cdot i \cdot x^i$B[u]=\sum_{i=0}^{+\infty}p[u][i]\cdot i \cdot x^i ,$d[u]$d[u] represents a point$u$degree of u .

array$B$B is what you want.

easy to spot,$A[1]=1$A[1]=1 ,$B[1]=0$B[1]=0 .

next consider$u\neq 1$In the case of u\neq 1 ,

$A[u]=\sum_{i=0}^{+\infty}p[u][i]\cdot x^i=\sum_{i=1}^{+\infty}p[u][i]\cdot x^i=\sum_{i=1}^{+\infty}x^i\cdot\frac{1}{d[u]}\sum_{v}p[v][i-1]$A[u]=\sum_{i=0}^{+\infty}p[u][i]\cdot x^i=\sum_{i=1}^{+\infty}p[u][i ]\cdot x^i=\sum_{i=1}^{+\infty}x^i\cdot\frac{1}{d[u]}\sum_{v}p[v][i-1]

$=\frac{x}{d[u]}\sum_{v}\sum_{i=1}^{+\infty}p[v][i-1]\cdot x^{i-1}=\frac{x}{d[u]}\sum_{v}\sum_{i=0}^{+\infty}p[v][i]\cdot x^i=\frac{x}{d[u]}\sum_{v}A[v]$=\frac{x}{d[u]}\sum_{v}\sum_{i=1}^{+\infty}p[v][i-1]\cdot x^{i-1}=\ frac{x}{d[u]}\sum_{v}\sum_{i=0}^{+\infty}p[v][i]\cdot x^i=\frac{x}{d[u ]}\sum_{v}A[v]

$B[u]=\sum_{i=0}^{+\infty}p[u][i]\cdot i \cdot x^i=\sum_{i=1}^{+\infty}p[u][i]\cdot i \cdot x^i=\sum_{i=1}^{+\infty}i\cdot x^i\cdot \frac{1}{d[u]}\cdot\sum_{v}p[v][i-1]$B[u]=\sum_{i=0}^{+\infty}p[u][i]\cdot i \cdot x^i=\sum_{i=1}^{+\infty}p[u ][i]\cdot i \cdot x^i=\sum_{i=1}^{+\infty}i\cdot x^i\cdot \frac{1}{d[u]}\cdot\sum_{ v}p[v][i-1]

$=\frac{x}{d[u]}\sum_{i=0}^{+\infty}(i+1)\cdot x^i\cdot\sum_{v}p[v][i]=\frac{x}{d[u]}\sum_{v}(\sum_{i=0}^{\infty}i\cdot x^i\cdot p[v][i]+\sum_{i=0}^{\infty}x^i\cdot p[v][i])$=\frac{x}{d[u]}\sum_{i=0}^{+\infty}(i+1)\cdot x^i\cdot\sum_{v}p[v][i]= \frac{x}{d[u]}\sum_{v}(\sum_{i=0}^{\infty}i\cdot x^i\cdot p[v][i]+\sum_{i= 0}^{\infty}x^i\cdot p[v][i])

$=\frac{x}{d[u]}\sum_{v}(A[v]+B[v])$=\frac{x}{d[u]}\sum_{v}(A[v]+B[v])

In the formula$v$v with$u$u adjacent.

Find all by DFS$A$A array, and then use DFS to find all$B$The B array is enough.

time complexity$O(n\log n)$O(n\log n)

Problem J Abstract Painting

Considering DP, let$f[i][S]$f[i][S] indicates that the current transfer to the$i$i position, the$i+1$i+1 position to the$i+10$Whether there is already a closing parenthesis at i+10 positions.

On each transfer, brute-force enumerates the$i$Closing parentheses at i positions (a total of$2^5$2^5 types), to judge whether it is with$S$S contradicts, and then transfer directly.

time complexity$O(2^{15}*n)$O(2^{15}*n)

Problem K Ragdoll

Consider the equation first$x\oplus y=gcd(x,y)$x\oplus y=gcd(x,y) , since$x \oplus y \geq |x-y| \geq gcd(x,y)$x \oplus y \geq |xy| \geq gcd(x,y) , so both inequality signs must be taken at the same time. In particular,$|x-y|=gcd(x,y)$|xy|=gcd(x,y) . violent enumeration$gcd(x,y)$gcd(x,y) and$x$x , judging$(x,y)$(x, y) is true. Preprocess all such pairs, time complexity$O(n\ln n)$O(n\ln n)

At the same time, it can be found that the number of occurrences of the same number in all pairs of numbers does not exceed$c$c times. ($c \approx 60$c \approx 60 ) so direct heuristic merge and update the answer from time to time.

time complexity$O(cn\log n)$O(cn\log n)

Problem L Coordinate Paper

can be found, as long as it is determined$a_1$a_1 , you can determine$(\sum_{i=1}^na_i) \bmod (k+1)$(\sum_{i=1}^na_i) The result of \bmod (k+1).

We violently enumerate$a_1 \bmod (k+1)$a_1 \bmod (k+1) , then$\sum_{i=1}^na_i$The minimum value of \sum_{i=1}^na_i can be in$O(1)$The result is calculated in O(1) time complexity. We assert that only$S \geq min \sum_{i=1}^na_i$S \geq min \sum_{i=1}^na_i and$S \bmod (k+1) = (\sum_{i=1}^na_i) \bmod (k+1)$S \bmod (k+1) = (\sum_{i=1}^na_i) \bmod (k+1) must have a solution, which can be found in$O(k)$Find a valid one in O(k) time complexity$a_1 \bmod (k+1)$a_1 \bmod (k+1) .

Consider it$a_1 \bmod (k+1)$The minimum value of the sum after a_1 \bmod (k+1) is taken as$a_1 \bmod (k+1),(a_1+1) \bmod (k+1),...,(a_1+(n-1))\bmod (k+1)$a_1 \bmod (k+1),(a_1+1) \bmod (k+1),...,(a_1+(n-1))\bmod (k+1) .

Next, consider how to make the answer bigger, we can first put$0$0 becomes$k+1$k+1 ; if$0$0 can be used up$1$1 becomes$k+2$k+2 ... and thus the final sum$S$S. _

time complexity$O(n+k)$O(n+k) .

Teams that don't pass can try$n=4, k=5, S=8$Whether n=4, k=5, S=8 can construct a solution, many teams WA is at this test point.

(in fact the original$L$Question L is not this question, but it collided with a question of csp on Saturday, so I decided to change it temporarily)