模拟赛 - 省选预热三

2015.11.21 13:26 Sat| 13 visits oi_2016| 2016_竞赛日常| Text

这一次是字符串专场。题目难度并不大,140142 和 xjk 都 AK 啦!我由于开开心心地睡过了头,第一题并没有做啊,然而听说是水题……

BZOJ1212 [HNOI2004]L语言

将单词逆序插入到 trie 树中。然后枚举文本串的每一位,在 trie 树中向前查询,得到前 x 位是否能够匹配。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

struct node
{
    node *son[26];
    bool end;
    node() : end(0) { memset(son, 0, sizeof son); }
};

node *root = new node();

void insert(char str[])
{
    node *p = root;
    while (*str)
    {
        if (!p->son[*str - 'a'])
            p->son[*str - 'a'] = new node();
        p = p->son[*str - 'a']; ++str;
    }
    p->end = true;
}

char str[1100000];
bool dp[1100000];
int n, m, len, ans;

bool check(int t)
{
    node *p = root;
    for (int i = 0; i < t; ++i)
    {
        if (!p->son[str[t - i] - 'a']) return false;
        p = p->son[str[t - i] - 'a'];
        if (p->end && dp[t - i - 1]) return true;
    }
    return false;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", str);
        len = strlen(str);
        reverse(str, str + len);
        insert(str);
    }
    gets(str);
    while (m--)
    {
        gets(str + 1);
        len = strlen(str + 1);
        dp[0] = 1; ans = 0;
        for (int i = 1; i <= len; ++i)
            if ((dp[i] = check(i))) ans = i;
        printf("%d\n", ans);
    }
    return 0;
}

[SDOI2008]Sandy的卡片

将序列差分一下之后问最长公共子串。虽然串的数量有点多,可是它们都很短。于是和 CLJ 的例题 LCS2 一样做就好了。用 map 存边。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;

int n, len, tot, ans, a[1005];

struct node
{
    node *pre;
    map<int, node*> son;
    int len, ans, ans1;
    node(int _len = 0) : len(_len), ans(_len), ans1(0) {}
    void *operator new(size_t s);
} sam[405], *pos;

void *node::operator new(size_t s) { return pos++; }

node *root, *last, *top[405];
vector<node*> v[405];

void reset()
{
    pos = sam;
    last = root = new node();
}

void insert(int c)
{
    node *p = last, *np = new node(p->len + 1);
    while (p && p->son.find(c) == p->son.end())
        p->son[c] = np, p = p->pre;
    if (!p) np->pre = root;
    else
    {
        node *q = p->son[c];
        if (q->len == p->len + 1) np->pre = q;
        else
        {
            node *nq = new node(p->len + 1);
            nq->son = map<int, node*>(q->son);
            nq->pre = q->pre;
            np->pre = q->pre = nq;
            while (p && p->son[c] == q)
                p->son[c] = nq, p = p->pre;
        }
    }
    last = np;
}

void topsort()
{
    int temp = 0;
    for (node *i = sam; i != pos; ++i)
        v[i->len].push_back(i), temp = max(temp, i->len);
    for (int i = 0; i <= temp; ++i)
        for (int j = 0; j < (int)v[i].size(); ++j)
            top[tot++] = v[i][j];
}

int getans()
{
    node *p = root;
    int re = 0, now = 0;
    for (int i = 0; i < len; ++i)
    {
        if (p->son.find(a[i]) != p->son.end())
            ++now, p = p->son[a[i]];
        else
        {
            while (p && p->son.find(a[i]) == p->son.end())
                p = p->pre;
            if (!p) now = 0, p = root;
            else now = p->len + 1, p = p->son[a[i]];
        }
        p->ans1 = max(p->ans1, now);
    }
    for (int i = tot - 1; i >= 1; --i)
    {
        top[i]->ans = min(top[i]->ans, top[i]->ans1);
        top[i]->pre->ans1 = max(top[i]->ans1, top[i]->pre->ans1);
        top[i]->ans1 = 0; re = max(re, top[i]->ans);
    }
    return re;
}

int main()
{
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
    cin >> n;
    if (n == 1)
    {
        scanf("%d", &len);
        printf("%d\n", len);
        return 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &len);
        for (int j = 0; j < len; ++j)
            scanf("%d", &a[j]);
        --len;
        for (int j = 0; j < len; ++j)
            a[j] = a[j + 1] - a[j];
        if (i == 1)
        {
            reset();
            for (int j = 0; j < len; ++j)
                insert(a[j]);
            topsort();
        }
        else
        {
            ans = getans();
        }
    }
    printf("%d\n", ans + 1);
    return 0;
}

BZOJ3530 [Sdoi2014]数数

AC 自动机+数位DP。这大概是我的第一道自己写明白了的数位DP吧。也就是这道题让宋爷和小萝莉爆零了。

为了便于叙述,设 N=65432。那么答案就是 "0xxxx" + "1xxxx" + ... + "5xxxx" + "60xxx" + ... + "64xxx" + "650xx" + ... + "6540x" + ... + "65432" + "xxxx" + "xxx" + "xx" + "x" - "0xxxx" - ... - "0x" - "0",其中 ooxxx 表示当前从在自动机上匹配到 oo 的结点开始再随便走 len(xxx) 步的方案数。先 DP 预处理出从自动机上每一个结点开始随便走 1...l 步的方案数,之后就可以很方便地查询答案了。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

struct trie
{
    struct node
    {
        node *son[10], *pre;
        int len, vis; int dp[1205];
        bool end;
        node(int _len = 0) : len(_len), vis(-1), end(0)
        {
            memset(son, 0, sizeof son); pre = 0;
            memset(dp, 0, sizeof dp);
        }
    };

    node *root;

    trie() { root = new node(); }

    void insert(char str[])
    {
        node *p = root;
        while (*str)
        {
            if (!p->son[*str - '0'])
                p->son[*str - '0'] = new node(p->len + 1);
            p = p->son[*str - '0']; ++str;
        }
        p->end = true;
    }

    void build_ac()
    {
        queue<node *> q;
        root->pre = root;
        for (int i = 0; i < 10; ++i)
            if (!root->son[i]) root->son[i] = root;
            else root->son[i]->pre = root, q.push(root->son[i]);
        while (!q.empty())
        {
            node *t = q.front(); q.pop();
            t->end |= t->pre->end;
            for (int i = 0; i < 10; ++i)
                if (!t->son[i]) t->son[i] = t->pre->son[i];
                else t->son[i]->pre = t->pre->son[i], q.push(t->son[i]);
        }
    }

    void predfs(node *p)
    {
        p->vis = 0;
        p->dp[0] = 1;
        for (int i = 0; i < 10; ++i)
        {
            if (!p->son[i]->end && p->son[i]->vis != 0)
                predfs(p->son[i]);
        }
    }

    void dfs(node *p, int t)
    {
        p->vis = t;
        for (int i = 0; i < 10; ++i)
        {
            p->dp[t] = (p->dp[t] + p->son[i]->dp[t - 1]) % mod;
            if (!p->son[i]->end && p->son[i]->vis != t)
                dfs(p->son[i], t);
        }
    }

    int query(node *p, char str[], int d)
    {
        if (p->end) return 0;
        if (d == -1) return 1;
        int re = query(p->son[*str - '0'], str + 1, d - 1);
        for (int i = 0; i < *str - '0'; ++i)
            re = (re + p->son[i]->dp[d]) % mod;
        return re;
    }
} t;

char ori[1505], str[1505];
int n, m;

int main()
{
    scanf("%s", ori);
    n = strlen(ori);
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%s", str);
        t.insert(str);
    }
    t.build_ac();
    t.predfs(t.root);
    for (int i = 1; i <= n; ++i)
        t.dfs(t.root, i);
    int ans = 0;
    ans = t.query(t.root->son[ori[0] - '0'], ori + 1, n - 2);
    for (int i = 1; i < ori[0] - '0'; ++i)
        ans = (ans + t.root->son[i]->dp[n - 1]) % mod;
    for (int i = 1; i < n; ++i)
        ans = ((ans + t.root->dp[i]) % mod
            - t.root->son[0]->dp[i - 1] + mod) % mod;
    cout << ans << endl;
    return 0;
}