【2024暑#109】ACM暑期第四次测验（个人赛）题解
# A - 旋转网格
# Solution
折半搜索
先从起点暴力枚举 次旋转的情况，然后从终点暴力枚举 次旋转的情况，最后用 map 看是否有相同的值
# Code
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int>> vvi;
int main() {
freopen ("A.in", "r", stdin);
ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
auto flip = [&](int x, int y, vvi a) {
auto b = a;
for (int dx = 0; dx < n - 1; dx++)
for (int dy = 0; dy < m - 1; dy++)
b[x + dx][y + dy] = a[x + n - 2 - dx][y + m - 2 - dy];
return b;
};
auto bfs = [&](vvi a) {
map<vvi, int> res;
queue<vvi> q; q.push(a); res[a] = 0;
while (!q.empty()) {
vvi t = q.front(); q.pop();
int d = res[t];
if (d >= 10) break;
for (int x = 0; x <= 1; x++)
for (int y = 0; y <= 1; y++) {
vvi b = flip(x, y, t);
if (!res.count(b)) {
res[b] = d + 1;
q.push(b);
}
}
}
return res;
};
vvi b(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
b[i][j] = i * m + j + 1;
auto res1 = bfs(a);
auto res2 = bfs(b);
int ans = 22;
for (auto &[v, d] : res2) {
if (res1.count(v)) ans = min(ans, res1[v] + d);
}
cout << (ans > 20 ? -1 : ans) << '\n';
return 0;
}
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
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
# B - 整点栅格统计
# Solution
由于 不大，对于每个点 ，我们枚举其对角线 我们能计算出剩下两个点的坐标，然后判断是不是在区域内即可
# Code
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
int ans = 0;
for (int x = 0; x <= n; x++) {
for (int y = 0; y <= m; y++) {
if (i == x && j == y) {
continue;
}
if ((i - x + j - y) % 2 != 0) {
continue;
}
int a = (i - j + x + y) / 2;
int b = (i + j - x + y) / 2;
int c = (x - y + i + j) / 2;
int d = (x + y - i + j) / 2;
if (0 <= a && a <= n && 0 <= b && b <= m && 0 <= c && c <= n && 0 <= d && d <= m) {
ans++;
}
}
}
std::cout << ans << " \n"[j == m];
}
}
return 0;
}
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
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
# C - Get sum
# Question
给定一个序列 。
你需要从 中选择零个或多个元素，使得：如果你选择了 ，满足对于 ，你最多只能选择 个元素。
计算你所选择元素的最大总和。
# Solution
易得最多只能选两个，从大到小排序后 即为所求。
# Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 5;
ll Tex = 1, n;
vector<ll> a;
void AC()
{
a.push_back(0);
a.push_back(0);
cin >> n;
for(int i = 1; i <= n; i ++)
{
ll x;
cin >> x;
a.push_back(x);
}
sort(a.begin(), a.end(), greater<ll>());
cout << a[0] + a[1] << endl;
}
int main()
{
ios::sync_with_stdio(false);
while(Tex --) AC();
return 0;
}
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
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
# D - 又是一年七夕
# Solution
观察发现，搭配其实可以看做一种并查集中的亲属关系，所以先用并查集把一些有搭配的云朵看成一个 “大云朵”，然后对 “大云朵”，做背包 DP 即可
# Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
int N, M, W; cin >> N >> M >> W;
vector<int> w(N + 1), v(N + 1);
for (int i = 1; i <= N; i++) cin >> w[i] >> v[i];
vector<int> fa(N + 1);
iota(fa.begin(), fa.end(), 0);
function<int(int)> find = [&](int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
};
for (int i = 1; i <= M; i++) {
int x, y; cin >> x >> y;
int fx = find(x), fy = find(y);
if (fx != fy) fa[fx] = fy;
}
for (int i = 1; i <= N; i++) {
int f = find(i);
if (f != i) {
w[f] += w[i];
v[f] += v[i];
w[i] = v[i] = 0;
}
}
vector<int> dp(W + 1);
for (int i = 1; i <= N; i++) {
if (w[i] == 0) continue;
for (int j = W; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
return 0;
}
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
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
# E - 乱
# Solution
我们肯定希望答案变得尽量平均，但是由于我们只能给 ，所以我们的操作是受到限制的
我们发现，对于两个数 ，如果 ，那么我们让 ，则乘积一定不会变劣
由于 不大，所以暴力跑就可以了
# Code
#include <bits/stdc++.h>
using namespace std;
const long long TT = 998244353;
int main() {
ios::sync_with_stdio(false);
int T; cin >> T;
while (T--) {
int n; cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int flg = 1;
while (flg) {
flg = 0;
for (int i = n; i - 1 >= 1; i--) {
if (a[i] > a[i - 1]) {
a[i] -= 1, a[i - 1] += 1;
flg = 1; break;
}
}
}
long long ans = 1;
for (int i = 1; i <= n; i++) ans = (ans * a[i]) % TT;
cout << ans << '\n';
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# F - Mex
# Solution
签到题，用一个桶记录下一个整数是否出现过，然后循环取找第一个没有出现过的数
# Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<int> cnt(2005, 0);
for (int i = 1; i <= n; i++) {
int x; cin >> x; cnt[x] = 1;
}
for (int i = 0; i <= 2000; i++) {
if (cnt[i] == 0) {
cout << i << '\n';
return 0;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
上次更新: 2025/04/08, 18:03:31