SDOI2008 Sandy的卡片( 后缀数组 )

求出后缀数组, 然后二分答案, 对height数组分组检验答案. 时间复杂度O(|S| log|S|)

--------------------------------------------------------------------------------

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 1009;

const int maxN = 1000009;

inline int read() {

char c = getchar();

for(; !isdigit(c); c = getchar());

int ret = 0;

for(; isdigit(c); c = getchar())

ret = ret * 10 + c - ‘0‘;

return ret;

}

bool vis[maxn];

int str[maxn][maxn], len[maxn], n, Top;

int S[maxN], Id[maxN], stk[maxN], N;

int cnt[maxN], Sa[maxN], Height[maxN], Rank[maxN];

void Build(int m) {

int *x = Height, *y = Rank;

for(int i = 0; i < m; i++) cnt[i] = 0;

for(int i = 0; i < N; i++) cnt[x[i] = S[i]]++;

for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];

for(int i = N; i--; ) Sa[--cnt[x[i]]] = i;

for(int k = 1, p = 0; k <= N; k <<= 1, p = 0) {

for(int i = N - k; i < N; i++) y[p++] = i;

for(int i = 0; i < N; i++)

if(Sa[i] >= k) y[p++] = Sa[i] - k;

for(int i = 0; i < m; i++) cnt[i] = 0;

for(int i = 0; i < N; i++) cnt[x[y[i]]]++;

for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];

for(int i = N; i--; ) Sa[--cnt[x[y[i]]]] = y[i];

swap(x, y);

p = 1;

x[Sa[0]] = 0;

for(int i = 1; i < N; i++) {

if(y[Sa[i]] != y[Sa[i - 1]] || y[Sa[i] + k] != y[Sa[i - 1] + k]) p++;

x[Sa[i]] = p - 1;

}

if(p >= N) break;

m = p;

}

for(int i = 0; i < N; i++) Rank[Sa[i]] = i;

Height[0] = 0;

for(int i = 0, h = 0; i < N; i++) if(Rank[i]) {

if(h) h--;

while(S[i + h] == S[Sa[Rank[i] - 1] + h]) h++;

Height[Rank[i]] = h;

}

}

void Init() {

int mn = 1 << 30, mx = -1 << 30;

n = read();

for(int i = 0; i < n; i++) {

len[i] = read();

for(int j = 0; j < len[i]; j++) str[i][j] = read();

for(int j = len[i]; --j; ) {

str[i][j] -= str[i][j - 1];

mn = min(mn, str[i][j]);

mx = max(mx, str[i][j]);

}

}

N = 0;

for(int i = 0; i < n; i++) {

for(int j = 1; j < len[i]; j++) {

S[N] = str[i][j] - mn + n;

Id[N++] = i;

}

S[N] = n - i - 1;

Id[N++] = n;

}

Build(mx - mn + n + 1);

memset(vis, 0, sizeof vis);

vis[n] = 1;

Top = 0;

}

bool chk(int v) {

while(Top) vis[stk[--Top]] = 0;

for(int i = 1; i < N; i++) if(Height[i] >= v) {

if(!vis[Id[Sa[i - 1]]])

vis[stk[Top++] = Id[Sa[i - 1]]] = 1;

if(!vis[Id[Sa[i]]])

vis[stk[Top++] = Id[Sa[i]]] = 1;

if(Top >= n) return true;

} else {

while(Top) vis[stk[--Top]] = 0;

}

return false;

}

void Work() {

int l = 1, r = maxN, ans = 0;

while(l <= r) {

int m = (l + r) >> 1;

if(chk(m)) {

ans = m, l = m + 1;

}

else

r = m - 1;

}

printf("%d\n", ++ans);

}

int main() {

Init();

Work();

return 0;

}

--------------------------------------------------------------------------------

时间: 01-14

SDOI2008 Sandy的卡片( 后缀数组 )的相关文章

BZOJ4698 [SDOI2008] Sandy的卡片 - 后缀数组,二分

题意:求在N个串中都出现的最长子串 的长度 很容易想到二分转化为判定性问题.考虑长度M,我们按照长度M进行分组,每个组内进行答案验证,即检查组内是否有N个串的后缀都出现. 时间复杂度O(LlogM) 其实是个经典题. 二分时候记得初始化! 1 #include <bits/stdc++.h> 2 using namespace std; 3 4 struct SA { 5 int str[2100005]; 6 int x[2100005],y[2100005],u[2100005],v[21

BZOJ 4698: Sdoi2008 Sandy的卡片

4698: Sdoi2008 Sandy的卡片 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 225  Solved: 95[Submit][Status][Discuss] Description Sandy和Sue的热衷于收集干脆面中的卡片.然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积 攒卡片兑换超炫的人物模型.每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型 ,首先必须要集够N张卡片,对

bzoj4698 / P2463 [SDOI2008]Sandy的卡片

P2463 [SDOI2008]Sandy的卡片 直接二分长度暴力匹配....... 跑的还挺快 (正解是后缀数组的样子) 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 void read(int &x){ 6 char c=getchar();x=0; 7 while(c<'0'||c>'9')c=getchar(); 8 w

[Sdoi2008]Sandy的卡片

[Sdoi2008]Sandy的卡片 题目 Sandy和Sue的热衷于收集干脆面中的卡片.然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型.每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型,首先必须要集够N张卡片,对于这N张卡片,如果他们都有一个相同的子串长度为k,则可以兑换一个等级为k的人物模型.相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串.Sandy的卡片数远远小于要求的N,于是Sue决定

luogu 2463 [SDOI2008]Sandy的卡片 kmp || 后缀数组 n个串的最长公共子串

题目链接 Description 给出\(n\)个序列.找出这\(n\)个序列的最长相同子串. 在这里,相同定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串. 思路 参考:hzwer. 法一:kmp 在第一个串中枚举答案串的开头位置,与其余\(n-1\)个串做\(kmp\). 法二:后缀数组 将\(n\)个串拼接起来.二分答案\(len\),将\(height\)分组,\(check\)是否有一组个数\(\geq len\)且落在\(n\)个不同的串中. 注意:\(n\)个串

P2463 [SDOI2008]Sandy的卡片

题目链接 \(Click\) \(Here\) 真的好麻烦啊..事实证明,理解是理解,一定要认认真真把板子打牢,不然调锅的时候真的会很痛苦..(最好是八分钟能无脑把\(SA\)码对的程度\(QAQ\)) 这个题最开始我想的是\(RMQ\)遍历每一个子区间,但是意识到复杂度是\(O(N^2)\)然后就\(GG\)了.怎么说呢,后缀数组和二分似乎是很常见的组合(和莫队也是?),这个题只需要在\(height\)数组里二分\(lcp\)长度即可,\(check\)函数里面处理一下,要让区间内所有原串都

[Luogu2463][SDOI2008]Sandy的卡片

BZOJ权限题qwq Luogu sol "两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串" 其实就是差分一波以后完全相同 所以对输入的数据进行差分,同时记一下每一个位置是属于哪个串的. 记得在串与串中间加入一个没有出现的字符. 求出SA后二分答案\(mid\),问题变成:\(Height\)数组里是否存在一个大于等于\(mid\)的连续段使每个串都在里面出现过. 开桶记录.记一个\(id\)避免每次对桶的清空. code #include<cstdio> #

后缀数组小结?

做了一圈(就那么几道还叫一圈)$SA$的题,小结一下,方便自己看 [NOI2016]优秀的拆分 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 #define mem(x) memset((x),0,sizeof((x))) 6 struct SA{ 7 char s[60005]; 8 int n,m; 9 int t1[60005],t2[600

【SDOI2008】Sandy的卡片

题目描述 Sandy和Sue的热衷于收集干脆面中的卡片. 然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型. 每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型,首先必须要集够N张卡片,对于这N张卡片,如果他们都有一个相同的子串长度为k,则可以兑换一个等级为k的人物模型.相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串. Sandy的卡片数远远小于要求的N,于是Sue决定在Sandy的生日将自己的卡