Problem A - Levko and Array Recovery (by Yangerma)
對一個長度最大為\(5000\)的序列，有兩種操作：區間加值和RMQ。今天依時間順序給你一張操作的紀錄，最多有\(5000\)筆操作，其中對於每個RMQ操作都附有它的答案。要求構造出一個符合所有詢問的原序列（可能無解）。
題解：
首先可以預處理，每個位置在每個時間點，相較於原序列的delta值，直接建表。
首先可以預處理，每個位置在每個時間點，相較於原序列的delta值，直接建表。
每筆RMQ有兩個意義：
\(1.\)它是一個上界
\(2.\)區間中有個值等於它
稍微感受一下就發現\(2\)比\(1\)難很多，所以策略就是先忽略\(2\)只考慮\(1\)。在滿足\(1\)的前提下，任何數字越大對\(2\)而言就一定越好。
於是做法就是，對於序列每個位置，就直接跑過所有詢問，配合delta值的表就可以得到它所有的上界，然後直接讓它等於最小的那一個。
最後再把所有操作跑一遍，看看是不是真的滿足\(2\)，如果不是就無解。
\(1.\)它是一個上界
\(2.\)區間中有個值等於它
稍微感受一下就發現\(2\)比\(1\)難很多，所以策略就是先忽略\(2\)只考慮\(1\)。在滿足\(1\)的前提下，任何數字越大對\(2\)而言就一定越好。
於是做法就是，對於序列每個位置，就直接跑過所有詢問，配合delta值的表就可以得到它所有的上界，然後直接讓它等於最小的那一個。
最後再把所有操作跑一遍，看看是不是真的滿足\(2\)，如果不是就無解。
時間複雜度：\(O(NQ)\)
這題很慚愧地卡了一陣子，後來才發現\(NQ\)能做的事情比想像中多很多XD。
Problem B - Levko and Array (by Yanger)
給你一個最長2000的整數序列。對一個序列，定義它的「美麗度」為所有相鄰值的差的最大值（美麗度越低越好）。問若你可以改變數列的\(k\)個值，美麗度最低可以是多少？
題解：
答案顯然有單調性，所以就二分搜吧。
對於每個答案，有些值需要改，有些值不用。考慮不用改的那些值，它們滿足一個充要性質：相鄰兩個之間的斜率（這邊指的是拔掉要改的值之後相鄰，實際index不見得相鄰）的絕對值小於等於答案。所以我們的目標就變成找一個最長子序列滿足上面那個條件。這件事可以
\(O(N*N)\) DP做到：令dp[i]代表以 i 為結尾的最長子序列，求\(dp[i]\)的方法就是就回頭看\(dp[0 ~ i-1]\)看有哪個可以接得上去。
找到最長子序列後就看它是否大於等於n-k，來判斷這個答案O不OK。
時間複雜度：\(O(N*N*log(maxval))\)
code: http://codeforces.com/contest/360/submission/17545531
沒有留言:
張貼留言