RT,我的这发提交可以 AC。
但是,当我在代码中加入 assert(y <= 1864)
的时候,这份代码就 RE 了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, S = 110000, A = 1e5;
int n, m[N], s[S], col[S], ob = 1865, cur;
int t1[S], t2[S], c[A << 1], height[S], sa[S], rk[S];
void BuildSA()
{
int *x = t1, *y = t2;
int lim = A * 2 - 5;
fill(c + 1, c + lim + 1, 0);
for(int i = 1; i <= cur; i++) c[x[i] = (s[i] + A)]++;
for(int i = 2; i <= lim; i++) c[i] += c[i - 1];
for(int i = cur; i; i--) sa[c[x[i]]--] = i;
for(int k = 1; k <= cur; k <<= 1)
{
int p = 0;
for(int i = cur - k + 1; i <= cur; i++) y[++p] = i;
for(int i = 1; i <= cur; i++) if(sa[i] > k) y[++p] = sa[i] - k;
fill(c + 1, c + lim + 1, 0);
for(int i = 1; i <= cur; i++) c[x[y[i]]]++;
for(int i = 2; i <= lim; i++) c[i] += c[i - 1];
for(int i = cur; i; i--) sa[c[x[y[i]]]--] = y[i];
swap(x, y);
x[sa[1]] = 1;
for(int i = 2; i <= cur; i++)
x[sa[i]] = x[sa[i - 1]] + (y[sa[i - 1]] != y[sa[i]] || (sa[i] + k <= cur && sa[i - 1] + k <= cur && y[sa[i - 1] + k] != y[sa[i] + k]));
if(x[sa[cur]] == cur) break;
lim = x[sa[cur]];
}
for(int i = 1; i <= cur; i++) rk[sa[i]] = i;
}
void BuildHeight()
{
for(int i = 1, k = 0; i <= cur; i++)
{
if(k) k--;
while(s[i + k] == s[sa[rk[i] - 1] + k]) k++;
height[rk[i]] = k;
}
}
int stk[N], top;
bool vis[N];
bool Check(int res)
{
while(top) vis[stk[top--]] = false;
for(int i = 1; i <= cur; i++)
{
if(height[i] < res)
{
while(top) vis[stk[top--]] = false;
}
if(!vis[col[sa[i]]])
{
vis[col[sa[i]]] = true;
stk[++top] = col[sa[i]];
if(top == n) return true;
}
}
return false;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &m[i]);
int x, y;
assert(x <= 1864);
scanf("%d", &x);
for(int j = 2; j <= m[i]; j++)
{
scanf("%d", &y);
assert(y <= 1864);
s[++cur] = y - x;
col[cur] = i;
x = y;
}
s[++cur] = ob++;
}
BuildSA();
BuildHeight();
int lb = 0, rb = (*min_element(m + 1, m + n + 1)) - 1;
while(lb < rb)
{
int mid = lb + rb + 1 >> 1;
if(Check(mid)) lb = mid;
else rb = mid - 1;
}
printf("%d\n", lb + 1);
return 0;
}
是我对题面的理解有误,还是题面真的有误?/yun