bzoj刷题记录4.17-4.21

bzoj2806: [Ctsc2012]Cheat

ctsc神题....之前的代码其实是$O(n^2\lg n)$的活该tle...

二分答案，用后缀自动机判断是否出现，然后dp。

对于任一一个位置$i$，以其结尾能匹配的位置必然成一个区间，设最小的转移位置为$b_i$，则有：

$$dp[i] = \max\{dp[i-1], (dp[j]+(i-j))[j\in [b_i, i-Limit]]\}$$

首先$dp[i] = dp[i-1]$，后面提出一些奇奇怪怪的东西，变成：

$$dp[i] = i+\max\left\{dp[j]-j|j\in [b_i, i-Limit]\right\}$$

由于$b_i$和$i-Limit$都是单调不减的，因此可以用单调队列维护，总复杂度$O(n\lg n)$。然而我自带大常数，居然擦时限过...

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2500005*2;
int chl[MAXN*2][3], fa[MAXN*2], maxl[MAXN*2], root = 1, top = 1, last = 1;
void push(int x)
{
    int np = ++top, p = last; maxl[np] = maxl[p]+1;
    while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
    if (!p) fa[np] = root;
    else {
        int q = chl[p][x];
        if (maxl[q] == maxl[p]+1) fa[np] = q;
        else {
            int nq = ++top; maxl[nq] = maxl[p]+1;
            chl[nq][0] = chl[q][0], chl[nq][1] = chl[q][1];
            fa[nq] = fa[q], fa[q] = fa[np] = nq;
            while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
        }
    }
    last = np;
}
char str[MAXN];
int dp[MAXN], max_back[MAXN];
int n, m;
void match(char str[], int l, int r)
{
    if (l <= 0 || l > r) return;
    int nd = root, ans = 0, len = 0;
    for (int i = l; i <= r; i++) {
        int x = str[i]-'0';
        if (chl[nd][x]) nd = chl[nd][x], len++;
        else {
            while (nd && !chl[nd][x]) nd = fa[nd];
            if (!nd) nd = root, len = 0;
            else len = maxl[nd]+1, nd = chl[nd][x];
        }
        ans = max(ans, len);
        max_back[i] = i-len;
    } 
}
int deq[MAXN], head, tail;
bool do_dp(int L)
{
    int l = strlen(str+1);
    head = 1, tail = 0;
    for (int i = 1; i <= l; i++) {
        dp[i] = dp[i-1];
        int p = i-L;
        if (p >= 0) {
            while (head <= tail && dp[deq[tail]]-deq[tail] < dp[p]-p) tail--;
            deq[++tail] = p;
        }
        while (head <= tail && deq[head] < max_back[i]) head++;
        if (head <= tail) dp[i] = max(dp[i], i+dp[deq[head]]-deq[head]);
    }
    return dp[l]*10 >= l*9;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%s", str);
        for (char *p = str; *p != '\0'; p++)
            push(*p-'0');
        push(2);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%s", str+1);
        memset(max_back, 0, sizeof max_back);
        match(str, 1, strlen(str+1));
        int l = 1, r = strlen(str+1), mid;
        while (l <= r) {
            mid = (l+r)>>1;
            if (do_dp(mid)) l = mid+1;
            else r = mid-1;
        }
        printf("%d\n", l-1);
    }
    return 0;
}

bzoj4310: 跳蚤

又一道神题...
大爷题解传送门：http://www.cnblogs.com/joyouth/p/5352813.html

看完豁然开朗...

kth函数的那套理论总是忘...这次复习一个.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200100*2;
int chl[MAXN][26], fa[MAXN], maxl[MAXN];
long long way[MAXN];
int top = 1, root = 1, last = 1;
void push(int x)
{
    int p = last, np = ++top; maxl[np] = maxl[p] + 1;
    while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
    if (!p) fa[np] = root;
    else {
        int q = chl[p][x];
        if (maxl[q] == maxl[p] + 1) fa[np] = q;
        else {
            int nq = ++top; maxl[nq] = maxl[p]+1;
            memcpy(chl[nq], chl[q], sizeof chl[q]);
            fa[nq] = fa[q], fa[q] = fa[np] = nq;
            while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
        }
    }
    last = np;
}
long long dfs(int nd)
{
    if (!nd) return 0;
    if (way[nd] != -1) return way[nd];
    way[nd] = 1;
    for (int i = 0; i < 26; i++)
        way[nd] += dfs(chl[nd][i]);
    return way[nd];
}
int vis[MAXN];
void display(int nd)
{
    if (!nd || vis[nd]) return;
    vis[nd] = 1;
    printf("--%d-- : fa = %d, maxl = %d, way = %d\n", nd, fa[nd], maxl[nd], dfs(nd));
    for (int i = 0; i < 26; i++)
        if (chl[nd][i])
            printf("+%c-->%d ", i+'a', chl[nd][i]);
    puts("");
    for (int i = 0; i < 26; i++)
        display(chl[nd][i]);
}
int n, k;
char str[MAXN];
void kth(int str[], long long k, int &top)
{
    int nd = root, t = 0; top = 0;
    while (1) {
        for (int i = 0; i < 26; i++) {
            if ((t = chl[nd][i]) == 0) continue;
            if (k > dfs(t)) k -= dfs(t); // 整个略过
            else {
                nd = t, k--; // 去掉仅选择这个字母
                str[++top] = i;
                if (k == 0) return; // 如果结束
                break;
            }
        }
    }
}
int s[MAXN];
unsigned long long hash_tab[MAXN], bas = 31, power[MAXN];
unsigned long long hash_val(unsigned long long hash_tab[], int l, int r)
{
    return hash_tab[r]-hash_tab[l-1]*power[r-l+1];
}
unsigned long long hash_T[MAXN];
int strcmp_hash(int i, int j, int top)
{
    int l = 1, r = min(j-i+1, top), mid;
    while (l <= r) {
        mid = (l+r)>>1;
        if (hash_val(hash_tab, i, i+mid-1) == hash_val(hash_T, 1, mid)) l = mid+1;
        else r = mid-1;
    }
    if (l > min(j-i+1, top)) { return j-i+1<=top; }
    return str[i+l-1] < s[l]+'a';
}
bool judge(long long k, int lim)
{
    int top;
    kth(s, k, top);
    for (int i = 1; i <= top; i++) hash_T[i] = hash_T[i-1]*bas+s[i];
    int last_end = strlen(str+1), cnt = 1;
    for (int j = strlen(str+1); j >= 1; j--) {
        if (strcmp_hash(j, last_end, top)) continue;
        else if (strcmp_hash(j,j,top)) last_end = j, cnt++;
        else return 0;
    }
    return cnt <= lim;
}
int main()
{
    memset(vis, 0, sizeof vis);
    memset(way, -1, sizeof way); // 包括空串的总状态数
    scanf("%d", &k);
    scanf("%s", str+1);
    power[0] = 1;
    int l = strlen(str+1);
    for (int i = 1; i <= l; i++) power[i] = power[i-1]*bas;
    for (int i = 1; i <= l; i++)
        hash_tab[i] = hash_tab[i-1]*bas+(str[i]-'a');
    for (char *p = str+1; *p != '\0'; ++p)
        push(*p-'a');
    long long lp = 1, rp = dfs(root)-1, mid;
    while (lp <= rp) {
        mid = (lp+rp)>>1;
        if (judge(mid, k)) rp = mid-1;
        else lp = mid+1;
    }
    int top;
    kth(s, rp+1, top);
    for (int i = 1; i <= top; i++)
        putchar(s[i]+'a');
    puts("");
    return 0;
}