传送门

很容易想到,题目中的相同是指差分数组相同。

那么可以把差分数组连起来,中间加上一个没有出现过的且字典序小的数

双指针移动,用st表维护height数组中的最小值。

当然用单调队列应该也可以且更快。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 1010000 using namespace std; int n, m, t, cnt, len, ans, mx, mn = 1e9;
int pos[N], a[N / 1000], num[N / 1000], sa[N], height[N], Rank[N], b[N], x[N], y[N], d[N][22], s[N]; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline void build_sa()
{
int i, k, p;
for(i = 0; i < m; i++) b[i] = 0;
for(i = 0; i < n; i++) b[x[i] = s[i]]++;
for(i = 1; i < m; i++) b[i] += b[i - 1];
for(i = n - 1; i >= 0; i--) sa[--b[x[i]]] = i;
for(k = 1; k <= n; k <<= 1)
{
p = 0;
for(i = n - k; i < n; i++) y[p++] = i;
for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(i = 0; i < m; i++) b[i] = 0;
for(i = 0; i < n; i++) b[x[y[i]]]++;
for(i = 1; i < m; i++) b[i] += b[i - 1];
for(i = n - 1; i >= 0; i--) sa[--b[x[y[i]]]] = y[i];
swap(x, y);
p = 1, x[sa[0]] = 0;
for(i = 1; i < n; i++)
x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
if(p >= n) break;
m = p;
}
} inline void build_height()
{
int i, j, k = 0;
for(i = 0; i < n; i++) Rank[sa[i]] = i;
for(i = 0; i < n; i++)
{
if(k) k--;
j = sa[Rank[i] - 1];
while(s[i + k] == s[j + k]) k++;
height[Rank[i]] = k;
}
} inline void build_st()
{
int i, j;
for(i = 1; i < n; i++) d[i][0] = height[i];
for(j = 1; (1 << j) < n; j++)
for(i = 1; i + (1 << j) - 1 < n; i++)
d[i][j] = min(d[i][j - 1], d[i + (1 << j - 1)][j - 1]);
} inline int query(int l, int r)
{
l++;
if(l > r) return 0;
int tmp = log2(r - l + 1);
return min(d[l][tmp], d[r - (1 << tmp) + 1][tmp]);
} inline void solve()
{
int i, j = 0;
for(i = 0; i < n; i++)
{
while(j < n && cnt < t)
{
if(!num[pos[sa[j]]]++ && pos[sa[j]]) cnt++;
j++;
}
if(cnt == t) ans = max(ans, query(i, j - 1));
if(!--num[pos[sa[i]]] && pos[sa[i]]) cnt--;
}
} int main()
{
int i, j, k;
t = read();
for(i = 1; i <= t; i++)
{
k = read();
for(j = 1; j <= k; j++) a[j] = read();
for(j = 1; j < k; j++)
{
pos[n] = i;
s[n++] = a[j + 1] - a[j];
mn = min(mn, s[n - 1]);
}
s[n++] = mx++;
}
for(i = 0; i < n; i++)
if(pos[i]) s[i] = s[i] - mn + mx, m = max(m, s[i]);
m++;
build_sa();
build_height();
build_st();
solve();
printf("%d\n", ans + 1);
return 0;
}

  

最新文章

  1. java 大数据处理类 BigDecimal 解析
  2. IOS 图片全屏预览
  3. ActionBar只显示图标不显示文字
  4. OS开发 touch事件的优先级和事件传递
  5. WBS说明
  6. 一个小团队TDD游戏及实践
  7. 多个inline元素、block元素、inline-block元素在父容器中的换行情况
  8. angular中的$http配置和参数
  9. ES6小点心第二弹——底部浮现弹窗
  10. 1023. Have Fun with Numbers (20)
  11. Linux shell编写端口扫描脚本
  12. URLConnection和HttpURLConnection
  13. drupal7 的核心模块
  14. 【剑指offer】栈的压入、弹出序列
  15. 使用 phpStudy + VSCODE 进行 PHP 断点调试
  16. 细说React(一)
  17. C#调用OCR组件识别图片文字
  18. 【bzoj3125】CITY 插头dp
  19. CF605E Intergalaxy Trips 贪心 概率期望
  20. php 重写session

热门文章

  1. 第010课_掌握ARM芯片时钟体系
  2. 【转】JavaScript 节点操作 以及DOMDocument属性和方法
  3. sessionStorage对象
  4. iOS监听电话来电、挂断、拨号等
  5. 【转】LDA-linear discriminant analysis
  6. NOIP计划索引
  7. 【AC自动机】bzoj3172: [Tjoi2013]单词
  8. MYSQL不能显示中文字,显示错误“ERROR 1366 (HY000): Incorrect string value: &#39;\xE5\xBC\xA0\xE4\xB8\x89&#39;”
  9. 分享几个能用的 editplus 注册码
  10. 面试题--如何防止sql注入,使用PreparedStatement的预编译,传入的内容就不会和原来的语句发生任何匹配的关系,达到防止注入的方法