SZTU Monthly 2023 Nov.
写在前面
题目难度：
这次比赛难度划分是两道简单题，两道中等题，两道困难题。 \(DA\) 简单题 ， \(BF\) 中等题， \(CE\) 困难题。
题目难度都不大，需要注意的细节较多
A 魔法少女英梨梨
考点：
- 思维
- 博弈论
题解：
每人进行一次操作之后都会改变牌桌上的 \(1\) 的个数的奇偶性。
平局的情况：
- 能添加的 \(1\) 小于 \(k\) 且初始牌桌上不是刚好差一张
- 全场的 \(1\) 都凑不出 \(k\)
先手赢：
- 初始牌桌上的 \(1\) 的个数和 \(k\) 的奇偶性不同，即操作后奇偶性相同
- 初始牌桌刚好差一张，可以从牌堆中加牌
- 初始牌桌已经满足胜利条件
其余情况就是后手赢
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
void solve()
{
ll n, k, c;
cin >> n >> k >> c;
string s;
cin >> s;
int cnt = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '1')
cnt++;
}
if (c < k && k > cnt + 1 || cnt + c < k)
cout << "GG!" << endl;
else if ((cnt + k) % 2 == 1 || (k == cnt + 1 && c > 0) || cnt >= k)
cout << "Eriri win!" << endl;
else
cout << "Megumi kato win!" << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}B 堕落星球
考点：
- 思维
- 排序
题解：
考虑距离的最小值即为横坐标相减的最小值与纵坐标相减的和的最小值
我们将序列进行排序，每个点与相邻的两个点之间的差值一定小于其他点，故我们选前 \(n\) 个为横坐标，后 \(n\) 个为纵坐标即可。
数据量很小，也可以选择用 \(O(n^2)\) 的排序，如冒泡排序。
这里的排序升序和降序不影响结果。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define endl '\n'
void solve()
{
int n;
cin >> n;
vector<int> a(2 * n);
for (int i = 0; i < 2 * n; i++)
cin >> a[i];
sort(all(a));
ll ans = 0;
for (int i = 1; i < n; i++)
{
ans += a[i] - a[i - 1];
ans += a[i + n] - a[i + n - 1];
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}C 我想吃烤鸭
考点：
- 二分
题解：
考虑二分答案，对毒素的持续时间进行二分。
需要注意的是，鸭鸭恶霸的生命值可能高达 \(10^{18}\) ，故 check 函数不能一点一点的去数伤害，需要直接通过受伤的时间点之间的间隔来判断这次受伤毒素持续了多久。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e2 + 10;
vector<ll> a(N);
ll n, h;
bool check(ll k)
{
ll sum = k;
for (int i = n - 1; i > 0; i--)
{
if (a[i + 1] - a[i] > k)
sum += k;
else
sum += a[i + 1] - a[i];
}
return sum >= h;
}
void solve()
{
cin >> n >> h;
for (int i = 1; i <= n; i++)
cin >> a[i];
ll l = 1, r = 1e18, ans = 0;
while (l <= r)
{
ll mid = (l + r) / 2;
if (check(mid))
ans = mid, r = mid - 1;
else
l = mid + 1;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}D 灭霸要打响指啦！
考点：
- 简单语法
题解：
直接判断奇偶性输出即可
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
cout << (n % 2 == 0 ? "NO" : "YES") << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}E 国足巨星！
考点：
- 组合数学
- 贪心
题解：
计算出每项能力还差多少能力值，然后进行排序，用最少的技能点得到最多的能力。
对于一项能力，计算出 \(A_n^m\) 即为一项能力的方案数，其中 \(n\) 为这项能力还有多少人没有， \(m\) 为这项能力还差几点。
将每项能力的方案数累乘就是总的方案数，记得取模 \(998244353\)
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
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define endl '\n'
const int mod = 998244353;
const int N = 1e3 + 10;
int a[N][N];
int cal(int m, int n)
{
ll res = 1;
for (int i = m; i >= 1; i--, n--)
{
res *= n;
res %= mod;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k, q;
cin >> n >> m >> k >> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
ll ans1 = 0, ans2 = 1;
vector<int> v;
for (int j = 0; j < m; j++)
{
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (a[i][j])
cnt++;
}
if (cnt >= k)
{
ans1++;
continue;
}
v.push_back(k - cnt);
}
sort(all(v));
for (int i = 0; i < v.size(); i++)
{
if (q < v[i])
break;
ans2 *= cal(v[i], n - k + v[i]);
ans2 %= mod;
ans1++;
q -= v[i];
}
cout << ans1 << endl
<< ans2;
return 0;
}F 大学计算机
考点：
- 数学
题解：
由题可知，这是计算一个等差数列的前 \(n\) 项和。
需要注意的有：
\(b\) 并不是等差数列其中一项
会有出现死循环的情况
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
void solve()
{
ll ans, a, b, c;
cin >> ans >> a >> b >> c;
ll cnt = (b - a) / c;
if (cnt * c + a == b)
cnt--;
if (b < a && c > 0 || b > a && c < 0)
cnt = -1;
ans += (cnt + 1) * a + cnt * (cnt + 1) / 2 * c;
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}SZTU Monthly 2023 Nov.
http://xiaowhang.github.io/archives/1599660916/