WillHou's Blog
0%

【题解】CSP 模拟赛第一场题解

发表于 分类于 Valine：
MFSTEM CSP 第一场模拟赛的题解（非常详细）

T1. 不重最长子串

Link：点我跳转

题目概括：给定一个字符串 \(s\)，找出其中不含有重复字符的最长子串的长度。字符串由英文字母、数字和空格组成。长度在 \(0\sim 50000\) 之间

关于子串的定义，请出门右转到百度百科

一道水题，但还是有亿些技巧。

技巧：loc[i] 标记 \(i\) 出现的位置，求最长 / 不重复问题时会使用到。具体到这一题，loc[i] 表示第 \(i\) 个字符上一次出现的位置。

记录每一个字符之前相同字符出现的位置，否则初始位置全部为 \(-1\)，也可以直接计算，每一次计算可以形成最长的序列长度然后更新。

核心思想：先定后配。即枚举一个端点，匹配另一个端点。具体到这一题，是枚举右端点，匹配左端点。

需要注意的是这个大坑：字符串也可以由空格组成。所以一定要用 getline。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5e4 + 9;
int ans, pos[N], loc[130];
string s;
int main() {
    getline(cin, s);
    memset(loc, -1, sizeof loc);
    for (int i = 0; i < s.size(); i++)
        pos[i] = loc[s[i]], loc[s[i]] = i;
    for (int i = 0, j = 0; j < s.size(); j++) { // i-left, j-right
        if (pos[j] >= i) i = pos[j] + 1;
        ans = j-i+1 > ans ? j-i+1 : ans;
    }
    printf("%d", ans);
    return 0;
}

还有这种写法，是比较好想到的，就不做过多的解释，看注释即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>
using namespace std;
const int N = 130;
int loc[N], l, mx; // l-左端点
int main() {
    string s;
    getline(cin, s);
    memset(loc, -1, sizeof loc);
    for (int i = 0; i < s.size(); i++) {
        if (loc[s[i]] >= l) { // 出现了两次
            l = loc[s[i]] + 1;
        } else {
            mx = max(mx, i-l+1); // 更新最大值
        }
        loc[s[i]] = i; // 更新上一次出现的位置
    }
    cout << mx;
    return 0;
}

T2. 小J的加密算法

Link：点我跳转

题目概括：输入一个字符串，将其按照 Z 字形重新排列，输出排列后的样子。例如：有字符串 LSRDCYJDL，Z 字形的行数为 \(3\)，该字符串应该长这样：

1
2
3
L   C   L
S D Y D
R   J

输出应该长这样（按行输出）：

1
LCLSDYDRJ

（关于这个字符串的意思，我不敢多说，有知道的评论区见）

水题，找规律即可。

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
#include <iostream>
using namespace std;
const int N = 1009;
int col, c;
char m[N][N];
string s;
int main() {
    cin >> s >> c;
    if (c == 1) {
        cout << s;
        return 0;
    }
    for (int i = 0, r = 0; i < s.size(); i++) {
        if (col%(c-1) == 0) {
            m[r++][col] = s[i];
            if (r == c)
                r = c - 2, col++;
        } else {
            m[r--][col++] = s[i];
        }
    }
    for (int i = 0; i < c; i++)
        for (int j = 0; j <= col; j++)
            if (m[i][j])
                putchar(m[i][j]);
    return 0;
}

T3. 数列的个数

Link：点我跳转

题目概括：给出两个整数 \(n, m\)。问有多少个长度为 \(n\) 的序列 \(A\)，满足以下条件：

  • \(1 ≤ A_i ≤ m(i = 1, 2,\dots, n)\)
  • \(\forall i\in [1, n-1]\)，\(A_{i+1}\) 是 \(A_i\) 的倍数。

由于答案可能很大，所以你只需要输出答案对 \(998244353\) 取模的结果。

比较难，放洛谷应该是绿题的水平。

本题的核心思想仍然是“先定后配”。

分析过程如下：

关键词：倍数

因为 \(A_{i+1}\) 是 \(A_i\) 的倍数，所以 \(A_i\) 一定是 \(A_{i+1}\) 的约数。故这题会用到约数分解。

找规律 \(n=3, m=4:\)

枚举所有情况：

如果从第一个数开始向后推，并不方便发现规律。不妨先定下最后一个数，往前推前面的数。该思想称为：正难则反。

例如，以 \(4\) 为结尾的数列： 归结起来，就是： \[ \begin{cases} x\stackrel{\times 2^{a}}{\longrightarrow}y\stackrel{\times 2^{b}}{\longrightarrow}4\\ a + b \leq 2 \end{cases} \] 所以，欲求以 \(4\) 结尾的数列的方案数，即是求 \(a+b\leq2\) 有多少种可能。

方便起见，把 \(\leq\) 换成 \(=\)，我们再设一个未知数 \(c\) \[ a+b+c=2 \] 这样，我们就把这个问题转换为：有 \(n\) 个自然数相加的和为 \(k\)，解有多少种。

分析这个问题，可以用“隔板法”。注意：此处的隔板法是允许将多个板子插在一个空中的。

有 \(C^{k}_{n-1+k}\) 种方法。但是这种方法时间复杂度巨大，所以需要借助背包求解。

令 f[i][j] 表示前 \(i\) 个数用掉 \(j\) 个因子后的情况数。

1
2
f[i][j] = f[i-1][j] + f[i-1][j-1] + f[i-1][j-2] + ... + f[i-1][0]
        = f[i-1][j] + f[i][j-1] // 完全背包

降维后：f[j] = f[j] + f[j-1] 即 f[j] += f[j-1]。

这样就将组合数预处理出来了。

呼，终于到了上代码时间。码字码了几个小时了。

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
#include <iostream>
const int M = 998244353;
int f[20] = {1}, n, m;
int solve(int k) {
    int ans = 1;
    for (int i = 2; i*i <= k; ++i) {
        if (k % i) continue;
        int c = 0;
        while (k%i == 0) k /= i, ++c;
        ans = ans * 1LL * f[c] % M;
    }
    if (k > 1) ans = ans * 1LL * f[1] % M; // 质数情况
    return ans;
}
int main() {
    int ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= 19; ++j)
            (f[j] += f[j-1]) %= M;
    for (int i = 1; i <= m; ++i)
        (ans += solve(i)) %= M;
    printf("%d", ans);
    return 0;
}

T4. 匹配正则表达式

Link：点我跳转

先抖个机灵。C++ 头文件里内带正则表达式 regex 库，所以只需要调用库函数 regex_match 即可。

关于 regex 库的更多用法，请参考这篇博客

AC 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <regex>
using namespace std;
string s, p;
int main() {
    while (cin >> s >> p) {
        int ans = regex_match(s, regex(p));
        if (ans) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    return 0;
}

但这题显然不是考察我们的函数储备量，所以还要介绍下面这个方法。

本题的思路与 最长公共子序列(LCS) 比较相似。f[i][j] 表示 \(s\) 的前 \(i\) 个字符与 \(p\) 中的前 \(j\) 个字符是否能够匹配。在进行状态转移时，我们考虑 \(p\) 的第 \(j\) 个字符的匹配情况。

p[j] 是一个小写字母 a-z，则 s[i] 必须也为同样的小写字母方能完成匹配。

当 p[j] = '.' 时，p[j] 与 s[i] 一定能匹配成功；

当 p[j] = '*' 时，表示可对 p[j] 的前一个字符 p[j−1] 匹配（或理解为复制）任意次（包括 \(0\) 次）。 \[ dp[i][j] = \begin{cases} \ dp[i-1][j-1],\ s[i]=p[j]\\ \ dp[i][j-2],\ p[j]='*'\ \&\ s[i]\ne p[j-1]:\\ \ dp[i][j-2]\ or\ dp[i-1][j],\ p[j]='*'\ \&\ s[i]= p[j-1]: \end{cases} \]

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
#include <bits/stdc++.h>
using namespace std;
string s, p;
bool dp[50][50];
bool check(int i, int j) {
    if (i == 0) return false;
    if (p[j-1] == '.') return true;
    return s[i-1] == p[j-1];
}
int main() {
    while (cin >> s >> p) {
        int m = s.size();
        int n = p.size();
        memset(dp, false, sizeof dp);
        dp[0][0] = true;
        for (int i = 0; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (p[j-1] == '*') {
                    dp[i][j] |= dp[i][j-2];
                    if (check(i, j-1))
                        dp[i][j] |= dp[i-1][j];
                } else if (check(i, j)) {
                    dp[i][j] |= dp[i-1][j-1];
                }
        if (dp[m][n])
            cout << "Yes" << '\n';
        else
            cout << "No" << '\n';
    }
    return 0;
}