假淘宝网站怎么做,企业做网站属于广告宣传费吗,做网站推广的工资,wordpress 文章 目录题目描述 Sandy和Sue的热衷于收集干脆面中的卡片。 然而#xff0c;Sue收集卡片是因为卡片上漂亮的人物形象#xff0c;而Sandy则是为了积攒卡片兑换超炫的人物模型。 每一张卡片都由一些数字进行标记#xff0c;第i张卡片的序列长度为Mi#xff0c;要想兑换人物模型#…题目描述 Sandy和Sue的热衷于收集干脆面中的卡片。 然而Sue收集卡片是因为卡片上漂亮的人物形象而Sandy则是为了积攒卡片兑换超炫的人物模型。 每一张卡片都由一些数字进行标记第i张卡片的序列长度为Mi要想兑换人物模型首先必须要集够N张卡片对于这N张卡片如果他们都有一个相同的子串长度为k则可以兑换一个等级为k的人物模型。相同的定义为两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。 Sandy的卡片数远远小于要求的N于是Sue决定在Sandy的生日将自己的卡片送给Sandy在Sue的帮助下Sandy终于集够了N张卡片但是Sandy并不清楚他可以兑换到哪个等级的人物模型现在请你帮助Sandy和Sue看看他们最高能够得到哪个等级的人物模型。 输入输出格式 输入格式 第一行为一个数N表示可以兑换人物模型最少需要的卡片数即Sandy现在有的卡片数 第i1行到第iN行每行第一个数为第i张卡片序列的长度Mi之后j1到j1Mi个数用空格分隔分别表示序列中的第j个数 输出格式 一个数k表示可以获得的最高等级。 输入输出样例 输入样例#1 复制 2
2 1 2
3 4 5 9输出样例#1 复制 2 说明 数据范围 30%的数据保证n50 100%的数据保证n1000,M1000,2Mi101 题意 给定几串序列问他们最长公共子序列是多长。 思路 类似之前做的Muisical, Themehttps://www.cnblogs.com/wyboooo/p/9865919.html 都是可以通过增加一个定值所以只需要处理间隔。 不同的地方在于这个题目是多个不同的串。可以想到的是是不是可以将这些串拼接起来。 拼起来就需要考虑一个问题找到的这个串应该要避免他们跨越了拼接的那个间隔。 所以首先我们应该要用一个原来的串中从来没有出现过的字符来分隔两个串。 其次当我们二分寻找答案的时候应该要考虑我们找到的这个区间他们表示的后缀的首字母也就是sa[i]是不是分别属于n个串。 所以我们要标好每个位置属于哪个串。 1 #include iostream2 #include set3 #include cmath4 #include stdio.h5 #include cstring6 #include algorithm7 #include vector8 #include queue9 #include map10 using namespace std;11 typedef long long LL;12 #define inf 0x7f7f7f7f13 14 const int maxn 1005;15 int a[maxn][maxn], s[maxn * maxn], s_len[maxn], id[maxn * maxn], vis[maxn];16 int sa[maxn * maxn];17 int t1[maxn * maxn], t2[maxn * maxn], c[maxn * maxn];18 int rnk[maxn * maxn], height[maxn * maxn];19 int n, len;20 21 void build_sa(int s[], int n, int m)22 {23 int i, j, p, *x t1, *y t2;24 for(i 0; i m; i)c[i] 0;25 for(i 0; i n; i)c[x[i] s[i]];26 for(i 1; i m; i)c[i] c[i - 1];27 for(i n - 1; i 0; i--)sa[--c[x[i]]] i;28 for(j 1; j n; j 1){29 p 0;30 for(i n - j; i n; i)y[p] i;31 for(i 0; i n; i)if(sa[i] j)y[p] sa[i] - j;32 for(i 0; i m; i)c[i] 0;33 for(i 0; i n; i)c[x[y[i]]];34 for(i 1; i m; i)c[i] c[i - 1];35 for(i n - 1; i 0; i--)sa[--c[x[y[i]]]] y[i];36 swap(x, y);37 p 1;38 x[sa[0]] 0;39 for(i 1; i n; i){40 x[sa[i]] y[sa[i - 1]] y[sa[i]] y[sa[i - 1] j] y[sa[i] j] ? p - 1 : p;41 }42 if(p n)break;43 m p;44 }45 }46 47 void get_height(int s[], int n)48 {49 int i, j, k 0;50 for(i 0; i n; i)rnk[sa[i]] i;51 for(i 1; i n; i){52 if(k)k--;53 j sa[rnk[i] - 1];54 while(s[i k] s[j k])k;55 height[rnk[i]] k;56 }57 }58 int sta[maxn * maxn], top;59 bool check(int mid)60 {61 while(top)vis[sta[top--]] false;62 for(int i 1; i len; i){63 if(height[i] mid){64 while(top)vis[sta[top--]] false;65 }66 if(!vis[id[sa[i]]]){67 vis[id[sa[i]]] true;68 sta[top] id[sa[i]];69 if(top n)return true;70 }71 }72 return false;73 }74 75 int main()76 {77 scanf(%d, n);78 len 0;79 int mmx -1;80 for(int i 1; i n; i){81 vis[i] false;82 scanf(%d, s_len[i]);83 for(int j 1; j s_len[i]; j){84 scanf(%d, a[i][j]);85 if(j)mmx max(mmx, a[i][j] - a[i][j - 1]);86 }87 }88 int mmin inf;89 for(int i 1; i n; i){90 for(int j 2; j s_len[i]; j){91 s[len] a[i][j] - a[i][j - 1];92 id[len] i;93 mmin min(mmin, s[len]);94 }95 s[len] mmx;96 }97 for(int i 1; i len; i){98 s[i] s[i] - mmin 1;99 //couts[i]endl;
100 }
101
102 build_sa(s, len 1, 2000);
103 /*for(int i 1; i len; i){
104 coutsa[i]endl;
105 }*/
106 get_height(s, len);
107 /*coutlenendl;
108 for(int i 2; i len; i){
109 coutheight[i]endl;
110 }*/
111 //coutlenendl;
112 int st 0, ed len, ans -1;
113 while(st ed){
114 int mid (st ed) / 2;
115 if(check(mid)){
116 st mid 1;
117 ans mid;
118 }
119 else{
120 ed mid - 1;
121 }
122 }
123
124 printf(%d\n, ans 1);
125 return 0;
126 } 转载于:https://www.cnblogs.com/wyboooo/p/9876295.html
