P5284 [十二省联考2019]字符串问题

时间：2023-03-09 23:14:52
P5284 [十二省联考2019]字符串问题

这是一道涵盖了字符串、图论、数据结构三个方面的综合大题。

把这道题放在D1T2的人应该拖出去打

前置芝士

首先，您至少要会topsort。

其次，如果您只想拿个暴力分，字符串Hash就足够了；如果您想拿满分，SA和SAM您至少要会一种（本文采用SA）。

最后，正解还需要您了解线段树优化建边，并在此基础上用主席树实现。

暴力算法一

对于测试点1~4，暴力建图，Hash优化，可以拿到40分的高分。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N = 2e5 + 6;
char s[N];
int n, na, la[N], ra[N], nb, lb[N], rb[N], nm, ma[N], mb[N];

namespace Hash {
    const int P = 13331;
    ull h[N], p[N];

    inline void main() {
        p[0] = 1;
        for (int i = 1; i <= n; i++) h[i] = h[i-1] * P + s[i], p[i] = p[i-1] * P;
    }

    inline ull get(int l, int r) {
        return h[r] - h[l-1] * p[r-l+1];
    }
}

namespace Graph {
    vector<int> e[N<<1];
    int a[N<<1], d[N<<1], f[N<<1];
    queue<int> q;

    inline void init() {
        for (int i = 1; i <= na + nb; i++) e[i].clear(), a[i] = d[i] = f[i] = 0;
        for (int i = 1; i <= na; i++) a[i] = ra[i] - la[i] + 1;
    }

    inline void add(int x, int y) {
        e[x].push_back(y), ++d[y];
    }

    inline void topsort() {
        for (int i = 1; i <= na + nb; i++) if (!d[i]) q.push(i);
        while (q.size()) {
            int x = q.front();
            q.pop();
            for (unsigned int i = 0; i < e[x].size(); i++) {
                int y = e[x][i];
                f[y] = max(f[y], f[x] + a[x]);
                if (!--d[y]) q.push(y);
            }
        }
        for (int i = 1; i <= na + nb; i++)
            if (d[i]) {
                puts("-1");
                return;
            }
        ll ans = 0;
        for (int i = 1; i <= na + nb; i++) ans = max(ans, (ll)f[i] + a[i]);
        cout << ans << endl;
    }

    inline void main() {
        Hash::main();
        init();
        for (int i = 1; i <= nm; i++) add(ma[i], mb[i] + na);
        for (int j = 1; j <= nb; j++) {
            ull now = Hash::get(lb[j], rb[j]);
            int len = rb[j] - lb[j];
            for (int i = 1; i <= na; i++)
                if (len < a[i] && Hash::get(la[i], la[i] + len) == now) add(j + na, i);
        }
        topsort();
    }
}

inline void work() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    scanf("%d", &na);
    for (int i = 1; i <= na; i++) scanf("%d %d", &la[i], &ra[i]);
    scanf("%d", &nb);
    for (int i = 1; i <= nb; i++) scanf("%d %d", &lb[i], &rb[i]);
    scanf("%d", &nm);
    for (int i = 1; i <= nm; i++) scanf("%d %d", &ma[i], &mb[i]);
    Graph::main();
}

int main() {
    int T;
    cin >> T;
    while (T--) work();
    return 0;
}

暴力算法二

对于测试点1、4、5、6，所有A串的前缀总数是可接受的，全部枚举出来，暴力建图，可以拿到40分的高分。

暴力算法三

结合暴力算法一和二，面向数据分治，可以拿到60分的高分。

（滑稽

错误算法

我们对字符串跑一遍SA，一个显而易见的事实是，每个 \(b\) 串一定会连向SA上的一个区间。

线段树优化建图即可。

虽然是错误算法，但可以拿到80分的高分。

正确算法

错误算法中有这样一句话：

每个 \(b\) 串一定会连向SA上的一个区间。

但是，显然，如果 \(b\) 串长度大于 \(a\) 串，那么 \(b\) 串一定不会是 \(a\) 串的前缀。

因此，每个 \(b\) 串一定会连向SA上的一个区间中的若干个点。

考虑用主席树代替线段树。

按长度从大到小将 \(a\) 串依次插入主席树中。

在大于 \(b\) 串长度的主席树历史版本上优化建图。

下面代码的实现细节参考了小粉兔在https://www.cnblogs.com/PinkRabbit/p/SHOI2019D1T2.html中的思路，但并不雷同

#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
using namespace std;
const int N = 2e5 + 6;
char s[N];
int T, n, na, la[N], ra[N], nb, lb[N], rb[N], nm, ma[N], mb[N], tot;
struct Str {
    int l, len, id;
    inline Str() {}
    inline Str(int l, int len, int id) : l(l), len(len), id(id) {}
    inline bool operator < (const Str o) const {
        return (len ^ o.len) ? len > o.len : id < o.id;
    }
} str[N<<1];

namespace SA {
    int m = 26, sa[N], rk[N], tp[N], tx[N], he[N], st[N][20];

    inline void tsort() {
        for (int i = 1; i <= m; i++) tx[i] = 0;
        for (int i = 1; i <= n; i++) ++tx[rk[i]];
        for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
        for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i];
    }

    inline bool pd(int i, int w) {
        return tp[sa[i-1]] == tp[sa[i]] && tp[sa[i-1]+w] == tp[sa[i]+w];
    }

    inline void main() {
        for (int i = 1; i <= n; i++) rk[i] = s[i] - 'a' + 1, tp[i] = i;
        tsort();
        for (int w = 1, p = 0; p < n; w <<= 1, m = p) {
            p = 0;
            for (int i = 1; i <= w; i++) tp[++p] = n - w + i;
            for (int i = 1; i <= n; i++) if (sa[i] > w) tp[++p] = sa[i] - w;
            tsort(), swap(rk, tp), rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i++) rk[sa[i]] = pd(i, w) ? p : ++p;
        }
        int p = 0;
        for (int i = 1; i <= n; i++) {
            if (p) --p;
            int j = sa[rk[i]-1];
            while (s[i+p] == s[j+p]) ++p;
            he[rk[i]] = p;
        }
        for (int i = 1; i <= n; i++) st[i][0] = he[i];
        int w = log(n) / log(2);
        for (int k = 1; k <= w; k++)
            for (int i = 1; i + (1 << k) - 1 <= n; i++)
                st[i][k] = min(st[i][k-1], st[i+(1<<(k-1))][k-1]);
    }

    inline int get(int l, int r) {
        int k = log(r - l + 1) / log(2);
        return min(st[l][k], st[r-(1<<k)+1][k]);
    }
}

namespace Graph {
    vector<int> e[N<<5];
    ll a[N<<5], d[N<<5], f[N<<5];
    queue<int> q;

    inline void add(int x, int y) {
        e[x].push_back(y), ++d[y];
    }

    inline void topsort() {
        for (int i = 1; i <= tot; i++) if (!d[i]) q.push(i);
        while (q.size()) {
            int x = q.front();
            q.pop();
            for (unsigned int i = 0; i < e[x].size(); i++) {
                int y = e[x][i];
                f[y] = max(f[y], f[x] + a[x]);
                if (!--d[y]) q.push(y);
            }
        }
        for (int i = 1; i <= tot; i++)
            if (d[i]) {
                puts("-1");
                return;
            }
        ll ans = 0;
        for (int i = 1; i <= tot; i++) ans = max(ans, f[i] + a[i]);
        printf("%lld\n", ans);
    }
}

namespace Seg {
    struct T {
        int l, r;
    } t[N<<5];
    int rt[N];

    int ins(int o, int l, int r, int x, int k) {
        int p = ++tot;
        t[p] = t[o];
        if (o) Graph::add(p, o);
        if (l == r) Graph::add(p, k);
        else if (x <= mid) Graph::add(p, t[p].l = ins(t[o].l, l, mid, x, k));
        else Graph::add(p, t[p].r = ins(t[o].r, mid + 1, r, x, k));
        return p;
    }

    void add(int p, int l, int r, int L, int R, int k) {
        if (!p || r < L || l > R) return;
        if (L <= l && r <= R) Graph::add(k, p);
        else add(t[p].l, l, mid, L, R, k), add(t[p].r, mid + 1, r, L, R, k);
    }
}

inline void work() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    SA::main();
    scanf("%d", &na);
    for (int i = 1; i <= na; i++) scanf("%d %d", &la[i], &ra[i]);
    scanf("%d", &nb);
    for (int i = 1; i <= nb; i++) scanf("%d %d", &lb[i], &rb[i]);
    scanf("%d", &nm);
    for (int i = 1; i <= nm; i++) scanf("%d %d", &ma[i], &mb[i]);
    for (int i = 1; i <= na; i++) Graph::a[i] = ra[i] - la[i] + 1;
    for (int i = 1; i <= na; i++) str[i] = Str(la[i], ra[i] - la[i] + 1, i);
    for (int i = 1; i <= nb; i++) str[na+i] = Str(lb[i], rb[i] - lb[i] + 1, na + i);
    sort(str + 1, str + na + nb + 1);
    tot = na + nb;
    int now = 0;
    for (int i = 1; i <= na + nb; i++)
        if (str[i].id <= na) ++now, Seg::rt[now] = Seg::ins(Seg::rt[now-1], 1, n, SA::rk[str[i].l], str[i].id);
        else {
            int k = SA::rk[str[i].l], l = 1, r = k, L, R;
            while (l < r)
                if (SA::get(mid + 1, k) >= str[i].len) r = mid;
                else l = mid + 1;
            L = l, l = k + 1, r = n + 1;
            while (l < r)
                if (SA::get(k + 1, mid) >= str[i].len) l = mid + 1;
                else r = mid;
            Seg::add(Seg::rt[now], 1, n, L, R = l - 1, str[i].id);
        }
    for (int i = 1; i <= nm; i++) Graph::add(ma[i], mb[i] + na);
    Graph::topsort();
    for (int i = 1; i <= tot; i++) Graph::e[i].clear(), Graph::a[i] = Graph::d[i] = Graph::f[i] = 0;
}

int main() {
    cin >> T;
    while (T--) work();
    return 0;
}

相关文章