Codeforces 373 Div2

I haven’t completed the 373Div1 questions yet. . . It feels so difficult. . . Let’s read it before going to bed. . .

There is a problem with question D in Div2 this time. There are only four questions. There were three questions during the competition, so there was only one question I wanted to remember. . .

Title link and Code link

A. Vitya in the Countryside

The meaning of the question is to give the law of a cycle, and then give a number at a certain position in the cycle, and ask whether it can be used to judge whether it is rising or falling based on this information. If it cannot be determined, -1 is output.

**I fell into this. Even if I found out later, I lost a lot of points. . . The so-called extreme of things must be reversed, and it can definitely be judged at the extreme value. **

B. Anatoly and Cockroaches

The meaning of the question is that a string consisting of ‘r’ and ‘b’ is given, and then two operations can be performed, 1. Swap the characters at two positions; 2. Change the character at a certain position. Ask how many minimum operations are required for the final string to be alternating ‘r’’b’.

In the end it’s either rbrbrbr… or brbrbr….

Consider two situations, and then calculate the amount x of r to b, and the amount y of b to r, and the result is min(x,y)+abs(x-y).

C. Efim and Strange Grade

The meaning of the question is to give a decimal with a length of $n(n\leq200000)$, and then carry it up to t times in the decimal place, and ask for the maximum value of the final result. Request canonical output.

If you are greedy, look for the first decimal place that is greater than or equal to 5, and then look for consecutive ones that are greater than or equal to 4 before this 5, and end when you encounter one that is less than 4, because you can no longer advance. Pay attention to some details. . .

I have been thinking about it and writing it for a long time. . . Fortunately there is no fst.

E. Sasha and Array

The meaning of the question is that n numbers and m operations are given. The number at each position is $f[a_i]$, and f[x] represents the x-th term of the Fibonacci sequence. Now there are two situations for each operation. The first one queries the range sum. The second method adds f[x] to each value in the interval.

A very novel question. I found that for each Fibonacci value, the matrix can be quickly raised to the power. Then adding a value to the interval is equivalent to multiplying another matrix in front of the matrix, so build a line segment tree and mark it with lz.

Is this the end? Suddenly I feel like I have nothing to say, but why do I still find it difficult when I do it? . .