USACO07DEC Best Cow Line G

发表于2020-07-13更新于2023-09-15字数统计701阅读时长7分

Best Cow Line G

Description

给定长度为 NN 的字符串 SS，每次可从 SS 的两端选取一个字符插入空字符串 TT 尾部。求字典序最小的字符串 TT。

Solution

考虑贪心：比较当前 SS 与 reverse(S)reverse(S) 的字典序，如果 SS 的字典序小则从 SS 头部取出字符；否则从尾部取出。
本题数据加强，逐位比较会被卡。需 hashhash + 二分或倍增求出最长相同前缀子串，比较下一个位置的大小。
注：字符串 hashhash(%) 不能直接用来比较字符串大小。

Code

二分子串长度

Best Cow Line G
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>

typedef unsigned long long uLL;
constexpr int MAXN = 5e5 + 5;
constexpr uLL base = 13331;

using namespace std;

int n;
uLL H1[MAXN], H2[MAXN], P[MAXN] = {1};
char s[MAXN], revs[MAXN];
string ans;

inline void Init() {
    for (int i = 1; i <= n; i++) P[i] = P[i - 1] * base;
    for (int i = 1; i <= n; i++) H1[i] = H1[i - 1] * base + s[i] - 'A' + 1;
    for (int i = 1; i <= n; i++) H2[i] = H2[i - 1] * base + revs[i] - 'A' + 1;
}

inline uLL getHash(int l, int r, uLL * H) {
    return H[r] - H[l - 1] * P[r - l + 1];
}

inline bool compare(int l, int r) {
    int L = 0, R = r - l, len = -1;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (getHash(l, l + mid, H1) == getHash(n - r + 1, n - r + 1 + mid, H2)) 
            len = mid, L = mid + 1;
        else R = mid - 1;
    }
    return s[l + len + 1] < s[r - len - 1];
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) 
        getchar(), s[i] = getchar(), revs[n - i + 1] = s[i];
    Init();
    int l = 1, r = n;
    while (l <= r) {
        if (compare(l, r)) ans += s[l], l++;
        else ans += s[r], r--;
    }
    for (int i = 0; i < n; i++) {
        if (i && i % 80 == 0) putchar('\n');
        putchar(ans[i]);
    }
    return 0;
}

倍增

Best Cow Line G
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>


typedef unsigned long long uLL;
constexpr uLL base = 13331;
constexpr int MAXN = 5e5 + 5;

using namespace std;

int n;
uLL H1[MAXN], H2[MAXN], P[MAXN] = {1};
char s[MAXN], revs[MAXN];
string ans;

inline void Init() {
    for (int i = 1; i <= n; i++) P[i] = P[i - 1] * base;
    for (int i = 1; i <= n; i++) H1[i] = H1[i - 1] * base + s[i] - 'A' + 1;
    for (int i = 1; i <= n; i++) H2[i] = H2[i - 1] * base + revs[i] - 'A' + 1;
}

inline uLL getHash(int l, int r, uLL* H) {
    return H[r] - H[l - 1] * P[r - l + 1];
}

inline bool compare(int l, int r) {
    int len = 1, Lst = l - 1, Rst = n - r;
    while (len) {
        if (Lst + len <= r &&
            getHash(l, Lst + len, H1) == getHash(n - r + 1, Rst + len, H2)) {
            Lst += len, Rst += len, len <<= 1;
        } else
            len >>= 1;
    }
    return s[Lst + 1] < revs[Rst + 1];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        getchar(), s[i] = getchar(), revs[n - i + 1] = s[i];
    Init();
    int l = 1, r = n;
    while (l <= r) {
        if (compare(l, r)) ans += s[l], l++;
        else ans += s[r], r--;
    }
    for (int i = 0; i < n; i++) {
        if (i && i % 80 == 0) putchar('\n');
        putchar(ans[i]);
    }
    return 0;
}