The article directories

    • Monotonic stack solution report
      • PKU 2082 Terrible Sets
      • HDU 2430 Beans
      • HDU 4252 A Famous City
      • PKU 2796 Feel Good
      • HDU 3410 Passing the Message
      • HDU 6759 Leading Robots
      • HDU 5033 Building
      • HDU 4923 Room and Moor
      • PKU 3250 Bad Hair Day

Monotonic stack solution report

PKU 2082 Terrible Sets

After arranging the rectangles on the x axis, it is the problem of finding the largest contiguous subrectangles.

HDU 2430 Beans

HDU 2430 Beans Given n(n<=106) n(n<=10 ^6) n(n<=106) numbers A [I] a[I] a[I] a[I] and two numbers K K K and P(0 <= P < K) P(0 <= P < K) P(0<=P

  • Solution: prefix and + monotone stack
  • 1) Find the prefix and then modulo K, K, K. Get the prefix and array sum[I] sum[I] sum[I] representing the sum of the preceding I I I terms (subscripts start at 1 for convenience).
  • 2) Let the value of K K on the sum module of the interval (I,j) (I,j) (I,j) be: M ( i , J) = (s u m [j] – s u m/I – 1) m o K m (I, j) = d (sum [j] – sum] [I – 1) \ mod m (I, j) = K (sum [j] – sum [I – 1]) modK What we need to do is for any j,j,j, we want to make the values of I, I, I as small as possible, and M(I,j)<=P M(I,j)<=P M(I,j)<=P.
  • 3) Enumerate j, j, j, and then transform it into a line segment tree to find the interval optimal problem.

HDU 4252 A Famous City

Links:HDU 4252 A Famous City

Given a histogram area, ask what is the minimum number of rectangles to fill the area. Histogram of each level shall, in accordance with the h [I] (1 < = I < = n) h [I] (1 < = I < = n) h [I] (1 < = I < = n) is given in the form of.One solution is as follows: the answer is 8.

  • Consider the following three cases:
  • 1) If the whole graph is monotonically increasing, i.e. H [I −1]
  • 2) If h[I −1]> H [I] H [i-1] > H [I] H [I] h[I −1]> H [I], then it is necessary to consider whether H [I] H [I] h[I] can merge with the same height previously appeared (as shown in the orange square bar above);
  • 3) if the h [I – 1] [I] = = h h] [I – 1 = = h h [I] [I – 1] = = h [I], then h h h [I] [I] [I] no purpose;
  • Based on the above properties, a monotone stack is used to maintain a monotone increasing sequence, and the height of the top element T O P top TOP and the current element I I I is determined as follows:
  • 1) The stack is empty or h[to P]< H [I] H [TOP]< H [I] h[TOP]

    0 H [I]>0 h[I]>0 h[I]>0 h[I]>0 then the stack is pushed;
    [i],>
  • 2) Stack is not empty and h[top]==h[I] h[top]==h[I] h[top]==h[I];
  • H [I] h[TOP]>h[I] h[TOP]>h[I] h[I] h[TOP]>h[I]; When the stack is empty or h[top]< H [I] H [TOP]< H [I] H [TOP]< H [I], and 1) judgment is similar, H [I]>0 H [I]>0 h[I]>0 h[I]>0 h[I]>0.
  • [Note: To get all elements off the stack, add a -1 to the end of the element.]

PKU 2796 Feel Good

PKU 2796 Feel Good The given number n n n a [I] (0 < = a [I] < = 1 0 6) a [I] (0 < = a [I] < = 10 ^ 6) a [I] (0 < = a [I] < = 106), Make s u m (I, j) = ∑ k = I j a, [k] sum (I, j) = \ sum_ I} {k = ^ j a, [k] sum (I, j) = ∑ k = ija [k]. Find the maximum value of S um(I,j)∗m I na(I,j) sum(I,j)*min_a(I,j) sum(I,j)∗mina(I,j).

  • Following the HDU 1506 Largest Rectangle in a Histogram idea, using monotone stack to maintain a monotone invariant sequence, preprocessing prefix and. Note that there are zero cases, so the first candidate maximum can’t be zero, it has to be something less than zero.

HDU 3410 Passing the Message

HDU 3410 Passing the Message Given n n n a[I](0<=a[I]<=105) a[I](0<=a[I]<=10 ^5) a[I](0<=a[I]<=105) a[I](0<=a[I]<=105) And the largest and smaller number to the right of each number.

  • Solution: Monotone decreasing stack
  • Scan both sides separately and maintain a monotonically decreasing stack;

HDU 6759 Leading Robots

HDU 6759 Leading Robots Given n(n<=50000) n(n<=50000) n(n<=50000) n(n<=50000) individual starting position s s s and acceleration A a a a, everyone doing uniform acceleration, ask how many people can be the “leader” at some point (i.e., no one can match it).

  • A few ideas to consider:
  • 1) Each person’s displacement curve is a parabola symmetric with respect to the y y axis, and only in the first quadrant;
  • 2) Any two parabolas will either coincide, or there will be only one intersection. In other words, if the starting position is behind, the only chance of overtaking is if the acceleration is greater than that of someone larger than the starting position;
  • 3) Two people in the same starting position, the one with the lower acceleration never has a chance to become the leader;
  • 4) Two people with the same starting position and the same acceleration have no chance of becoming the leader;
  • For two persons R I R_i Ri and Rj R_j Rj, such that (s I >sj and a I

    s_j and a_i < a_j) (Si >sj and AI < AJ), Then the time aj a_j AJ catches up with a I a_i AI is: I – s j t > = 2 (s) a j – a I t > = \ SQRT {\ frac {2} (s_i – s_j) {a_j – a_i}} t > = aj – ai2 (si – sj)
    )>
  • Consider three persons, R 1 = (s 1, a 1), R 2 = (S 2, a 2), R 3 = (s 3, a 3) R_1 = (s_1, a_1), R_2 = (s_2, a_2), R_3 = (s_3, a_3) R1 = (s1, a1), R2 = (s2, a2), R3 = (s3, a3), and meet (s 1 > s > 2 s (3) (s_1 > s_2 > s_3) > s2 > s1 (s3). If R2, R_2 R2 wants to catch up, it must be (a2>a1) (a_2 > a_1) (a2> A1), R3 R_3 R3 wants to catch up with (a3>max(a1,a2)) (a_3 > Max (a_1,a_2)) (A3 > Max (a1, A2)). But that’s not enough. Just think, if R3, R_3, R3 catches up with R2, R_2 R2 before R2, R_2 R2 catches up with R1, R_1 R1, then R2, R_2 R2 never has a chance to be number one.
  • So, for a sequence with decreasing position and increasing acceleration, we need to maintain a monotonically increasing sequence of “catch-up time”;
  • The algorithm is designed as follows:
  • 1) Firstly, sort the data and decrease according to the starting position as the first keyword. If the position is the same, the acceleration decreases;
  • 2) For the same position, the minor element of acceleration is directly removed; Hash the element whose two keywords are the same, not as a “bellwether” candidate;
  • 3) Scan the data from front to back, record that the maximum value of the current acceleration is Maxa Max_a Maxa, skip the processing for all the scanned acceleration less than or equal to Maxa Max_a Maxa, and update the maximum value of the acceleration after each scan:
  • 3. A) If there are less than two elements in the stack, the current element is pushed;
  • T top t_{top} tTOP, tcur t_{cur} tcur, tcur t_{cur} tcur T top>=tcur t_{top} >= t_{cur} tTOP >=tcur; ttop>=tcur t_{top} >= t_{cur} tTOP >=tcur;
  • After the scan is complete, all the top elements are removed from the stack, and the person who is not hashed is the one who can become the “leader” at some point;
  • [Note: square root + division will cause precision error when calculating time, and can be converted to multiplication when comparing.]

HDU 5033 Building

HDU 5033 Building Given n(n<=105) N (n<=10 ^5) n(n<=105) buildings x[I] x[I] x[I] coordinates and height h[I] h[I] H [I] h[I], And then Q(Q<=105) Q(Q<=10 ^5) Q(Q<=105) times, asking how much elevation is required to see the sky at a certain location;

  • Solution: Off-line algorithm + monotonous stack slope optimization
  • For any p, p, p you have to think about the left and right sides, but the left and right sides are the same, so you’re only thinking about the left side; And then I reverse it and I do it again, and I add the two angles to the X-axis, and I subtract 180 degrees. Then there are the following points to note:
  • 1) For a certain p p p position, the building to the left of it must be monotonically decreasing as x x x increases, or it will certainly not be the building with the highest elevation that obstructs the view.

  • 2) once appear three highly monotone decreasing building, the shape of them form a concave shape, so in the middle of the building, it is impossible to become obstacles of buildings, so you can think in the middle of the building does not exist (can literally find a of the points on the axis do wired into the middle of the building, must be handed in on the first or the third buildings);

  • 3) Therefore, for the building sequence, we only need to maintain a sequence where the adjacent buildings gradually become steeper (numerically, the slope gradually becomes larger and larger towards the negative direction), and we can use monotone stack to maintain this sequence;

  • 4) For any position p p p, now to find the building that affects its view, you can check the buildings in the stack and make the slope of the two buildings at the top of the stack be Ktop K_{top} Ktop, and the slope of the two buildings at the top of the stack be K P K_p Kp, If Ktop<=Kp K_{top} <= K_p Ktop<=Kp (note that the slope is always negative), then out of the stack, continue to judge; Otherwise, it finds the building that blocks its view;

HDU 4923 Room and Moor

Links:HDU 4923 Room and Moor

Given A sequence A of n(n<=100000) n(n<=100000) n(n<=100000) elements consisting only of 0 and 1, find A non-decreasing sequence B that satisfies the following conditions:

  • A. monotonous b. monotonous C. monotonous D. monotonous
  • First, divide all the numbers into the following segments: 111000, 11100, 110, 1111110, namely, they all start with 1 and end with 0. Then for a certain paragraph, assuming that the number of 1 is A, A, a, and the number of 0 is B, B, b, and let the selected b I =x, B_i =x, Bi=x, then the sum of the squares of difference is: A (x−1)2+bx2 a(x−1) ^2 +bx ^2 A (x−1) ^2 +bx ^2 A (x−1) ^2 +bx ^2 A (x−1) ^2 a(x−1) ^2 a(x−1) ^2 +bx2
  • If B, I, B_i, Bi can be found in this way, then the solution of the problem will be solved;
  • When B I >B I +1 B_i > B_{I +1} Bi>Bi+1, we can choose to merge B I B_i Bi and B I +1 B_{I +1} Bi+1, and maintain the sequence with monotonically increasing stacks. Know that the elements in the stack are monotonically increasing positions.

PKU 3250 Bad Hair Day

Links:PKU 3250 Bad Hair Day

The question: N (n<=105) n(n<=10 ^5) n(n<=105) individuals are arranged from left to right, given their height h[I] h[I] h[I],, The number of people whose height is lower than that of the ith I I person looking to the right is s[I] s[I] s[I] s[I], ∑ I =1ns[I] \sum_{I =1}^{n} s[I] ∑ I =1ns[I].

  • Let’s consider the following two scenarios:
  • 1) As shown in the figure below, the current person number is C C C, a A A and b b are in reverse order, then the solutions of A A a and B b are c C C;

  • 2) As shown in the figure below, the current person number is C c C, a A A and B b are in order (or a and B are the same height), then only b b b solution is C c C; And what we found in this problem is that when we solve for b, b, b, a, a, a, we already have the solution, we don’t need it anymore;

  • To understand a, A, a and B, b as elements in the stack, we first insert an infinite number at the end of the sequence, then maintain a monotonically decreasing stack, enumerate each person’s height h[I] H [I] H [I] from left to right, and then compare the height of the top element of the stack with the current height. If the height of the element at the top of the stack <= the current height, the furthest person visible to the person at the top of the stack is the current I I I person, then the answer is accumulated and the answer is removed from the stack, and the iterative loop is processed until the height of the element at the top of the stack > the current height or the stack is empty, and then the I I I is added to the stack.
  • As shown in the figure, the red square column is H [I] H [I] H [I], the green square column is all the elements to be removed from the stack, and the blue square column is the element still in the stack after processing, and the elements in the stack always keep monotonically decreasing.