关于我想了好久才想出这题咋做这档事 - 9

发表于 分类于
UVA1401, CF955D, CF985F, [JSOI2007]文本生成器, [HEOI2012]旅行问题, UVA1519, BZOJ2462/BZOJ2351, Leetcode201, HDU3336, POJ2752 题解

#Prob. 1 UVA1401 Remember the Word

Time Limit: 3s | Memory Limit: N/A MB

#题意简述

给定一个字符串 \(S(|S|\leq3\cdot10^5)\) 以及 \(n(n\leq4000)\) 个单词 \(T_i(T_i\leq100)\)，问有多少种方式将 \(S\) 划分为若干个 \(T_i\) 拼接的形式，答案对 \(20071027\) 取模。

#大体思路

考虑在 trie 上进行 DP，设 \(\ell\) 表示 \(|S|\)，\(f_{i}\) 表示拼出 \(S[i\dots\ell]\)（字符串从 \(0\) 开始编号，设 \(S_{\ell}\) 为空）可行的方案数，显然有初始状态 \(f_{\ell}=1\)，然后考虑从大到小枚举还需拼出的字符串的长度，从该字符串结尾开始向后寻找可行的单词，进行 DP 即可。

#Code

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
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 500010;
const int MOD = 20071027;
const int INF = 0x3fffffff;

struct Trie {int ch[30], tag;} t[N];

int cnt, n, f[N], T;
char s[N];

inline void insert(char *S) {
    int p = 0, len = strlen(S);
    for (int i = 0; i < len; ++ i) {
        int k = S[i] - 'a';
        if (!t[p].ch[k]) t[p].ch[k] = ++ cnt;
        p = t[p].ch[k];
    }
    t[p].tag |= true;
}

inline void clear() {
    for (int i = 0; i <= cnt; ++ i) {
        for (int j = 0; j < 26; ++ j)
          t[i].ch[j] = 0;
        t[i].tag = 0;
    }
    mset(f, 0); cnt = 0;
}

int main() {
    while (scanf("%s", s) != EOF) {
        clear(); scanf("%d", &n);
        for (int i = 1; i <= n; ++ i) {
            char S[N]; scanf("%s", S);
            insert(S);
        }
        int len = strlen(s); f[len] = 1;
        for (int i = len - 1; i >= 0; -- i) {
            int p = 0;
            for (int j = i; j < len; ++ j) {
                int k = s[j] - 'a';
                if (!t[p].ch[k]) break;
                else p = t[p].ch[k];
                if (t[p].tag) (f[i] += f[j + 1]) %= MOD;
            }
        }
        printf("Case %d: %d\n", ++ T, f[0]);
    }
    return 0;
}

#Prob. 2 CF955D Scissors

Time Limit: 1s | Memory Limit: 256MB

#题意简述

给定两个串 \(s,t\) 和整数 \(k(|t|\leq2\cdot k\leq|s|\leq5\cdot10^5)\)，你可以在 \(s\) 中取出任意的两个不相交的串，将它们按顺序拼在一起形成一个新串。求一种取串的方案使得 \(t\) 是新串的子串。

#大体思路

注意到如果 \(t\) 是得到的新串的子串，那么一定是将 \(t\) 分为了两部分（可能存在一部分是空串），于是我们对于每个前缀和后缀都求出最靠前/靠后的出现位置，最后尝试进行组合即可。

来考虑如何求出对应位置，考虑当前缀长度增加时，显然如果较短的前缀都不行的位置，较长的前缀一定也不行，于是这个位置一定是递增的，反之亦然。

于是我们就可以通过维护一个当前匹配位置的指针结合 Hash 求得上面两种位置。

总体时间复杂度为 \(O(|s|+|t|)\).

#Code

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
#define ll long long
#define ull unsigned long long
#define mset(l,x) memset(l,x,sizeof(l))

const int N = 600010;
const ull BASE = 131;
const int INF = 0x3fffffff;

char s[N], t[N];
int n, m, k, prep[N], sufp[N];
ull hs[N], ht[N], p[N];

inline ull Gethash(ull hash[], int l, int len) {
    return hash[l + len - 1] - hash[l - 1] * p[len];
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    scanf("%s%s", s + 1, t + 1); p[0] = 1;
    for (int i = 1; i <= n; ++ i)
      hs[i] = hs[i - 1] * BASE + (ull)(s[i] - 'a' + 1);
    for (int i = 1; i <= m; ++ i)
      ht[i] = ht[i - 1] * BASE + (ull)(t[i] - 'a' + 1);
    for (int i = 1; i <= n; ++ i) p[i] = p[i - 1] * BASE;
    mset(prep, -1); mset(sufp, -1);
    for (int x = 1, l = 1; x <= m; ++ x) {
        while (l + x - 1 <= n && Gethash(hs, l, x) != ht[x]) ++ l;
        if (l + x - 1 <= n) prep[x] = l + x - 1;
        else break;
    }
    for (int x = 1, l = k; x < m; ++ x) {
        if (prep[x] >= k || prep[x] == -1) break;
        while (l <= n && (x > l || Gethash(hs, l - x + 1, x) != ht[x])) ++ l;
        if (l <= n) prep[x] = l;
        else prep[x] = -1;
    }
    prep[0] = k;
    if (~prep[m]) prep[m] = max(prep[m], k);
    for (int x = 1, l = n; x <= m; ++ x) {
        while (l - x + 1 >= 1 &&
               Gethash(hs, l - x + 1, x) != Gethash(ht, m - x + 1, x)) -- l;
        if (l - x + 1 >= 1) sufp[m - x + 1] = l - x + 1;
        else break;
    }
    for (int x = 1, l = n - k + 1; x < m; ++ x) {
        if (sufp[m - x + 1] <= n - k + 1 || sufp[m - x + 1] == -1) break;
        while (l >= 1 && (l > n - x + 1 || 
               Gethash(hs, l, x) != Gethash(ht, m - x + 1, x))) -- l;
        if (l >= 1) sufp[m - x + 1] = l;
        else sufp[m - x + 1] = -1;
    }
    if (~sufp[1]) sufp[1] = min(sufp[1], n - k + 1);
    sufp[m + 1] = n - k + 1;
    for (int i = 0; i <= m; ++ i) {
        if (prep[i] == -1 || sufp[i + 1] == -1) continue;
        if (prep[i] >= sufp[i + 1]) continue;
        if (i > k || m - i > k) continue;
        if (i != 0 && i != m)
            if (prep[i] < k || n - sufp[i + 1] + 1 < k) continue;
        printf("Yes\n%d %d", prep[i] - k + 1, sufp[i + 1]);
        return 0;
    }
    printf("No");
    return 0;
}

#Prob. 3 CF985F Isomorphic Strings

Time Limit: 3s | Memory Limit: 256MB

#题意简述

我们定义两个串 \(s\) 和 \(t\) 相似当且仅当存在一种映射，将 \(s\) 中出现的每种字符映射到另一种字符上，按此映射进行变化，得到的字符串为 \(t\)。

现给出一个长度为 \(n(n\leq2\cdot10^5)\) 的字符串 \(S\)，以及 \(m(m\leq2\cdot10^5)\) 次询问，每次询问三个数 \(x,y,k\)，表示询问从 \(x\) 开始的长度为 \(k\) 的字符串与从 \(y\) 开始的长度为 \(k\) 的字符串是否相似。

#大体思路

我们可以考虑用 01 串去表示每个字符对应的位置序列（这个位置是该字符则是 1 否则是 0），于是注意到相似意味着将两个串的所有位置序列从小到大排序后，相同位置上对应的位置序列应当是相同的，我们可以用类似字符串哈希的方法对位置序列进行处理。

#Code

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
#define ll long long
#define ull unsigned long long
#define mset(l,x) memset(l,x,sizeof(l))
using namespace std;

const int N = 300010;
const ull BASE = 131;
const ull MOD = 1e9 + 7;
const int INF = 0x3fffffff;

char s[N];
int n, q, x, y, len;
ull h[N][30], p[N], a[N], b[N];

int main() {
    scanf("%d%d%s", &n, &q, s + 1);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= 26; ++ j)
        h[i][j] = ((h[i - 1][j] * BASE) % MOD + (ull)((s[i] - 'a' + 1) == j)) % MOD;
    p[0] = 1;
    for (int i = 1; i <= n; ++ i) p[i] = (p[i - 1] * BASE) % MOD;
    while (q --) {
        bool ok = true;
        scanf("%d%d%d", &x, &y, &len);
        for (int i = 1; i <= 26; ++ i) {
            a[i] = (h[x + len - 1][i] - (h[x - 1][i] * p[len]) % MOD + MOD) % MOD;
            b[i] = (h[y + len - 1][i] - (h[y - 1][i] * p[len]) % MOD + MOD) % MOD;
        }
        sort(a + 1, a + 27); sort(b + 1, b + 27);
        for (int i = 1; i <= 26; ++ i)
          if (a[i] != b[i]) {ok = false; break;}
        if (ok) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

#Prob. 4 [JSOI2007]文本生成器

Time Limit: 1s | Memory Limit: 128MB

#题意简述

给定一个有 \(n(n\leq60)\) 个单词的字典（单词长度不超过 \(100\)），问有多少个长度为 \(m(m\leq100)\) 的文本是可读的，我们定义一段文本是可读的当且仅当存在至少一个字典中的词在该文本中出现。

#大体思路

显然正难反易，我们可以求所有不可读的文本数量，然后用总数减去即可。

计数考虑在 AC 自动机上进行 DP，很套路的状态是 \(f_{i,j}\) 表示当前处理的长度为 \(i\)，当前在 AC 自动机的 \(j\) 号节点上，显然有 \(f_{0,0}=1\)，然后直接在 AC 自动机上进行转移即可，注意不要经过有终点标记的节点。

#Code

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
const int N = 10010;
const int MOD = 1e4 + 7;
const int INF = 0x3fffffff;

struct Trie {int ch[30], fail, tag;};
struct AC {
    Trie t[N]; int cnt;

    inline AC() {cnt = 0;}
    inline void insert(char *s) {
        int p = 0, len = strlen(s);
        for (int i = 0; i < len; ++ i) {
            int k = s[i] - 'A';
            if (!t[p].ch[k]) t[p].ch[k] = ++ cnt;
            p = t[p].ch[k];
        }
        t[p].tag |= true;
    }

    inline void build() {
        queue <int> q;
        for (int i = 0; i < 26; ++ i)
          if (t[0].ch[i]) q.push(t[0].ch[i]);
        while (q.size()) {
            int now = q.front(); q.pop();
            for (int i = 0; i < 26; ++ i)
              if (t[now].ch[i]) {
                  t[t[now].ch[i]].fail = t[t[now].fail].ch[i];
                  t[t[now].ch[i]].tag |= t[t[t[now].fail].ch[i]].tag;
                  q.push(t[now].ch[i]);
              } else t[now].ch[i] = t[t[now].fail].ch[i];
        }
    }
} ac;

int n, m, f[N][N], ans;
char s[N];

inline int fpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) (res *= a) %= MOD;
        b >>= 1, (a *= a) %= MOD;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i)
      scanf("%s", s), ac.insert(s);
    ac.build(); f[0][0] = 1;
    for (int i = 1; i <= m; ++ i)
      for (int j = 0; j <= ac.cnt; ++ j)
        for (int k = 0; k < 26; ++ k)
          if (!ac.t[ac.t[j].ch[k]].tag)
            (f[i][ac.t[j].ch[k]] += f[i - 1][j]) %= MOD;
    for (int i = 0; i <= ac.cnt; ++ i)
      (ans += f[m][i]) %= MOD;
    printf("%d", (fpow(26, m) - ans + MOD) % MOD);
    return 0;
}

#Prob. 5 [HEOI2012]旅行问题

Time Limit: s | Memory Limit: MB

#大体思路

不难发现我们要找的也就是两个串的最长公共后缀，这与 AC 自动机 fail 边所指向的节点的定义相吻合，于是只需要找到建出 AC 自动机的 fail 树，找到对应的 LCA 即可。

#Code

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
#define ll long long

const int N = 1000010;
const int MOD = 1e9 + 7;
const int INF = 0x3fffffff;

struct Edge {int u, v, nxt;} e[N];
struct Trie {int ch[26], fail;};

int n, ecnt = 1, head[N], m; ll ans[N];
vector<int> ds[N];

inline void add(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

struct AC_automaton {
    Trie t[N]; int cnt;

    inline AC_automaton() {cnt = 0, t[0].fail = -1;}
    inline void insert(char *s, int id) {
        int p = 0, len = strlen(s);
        ds[id].push_back(0);
        for (int i = 0; i < len; ++ i) {
            int k = s[i] - 'a';
            if (!t[p].ch[k]) {
                t[p].ch[k] = ++ cnt;
                ans[cnt + 1] = (ans[p + 1] * 26 % MOD + (ll)k) % MOD;
            }
            p = t[p].ch[k]; ds[id].push_back(p + 1);
        }
    }

    inline void build() {
        queue <int> q;
        for (int i = 0; i < 26; ++ i)
          if (t[0].ch[i]) q.push(t[0].ch[i]);
        while (q.size()) {
            int now = q.front(); q.pop();
            for (int i = 0; i < 26; ++ i)
              if (t[now].ch[i]) {
                  t[t[now].ch[i]].fail = t[t[now].fail].ch[i];
                  q.push(t[now].ch[i]);
              } else t[now].ch[i] = t[t[now].fail].ch[i];
        }
    }

    inline void build_tree() {
        for (int i = 1; i <= cnt; ++ i) add(t[i].fail + 1, i + 1);
    }
} ac;

int dfn[N], son[N], siz[N], top[N], T, f[N], d[N];

void dfs1(int x, int fa) {
    siz[x] = 1, f[x] = fa, d[x] = d[fa] + 1;
    for (int i = head[x]; i; i = e[i].nxt)
      if (e[i].v != fa) {
          dfs1(e[i].v, x);
          siz[x] += siz[e[i].v];
          if (siz[e[i].v] > siz[son[x]])
            son[x] = e[i].v;
      }
}

void dfs2(int x, int t) {
    dfn[x] = ++ T, top[x] = t;
    if (!son[x]) {return;} dfs2(son[x], t);
    for (int i = head[x]; i; i = e[i].nxt)
      if (e[i].v != f[x] && e[i].v != son[x])
        dfs2(e[i].v, e[i].v);
}

inline int LCA(int a, int b) {
    while (top[a] != top[b]) {
        if (d[top[a]] < d[top[b]]) swap(a, b);
        a = f[top[a]];
    }
    if (d[a] < d[b]) {swap(a, b);} return b;
}

int main() {
    scanf("%d", &n); char s[N];
    for (int i = 1; i <= n; ++ i) {
        scanf("%s", s);
        ac.insert(s, i);
    }
    ac.build(); ac.build_tree();
    dfs1(1, 0); dfs2(1, 1);
    scanf("%d", &m);
    while (m --) {
        int i, j, k, l;
        scanf("%d%d%d%d", &i, &j, &k, &l);
        int lca = LCA(ds[i][j], ds[k][l]);
        printf("%d\n", ans[lca]);
    }
    return 0;
}

#Prob. 6 UVA1519 Dictionary Size

Time Limit: 3s | Memory Limit: N/A MB

#Prob. 7 BZOJ2462 矩阵模板 / BZOJ2351 Matrix

Time Limit: N/A s | Memory Limit: N/A MB

#题意简述

给定一个 \(M(M\leq1000)\) 行 \(N(N\leq1000)\) 列的 01 矩阵，以及 \(Q\) 个 \(A(A\leq100)\) 行 \(B(A\leq100)\) 列的 01 矩阵，你需要求出这 \(Q\) 个矩阵哪些在原矩阵中出现过。

#大体思路

二维哈希板子。

#Code

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
#define ll long long
#define ull unsigned long long
#define mset(l,x) memset(l,x,sizeof(l))
using namespace std;

const int N = 1010;
const int INF = 0x3fffffff;
const int MOD = 1e8 + 7;
const ull b1 = 19260817;
const ull b2 = 998244353;

int n, m, a, b, q;
ull r[N][N], c[N][N], p1[N * N], p2[N * N];
bool h[MOD + 1];

int main() {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= a * b; ++ i)
      p1[i] = p1[i - 1] * b1, p2[i] = p2[i - 1] * b2;
    for (int i = 1; i <= n ; ++ i)
      for (int j = 1; j <= m; ++ j) {
          char t; cin >> t;
          r[i][j] = t - '0';
      }
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j)
        r[i][j] += r[i - 1][j] * b1;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j)
        r[i][j] += r[i][j - 1] * b2;
    for(int i = a; i <= n; i++) {
        for(int j = b; j <= m; j++) {
            ull tmp = r[i][j] - r[i - a][j] * p1[a]
                 - r[i][j - b] * p2[b] + r[i - a][j - b] * p1[a] * p2[b];
            h[tmp % MOD] = 1;
        }
    }
    scanf("%d", &q);
    while (q --) {
        for(int i = 1; i <= a; i++)
          for(int j = 1; j <= b; j++) {
              char t; cin >> t;
              c[i][j] = t - '0';
          }
        for(int i = 1; i <= a; i++)
            for(int j = 1; j <= b; j++)
                c[i][j] += c[i - 1][j] * b1;
        for(int i = 1; i <= a; i++) 
            for(int j = 1; j <= b; j++)
                c[i][j] += c[i][j - 1] * b2;
        putchar(h[c[a][b] % MOD] ? '1' : '0'); putchar('\n');
    }
    return 0;
}

#Prob. 8 Leetcode201. 数字范围按位与

Time Limit: N/A s | Memory Limit: N/A MB

#题意简述

给定 \(l,r(1\leq l\leq r\leq2^{31}-1)\)，求 \([l,r]\) 中所有数 \(\&\) 运算的结果。

#大体思路

注意到一但某一位向前进过位，那么之后的所有位置都不会有任何贡献，于是我们直接将 \(l,r\) 分别转为二进制后从高位到低位扫一遍即可。

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rangeBitwiseAnd(int l, int r) {
        int lenl = 0, lenr = 0, L[35], R[35], ans = 0;
        while (l) L[lenl ++] = (l & 1), l >>= 1;
        while (r) R[lenr ++] = (r & 1), r >>= 1;
        if (lenl != lenr) {return 0;}
        for (int i = lenl - 1; ~i; -- i) {
            if (L[i] != R[i]) break;
            ans += (L[i] << i);
        }
        return ans;
    }
};

#Prob. 9 HDU3336 Count the string

Time Limit: 1s | Memory Limit: 32MB

#题意简述

给定字符串 \(S(|S|\leq2\cdot10^5)\)，问每个前缀的出现次数和，对 \(10007\) 取模。

#大体思路

考虑到一个串的子串的出现位置集合一定包含这个串的出现集合，于是我们考虑 KMP 的 fail 边（next 边），它的定义是最长公共前后缀，于是我们求出 next[] 数组后从后往前按 next 边进行转移即可。

#Code

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
const int N = 300010;
const int INF = 0x3fffffff;
const int MOD = 10007;

int t, n, nxt[N], num[N], ans;
char s[N];

int main() {
    scanf("%d", &t);
    while (t --) {
        scanf("%d%s", &n, s); ans = 0;
        for (int i = 0; i <= n; ++ i) num[i] = 1;
        int p = -1; nxt[0] = -1;
        for (int q = 0; q < n; ++ q) {
            while (p != -1 && s[q] != s[p]) p = nxt[p];
            ++ p, nxt[q + 1] = p;
        }
        for (int i = n; i >= 1; -- i)
          num[nxt[i]] += num[i];
        for (int i = 1; i <= n; ++ i)
          (ans += num[i]) %= MOD;
        cout << ans << endl;
    }
    return 0;
}

#Prob. 10 POJ2752 Seek the Name, Seek the Fame

Time Limit: 2s | Memory Limit: 64MB

#题意简述

给定字符串 \(S\)，求 \(S\) 中每个既是前缀又是后缀的串的长度。

#大体思路

注意到如果 \(T_1\) 是最长的这样一个串，\(T_2\) 一定既是 \(T_1\) 的后缀又是 \(T_1\) 的前缀，依次类推，而最长公共前后缀正与 KMP 的 nxet[] 的定义相符，所以我们只需要 KMP 求出 next[] 数组，然后一直向前跳即可。

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 500010;
const int INF = 0x3fffffff;

int len, nxt[N], cnt, ans[N];
char s[N];

int main() {
    while (scanf("%s", s) != EOF) {
        int p = -1; nxt[0] = -1, cnt = 0;
        len = strlen(s);
        for (int q = 0; q < len; ++ q) {
            while (~p && s[p] != s[q]) p = nxt[p];
            ++ p, nxt[q + 1] = p;
        }
        p = len;
        while (p) ans[++ cnt] = p, p = nxt[p];
        for (int i = cnt; i >= 1; -- i)
          printf("%d ", ans[i]);
        printf("\n");
    }
    return 0;
}