777-D. Cloud of Hashtags

Tags: greedy

出處:https://codeforces.com/contest/777/problem/D
提交:https://codeforces.com/contest/777/submission/110781183

問題:給定 $n\in[1,500000]$ 個前綴為 “#” 的字串,長度總和不超過 1000000,現在欲刪除每個字串的 (任意非負長度的) 後綴使得字串們由上而下滿足字典序 [1],請印出在總刪除字元數最少的情況之下的所有字串。

解法:首先觀察到一個事實,如果字串 a 和字串 b 已經滿足字典序,那麼對 b 加上任意長度的後綴 s 之後,字串 a 和字串 b.s 亦滿足字典序。根據這個事實,吾人可以由下往上依次進行刪減,每次都刪除當前最短的後綴使得相鄰上下兩字串滿足字典序,那麼持續此動作之後的最終結果就是答案。

附註:
[1] 所謂滿足字典序的意思與一般大家認知的相同,上方的字串由前往後掃的過程中如果第一次遇到一個字元與對應到下方字串之同個位置的字元值不同,那麼上方的字元必須小於下方的字元;如果過程中每個字元都相同,那麼上方字串的長度不可以超過下方字串。

實作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int n; string s[500000];

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    cin >> n;
    for (int i=0; i<n; i++) cin >> s[i];
    for (int i=n-1; i-1>=0; i--) {
        int j; bool fail = false;
        for (j=0; j<min(s[i-1].length(), s[i].length()); j++) {
            if (s[i-1][j] < s[i][j]) break;
            else if (s[i-1][j] > s[i][j]) {
                fail = true;
                break;
            }
        }
        if (fail || !fail && j== min(s[i-1].length(), s[i].length()))
            s[i-1].resize(j); // truncated to be s[i-1][0:j-1], the total length is j
    }
    for (int i=0; i<n; i++) cout << s[i] << '\n';
    return 0;
}

結果: Example image