bupt summer training for 16 #8 ——字符串處理

https://vjudge.net/contest/175596#overview

?

A.設第i次出現的位置左右端點分別為Li，Ri

初始化L0 = 0，則有ans = sum{ (L[i] - L[i-1]) * (n + 1 - Ri) }

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int last = 0;

char s[5010];

long long ans;

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for(int i = 1;i <= n;i ++) {
        if(i + 3 <= n && s[i] == 'b' && s[i + 1] == 'e' && s[i + 2] == 'a' && s[i + 3] == 'r') {
            ans += 1ll * (i - last) * (n + 1 - i - 3);
            last = i;
            i += 3;
        }
    }
    cout << ans;
    return 0;
}

?

B.AC自動機板子題，我的板子常數很大

#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 500010;

struct trie {
    int next[maxn][26], fail[maxn], end[maxn];
    int L, root;
    queue <int> q;

    int newnode() {
        for(int i = 0;i < 26;i ++)
            next[L][i] = -1;
        end[L] = 0;
        return L ++;
    }

    void clear() {
        L = 0;
        root = newnode();
    }

    int idx(char c) {
        return c - 'a';
    }

    void insert(char *buf) {
        int len = strlen(buf), now = root, c;
        for(int i = 0;i < len;i ++) {
            c = idx(buf[i]);
            if(next[now][c] == -1)
                next[now][c] = newnode();
            now = next[now][c];
        }
        end[now] ++;
    }

    void build() {
        for(int i = 0;i < 26;i ++) {
            if(next[root][i] == -1)
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                q.push(next[root][i]);
            }
        }
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            for(int i = 0;i < 26;i ++) {
                if(next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] =  next[fail[now]][i];
                    q.push(next[now][i]);
                }
            }
        }
    }

    int query(char *buf) {
        int len = strlen(buf), now = root, res = 0, tmp;
        for(int i = 0;i < len;i ++) {
            tmp = now = next[now][idx(buf[i])];
            while(tmp != root) {
                res += end[tmp];
                end[tmp] = 0;
                tmp = fail[tmp];
            }
        }
        return res;
    }
};

trie ac;

int Case, n;

char buf[1000010];

int main() {
    scanf("%d", &Case);
    while(Case --) {
        scanf("%d", &n), ac.clear();
        while(n --) scanf("%s", buf), ac.insert(buf);
        scanf("%s", buf), ac.build();
        printf("%d\n", ac.query(buf));
    }
    return 0;
}

?

C.考察對KMP中next數組的理解，由一個串重復而來

所以就是max(i - next[i])

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char s[1000010];

int nex[1000010];

int main() {
    int i, j, ans, len;
    while(~scanf("%s", s)) {
        len = strlen(s);
        nex[0] = -1;
        ans = 0;
        for(i = 1;i < len;i ++) {
            j = nex[i - 1];
            while(j >= 0 && s[j + 1] != s[i]) j = nex[j];
            if(s[j + 1] == s[i]) {
                nex[i] = j + 1;
                ans = max(ans, i - nex[i]);
            }
            else nex[i] = -1, ans = max(ans, i + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}

?

D.令a[i] -= a[i + 1]，題目就變成了

求數列中出現次數不小于2次的最長重復子串

后綴數組一個典型問題，二分子串長度即可

(考場上觀察了半天手里板子的接口...然后放棄了)

?

E.先假設要由空串刷成串2，區間DP即可

dp[i][j]代表把 i-j 這段刷成串2需要的最少次數

可能分成幾段分開去刷，所以不能直接ans = dp[L][R] (s1[L] != s2[L]，s1[R] != s2[R])

利用f[i]代表 1-i 這段由串1刷成串2的最少次數

ans = f[n]

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n, dp[110][110], f[110];

char s1[110], s2[110];

int main() {
    while(~scanf("%s %s", s1 + 1, s2 + 1)) {
        n = strlen(s1 + 1);
        memset(dp, 0x3f, sizeof dp);
        for(int d = 1;d <= n;d ++)
            for(int i = 1;i + d - 1 <= n;i ++) {
                int j = i + d - 1;
                if(i == j) dp[i][i] = 1;
                else if(j == i + 1) dp[i][j] = 2 - (s2[i] == s2[j]);
                else {
                    for(int k = i;k < j;k ++)
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] - (s2[i] == s2[k + 1]));
                }
            }
        for(int i = 1;i <= n;i ++) {
            f[i] = dp[1][i];
            if(s1[i] == s2[i]) f[i] = min(f[i - 1], f[i]);
            else 
                for(int j = 1;j < i;j ++)
                    f[i] = min(f[i],  f[j] + dp[j + 1][i]);
        }
        printf("%d\n", f[n]);
    }
    return 0;
}

?

F.簡單的字典樹

#include <cstdio>
#include <cstring>

const int maxn = 6000010;

struct trie {
    int ch[maxn][2];
    int val[maxn];
    int siz;

    void init() {
        siz = 1;
        memset(ch, 0, sizeof ch);
        memset(val, 0, sizeof val);
    }

    void insert(int x) {
        int i, u, c;
        int num[40] = {0};
        for(i = 0;i < 30;i ++)
            num[i] = x & (1 << i);
        for(i = u = 0;i < 30;i ++) {
            c = (num[29 - i] != 0);
            if(!ch[u][c]) ch[u][c] = siz ++;
            u = ch[u][c], val[u] ++;
        }
        val[0] ++;
    }

    void de1ete(int x) {
        int i, u, c;
        int num[40] = {0};
        for(i = 0;i < 30;i ++)
            num[i] = x & (1 << i);
        for(i = u = 0;i < 30;i ++) {
            u = ch[u][(num[29 - i] != 0)];
            val[u] --;
        }
        val[0] --;
    }

    void query(int x) {
        int i, u, c, ans = 0;
        int num[40] = {0};
        for(i = 0;i < 30;i ++)
            num[i] = x & (1 << i);
        for(i = u = 0;i < 30;i ++) {
            c = !(num[29 - i] != 0);
            if(ch[u][c] && val[ch[u][c]]) ans |= (1 << (29 - i)), u = ch[u][c];
            else u = ch[u][!c];
        }
        printf("%d\n", ans);
    }
};

trie now;

int n, x;

char str[5];

int main() {
    now.init();
    now.insert(0);
    scanf("%d", &n);
    while(n --) {
        scanf("%s %d", str, &x);
        switch(str[0]) {
            case '+':now.insert(x);break;
            case '-':now.de1ete(x);break;
            case '?':now.query(x);break;
        }
    }
    return 0;
}

?

G.

?

H.

?

I.

?

J.

?

K.最長回文子串，直接上馬拉車

板子不長，mp[i] - 1 表示以 i 為中心的最長回文串長度

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1000010;

char str[3], s[maxn], ma[maxn], ans[maxn];

int mp[maxn], l, len;

map <char, char> p;

void manacher() {
    l = 0;
    ma[l ++] = '$';
    ma[l ++] = '#';
    for(int i = 0;i < len;i ++)
        ma[l ++] = s[i], ma[l ++] = '#';
    ma[l] = 0;
    int mx = 0, id = 0;
    for(int i = 0;i < l;i ++) {
        mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
        while(ma[i + mp[i]] == ma[i - mp[i]]) mp[i] ++;
        if(i + mp[i] > mx) mx = i + mp[i], id = i;
    }
}

int main() {
    while(~scanf("%s %s", str, s)) {
        len = strlen(s);
        manacher();
        int leng = 0, pos = -1;
        for(int i = 0;i < l;i ++)
            if(mp[i] > leng)
                leng = mp[i], pos = i;
        leng --;
        if(leng == 1) {
            puts("No solution!");
            continue;
        }
        if(pos & 1) {
            printf("%d %d\n", pos / 2 - leng / 2, pos / 2 - leng / 2 + leng - 1);
            for(int i = pos / 2 - leng / 2, j = 1;j <= leng;i ++, j ++)
                ans[j] = s[i];
        }
        else {
            printf("%d %d\n", pos / 2 - leng / 2 - 1, pos / 2 - leng / 2 + leng - 2);
            for(int i = pos / 2 - leng / 2 - 1, j = 1;j <= leng;i ++, j ++)
                ans[j] = s[i];
        }
        ans[leng + 1] = 0;
        int dis = 'a' - str[0];
        for(int i = 0;i < 26;i ++)
            p['a' + i] = 'a' + (i + dis + 26) % 26;
        for(int i = 1;i <= leng;i ++)
            ans[i] = p[ans[i]];
        puts(ans + 1);
    }
    return 0;
}

?

L.變換同D題，然后就是裸的KMP了

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1000010;

char str[3], s[maxn], ma[maxn], ans[maxn];

int mp[maxn], l, len;

map <char, char> p;

void manacher() {
    l = 0;
    ma[l ++] = '$';
    ma[l ++] = '#';
    for(int i = 0;i < len;i ++)
        ma[l ++] = s[i], ma[l ++] = '#';
    ma[l] = 0;
    int mx = 0, id = 0;
    for(int i = 0;i < l;i ++) {
        mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
        while(ma[i + mp[i]] == ma[i - mp[i]]) mp[i] ++;
        if(i + mp[i] > mx) mx = i + mp[i], id = i;
    }
}

int main() {
    while(~scanf("%s %s", str, s)) {
        len = strlen(s);
        manacher();
        int leng = 0, pos = -1;
        for(int i = 0;i < l;i ++)
            if(mp[i] > leng)
                leng = mp[i], pos = i;
        leng --;
        if(leng == 1) {
            puts("No solution!");
            continue;
        }
        if(pos & 1) {
            printf("%d %d\n", pos / 2 - leng / 2, pos / 2 - leng / 2 + leng - 1);
            for(int i = pos / 2 - leng / 2, j = 1;j <= leng;i ++, j ++)
                ans[j] = s[i];
        }
        else {
            printf("%d %d\n", pos / 2 - leng / 2 - 1, pos / 2 - leng / 2 + leng - 2);
            for(int i = pos / 2 - leng / 2 - 1, j = 1;j <= leng;i ++, j ++)
                ans[j] = s[i];
        }
        ans[leng + 1] = 0;
        int dis = 'a' - str[0];
        for(int i = 0;i < 26;i ++)
            p['a' + i] = 'a' + (i + dis + 26) % 26;
        for(int i = 1;i <= leng;i ++)
            ans[i] = p[ans[i]];
        puts(ans + 1);
    }
    return 0;
}