洛谷P2463 [SDOI2008] Sandy 的卡片题解

题目链接：P2463 [SDOI2008] Sandy 的卡片

题意：

Sandy 和 Sue 都热衷于收集干脆面中的卡片。

然而，Sue 收集卡片是因为卡片上漂亮的人物形象，而 Sandy 则是为了积攒卡片兑换超炫的人物模型。

每一张卡片都由一些数字进行标记，第 \(i\) 张卡片的序列长度为 \(M_i\)，要想兑换人物模型，首先必须要集够 \(N\) 张卡片，对于这 \(N\) 张卡片，如果他们都有一个相同的子串长度为 \(k\)，则可以兑换一个等级为 \(k\) 的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。

Sandy 的卡片数远远小于要求的 \(N\)，于是 Sue 决定在 Sandy 的生日将自己的卡片送给 Sandy，在 Sue 的帮助下，Sandy 终于集够了 \(N\) 张卡片，但是，Sandy 并不清楚他可以兑换到哪个等级的人物模型，现在，请你帮助 Sandy 和 Sue，看看他们最高能够得到哪个等级的人物模型。

输入格式：

第一行为一个数 \(N\)，表示可以兑换人物模型最少需要的卡片数，即 Sandy 现在有的卡片数。

第 \(i+1\) 行到第 \(i+N\) 行每行第一个数为第 \(i\) 张卡片序列的长度 \(M_i\)，之后 \(j+1\) 到 \(j+1+M_i\) 个数，用空格分隔，分别表示序列中的第 \(j\) 个数。

输出格式：

一个数 \(k\)，表示可以获得的最高等级。

数据范围：

\(1 \le n\le1000,2\le M_i\le 101\) ，字符串中的每个数字的大小范围为 \([0,1864]\)。

考虑对原数组做差分，这样题目就变成了求 \(n\) 个字符串的最长公共子串的长度 \(+1\) 。

那就是 SP10570 了，题解戳这里，拼起来建 SA 再单调队列一下就完事了。

时间复杂度 \(\mathcal{O}(n \log n)\) 或 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2e6 + 55))
#define mem(a) memset(a, 0, sizeof(a))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

deque<int> q;
int s[N], t[N], sa[N], rk[N * 2], col[N], tmp[N * 2], height[N], cnt[N];
void sort(const int n, const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void getlcp(const int n)
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}
void init(const int n)
{
    const int m = max(n, 44444);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(n, m, w); sort(n, m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int tot, n = 0; cin >> tot;
    for(int i = 1, m; i <= tot; s[++n] = 23333 + i, i++)
    {
        cin >> m;
        for(int j = 1; j <= m; j++) cin >> t[j];
        for(int j = 1; j <= m; j++) t[j] = t[j + 1] - t[j] + 2333; // 防止出现负数
        for(int j = 1; j <= m; j++) { s[++n] = t[j], col[n] = i; }
    }
    s[n--] = 0; init(n); getlcp(n); mem(tmp);
    int sum = 0, res = 0; while(!q.empty()) q.pop_back();
    for(int i = n - tot + 1, r = n - tot + 1; i >= 1; i--)
    {
        if(!tmp[col[sa[i]]]) { ++sum; } ++tmp[col[sa[i]]];
        while(r >= i && sum == tot && tmp[col[sa[r]]] != 1) { --tmp[col[sa[r]]], --r; }
        while(!q.empty() && q.front() > r) q.pop_front();
        if(sum == tot) up(res, height[q.front()]);
        while(!q.empty() && height[q.back()] > height[i]) q.pop_back();
        q.push_back(i);
    }
    cout << res + 1 << '\n';
    return 0;
}