- 因為下午有些無聊，所以就 virtual 了一場 div. 4，體驗一下 div. 4，但打了 90 分鐘就覺得累到不想打了 QQ 半年多沒打競程，速度掉滿多的，專注力也有差。
- pC 一直讀錯題意。
pA. Lucky?
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int count(int n) {
9 return n / 100 + n / 10 % 10 + n % 10;
10}
11
12int main() {
13 ios::sync_with_stdio(0), cin.tie(0);
14 int n;
15 cin >> n;
16 while (n--) {
17 int t;
18 cin >> t;
19 if (count(t % 1000) == count(t / 1000)) {
20 cout << "YES\n";
21 } else {
22 cout << "NO\n";
23 }
24 }
25 return 0;
26}
pB. Equal Candies
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int main() {
9 ios::sync_with_stdio(0), cin.tie(0);
10 int t;
11 cin >> t;
12 while (t--) {
13 int n;
14 cin >> n;
15 vector<int> a(n);
16 for (int i = 0; i < n; i++) {
17 cin >> a[i];
18 }
19 int m = a[0];
20 for (int i = 0; i < n; i++) {
21 m = min(m, a[i]);
22 }
23 int sum = 0;
24 for (int i = 0; i < n; i++) {
25 sum += a[i] - m;
26 }
27 cout << sum << "\n";
28 }
29 return 0;
30}
pC. Most Similar Words
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int diff(const string &a, const string &b, int m) {
9 int ret = 0;
10 for (int i = 0; i < m; i++) {
11 ret += abs(a[i] - b[i]);
12 }
13 return ret;
14}
15
16int main() {
17 ios::sync_with_stdio(0), cin.tie(0);
18 int t;
19 cin >> t;
20 while (t--) {
21 int n, m;
22 cin >> n >> m;
23 vector<string> s(n);
24 for (int i = 0; i < n; i++) {
25 cin >> s[i];
26 }
27 int ans = 26 * 8;
28 for (int i = 0; i < n; i++) {
29 for (int j = i + 1; j < n; j++) {
30 ans = min(ans, diff(s[i], s[j], m));
31 }
32 }
33 cout << ans << '\n';
34 }
35 return 0;
36}
pD. X-Sum
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int main() {
9 ios::sync_with_stdio(0), cin.tie(0);
10 int t;
11 cin >> t;
12 while (t--) {
13 int n, m;
14 cin >> n >> m;
15 vector<vector<int>> a(n, vector<int>(m));
16 for (int i = 0; i < n; i++) {
17 for (int j = 0; j < m; j++) {
18 cin >> a[i][j];
19 }
20 }
21 map<int, int> cnt_sum;
22 map<int, int> cnt_diff;
23 for (int i = 0; i < n; i++) {
24 for (int j = 0; j < m; j++) {
25 cnt_sum[i + j] += a[i][j];
26 cnt_diff[i - j] += a[i][j];
27 }
28 }
29 int ans = 0;
30 for (int i = 0; i < n; i++) {
31 for (int j = 0; j < m; j++) {
32 ans = max(cnt_sum[i + j] + cnt_diff[i - j] - a[i][j], ans);
33 }
34 }
35 cout << ans << '\n';
36 }
37 return 0;
38}
pE. Eating Queries
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int main() {
9 ios::sync_with_stdio(0), cin.tie(0);
10 int t;
11 cin >> t;
12 while (t--) {
13 int n, q;
14 cin >> n >> q;
15 vector<int> a(n);
16 for (int i = 0; i < n; i++) {
17 cin >> a[i];
18 }
19 sort(a.begin(), a.end());
20 reverse(a.begin(), a.end());
21 vector<int> sum(n);
22 sum[0] = a[0];
23 for (int i = 1; i < n; i++) {
24 sum[i] = sum[i - 1] + a[i];
25 }
26 while (q--) {
27 int x;
28 cin >> x;
29 int ans = lower_bound(sum.begin(), sum.end(), x) - sum.begin() + 1;
30 if (ans > n) ans = -1;
31 cout << ans << "\n";
32 }
33 }
34 return 0;
35}
pF. Longest Strike
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int main() {
9 ios::sync_with_stdio(0), cin.tie(0);
10 int t;
11 cin >> t;
12 while (t--) {
13 int n, k;
14 cin >> n >> k;
15 vector<int> a(n);
16 map<int, int> sum;
17 for (int i = 0; i < n; i++) {
18 cin >> a[i];
19 sum[a[i]]++;
20 }
21 vector<int> cnt;
22 vector<int> num;
23 for (auto p : sum) {
24 num.push_back(p.first);
25 cnt.push_back(p.second);
26 }
27 int L = -1, R = -1;
28 for (int l = 0, r = 0; l < cnt.size(); l++) {
29 if (cnt[l] < k) continue;
30 for (r = max(r, l); r < cnt.size() and cnt[r] >= k and num[r] - num[l] == r - l; r++) {
31 }
32 r--;
33 if (num[r] - num[l] >= R - L) {
34 R = num[r], L = num[l];
35 }
36 }
37 if (L == -1) {
38 cout << -1 << "\n";
39 } else {
40 cout << L << " " << R << "\n";
41 }
42 }
43 return 0;
44}
pG. White-Black Balanced Subtrees
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8int dfs(int i, const vector<vector<int>> &children, const string &color, int &ans) {
9 int ret = color[i] == 'B' ? 1 : -1;
10 for (int u : children[i]) {
11 ret += dfs(u, children, color, ans);
12 }
13 if (ret == 0) ans++;
14 return ret;
15}
16
17int main() {
18 ios::sync_with_stdio(0), cin.tie(0);
19 int T;
20 cin >> T;
21 while (T--) {
22 int n;
23 cin >> n;
24 vector<vector<int>> children(n);
25 for (int i = 1; i < n; i++) {
26 int p;
27 cin >> p;
28 children[p - 1].emplace_back(i);
29 }
30 string color;
31 cin >> color;
32 int ans = 0;
33 dfs(0, children, color, ans);
34 cout << ans << '\n';
35 }
36 return 0;
37}
pH. Maximum Crossings
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8void solve(vector<ll> &a, vector<ll> &b, int l, int r, ll &ans) {
9 if (l >= r) return;
10 int mid = (l + r) / 2;
11 solve(a, b, l, mid, ans);
12 solve(a, b, mid + 1, r, ans);
13 int li = l, ri = mid + 1;
14 for (int i = l; i <= r; i++) {
15 if (ri > r or (li <= mid && a[li] < a[ri])) {
16 b[i] = a[li++];
17 ans += ri - mid - 1;
18 } else {
19 b[i] = a[ri++];
20 }
21 }
22 for (int i = l; i <= r; i++) {
23 a[i] = b[i];
24 }
25}
26
27int main() {
28 ios::sync_with_stdio(0), cin.tie(0);
29 int T;
30 cin >> T;
31 while (T--) {
32 int n;
33 cin >> n;
34 vector<ll> a(n), b(n);
35 for (int i = 0; i < n; i++) {
36 cin >> a[i];
37 }
38 ll ans = 0;
39 solve(a, b, 0, n - 1, ans);
40 cout << ans << "\n";
41 }
42 return 0;
43}
