值域范围疑似有误?
查看原帖
值域范围疑似有误?
51971
syksykCCCPAHs楼主2021/3/3 22:47

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

2021/3/3 22:47
加载中...