Codeforces Round 859 (Div. 4) 题解及总结
2023年3月28日练习。
题解
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 ; }
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 ; }
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 ; }
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 ; }
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 ; }
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 ; } 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 ; }
数的顺序无关紧要,因此不妨对数组由小到大进行排序,得到\(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 ; }