Codeforces 371
Title link and Code link
I saw that Div1 this time had three 2000 values (instead of 2500), and I saw Sister Cha posted [Problem Solution] (https://async.icpc-camp.org/d/555-codeforces-round-371) on the forum, and somehow I wanted to do it myself. . .
Div2A Meeting of Old Friends
The meaning of the question is to give two intervals and find the length of the intersection interval. If k is in the intersection, then the result is subtracted by 1.
Div2B Filya and Homework
The meaning of the question is that given n numbers, you can now add x to some numbers (which can be 0), or you can subtract x from some numbers, and ask whether the final values are equal.
Analysis shows that if the values of n numbers are less than three, then it is definitely possible. If it is equal to three types, an arithmetic sequence should be formed. If there are more than three types, then it is impossible.
DIV1A Sonya and Queries
The purpose of the question is to give a matching method, give a string of 01, and match the numbers from right to left. If it is 0, the position is required to be an even number; if it is 1, the position is required to be an odd number.
There are three operations each time, 1. Add a number to the set. 2. Delete a number from the set. 3. Given a 01 string, ask how many numbers in the set match the match.
Because this 01 string has a maximum of 18 digits, just open an array of 1<<18 and violently record it.
DIV1B Searching Rectangles
Interaction question, the meaning of the question is that there are two rectangles on the grid of n*n(2<=n<=2^16), and the two rectangles do not overlap. Now I ask you to find the positions of these two rectangles.
Every time you can ask for a rectangle, it will answer you how many rectangles are inside it that are completely inside it (0<=res<=2).
First bisect the x that separates the two rectangles on the horizontal axis. If it does not exist, find y.
Then find the four sides inside the divided rectangle.
The code written by Sister Ticha is really cool. . .
DIV1C Sonya and Problem Wihtout a Legend
The meaning of the question is to give a sequence of length n, you can add or subtract a number to each number, transform it into an increasing sequence, and ask for the minimum cost.
They all said that this question was a bad one, but I have never done it. . . POJ 3666,CF Round13 C
If increment is required first, then A[i]-=i, then sort A[i] and assume it is B[i].
Then if the data is 3000, the DP of O(n^2) can also be passed. DP[i][j] means that the first i numbers become monotonically increasing, and the last number is the minimum cost of B[j]. To put it bluntly, it means violently treating each number as the median of a range and considering its cost (the subsequent left-skewed tree is also based on this optimization). Because if this sequence is monotonically increasing, then the cost is 0. Monotonically decreasing, then the cost is the sum of each number - the median.
Therefore, the transfer equation can be obtained as
$$
dp[i][j]=min(dp[i-1][k])+|A[i]-B[j]| (k\leq i)
$$
The O(nlogn) method is to use a left-skewed tree. There is a special paper, and there is relatively little contact with the topic. I only know that this is a mergeable heap, which can be convenient for maximum and minimum values. This topic maintains the median. . .
For increasing intervals, treat each number as a separate pile, and the median is itself. When encountering a decreasing interval, merge the two intervals and maintain their median. The left-biased tree here is a minimum heap, not a maximum heap. Take the second example, if you maintain the maximum heap, then the median will be 4 at the second time, because you have to deal with an interval smaller than the median of the current interval. If you maintain the maximum heap, then the information of the median 2 will be gone, and it will be popped out before.
DIV1D Animals and Puzzle
The meaning of the question is to give an n*m grid, and the grid is either 0 or 1. Now there are q queries, asking about the side length of the square in which the largest one in the current rectangle is 1.
First, dp finds the current position as the lower right corner of the square and what is its maximum side length. The transfer equation is
$$
dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1
$$Speaking of which, a few days after this dp came out, the Google APAC Test also came out with this dp, and I burst into tears
Then construct a two-dimensional st table. For each query, the dichotomous answer mid satisfies x1+mid-1, y1+mid-1, x2, y2. If there is a value greater than or equal to mid in the interval, it is OK. Otherwise there is no square with that side length.
DIV1E Sonya Partymaker
The meaning of the question (the meaning of this question is not good…but this dp is somewhat amazing…it is also rarely seen, and everything is amazing…) Given a ring from 1 to m, there are n people sitting in the corresponding positions. Each person chooses a direction in advance, clockwise or counterclockwise, and then starts walking. Every step he takes, throws away the chairs at the location, and asks how long it will take at least to throw away all the chairs.
First organize this position into the position with the largest gap between 1 and n. Then, as Sister Cha said, you will find that 1 and 2 must run to the left. (Assuming that they both run to the right, it must not be optimal.) Enumerate the positions that run to the left. dp[i] represents the farthest position that the i-th person can cover.
Consider various scenarios:
The i-th person runs to the right, requiring dp[i-1] to be greater than or equal to A[i]-1. dp[i]=max(dp[i],A[i]+x)
If the i-th person runs to the left, it may be the i-1th person running to the right. In order to cover this interval, dp[i-1]>=A[i]-x-1,dp[i]=max(dp[i],A[i]) is required
If the i-th person runs to the left, it may be the i-2 running to the right. In order to cover this interval, it is required that dp[i-2]>=A[i]-x-1, dp[i]=max(dp[i],A[i-1]+x)
Learned the rotate function, rotate(begin,middle,end) exchanges the elements in the array [begin,middle) and the interval [middle,end]