2025春训第十二场

A. 拼写检查#

按要求模拟就行，只需要注意 如果要检查的单词在词表中出现，则原样输出该单词。

1
s = input()
2
n = int(input())
3
l = [input() for _ in range(n)]
4
if s in l:
5
    print(s)
6
else:
7
    for t in l:
8
        f = False
9
        if (len(s) == len(t)):
10
            if (sum(s[i] != t[i] for i in range(len(s))) == 1):
11
                f = True
12
        elif (len(s) == len(t) + 1):
13
            for i in range(len(s)):
14
                if (s[:i] + s[i + 1:] == t):
15
                    f = True
16
                    break
17
        elif (len(s) == len(t) - 1):
18
            for i in range(len(t)):
19
                if (s == t[:i] + t[i + 1:]):
20
                    f = True
21
                    break
22
        if f:
23
            print(t)
24
            break
25
    else:
26
        print('NOANSWER')

B. 翻转#

有点类似线性dp的思想，核心问题就是 0 和 1 的分界点在哪。预处理把右侧全变成 1 的操作数。

特别的对于 i = n，时如果是 s[i] = 0，翻转一次；如果 s[i] = 1，不用翻转；
其他情况，如果 s[i] = 1，不用动；如果 s[i] = 0 并且 s[i + 1] = 0，不用消耗翻转次数（因为把对于 [s[i + 1], n] 的最后一次翻转改成对于 [s[i], n] 的翻转就行），否则翻转两次（先把后面全变 0，然后一起变成 1）。

然后从左到右遍历，枚举分界点，遍历到 i 时把 i 变成 1，然后考虑当前翻转次数的奇偶性

如果是偶数，后面的序列不变，可以直接用前面维护的结果；
如果是奇数，后面序列翻转，如果 s[i + 1] 本来是 1，那只能再翻转一次了；如果 s[i + 1] 本来是 0，说明维护的时候已经翻转了一次，直接把最后一次无效翻转撤销掉即可。

1
#include <iostream>
2

3
using namespace std;
4

5
int a[100010], b[100010];
6

7
int main() {
8
    int n, t = 0;
9
    scanf("%d", &n);
10
    for (int i = 1; i <= n; ++i) {
11
        scanf("%1d", &a[i]);
12
    }
13
    a[n + 1] = 1;
14
    for (int i = n; i; --i) {
15
        if (a[i] || a[i + 1] == a[i]) b[i] = b[i + 1];
16
        else if (i == n) b[i] = 1;
17
        else b[i] = b[i + 1] + 2;
18
    }
19
    int res = b[1];
20
    for (int i = 1; i <= n; ++i) {
21
        if ((a[i] ^ (t & 1)) && a[i] != a[i - 1]) t++;
22
        res = min(res, t + ((t & 1) ? (a[i + 1] ? b[i + 1] + 1 : b[i + 1] - 1) : b[i + 1]));
23
    }
24
    printf("%d\n", res);
25
    return 0;
26
}

C. 集合#

比较暴力的做法（容易爆空间），可以用分治的思想，预处理 k 小的，暴力 k 大的，平均每次查询只需要 1000 次左右计算。

1
#include <iostream>
2
#include <unordered_map>
3

4
using namespace std;
5

6
unordered_map<int, int> s;
7
int n;
8
struct FenwickTree
9
{
10
    int val[100001];
11
    bool mark[100001];
12
    void add(int u) {
13
        if (mark[u]) return;
14
        mark[u] = true;
15
        for (; u <= n; u += u & -u) {
16
            val[u] += 1;
17
        }
18
    }
19
    int query(int u) {
20
        int res = 0;
21
        for (; u; u -= u & -u) {
22
            res += val[u];
23
        }
24
        return res;
25
    }
26
} tr[101];
27

28
int main() {
29
    ios::sync_with_stdio(0);
30
    cin.tie(0), cout.tie(0);
31
    int q;
32
    cin >> q;
33
    n = q;
34
    while (q--) {
35
        char c;
36
        int x;
37
        cin >> c >> x;
38
        if (c == '+') {
39
            if (s[x] == 0) {
40
                for (int i = 1; i <= 100; ++i) {
41
                    if (x % i == 0) {
42
                        if (x / i <= 100000) tr[i].add(x / i);
43
                    }
44
                }
45
            }
46
            s[x]++;
47
        }
48
        else {
49
            if (x > 100) {
50
                int i;
51
                for (i = 1; s[i * x]; ++i);
52
                cout << i * x << endl;
53
            }
54
            else {
55
                int l = 1, r = 100000;
56
                while (l < r) {
57
                    int mid = l + r >> 1;
58
                    if (tr[x].query(mid) < mid) r = mid;
59
                    else l = mid + 1;
60
                }
61
                cout << l * x << endl;
62
            }
63
        }
64
    }
65
    return 0;
66
}

不那么暴力的做法，因为没有删除操作，所以对于每一个 k，后一次得到的答案一定是在前一次答案的后面，于是把较小的 k 打上标记，每次查询从标记开始往后面查即可（但是我没想到，还在暴力树状数组+二分）。

D. 计数#

线性dp，大概思路很好想，比较难做到的是不重不漏，我🧠不行，于是写了个 $O(2^n \times n^3)$ 的大暴力对拍拍出来了。

每个 $A_i$ 只能有被删和不被删两种情况，令 $f_{i, 0}$ 表示只考虑 [1, i] 这个区间的内的数的情况下第 i 个数不被删的方案数， $f_{i, 1}$ 表示被删的方案数。

如果 $A_i$ 前有比他小的数，记第一个比他小的数为 $A_j$ 。

首先考虑 $f_{i, 0}$ ， $A_i$ 可以删的区间有 [k, i - 1]，其中 j + 1 ≤ k ≤ i - 1，在不全删掉的情况下，从左到右删和从右到左删一定是不重复的，所以方案数是 $\sum_{k = j + 1}^{i - 1} f_{i, 0}$ ；如果 [j + 1, i - 1] 全删掉了，方案数就是 j 的方案数 $f_{j, 0} + f_{j, 1}$ ，合并一下有

f_{i, 0} = \sum_{k = j}^{i - 1} f_{k, 0} + f_{j, 1}

考虑 $f_{i, 1}$ ， $A_i$ 可以被 $A_j$ 删也可以被能删掉 $A_j$ 的点删，所以

f_{i, 1} = f_{j, 0} + f_{j, 1}

如果没有比他小的数，他可以 [k, i - 1]，1 ≤ k ≤ i - 1，方案数就是不全删的方案数 + 全删的方案数（就是 1）

f_{i, 0} = \sum_{k = 1}^{i - 1}f_{k, 0} + 1

他不可能被左边的删掉，所以 $f_{i, 1} = 0$ .

1
#include <iostream>
2

3
using namespace std;
4

5
const int MOD = 998244353;
6
const int N = 300010;
7

8
int st[N], tp;
9
long long f[N][2], s[N];
10
int a[N];
11

12
int main() {
13
    int n;
14
    scanf("%d", &n);
15
    s[0] = 1;
16
    for (int i = 1; i <= n; ++i) {
17
        scanf("%d", &a[i]);
18
        while (tp && a[i] <= a[st[tp]]) tp--;
19
        if (!tp) {
20
            f[i][0] = s[i - 1];
21
        }
22
        else {
23
            f[i][0] = (((s[i - 1] - s[st[tp] - 1] + f[st[tp]][1]) % MOD) + MOD) % MOD;
24
            f[i][1] = (f[st[tp]][0] + f[st[tp]][1]) % MOD;
25
        }
26
        s[i] = (s[i - 1] + f[i][0]) % MOD;
27
        st[++tp] = i;
28
    }
29
    printf("%lld\n", (f[n][0] + f[n][1]) % MOD);
30
    return 0;
31
}

📎 大暴力，枚举所有子序列，挨个检查合法性（如果一个点被删了，那么一定有一个比他小的点没有被删，并且这两个点路径上的所有点都被删了）。

1
#include <iostream>
2

3
using namespace std;
4

5
int a[20];
6

7
int main() {
8
    int n;
9
    cin >> n;
10
    for (int i = 1; i <= n; ++i) {
11
        cin >> a[i];
12
    }
13
    int t = 0;
14
    for (int mask = 0; mask < (1 << n); ++mask) {
15
        bool big_f = true;
16
        for (int i = 1; i <= n; ++i) {
17
            if (((mask >> (i - 1)) ^ 1) & 1) {
18
                bool f = false;
19
                for (int j = 1; j <= n; ++j) {
20
                    if ((mask >> (j - 1)) & 1) {
21
                        if (a[j] < a[i]) {
22
                            bool ck = true;
23
                            int l = min(i, j), r = max(i, j);
24
                            for (int ii = l + 1; ii < r; ++ii) {
25
                                if (mask >> (ii - 1) & 1) {
26
                                    ck = false;
27
                                    break;
28
                                }
29
                            }
30
                            if (ck) {
31
                                f = true;
32
                                break;
33
                            }
34
                        }
35
                    }
36
                }
37
                if (!f) {
38
                    big_f = false;
39
                    break;
40
                }
41
            }
42
        }
43
        t += big_f;
44
    }
45
    cout << t << endl;
46
    return 0;
47
}

Star's Blog

A. 拼写检查#

B. 翻转#

C. 集合#

D. 计数#