題目描述

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

然而，Sue收集卡片是因為卡片上漂亮的人物形象，而Sandy則是為了積攢卡片兌換超炫的人物模型。

每一張卡片都由一些數字進行標記，第i張卡片的序列長度為Mi，要想兌換人物模型，首先必須要集夠N張卡片，對于這N張卡片，如果他們都有一個相同的子串長度為k，則可以兌換一個等級為k的人物模型。相同的定義為：兩個子串長度相同且一個串的全部元素加上一個數就會變成另一個串。

Sandy的卡片數遠遠小于要求的N，于是Sue決定在Sandy的生日將自己的卡片送給Sandy，在Sue的幫助下，Sandy終于集夠了N張卡片，但是，Sandy并不清楚他可以兌換到哪個等級的人物模型，現在，請你幫助Sandy和Sue，看看他們最高能夠得到哪個等級的人物模型。

輸入格式

第一行為一個數N，表示可以兌換人物模型最少需要的卡片數，即Sandy現在有的卡片數

第i+1行到第i+N行每行第一個數為第i張卡片序列的長度Mi，之后j+1到j+1+Mi個數，用空格分隔，分別表示序列中的第j個數

輸出格式

一個數k，表示可以獲得的最高等級。

輸入輸出樣例

輸入 #1 ? 2 2 1 2 3 4 5 9 輸出 #1 2

說明/提示

數據范圍：

30%的數據保證n<=50

100%的數據保證n<=1000,M<=1000,2<=Mi<=101

update：題面上數據范圍mi和m的范圍其實是一個東西... 真實數據范圍:40<=n<=1000,2<=mi<=101,字符串中的每個數字的大小范圍為[0,1864]

?

?

【題目大意】

??給定 n 個序列，求 n 個序列中相同的子串的最大長度，相同的定義是給每個子串里面的每個數加上一個數等于另外一個序列

【思路描述】

? 首先是想到將問題轉化為后綴數組進行一個字符串的操作

? 我們可以想到，當前后兩數之差和另外一個序列中的另外相鄰兩數之差相等時

? 給前者兩個數加一個相同的數就能夠得到另外一個序列

? 所以問題就能夠轉化為 連續相鄰兩數之差相同的最長子串長度

??子串，相同，數字一定屬于一定范圍而且比較小，好，后綴數組能寫

? 把所有序列拼成一個序列，做成一個字符串

? 每個序列中間用一個不同大數隔開

? 然后怎么查找這個長度呢

? 二分這個長度

? 然后考慮 check 函數怎么寫

? 比較 height [ i ] 當 i 的height [ i ] 大于長度的時候，說明這個序列符合要求

? 因為是按照字典序在檢索，所以能夠不錯漏，

? 其實有點像是在找 height 的最小值，同時保證每個最小值在不同的序列中

? 當找到 n 個的時候說明每個序列都有大于等于這個長度的相同子串

? 沒有找到的時候說明沒有，

? 然后二分

? 最后輸出答案，因為我們判斷的是差，而第一個字符沒有被判定

? 所以答案 + 1

?

---

【代碼】

?

注意： 1 . 因為是按照數字的大小排序，所以注意處理差的正負，把所有的負差需要變成正的 ? ? ?同時加一個數不破壞這個序列的屬性，直接加最小值即可 2 . 因為有可能前后兩個數字相同，于是差是0，為了和開頭的0避開，給 0+1? #include<cstdio> #include<iostream> #include<algorithm> #include<cmath> using namespace std; const int MAX = 1010; const int MAXM = 6010; const int MAXN = MAX * (MAXM + 1); const int DOT = 2000; int DOWN = 2000;int n = 0,num,m=-1; int a[MAX][MAXM], len[MAXM],b[MAXN]; int SA[MAXN], height[MAXN]; int rak[MAXN],id[MAXN]; int c[MAXN], x[MAXN], y[MAXN]; bool vis[MAXN]; void get_SA(int *s) {//初始化for (int i = 1; i <= n; i++)++c[x[i] = s[i]];//計算每一個字符的數量，同樣的放在一起for (int i = 2; i <= m; i++)c[i] += c[i - 1];//求前綴和for (int i = n; i >= 1; i--)SA[c[x[i]]--] = i;//從后往前，這樣就能求出最開始順序for (int k = 1; k <= n; k <<= 1){int num = 0;for (int i = n - k + 1; i <= n; i++) y[++num] = i;//把最后幾個字符放進去for (int i = 1; i <= n; i++)//按照順序遍歷if (SA[i] > k)//如果長度大于ky[++num] = SA[i] - k;//把第一個放進去for (int i = 1; i <= m; i++)c[i] = 0;for (int i = 1; i <= n; i++)c[x[i]]++;//x[i]是第一關鍵字for (int i = 2; i <= m; i++)c[i] += c[i - 1];//求前綴和for (int i = n; i >= 1; i--)SA[c[x[y[i]]]--] = y[i], y[i] = 0;swap(x, y);x[SA[1]] = 1; num = 1;for (int i = 2; i <= n; i++)x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? num : ++num;if (num == n) break;m = num;}for (int i = 1; i <= n; i++)rak[SA[i]] = i;return; } void get_height(int *s) {int j, k = 0;for (int i = 1; i <= n; i++) {if (k) k--;j = SA[rak[i] - 1];while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;height[rak[i]] = k;} } int sta[MAXN]; int top = 0; bool check(int x) {while (top) vis[sta[top--]] = 0;for (int i = 1; i <= n; i++){if (height[i] < x){while(top) vis[sta[top--]] = 0;}if (!vis[id[SA[i]]]){vis[id[SA[i]]] = 1;sta[++top] = id[SA[i]];if (top == num)return 1;}}return 0; } int main() {int minn=(1<<32)-1;int r = -1;scanf("%d", &num);for (int i = 1; i <= num; i++){scanf("%d", &len[i]);r = max(r, len[i]);for (int j = 1; j <= len[i]; j++){scanf("%d", &a[i][j]);}}n = 0;for (int i = 1; i <= num; i++){for (int j = 2; j <= len[i]; j++){b[++n] = a[i][j] - a[i][j - 1]+1;id[n] = i;minn = min(b[n], minn);}b[++n] = ++DOWN;}for (int i = 1; i <= n; i++){if (minn <= 0)b[i] -= minn + 1;elseb[i]++;m = max(b[i], m);}get_SA(b);//printf("**\n"); get_height(b);//printf("**\n");int ans=0;int l = 1;while (l <= r){int mid = (l + r) >> 1;if (check(mid)){ans = mid;l = mid + 1;}else{r = mid - 1;}}//printf("**\n");printf("%d", ans+1);return 0; } View Code

?

轉載于:https://www.cnblogs.com/rentu/p/11410359.html

總結

以上是生活随笔為你收集整理的【SDOI2008】Sandy的卡片（后缀数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。