【HDOJ】2890 Longest Repeated subsequence

摘要:
它类似于男子八题的后缀数组。

后缀数组的应用。和男人八题那个后缀数组差不多。

  1 /* 2890 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 const int maxn = 50050;
 44 int a[maxn], b[maxn], aa[maxn];
 45 int pos[maxn], pn;
 46 int rrank[maxn], height[maxn], sa[maxn];
 47 int wa[maxn], wb[maxn], wc[maxn], wv[maxn];
 48 int n, k, at;
 49 
 50 bool cmp(int *r, int a, int b, int l) {
 51     return r[a]==r[b] && r[a+l]==r[b+l];
 52 }
 53 
 54 void da(int *r, int *sa, int n, int m) {
 55     int i, j, *x=wa, *y=wb, *t, p;
 56     
 57     for (i=0; i<m; ++i) wc[i] = 0;
 58     for (i=0; i<n; ++i) wc[x[i]=r[i]]++;
 59     for (i=1; i<m; ++i) wc[i] += wc[i-1];
 60     for (i=n-1; i>=0; --i) sa[--wc[x[i]]] = i;
 61     for (j=1,p=1; p<n; j*=2, m=p) {
 62         for (p=0,i=n-j; i<n; ++i) y[p++] = i;
 63         for (i=0; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
 64         for (i=0; i<n; ++i) wv[i] = x[y[i]];
 65         for (i=0; i<m; ++i) wc[i] = 0;
 66         for (i=0; i<n; ++i) wc[wv[i]]++;
 67         for (i=1; i<m; ++i) wc[i] += wc[i-1];
 68         for (i=n-1; i>=0; --i) sa[--wc[wv[i]]] = y[i];
 69         for (t=x, x=y, y=t, i=1,p=1,x[sa[0]]=0; i<n; ++i)
 70             x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1:p++;
 71     }
 72 }
 73 
 74 void calheight(int *r, int *sa, int n) {
 75     int i, j, k=0;
 76     
 77     for (i=1; i<=n; ++i) rrank[sa[i]] = i;
 78     for (i=0; i<n; height[rrank[i++]]=k)
 79     for (k?k--:0, j=sa[rrank[i]-1]; r[i+k]==r[j+k]; ++k);
 80 }
 81 
 82 bool judge(int bound) {
 83     int i = 1;
 84     int pn = 0;
 85     
 86     while (i <= n) {
 87         if (height[i] < bound) {
 88             at = sa[i-1];
 89             sort(pos, pos+pn);
 90             int kk = 1, p = pos[0];
 91             rep(j, 1, pn) {
 92                 if (pos[j]-p >= bound) {
 93                     p = pos[j];
 94                     ++kk;
 95                 }
 96             }
 97             
 98             if (kk >= k)
 99                 return true;
100             pn = 0;
101             pos[pn++] = sa[i++];
102         } else {
103             pos[pn++] = sa[i++];
104         }
105     }
106     at = sa[n-1];
107     sort(pos, pos+pn);
108     int kk = 1, p = pos[0];
109     rep(j, 1, pn) {
110         if (pos[j]-p >= bound) {
111             p = pos[j];
112             ++kk;
113         }
114     }
115     
116     if (kk >= k)
117         return true;
118     
119     return false;
120 }
121 
122 void printSa(int n) {
123     for (int i=1; i<=n; ++i)
124         printf("%d ", sa[i]);
125     putchar('
');
126 }
127 
128 void printHeight(int n) {
129     for (int i=1; i<=n; ++i)
130         printf("%d ", height[i]);
131     putchar('
');
132 }
133 
134 void solve() {
135     sort(b, b+n);
136     int nn = unique(b, b+n) - b;
137     
138     rep(i, 0, n)
139         aa[i] = lower_bound(b, b+nn, a[i]) - b + 1;
140     aa[n] = 0;
141     
142     da(aa, sa, n+1, nn+4);
143     calheight(aa, sa, n);
144     
145     #ifndef ONLINE_JUDGE
146         // printSa(n);
147         // printHeight(n);
148     #endif
149     
150     int l = 1, r = n, mid;
151     int ans = 0, fr;
152     
153     while (l <= r) {
154         mid = (l + r) >> 1;
155         if (judge(mid)) {
156             ans = mid;
157             fr = at;
158             l = mid + 1;
159         } else {
160             r = mid - 1;
161         }
162     }
163     
164     printf("%d
", ans);
165     rep(i, 0, ans)
166         printf("%d
", b[aa[fr+i]-1]);
167 }
168 
169 int main() {
170     ios::sync_with_stdio(false);
171     #ifndef ONLINE_JUDGE
172         freopen("data.in", "r", stdin);
173         freopen("data.out", "w", stdout);
174     #endif
175     
176     int t;
177     
178     scanf("%d", &t);
179     while (t--) {
180         scanf("%d %d", &n, &k);
181         rep(i, 0, n) {
182             scanf("%d", &a[i]);
183             b[i] = a[i];
184         }
185         solve();
186         if (t)
187             putchar('
');
188     }
189     
190     #ifndef ONLINE_JUDGE
191         printf("time = %d.
", (int)clock());
192     #endif
193     
194     return 0;
195 }

免责声明:文章转载自《【HDOJ】2890 Longest Repeated subsequence》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇【HDOJ】2459 Maximum repetition substring【POJ】1743 Musical Theme下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

linux 查看计算机信息命令

1、 查看物理CPU的个数 #cat /proc/cpuinfo |grep "physical id"|sort |uniq|wc –l2、 查看逻辑CPU的个数 #cat /proc/cpuinfo |grep "processor"|wc –l 3、 查看CPU是几核 #cat /proc/cpuinfo |grep "cores"|uni...

shell脚本实现git和svn统计log代码行

实现的功能 git 根据传入的三个参数:起始统计日期、结束统计日期、git仓库地址。 脚本统计的是git仓库内的所有分支的log信息。 脚本统计的是指定时间段内、每一个提交人指定的git地址的所有分支里的提交代码行的新增情况。 其中代码行可分别统计出:新增的有效代码行数、新增的空行数、新增的注释行数。 并且脚本中还做了相应的提交历史“去重”,避免...

UnixLinux | 总结笔记 | 命令_ WC

wc[选项][参数]     wc命令用来计算数字。利用wc指令我们可以计算文件的Byte数、字数或是列数,若不指定文件名称,或是所给予的文件名为“-”,则wc指令会从标准输入设备读取数据。     -c或--bytes或——chars:只显示Bytes数;    -m或--chars : 打印字符数     -l或——lines:只显示列数;     -w...

【Java虚拟机5】Java内存模型(硬件层面的并发优化基础知识--指令乱序问题)

前言 其实之前大家都了解过volatile,它的第一个作用是保证内存可见,第二个作用是禁止指令重排序。今天系统学习下为什么CPU会指令重排。 存储器的层次结构图 1.CPU乱序执行指令的根源 CPU读取数据的时候会先从离自己最近且速度最快的L1_cache高速缓存取数据,取不到就找L2_cache,还取不到,就读内存。 CPU如果一个cpu在执行的时候需要访...

centos查看系统配置信息

1、linux查看版本当前操作系统发行信息 cat /etc/centos-release  2、查看内核版本uname -a或者cat /proc/version  3、查看CPU参数 1)、查看 CPU 物理个数  grep 'physical id' /proc/cpuinfo | sort -u | wc -l2)、查看 CPU 核心数量  ...

有选择的执行

有选择的执行 例如:which cowsay>/dev/null || echo "not install cowsay" 解析:which后面的cowsay>/dev/null为判断cowsay是否安装语句,已安装则返回0,未安装返回1,并将这个值赋给“ $?”(可通过echo $?查看);|| 表示如果$?为0,则执行后面的语句(ec...