LA 6856 Circle of digits 解题报告

时间:2021-08-21 09:58:09

题目链接

  先用后缀数组给串排好序。dc3 O(n)

二分答案+贪心check

  答案的长度len=(n+k-1)/k

如果起点为i长为len串大于当前枚举的答案,i的长度取len-1

  从起点判断k个串的长度是否大于等于n

check的时候最多枚举len个起点,每个位置需要枚举n/len个串,时间复杂度O(n),总的时间复杂度O(nlogn+n)

#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
using namespace std;
#define ll long long
#define MAXN 1000009
int sa[MAXN], pos[MAXN], Rank[MAXN], r[MAXN];
int d, n, k;
string s;
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[MAXN], wb[MAXN], wv[MAXN], Ws[MAXN];
inline int c0 (int *r, int a, int b) {
return r[a] == r[b] && r[a + ] == r[b + ] && r[a + ] == r[b + ];
}
int c12 (int k, int *r, int a, int b) {
if (k == ) return r[a] < r[b] || r[a] == r[b] && c12 (, r, a + , b + );
else return r[a] < r[b] || r[a] == r[b] && wv[a + ] < wv[b + ];
}
inline void sort (int *r, int *a, int *b, int n, int m)
{
int i;
for (i = ; i < n; i++) wv[i] = r[a[i]];
for (i = ; i < m; i++) Ws[i] = ;
for (i = ; i < n; i++) Ws[wv[i]]++;
for (i = ; i < m; i++) Ws[i] += Ws[i - ];
for (i = n - ; i >= ; i--) b[--Ws[wv[i]]] = a[i];
return;
}
inline void dc3 (int *r, int *sa, int n, int m)
{
int i, j, *rn = r + n, *san = sa + n, ta = , tb = (n + ) / , tbc = , p;
r[n] = r[n + ] = ;
for (i = ; i < n; i++) if (i % != ) wa[tbc++] = i;
sort (r + , wa, wb, tbc, m);
sort (r + , wb, wa, tbc, m);
sort (r, wa, wb, tbc, m);
for (p = , rn[F (wb[])] = , i = ; i < tbc; i++)
rn[F (wb[i])] = c0 (r, wb[i - ], wb[i]) ? p - : p++;
if (p < tbc) dc3 (rn, san, tbc, p);
else for (i = ; i < tbc; i++) san[rn[i]] = i;
for (i = ; i < tbc; i++) if (san[i] < tb) wb[ta++] = san[i] * ;
if (n % == ) wb[ta++] = n - ;
sort (r, wb, wa, ta, m);
for (i = ; i < tbc; i++) wv[wb[i] = G (san[i])] = i;
for (i = , j = , p = ; i < ta && j < tbc; p++)
sa[p] = c12 (wb[j] % , r, wa[i], wb[j]) ? wa[i++] : wb[j++];
for (; i < ta; p++) sa[p] = wa[i++];
for (; j < tbc; p++) sa[p] = wb[j++];
return;
}
inline bool check (int x) {
for (int i = ; i < d; i++) {
int j = i, t = ;
while (t < k) {
if (Rank[j % n] <= x) j += d;
else
j += d - ;
t++;
}
if (j - i >= n) return ;
}
return ;
}
int main() {
while (scanf ("%d %d", &n, &k) == ) {
cin >> s; s += s;
d = (n + k - ) / k;
for (int i = ; i < (n << ); i++) r[i] = s[i] - '';
r[n << ] = ;
dc3 (r, sa, s.size() + , );
for (int i = , p = ; i <= (n << ); i++)
Rank[sa[i]] = ++p;
for (int i = , p = ; i <= (n << ); i++)
if (sa[i] < n ) pos[++p] = sa[i];
int l = , r = n, last = -;
while (l <= r) {
int mid = (l + r) >> ;
if (check (Rank[pos[mid]]) ) last = pos[mid], r = mid - ;
else
l = mid + ;
}
for (int i = last; i < last + d; i++)
putchar (s[i]);
putchar ();
}
}