锐客网

  1. 首页 > it技术 > >

字符串|【VOJ1895】 ニニスの守護 后缀数组 DP

动态规划字符串

有一个十进制数字符串S，它是由一个严格上升的数列A拼接而成，要求你构造A使得：
1. 最后一个数最小
2. 在1的基础上字典序最大
【字符串|【VOJ1895】 ニニスの守護 后缀数组 DP】

#include #include #include #include #include #include #define Rep(i, x, y) for (int i = x; i <= y; i ++) #define Dwn(i, x, y) for (int i = x; i >= y; i --) #define RepE(i, x) for (int i = pos[x]; i; i = g[i].nex) using namespace std; typedef long long LL; typedef double DB; const int N = 100005; const LL mod = 100000000000007LL, m2 = mod * 20; int n, sa[N], t1[N], t2[N], rk[N], ht[N], c[N], f[N], g[N], ans, nx[N]; LL hs[N], sh[N]; char s1[N]; LL Mult(LL x, LL y) { LL z = 0; while (y) { if (y & 1) z += x; x <<= 1, y >>= 1; if (x > m2) x %= mod; } return z % mod; } bool cmp(int *r, int x, int y, int l) { return r[x] == r[y] && r[x + l] == r[y + l]; } void Bsa(char *s, int n, int m) { int *x = t1, *y = t2, p = 0; Rep(i, 0, m) c[i] = 0; Rep(i, 0, n) c[ x[i] = s[i] ] ++; Rep(i, 1, m) c[i] += c[i - 1]; Dwn(i, n, 0) sa[ --c[ x[i] ] ] = i; for (int j = 1; p <= n; j <<= 1, m = p) { p = 0; Rep(i, n-j+1, n) y[p ++] = i; Rep(i, 0, n) if (sa[i] >= j) y[p ++] = sa[i] - j; Rep(i, 0, m) c[i] = 0; Rep(i, 0, n) c[ x[y[i]] ] ++; Rep(i, 1, m) c[i] += c[i - 1]; Dwn(i, n, 0) sa[ --c[ x[y[i]] ] ] = y[i]; swap(x, y), p = 1, x[ sa[0] ] = 0; Rep(i, 1, n) x[ sa[i] ] = cmp(y, sa[i], sa[i - 1], j) ? p - 1 : p ++; } } void Bh(char *s, int n) { Rep(i, 0, n) rk[ sa[i] ] = i; } int main() { scanf ("%s", s1), n = strlen(s1), s1[n] = 0; Bsa(s1, n, 300), Bh(s1, n), n --; f[0] = 0, sh[0] = 1; Rep(i, 1, n) sh[i] = sh[i - 1] * 37 % mod; // assert(sh[i] < 0); Dwn(i, n, 0) hs[i] = (hs[i + 1] * 37 + s1[i] - 'a') % mod; // for (int i = 0, lt = 0; i <= n; i = lt) { while (s1[lt] == '0') lt ++; Rep(j, i, lt - 1) nx[j] = lt; if (s1[i] != '0') nx[i] = i, lt ++; } Rep(i, 0, n) { if (i) f[i] = max(f[i], f[i - 1]); int k = f[i]; f[i] = nx[ f[i] ]; int l = i - f[i] + 1, j = nx[i + 1]; LL h1, h2; h1 = hs[ f[i] ] - Mult(hs[ f[i] + l ], sh[l]) + mod; h2 = hs[j] - Mult(hs[j + l], sh[l]) + mod; if (rk[j] < rk[ f[i] ] || h1 % mod == h2 % mod) l ++; f[j + l - 1] = i + 1; f[i] = k; } int p = f[n] - 1; g[ f[n] ] = n + 1; Dwn(i, n, 1) { if (s1[i] == '0') g[i] = max(g[i], g[i + 1]); if (!g[i]) continue ; int j = nx[i], l = g[i] - nx[i]; if (i < l) { g[0] = max(g[0], i); break ; } LL h1, h2; h1 = hs[i - l] - Mult(hs[i], sh[l]) + mod; h2 = hs[j] - Mult(hs[j + l], sh[l]) + mod; if (rk[i - l] > rk[j] || h1 % mod == h2 % mod) l --; Rep(j, i - l, min(p, nx[ f[i - 1] ])) g[j] = i; p = min(p, i - l - 1); } while (ans <= n) { while (ans <= n && s1[ans] == '0') ans ++; if (!g[ans]) g[ans] = n + 1; Rep(i, ans, g[ ans ] - 1) printf("%c", s1[i]); printf(" "); ans = g[ans]; } puts(""); return 0; }



    推荐阅读


    上一篇：数学|【Contra】 矩阵乘法优化 dp

    下一篇：数学|【Topcoder SRM 641】BitToggler 期望 高斯消元