2025春训第三场 - Star's Blog

考场上只做出来了 A、C、D、F。我真的敲高精了，而且甚至加法取模都敲了，刚开始 B 有一个样例是错的，带沟里之后回不来了，考完之后被 @xx liu (qwertyuiop) 大佬一句话敲醒了😇。数学题确实有点不好想，当时也是尽力了。

A. 字符串比对#

签到题

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    string a, b;
7
    cin >> a >> b;
8
    if (a.length() != b.length()) cout << 1 << endl;
9
    else {
10
        bool f1 = true, f2 = true;
11
        for (int i = 0; i < a.length(); ++i) {
12
            if (a[i] != b[i]) f1 = false;
13
            if (toupper(a[i]) != toupper(b[i])) f2 = false;
14
        }
15
        if (f1) cout << 2 << endl;
16
        else if (f2) cout << 3 << endl;
17
        else cout << 4 << endl;
18
    }
19
    return 0;
20
}

B. 数学小店的奇妙兑换#

高精度除法 n / (k - 1).

1
#include <iostream>
2
#include <vector>
3
#define int long long
4

5
using namespace std;
6

7
vector<int> div(vector<int> a, int b) {
8
    vector<int> res(a.size(), 0);
9
    long long t = 0;
10
    for (int i = a.size() - 1; i >= 0; --i) {
11
        t = t * 10 + a[i];
12
        res[i] = t / b;
13
        t %= b;
14
    }
15
    while (res.back() == 0 && res.size() > 1) res.pop_back();
16
    return res;
17
}
18

19
signed main() {
20
    ios::sync_with_stdio(0);
21
    cin.tie(0), cout.tie(0);
22
    vector<int> n;
23
    string s;
24
    int k;
25
    cin >> s >> k;
26
    n.resize(s.length());
27
    for (int i = 0; i < s.length(); ++i) {
28
        n[i] = s[s.length() - i - 1] - '0';
29
    }
30
    vector<int> res = div(n, k - 1);
31
    for (int i = res.size() - 1; i >= 0; --i) {
32
        cout << res[i];
33
    }
34
    cout << endl;
35
    return 0;
36
}

C. 染色#

正向维护很困难，但是反向处理很简单，因为不用考虑这次染色的点会不会被后续的操作改变，给行和列各开一个删除标记，染色之后打上标记，每次操作完之后后续操作的行数或者列数 -1。

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

4
using namespace std;
5

6
struct Query
7
{
8
    int op, u, c;
9
};
10
bool vis[100010][2];
11
long long cnt[100010];
12
stack<Query> st;
13

14
int main() {
15
    int n, m, k, q;
16
    scanf("%d%d%d%d", &n, &m, &k, &q);
17
    for (int i = 1; i <= q; ++i) {
18
        int op, u, c;
19
        scanf("%d%d%d", &op, &u, &c);
20
        st.push({op, u, c});
21
    }
22
    while (!st.empty()) {
23
        auto [op, u, c] = st.top();
24
        st.pop();
25
        if (op == 0) {
26
            if (!vis[u][op]) {
27
                cnt[c] += n;
28
                vis[u][op] = true;
29
                m--;
30
            }
31
        }
32
        else {
33
            if (!vis[u][op]) {
34
                cnt[c] += m;
35
                vis[u][op] = true;
36
                n--;
37
            }
38
        }
39
    }
40
    for (int i = 1; i <= k; ++i) printf("%lld ", cnt[i]);
41
    printf("\n");
42
    return 0;
43
}

D. 魔法传送门#

因为答案乘的倍数就是二进制的位数，可以把每一份答案直接分摊到每个二进制位，开一个状态数组记录当前状态之前的全部状态的每个二进制位提供的方案数总和。遍历到一个状态的时候，先枚举二进制位更新答案，再枚举二进制位用新答案更新状态数组。

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

4
using namespace std;
5

6
const int MOD = 998244353;
7

8
int a[200010];
9
long long f[200010], s[30];
10

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

E. 同余方程 (fang)#

注意到 a 是连续区间，而 b² 和 c³ 是离散的，可以把 a 捏到 b² 或者 c³ 中；又因为题目要求 a ≤ b ≤ c，把 a 捏到 b² 中更好维护。具体的，需要动态维护一个长度为 k 的数组，记录 a + b² mod k 的每种结果的方案数，在从 1 到 n 枚举 b 的过程中更新每个可能的 c 对应的答案，累加即可。

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

4
using namespace std;
5

6
long long tr[1000010];
7
int n, k;
8

9
void add(int u, int v) {
10
    u++;
11
    for (; u <= k; u += u & -u) {
12
        tr[u] += v;
13
    }
14
}
15

16
long long query(int u) {
17
    u++;
18
    long long res = 0;
19
    for (; u; u -= u & -u) {
20
        res += tr[u];
21
    }
22
    return res;
23
}
24

25
int main() {
26
    int T;
27
    scanf("%d", &T);
28
    for (int t = 1; t <= T; ++t) {
29
        memset(tr, 0, sizeof(tr));
30
        scanf("%d%d", &n, &k);
31
        long long res = 0;
32
        for (int i = 1; i <= n; ++i) {
33
            long long l = (long long)i * i + 1, r = (long long)i * i + i;
34
            add(0, (r - l + 1) / k);
35
            r -= (r - l + 1) / k * k;
36
            if (l <= r) {
37
                l %= k, r %= k;
38
                if (l <= r) add(l, 1), add(r + 1, -1);
39
                else add(0, 1), add(r + 1, -1), add(l, 1);
40
            }
41
            res += query((long long)i * i * i % k);
42
        }
43
        printf("Case %d: %lld\n", t, res);
44
    }
45
    return 0;
46
}

F. 计算器 (monitor)#

就是简单的模拟题，写一个 8 的然后复制粘贴，适当删减就可以得到别的。

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

4
using namespace std;
5

6
vector<vector<char>> trans(int n, int t) {
7
    vector<vector<char>> res(3 + t * 2, vector<char>(t + 2, ' '));
8
    if (n == 0) {
9
        for (int i = 1; i <= t; ++i) {
10
            res[0][i] = res[2 + t * 2][i] = '-';
11
        }
12
        for (int i = 0; i < t; ++i) {
13
            res[1 + i][0] = res[1 + i][t + 1] = res[2 + t + i][0] = res[2 + t + i][t + 1] = '|';
14
        }
15
    }
16
    else if (n == 1) {
17
        for (int i = 0; i < t; ++i) {
18
            res[1 + i][t + 1] = res[2 + t + i][t + 1] = '|';
19
        }
20
    }
21
    else if (n == 2) {
22
        for (int i = 1; i <= t; ++i) {
23
            res[0][i] = res[1 + t][i] = res[2 + t * 2][i] = '-';
24
        }
25
        for (int i = 0; i < t; ++i) {
26
            res[1 + i][t + 1] = res[2 + t + i][0] = '|';
27
        }
28
    }
29
    else if (n == 3) {
30
        for (int i = 1; i <= t; ++i) {
31
            res[0][i] = res[1 + t][i] = res[2 + t * 2][i] = '-';
32
        }
33
        for (int i = 0; i < t; ++i) {
34
            res[1 + i][t + 1] = res[2 + t + i][t + 1] = '|';
35
        }
36
    }
37
    else if (n == 4) {
38
        for (int i = 1; i <= t; ++i) {
39
            res[1 + t][i] = '-';
40
        }
41
        for (int i = 0; i < t; ++i) {
42
            res[1 + i][0] = res[1 + i][t + 1] = res[2 + t + i][t + 1] = '|';
43
        }
44
    }
45
    else if (n == 5) {
46
        for (int i = 1; i <= t; ++i) {
47
            res[0][i] = res[1 + t][i] = res[2 + t * 2][i] = '-';
48
        }
49
        for (int i = 0; i < t; ++i) {
50
            res[1 + i][0] = res[2 + t + i][t + 1] = '|';
51
        }
52
    }
53
    else if (n == 6) {
54
        for (int i = 1; i <= t; ++i) {
55
            res[0][i] = res[1 + t][i] = res[2 + t * 2][i] = '-';
56
        }
57
        for (int i = 0; i < t; ++i) {
58
            res[1 + i][0] = res[2 + t + i][0] = res[2 + t + i][t + 1] = '|';
59
        }
60
    }
61
    else if (n == 7) {
62
        for (int i = 1; i <= t; ++i) {
63
            res[0][i] = '-';
64
        }
65
        for (int i = 0; i < t; ++i) {
66
            res[1 + i][t + 1] = res[2 + t + i][t + 1] = '|';
67
        }
68
    }
69
    else if (n == 8) {
70
        for (int i = 1; i <= t; ++i) {
71
            res[0][i] = res[1 + t][i] = res[2 + t * 2][i] = '-';
72
        }
73
        for (int i = 0; i < t; ++i) {
74
            res[1 + i][0] = res[1 + i][t + 1] = res[2 + t + i][0] = res[2 + t + i][t + 1] = '|';
75
        }
76
    }
77
    else {
78
        for (int i = 1; i <= t; ++i) {
79
            res[0][i] = res[1 + t][i] = res[2 + t * 2][i] = '-';
80
        }
81
        for (int i = 0; i < t; ++i) {
82
            res[1 + i][0] = res[1 + i][t + 1] = res[2 + t + i][t + 1] = '|';
83
        }
84
    }
85
    return res;
86
}
87

88
void print(vector<vector<char>> t) {
89
    for (auto i : t) {
90
        for (auto j : i) putchar(j);
91
        putchar('\n');
92
    }
93
}
94

95
void cat(vector<vector<char>> &a, vector<vector<char>> b) {
96
    for (int i = 0; i < a.size(); ++i) {
97
        a[i].push_back(' ');
98
        a[i].insert(a[i].end(), b[i].begin(), b[i].end());
99
    }
100
}
101

102
int main() {
103
    int n;
104
    char s[10];
105
    while (scanf("%d%s", &n, s), n && s[0] != 0) {
106
        auto res = trans(s[0] - 48, n);
107
        for (int i = 1; s[i]; ++i) {
108
            cat(res, trans(s[i] - 48, n));
109
        }
110
        print(res);
111
        putchar('\n');
112
    }
113
    return 0;
114
}