AtCoder Grand Contest 003
Title link and Code link
During the comparison, I only did three questions. Later, I felt that question D in this period was possible, and the idea of question E was still amazing. I felt that this kind of question did not rely on any specific algorithm, but relied on thinking to transform the question. Like many of the previous Atcoder questions, it depends on IQ. . . As for question F. . . I understand the structure of the matrix and the correctness of inferring the matrix from the answers, but I feel like I still need to practice how to create the matrix through some recursive relationships = =.
A Wanna go back home
The meaning of the question is that Snuke walks |s| times, each time in four directions, east, west, north, and south, at any distance. The direction of the walk is given, and the question is whether he can return to the original point in the end.
The relative directions must all appear or not appear, so as to ensure that the distance moved in these two directions is 0.
B Simplified mahjong
The meaning of the question is that Snuke has a pile of cards. The numbers on each card are 1~N. There are Ai cards with the number i. The numbers on the two cards that differ by no more than 1 can form a pair. How many pairs can be formed at most.
I had always been WA before, but then I became greedy. If the number i is an even number, then I will form a pair. If it is an odd number, find the last one to form a pair.
C BBuBBblesort!
The meaning of the question is to give N numbers and want to arrange these N numbers in order according to size. There are two exchange methods: 1. Exchange 2 adjacent numbers; 2. Exchange 3 adjacent numbers.
Ask how many operations 1 must be used at least to make the numbers in order.
It can be found that after sorting these N numbers, if the difference between the position before sorting and the position after sorting a number is an even number, then it can be achieved through operation 2, but if it is an odd number, there is no other way. To reach this state, it must be achieved through operation 1.
D Anticube
The meaning of the question is to give N numbers and find a set. The multiplication of two numbers in the set is not a cubic number. Ask for the maximum number of elements in the set.
In fact, the problem later became how to decompose the number, which has always been TLE.
The numbers are at the 10^10 level. After filtering the 10^3 level factors, only p, pq, and p^2 are left. Consider how to process them. In addition, the p^2 form also needs to pay attention to the accuracy issue.
What remains is a matter of which of the two is greater.
E Sequential operations on Sequence
The meaning of the question is that there is currently a sequence 1…N, with Q operations. In each operation, the sequence is repeatedly replaced by the first Qi numbers of the original sequence. Ask the number of occurrences of each element in the final sequence.
Able to discover patterns, if Qi>Q(i+1), then the previous Qi is meaningless.
This will turn all operations into an increasing sequence.
It is still found that elements with small numbers must appear more frequently than elements with large numbers, so the final problem is to consider using the suffix sum. Then think from back to front and mark the last element as 1, that is, all elements are 1.
Each operation from back to front is equivalent to a folding. Consider where the contributions of the subsequent positions are respectively contributed. If the position pos>Qi, then you will find that the value at the Qi position += (pos/Qi)*(the value of the pos), the value at the pos%Qi position +=pos%Qi.
It seems difficult to summarize a systematic solution to this kind of problem. Every time I encounter it, I rely on experts to ask if there are any similar problems. . . ?
F Fraction of Fractal
The meaning of the question is h*w square grid, each grid is either a white dot or a black dot. All these black spots are connected in four directions: up, down, left and right.
Now give the method to find the k-th level picture. The k-th level picture comes from the k-1th level picture. If the position is a white point, the position is replaced with the white point of h*w; if it is a black point, the position is replaced with the original picture.
Ask how many connected blocks the black dots in the k-th graph are.
First filter out other simple conditions. If the graph can be connected to the left, right, top and bottom, then the final result will be 1 no matter how big k is.
If the picture cannot be connected to the left, right, top and bottom, then the final result is the number of black points a^(k-1).
Now we only consider the situation where one side is connected and the other side is not. For example, the left and right are connected, but the up and down are not connected.
Now the number of black points in this picture is a, the number of pairs of points connected to the left and right is b, and the number of pairs of black points on the leftmost and rightmost edges of the boundary is c.
Okay, now assuming that you already know how many connected blocks there are in the k-1th layer, set to x, and the number of y connections in the k-1th layer, then how to deduce the kth layer?
First x*a, this does not consider the connection situation at all. Assume that each connected block will be split into a, then the total is x*a, and then subtract x*b. This b block is not the number of newly generated connected blocks. It is subtracted and is generated internally.
The following y is the number of connections in the previous round. If it was connected in the previous round, each pair of y is split and there will be a pair of c pairs that are newly generated connected blocks. This is a new external connection.
Summarized in this way, we can get a matrix,
$$
{\begin{pmatrix}
a&-b\
0&c
\end{pmatrix}}^{k-1}
{\begin{pmatrix}
1\
1
\end{pmatrix}}
$$
It was very messy, and I went to the forum to ask, and found that what was discussed was not much different from what I thought at the beginning. I gave you a [link] (https://async.icpc-camp.org/d/545-atcoder-grand-contest-003-f-fraction-of-fractal) for reference.