Codeforces Round #669 (Div. 2)/Codeforces1407 ABCD
- 2020 年 9 月 9 日
- 筆記
- Codeforces
A. Ahahahahahahahaha
通過作者半個小時的觀察：全零和全一必定有一個是符合要求的答案，因為0的個數和1的個數至少有一個大於等於\(\frac{n}{2}\)。
B. Big Vova
貪心。
將剩餘可用的數字用一個集合裝起來，然後從小到大枚舉下標\(i\)，每次枚舉可用的數字，保存使前綴GCD最大的那個數字，這個數字就是\(b_i\)。
C. Chocolate Bunny
通過觀察可得：一次? i j和一次? j i可以確定\(p_i\)和\(p_j\)中的較小值及其下標。
證明：假設\(p_i > p_j\)，那麼\(p_i \% p_j < p_j\)，\(p_j \% p_i = p_j\)，所以兩個返回值中較大的就是\(p_i\)和\(p_j\)中較小的那一個，即\(p_j\)，並且可以知道較小值的下標為\(j\)，同時較大值的下標也確定了為\(i\)。反之同理。
然後就可以記錄較大值的下標\(p\)，初始值為\(1\)，然後從下標為\(2\)的位置開始遍曆數組，每次用兩個操作確定一個位置上的值，更新較大值的下表。
這樣，用\(2(n-1)\)次操作可以確定\(1\)至\(n-1\)的位置，且此時較大值的下標就是\(n\)的下標。
D. Discrete Centrifugal Jumps
單調棧優化DP。
現在有一個單調棧\(up\)，棧中元素單調上升，然後有一個序列\(h\)，遍歷這個序列，不斷嘗試將當前元素加入單調棧。
現在要新加進來一個元素：
- 若元素的值大於棧頂對應元素，則直接加入。
- 反之，就將棧頂出棧，重複直到元素的值大於棧頂對應元素。
可以發現，將棧頂出棧後，若棧頂元素大於當前枚舉到的元素，則新的棧頂元素到當前枚舉到的元素之間的所有元素都大於兩者，即新的棧頂對應元素到當前枚舉到的元素的跳躍是一個滿足條件3的跳躍。
同理可以維護一個棧中元素單調下降的單調棧\(down\)。
然後\(dp_i\)就只可能從\(dp_{i-1}\)轉移的來，或者是從\(up\)中的元素轉移得來，或者是從\(down\)中的元素轉移得來。
