2025武汉新生赛部分题解及游记#

游记#

2025 年已经见底，今年最后一场参加的线下赛也告一段落。不知不觉已经过了快半年的时间，在这里先感谢这半年来帮助过我的学长，同学们，感谢他们作为我的领路人，帮助我应对大学里的事物，带我入门算法，学习计算机相关的知识。希望未来的自己能够争气点。

本次比赛仍需要反思的，首先是保持冷静。A 题样例都没看就开始搓，最后发现时几乎是全部重写，浪费了大量时间。另外对于一些细节方面仍需注意。例如算式中存在的计算符的优先性。最后对于拿不太准的代码，应当多造样例多测，这样能避免很多不应该出现的罚时。

这次是第二次去华农参加的比赛。相对于第一次，这次抽到了怎么按也按不动的键盘，刚交完 Wrong Answer 后就蓝屏的电脑，运气还是差了点 TAT。但这次发的面包好吃(~~虽然不咋饿~~)。这次仍然很幸运的拿到了签到题的一血，让我也不至于空手而归。另外，华农不愧是华“农”，比赛完在华农乱逛，田，一望无际的田~~

经历了这次比赛，意识到了自己与强者之间的差距真的很大。。。在算法这条路上仍是任重道远。希望自己以后加油吧！

部分题解#

L - 那我问你#

题意：#

输入三个整数 a，b，c，输出“The paper you submitted have a Pros and b Cons, so I have c Questions for you.”。

代码：#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using ld = long double;
5
using pi = pair<ll, ll>;
6

7
#define fi first
8
#define se second
9

10
const int MAXN = 6e7;
11
const double eps = 1e-5;
12
const ll mod = 1e9 + 7;
13

14
void solve ()
15
{
16
    ll a, b, c; cin >> a >> b >> c;
17
    cout << "The paper you submitted have " << a << " Pros and " << b << " Cons, so I have " << c << " Questions for you.";
18
}
19

20
int main ()
21
{
22
    ios::sync_with_stdio(0);
23
    cin.tie(0);
24
    int _ = 1;
25
    // cin >> _;
26
    while (_--) {
27
        solve();
28
    }
29
    return 0;
30
}

A - 昨日重现#

题意：#

给定一个长度不超过 100 的字符串，在五所大学(HUST, WHU, WHUT, HZAU, CCNU)的缩写中，找出在字符串中作为子序列出现次数最多且字典序最小的一个，输出大学的缩写及最大次数。

思路：#

这里就不深究此题了，for 循环足以解决。

代码：#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using ld = long double;
5
using pi = pair<ll, ll>;
6

7
#define fi first
8
#define se second
9

10
const int MAXN = 6e7;
11
const double eps = 1e-5;
12
const ll mod = 1e9 + 7;
13

14
void solve ()
15
{
16
    string s; cin >> s;
17
    vector <ll> cnt(5, 0);
18
    ll n = s.size();
19

20
    for (ll i = 0; i < n; i++) {
21
        if (s[i] == 'C') {
22
            for (ll j = i + 1; j < n; j++) {
23
                if (s[j] == 'C') {
24
                    for (ll k = j + 1; k < n; k++) {
25
                        if (s[k] == 'N') {
26
                            for (ll l = k + 1; l < n; l++) {
27
                                if (s[l] == 'U') cnt[0]++;
28
                            }
29
                        }
30
                    }
31
                }
32
            }
33
        }
34
    }
35

36
    for (ll i = 0; i < n; i++) {
37
        if (s[i] == 'H') {
38
            for (ll j = i + 1; j < n; j++) {
39
                if (s[j] == 'U') {
40
                    for (ll k = j + 1; k < n; k++) {
41
                        if (s[k] == 'S') {
42
                            for (ll l = k + 1; l < n; l++) {
43
                                if (s[l] == 'T') cnt[1]++;
44
                            }
45
                        }
46
                    }
47
                }
48
            }
49
        }
50
    }
51

52
    for (ll i = 0; i < n; i++) {
53
        if (s[i] == 'H') {
54
            for (ll j = i + 1; j < n; j++) {
55
                if (s[j] == 'Z') {
56
                    for (ll k = j + 1; k < n; k++) {
57
                        if (s[k] == 'A') {
58
                            for (ll l = k + 1; l < n; l++) {
59
                                if (s[l] == 'U') cnt[2]++;
60
                            }
61
                        }
62
                    }
63
                }
64
            }
65
        }
66
    }
67

68
    for (ll i = 0; i < n; i++) {
69
        if (s[i] == 'W') {
70
            for (ll j = i + 1; j < n; j++) {
71
                if (s[j] == 'H') {
72
                    for (ll k = j + 1; k < n; k++) {
73
                        if (s[k] == 'U') {
74
                            for (ll l = k + 1; l < n; l++) {
75
                                if (s[l] == 'T') cnt[4]++;
76
                            }
77
                        }
78
                    }
79
                }
80
            }
81
        }
82
    }
83

84
    for (ll i = 0; i < n; i++) {
85
        if (s[i] == 'W') {
86
            for (ll j = i + 1; j < n; j++) {
87
                if (s[j] == 'H') {
88
                    for (ll k = j + 1; k < n; k++) {
89
                        if (s[k] == 'U') cnt[3]++;
90
                    }
91
                }
92
            }
93
        }
94
    }
95

96
    if (cnt[0] == max({cnt[0], cnt[1], cnt[2], cnt[3], cnt[4]})) {
97
        cout << "CCNU " << cnt[0] << '\n';
98
    }else if (cnt[1] == max({cnt[0], cnt[1], cnt[2], cnt[3], cnt[4]})) {
99
        if (cnt[0] == cnt[1]) {
100
            cout << "CCNU " << cnt[0] << '\n';
101
        }else {
102
            cout << "HUST " << cnt[1] << '\n';
103
        }
104
    }else if (cnt[2] == max({cnt[0], cnt[1], cnt[2], cnt[3], cnt[4]})) {
105
        if (cnt[0] == cnt[2]) {
106
            cout << "CCNU " << cnt[0] << '\n';
107
        }else if (cnt[1] == cnt[2]) {
108
            cout << "HUST " << cnt[1] << '\n';
109
        }else {
110
            cout << "HZAU " << cnt[2] << '\n';
111
        }
112
    }else if (cnt[3] == max({cnt[0], cnt[1], cnt[2], cnt[3], cnt[4]})) {
113
        if (cnt[0] == cnt[3]) {
114
            cout << "CCNU " << cnt[0] << '\n';
115
        }else if (cnt[1] == cnt[3]) {
116
            cout << "HUST " << cnt[1] << '\n';
117
        }else if (cnt[2] == cnt[3]) {
118
            cout << "HZAU " << cnt[2] << '\n';
119
        }else {
120
            cout << "WHU " << cnt[3] << '\n';
121
        }
122
    }else if (cnt[4] == max({cnt[0], cnt[1], cnt[2], cnt[3], cnt[4]})) {
123
        if (cnt[0] == cnt[4]) {
124
            cout << "CCNU " << cnt[0] << '\n';
125
        }else if (cnt[1] == cnt[4]) {
126
            cout << "HUST " << cnt[1] << '\n';
127
        }else if (cnt[2] == cnt[4]) {
128
            cout << "HZAU " << cnt[2] << '\n';
129
        }else if (cnt[3] == cnt[4]) {
130
            cout << "WHU " << cnt[3] << '\n';
131
        }else {
132
            cout << "WHUT " << cnt[4] << '\n';
133
        }
134
    }
135
}
136

137
int main ()
138
{
139
    ios::sync_with_stdio(0);
140
    cin.tie(0);
141
    int _ = 1;
142
    // cin >> _;
143
    while (_--) {
144
        solve();
145
    }
146
    return 0;
147
}

B - 易守难攻#

题意：#

给定一个空的 n 行 m 列的网格，需要往每一个格子填入一个 $1$ ~ $n\times m$ 的高度值，满足有 k 个网格的高度值严格大于 8 个相邻格子的高度值，且这 k 个网格不位于边界上。输出满足条件的网格，或者报告不存在这样的分配方式。

思路：#

首先明确：将大数一个隔一个的放是最大化能放置网格的放置方法。手模几个样例可以发现，若 $(n - 1) / 2 \times (m - 1) / 2 < k$ ，则放不下满足条件的 k 个网格。我们可以从最大数开始放置。先将大数一个隔一个数地放，保证大数之间不会互相干扰。再依次放置其他数即可，可以保证大数总是可以满足条件的，且其他数不会形成新的满足条件的网格。

代码：#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using ld = long double;
5
using pi = pair<ll, ll>;
6

7
#define fi first
8
#define se second
9

10
const int MAXN = 6e7;
11
const double eps = 1e-5;
12
const ll mod = 1e9 + 7;
13

14
void solve ()
15
{
16
    ll n, m, k; cin >> n >> m >> k;
17
    if (((n - 1) / 2) * ((m - 1) / 2) < k) {
18
        cout << "No" << '\n';
19
        return;
20
    }
21

22
    vector <vector <ll> > v(n + 1, vector <ll> (m + 1));
23
    vector <vector <bool> > vis(n + 1, vector <bool> (m + 1, false));
24

25
    ll t = n * m;
26
    if (k != 0) {
27
        ll cnt = 0;
28
        bool found = true;
29
        for (int i = 2; i < n; i += 2) {
30
            for (int j = 2; j < m; j += 2) {
31
                cnt++;
32
                v[i][j] = t--;
33
                vis[i][j] = true;
34
                if (cnt == k) found = false;
35
                if (!found) break;
36
            }
37
            if (!found) break;
38
        }
39
    }
40

41
    for (int i = 1; i <= n; i++) {
42
        for (int j = 1; j <= m; j++) {
43
            if (vis[i][j]) continue;
44
            v[i][j] = t--;
45
        }
46
    }
47

48
    cout << "Yes" << '\n';
49
    for (int i = 1; i <= n; i++) {
50
        for (int j = 1; j <= m; j++) {
51
            cout << v[i][j] << ' ';
52
        }
53
        cout << '\n';
54
    }
55
}
56

57
int main ()
58
{
59
    ios::sync_with_stdio(0);
60
    cin.tie(0);
61
    int _ = 1;
62
    cin >> _;
63
    while (_--) {
64
        solve();
65
    }
66
    return 0;
67
}

F - Anon 的疑问#

题意：#

询问 $q$ 次 $(1 \leq q \leq 1e6)$ ，每次询问给定一个正整数 $n(1 \leq n \leq 2e7)$ ，判断其能否被分解为两个正整数的平方和。

思路：#

这里给出两种思路。

第一种思路：首先可以观察到这里的数据量并不是很大，我们完全可以直接预处理平方在 $2e7$ 内的数，然后枚举得到所有满足条件的正整数。时间复杂度: $O(2e7)$ 。

第二种思路：可以利用两平方和定理：对于任意的正整数 $n = a^2 + b^2(a, b \in Z)$ ，当且仅当在 n 的质因数分解中，所有形如 $p \equiv 3 (mod 4)$ 的质数，其指数都是偶数。根据定理，我们可以先预处理出在 $2e7$ 内所有数的最小质因数，然后再根据每个数判断其指数奇偶性。

但是这里由于询问次数可能很多，时间复杂度相对于暴力可能没有优势，且无法通过本题，仅供参考。

时间复杂度： $O(q\times nlogn)$ 。

代码：#

思路一：#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using ld = long double;
5
using pi = pair<ll, ll>;
6

7
#define fi first
8
#define se second
9

10
const int MAXN = 6e7;
11
const double eps = 1e-5;
12
const ll mod = 1e9 + 7;
13

14
bool vis[20000005];//这里如果用vector记录可能会被卡常
15

16
void solve ()
17
{
18
    ll n; cin >> n;
19
    if (vis[n]) {
20
        cout << "Yes" << '\n';
21
    }else {
22
        cout << "No" << '\n';
23
    }
24
}
25

26
int main ()
27
{
28
    ios::sync_with_stdio(0);
29
    cin.tie(0); cout.tie(0);
30
    int _ = 1;
31
    cin >> _;
32

33
    for (int i = 1; i < 4473; i++) {
34
        if (i * i > 2e7 + 2) break;
35
        for (int j = i; j < 4473; j++) {
36
            if (i * i + j * j > 2e7 + 2) break;
37
            vis[i * i + j * j] = true;
38
        }
39
    }
40

41
    while (_--) {
42
        solve();
43
    }
44
    return 0;
45
}

思路二：（仅供参考）#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using ld = long double;
5
using pi = pair<ll, ll>;
6

7
#define fi first
8
#define se second
9

10
const int N = 2e7 + 1;
11
const double eps = 1e-5;
12
const ll mod = 1e9 + 7;
13

14
bool isprime[N];
15
int prime[N], mnp[N];
16
ll cnt = 0;
17

18
void get_mn_prime_factor ()
19
{
20
    mnp[1] = 1;
21
    for (int i = 2; i < N; i++) {
22
        if (!isprime[i]) {
23
            prime[cnt++] = i;
24
            mnp[i] = i;
25
        }
26
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
27
            isprime[i * prime[j]] = true;
28
            mnp[i * prime[j]] = prime[j];
29
            if (i % prime[j] == 0) break;
30
        }
31
    }
32
}
33

34
void solve ()
35
{
36
    ll n; cin >> n;
37

38
    auto check = [&] (int x) -> bool {
39
        ll t = x;
40
        while (t != 1) {
41
            ll p = mnp[t];
42
            ll cnt = 0;
43
            while (t % p == 0) {
44
                t /= p;
45
                cnt++;
46
            }
47
            if (p % 4 == 3 && cnt & 1) {
48
                return false;
49
            }
50
        }
51
        if ((ll)sqrtl(x) * (ll)sqrtl(x) == x) return false;//特判
52
        else return true;
53
    };
54

55
    cout << (check(n) ? "Yes" : "No") << '\n';
56
}
57

58
int main ()
59
{
60
    ios::sync_with_stdio(0);
61
    cin.tie(0);
62
    int _ = 1;
63
    cin >> _;
64
    get_mn_prime_factor();
65
    while (_--) {
66
        solve();
67
    }
68
    return 0;
69
}

G - 你好，世界#

题意：#

有一个初始值为 0 的 N 位计数器，用来预测一条指令是否应当执行。

当扫描到一条指令时，若计数器的值小于 $2^{N - 1}$ ，则预测该指令将不被执行，否则预测将被执行。
无论是否预测正确，如果当前指令的真实状况为需要执行，则计数器增加 1，否则计数器减少 1。
计数器的增加和减少不会超过 $[0,2^N)$ 这一界限。

你需要构造一个长度为 len 的 01 字符串（指令），0 代表不执行，1 代表执行，使得预测错误的次数最大。

思路：#

诈骗题。理解题意后，不难发现只需要使前 $2^{N - 1}$ 个指令执行，后面的指令只需不执行，执行(01 循环)即可。

代码：#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using ld = long double;
5
using pi = pair<ll, ll>;
6

7
#define fi first
8
#define se second
9

10
const int MAXN = 6e7;
11
const double eps = 1e-5;
12
const ll mod = 1e9 + 7;
13

14
ll qpow (ll a, ll b)
15
{
16
    ll res = 1;
17
    while (b) {
18
        if (b & 1) res = res * a;
19
        a = a * a;
20
        b >>= 1;
21
    }
22
    return res;
23
}
24

25
void solve ()
26
{
27
    ll n, len; cin >> n >> len;
28
    ll tag = len;
29
    if (n <= 60) tag = min(qpow(2, n - 1), len);
30

31
    for (int i = 0; i < tag; i++) {
32
        cout << 1;
33
    }
34
    for (int i = 0; i < len - tag; i++) {
35
        cout << (i & 1);
36
    }
37
}
38

39
int main ()
40
{
41
    ios::sync_with_stdio(0);
42
    cin.tie(0);
43
    int _ = 1;
44
    // cin >> _;
45
    while (_--) {
46
        solve();
47
    }
48
    return 0;
49
}

H - 哆啦 A 梦的神奇铜锣烧储存系统#

题意：#

有 $n$ 个宝箱，其中有 $k$ 个宝箱里装有铜锣烧，哆啦 A 梦先从中选择 $m$ 个他认为最有可能装有铜锣烧的宝箱，然后在剩下的 $n - m$ 个宝箱中随机打开 $n - (m + q)$ 个空箱子（若没有空箱子则不打开），最后剩下 $q$ 个宝箱是关闭的。求出剩下的未打开 $q$ 个宝箱中铜锣烧的期望数量（模 998244353）。

思路：#

简洁的思路是：我们考虑任意一个真箱子，在每一次选完 $m$ 个后，这个箱子仍然存在于 $n - m$ 个箱子的期望为 $E[X_i] = \frac{n - m}{n}$ 。一共有 $k$ 个真箱子，只需要将 $k$ 个期望累加就能得出答案： $\frac{n - m}{n} \times k$ 。

详细过程：（鸣谢笔者ichooooooo！）

首先，这是一道超几何分布题

经典场景：总共有 $N$ 个商品，其中 $M$ 个特殊品，选取 $n$ 个出来

求 $n$ 个商品中特殊商品期望设 $X$ 是 $n$ 个商品里的特殊品数量 $E = \sum_{X = 0}^{M}(X \times P(X))$

这里 $P(X)$ 是从 $n$ 个中抽取 $X$ 个特殊品的概率， $X \times P(X)$ 是抽到 $i$ 个特殊元素时，特殊品数量的期望贡献， $(n - X) \times P(X)$ 则是抽到 $i$ 个特殊元素时，非特殊品数量的期望贡献
求 $P(X)$ 超几何分布知识，我们用 $\binom{k}{i}$ 表示 $C(i, k)$ ，最终公式 $\frac{\binom{M}{X}\binom{N - M}{n - X}}{\binom{N}{n}}$ 其中 $\binom{M}{X}$ 表示从 $X$ 个总特殊品选取 $M$ 个，那么剩下 $n - X$ 个是非特殊，再从 $N - M$ 个总非特殊选取 $n - X$ 个，相乘是“有利情况”，除总情况就是概率
期望化简后求和结果 $\frac{M}{N} \times n$

回到题目，根据上面我们最终需要得到抽 n 个商品时，非特殊商品的期望，即 ${\sum_{i = 0}^{min(k, m)}(k - i)} \times P(i)$ 展开得 $\frac{\sum_{i = 0}^{min(k, m)}\binom{k}{i}\binom{n - k}{m - i}(k - i)}{\binom{n}{m}}$ 化简得 $\frac{n - m}{n} \times k$

关于为什么 q 不会影响到最终结果

q 只抽取空箱子，不影响特殊品的数量，根据公式，P(i)不变，权值 k - i 也不变，所以结果不变

代码：#

原始公式:#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using ld = long double;
5
using pi = pair<ll, ll>;
6

7
#define fi first
8
#define se second
9

10
const int MAXN = 1e6 + 10;
11
const double eps = 1e-5;
12
const ll mod = 998244353;
13

14
vector <ll> f(MAXN), g(MAXN);
15

16
ll qpow (ll a, ll b)
17
{
18
    ll res = 1;
19
    while (b) {
20
        if (b & 1) res = res * a % mod;
21
        a = a * a % mod;
22
        b >>= 1;
23
    }
24
    return res % mod;
25
}
26

27
ll C (ll n, ll m)
28
{
29
    if (m < 0 || m > n) return 0;
30
    return f[n] * g[m] % mod * g[n - m] % mod;
31
}
32

33
void solve ()
34
{
35
    ll n, k, m, q; cin >> n >> k >> m >> q;
36
    ll a = 0, b = 0;
37
    for (int i = 0; i <= min(k, m); i++) {
38
        a = (a + C(k, i) * C(n - k, m - i) % mod * (k - i) % mod) % mod;
39
    }
40
    b = C(n, m);
41
    ll ans = a * qpow(b, mod - 2) % mod;
42
    cout << ans << '\n';
43
}
44

45
int main ()
46
{
47
    ios::sync_with_stdio(0);
48
    cin.tie(0);
49
    int _ = 1;
50
    // cin >> _;
51

52
    f[0] = 1, g[0] = 1;
53
    for (int i = 1; i < MAXN; i++) {
54
        f[i] = f[i - 1] * i % mod;
55
        g[i] = qpow(f[i], mod - 2) % mod;
56
    }
57

58
    while (_--) {
59
        solve();
60
    }
61
    return 0;
62
}

化简：#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
using ld = long double;
5
using pi = pair<ll, ll>;
6

7
#define fi first
8
#define se second
9

10
const int MAXN = 6e7;
11
const double eps = 1e-5;
12
const ll mod = 998244353;
13

14
ll qpow (ll a, ll b)
15
{
16
    ll res = 1;
17
    while (b) {
18
        if (b & 1) res = res * a % mod;
19
        a = a * a % mod;
20
        b >>= 1;
21
    }
22
    return res % mod;
23
}
24

25
void solve ()
26
{
27
    ll n, k, m, q; cin >> n >> k >> m >> q;
28
    cout << (n - m) * k % mod * qpow(n, mod - 2) % mod << '\n';
29
}
30

31
int main ()
32
{
33
    ios::sync_with_stdio(0);
34
    cin.tie(0);
35
    int _ = 1;
36
    // cin >> _;
37
    while (_--) {
38
        solve();
39
    }
40
    return 0;
41
}