抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

一方の笔记本

The only source of knowledge is experience.

博客

随笔

朋友

归档

关于

Codeforces Round 859 (Div. 4) 题解及总结

算法学习题解 - Codeforces

发布于：2023年3月28日

次浏览

2023年3月28日练习。

题解

A - Plus or Minus

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		int a, b, c;
		cin >> a >> b >> c;
		cout << ((a + b == c) ? '+' : '-') << endl;
	}
	return 0;
}

B - Grab the Candies

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	int total = 0, even = 0;
	for (int i = 0, a; i < n; i++) {
		cin >> a;
		if (a % 2 == 0) even += a;
		total += a;
	}
	cout << (even * 2 > total? "YES": "NO") << endl;
}
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

C - Find and Replace

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
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;
 
void solve() {
	int n;
	string s;
	cin >> n >> s;
	unordered_map<char, int> mp;
	int last = 0;
	for (int i = 0; i < n; i++) {
		if (mp.find(s[i]) == mp.end() || mp[s[i]] ^ last) {
			mp[s[i]] = (last ^= 1);
		} else {
			cout << "NO" << endl;
			return;
		}
	}
	cout << "YES" << endl;
}
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

D - Odd Queries

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
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

const int N = 2e5 + 100;

int prefix[N];

void solve() {
	int n, q, total = 0;
	cin >> n >> q;
	for (int i = 1, a; i <= n; i++) {
		cin >> a;
		total += a;
		prefix[i] = prefix[i - 1] + a;
	}
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k;
		int ans = total - (prefix[r] - prefix[l - 1]) + (r - l + 1) * k;
		cout << (ans % 2? "YES": "NO") << endl;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

E - Interview

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
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <sstream>
using namespace std;

const int N = 2e5 + 100;

int prefix[N];

void solve() {
	int n;
	cin >> n;
	for (int i = 1, a; i <= n; i++) {
		cin >> a;
		prefix[i] = prefix[i - 1] + a;
	}
	int l = 1, r = n;
	while (l < r) {
		int mid = (l + r) >> 1, q;
		cout << "? " << (mid - l + 1);
		for (int i = l; i <= mid; i++) {
			cout << ' ' << i;
		}
		cout << endl;
		cin >> q;
		if (q == prefix[mid] - prefix[l - 1]) {
			l = mid + 1;
		} else r = mid;
	}
	cout << "! " << l << '\n';
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

F - Bouncy Ball

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
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

void solve() {
	int n, m, i1, j1, i2, j2;
	string dir;
	cin >> n >> m >> i1 >> j1 >> i2 >> j2 >> dir;
	int bounces = 0, pass_starting_pos_cnt = 0;
	int i = i1, j = j1;
	while (i != i2 || j != j2) {
		pair<int, int> pos = { i, j };
		if (pos == pair<int, int>{i1, j1}) pass_starting_pos_cnt++;
		if (pass_starting_pos_cnt > 4) {
			cout << -1 << endl;
			return;
		}
		// update direction
		string last_dir = dir;
		if (i == n && dir[0] == 'D') dir[0] = 'U';
		if (i == 1 && dir[0] == 'U') dir[0] = 'D';
		if (j == m && dir[1] == 'R') dir[1] = 'L';
		if (j == 1 && dir[1] == 'L') dir[1] = 'R';
		if (last_dir != dir) bounces++;
		i += (dir[0] == 'U' ? -1 : 1);
		j += (dir[1] == 'L' ? -1 : 1);
	}
	cout << bounces << endl;
}

int main() {
	cin.tie(0), cout.sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

G - Subsequence Addition

数的顺序无关紧要，因此不妨对数组由小到大进行排序，得到\(b_1,b_2, \cdots b_n\)，显然数组中前\(k\)个\(1\)可以通过将初始的\(1\)复制\((k-1)\)次得到，那么集合\(\{1,2,\cdots,k\}\)中的每一个元素都可以由这\(k\)个\(1\)的子序列求和得到。假设\(b_t\)是数组中第一个大于\(1\)的数，如果\(b_t \leq k\)，那么\(b_1,b_2,\cdots,b_t\)组成的序列满足题设条件，加入\(b_t\)，\(\{b_i\}_{i=1}^{t}\)可以表示\(\{1,2,\cdots,b_t+k\}\)中的每一个数，以此类推，可以检查原数组是否合法。

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
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

const int N = 2e5 + 100;

int arr[N];

void solve() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i] == 1) sum++;
		else if (sum >= arr[i]) {
			sum += arr[i];
		} else {
			cout << "NO" << endl;
			return;
		}
	}
	cout << "YES" << endl;
}

int main() {
	cin.tie(0), cout.sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

总结

这个Div. 4的竞赛居然花了三个小时才做完，确实需要多参加参加竞赛了。以下是起手模板。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<typename T> inline T read() {
    T x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

template<typename T> void write(T x) { 
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    return 0;
}

评论