欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

P2852 [USACO06DEC]Milk Patterns G题解

程序员文章站 2022-04-10 09:44:10
P2852 [USACO06DEC]Milk Patterns G题意:正解:这题其实就是求不同后缀间的 有k个后缀 出现相同前缀 的这个前缀的最长长度。可以想到这题是用后缀数组了,其中height数组代表的是sa[i-1]和sa[i]的最长公共前缀长度,相当于是有两个后缀出现相同前缀时这个前缀的最长长度,而这题是针对k来考虑,这样的话,其实能转换成另一个问题了,就是在height数组上,区间长度为k-1,所有区间中最小值的最大值,然后众所周知这是单调队列的经典模板题目。代码:#include&l...

P2852 [USACO06DEC]Milk Patterns G

题意
P2852 [USACO06DEC]Milk Patterns G题解

正解:这题其实就是求不同后缀间的 有k个后缀 出现相同前缀 的这个前缀的最长长度。可以想到这题是用后缀数组了,其中height数组代表的是sa[i-1]和sa[i]的最长公共前缀长度,相当于是有两个后缀出现相同前缀时这个前缀的最长长度,而这题是针对k来考虑,这样的话,其实能转换成另一个问题了,就是在height数组上,区间长度为k-1,所有区间中最小值的最大值,然后众所周知这是单调队列的经典模板题目。

代码

#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define PI acos(-1)
#define eps 1e-8
#define rint register int
using namespace std;
typedef long long LL;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<LL, LL> pll;
typedef pair<double, double> pdd;
typedef map<int, int> mii;
typedef map<char, int> mci;
typedef map<string, int> msi;
template<class T>
void read(T &res) {
  int f = 1; res = 0;
  char c = getchar();
  while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
  while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); }
  res *= f;
}
const int ne[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1};
const int INF = 0x3f3f3f3f;
const int N = 3e5+10;
const LL Mod = 1e9+7;
const int M = 1e6+10;
int s[N];
LL sa[M], t[M], t2[M], c[M], n;
void build_sa(int m) {
  LL *x = t, *y = t2;
  //基数排序
  _for(0, m, i) c[i] = 0;
  _for(0, n, i) c[x[i]=s[i]]++;
  _for(1, m, i) c[i] += c[i-1];
  for(int i = n-1; i >= 0; --i) sa[--c[x[i]]] = i;
  for(int k = 1, p; k <= n; k <<= 1) {
    p = 0;
    //直接利用sa数组排序第二关键字
    _for(n-k, n, i) y[p++] = i;
    _for(0, n, i) if(sa[i] >= k) y[p++] = sa[i] - k;
    //基数排序第一关键字
    _for(0, m, i) c[i] = 0;
    _for(0, n, i) c[x[y[i]]]++;
    _for(1, m, i) c[i] += c[i-1];
    for(int i = n-1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
    //根据sa和y数组计算新的数组
    _for(0, n, i) x[i] ^= y[i], y[i] ^= x[i], x[i] ^= y[i];
    p = 1; x[sa[0]] = 0;
    _for(1, n, i)
      x[sa[i]] = y[sa[i]]==y[sa[i-1]] && (sa[i]+k<n?y[sa[i]+k]:-1)==(sa[i-1]+k<n?y[sa[i-1]+k]:-1) ? p-1 : p++;
    if(p >= n) break;  //以后即使继续倍增,sa也不会改变,退出
    m = p;  //下次基数排序的最大值
  }
// rak数组表示下标为i的后缀排名是多少
// RMQ(height, rank[j]+1, rank[k])可以知道j和k(rak[j] < rak[k])的最长公共前缀长度
int rak[N], height[N];
void getHeight() {
  int j, k = 0;
  _for(0, n, i) rak[sa[i]] = i;
  _for(0, n, i) {
    if(!rak[i]) continue;
    if(k) --k;
    j = sa[rak[i]-1];
    while(s[i+k] == s[j+k]) ++k;
    height[rak[i]] = k;
  }
}
int k, mx;
deque<int> dq;
int main() {
  scanf("%d %d", &n, &k);
  _for(0, n, i) scanf("%d", &s[i]), mx = max(mx, s[i]);
  build_sa(mx+1); getHeight();
  int ans = 0;
  _for(0, n, i) {
    while(!dq.empty() && dq.front() < i-k+2) dq.pop_front();  
    while(!dq.empty() && height[dq.back()] >= height[i]) dq.pop_back();
    dq.push_back(i);
    if(i >= k-2) ans = max(ans, height[dq.front()]);
  }
  printf("%d\n", ans);
  return 0;
}

本文地址:https://blog.csdn.net/qq_43408978/article/details/108558887