每天一场 Div. 2 是不是太少了。
比赛链接
给定三个正整数 $n, a, b$，要求先涂 $a$ 个连续红色，然后再涂 $b$ 个连续蓝色。问最后的的图形是否对称。
显然分奇偶考虑，如果 $n$ 是偶数则 $b$ 必须是偶数，否则 $b$ 必须是奇数。若 $a \le b$，则我们可以不用考虑 $a$，否则 $a$ 的奇偶性必须和 $b$ 一致。
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
| void solve() {
int n, a, b;
cin >> n >> a >> b;
if (n % 2 == 0) {
if (b % 2 != 0) {
cout << "NO\n";
} else if (a <= b) {
cout << "YES\n";
} else if ((a - b) % 2 == 0) {
cout << "YES\n";
} else {
cout << "NO\n";
}
} else {
if (b % 2 == 0) {
cout << "NO\n";
} else if (a <= b) {
cout << "YES\n";
} else if ((a - b) % 2 == 0) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
|
给定一个有 $n$ 个元素的数组 $a$ 和一个正整数 $k$，对于每一个元素 $a_i$ 可以选择加上 $m \times k$，$m$ 是非负整数。问若干次操作后使得 $\gcd(a_1,a_2,\dots,a_n) \gt 1$ 时，$a$ 数组的值。
我们不难想到，在模 $k+1$ 意义下，$x+k \equiv x-1 \pmod{k+1}$，所以我们只要对每一个元素操作 $a_i \bmod (k + 1)$ 次就行。
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;
#define int long long
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
if (n == 1) {
cout << k + a[0] << "\n";
return;
}
if (k % 2 == 1) {
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 1)
a[i] += k;
cout << a[i] << " \n"[i == n - 1];
}
return;
}
for (int i = 0; i < n; i++) {
a[i] += k * (a[i] % (k + 1));
}
for (int i = 0; i < n; i++) {
cout << a[i] << " \n"[i == n - 1];
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
|
C - Even Larger
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;
#define int long long
void solve() {
int n;
cin >> n;
vector<int> a(n + 10);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0;
for (int i = 2; i <= n; i += 2) {
if (a[i] < a[i - 1]) {
ans += a[i - 1] - a[i];
a[i - 1] = a[i];
}
if (a[i] < a[i + 1]) {
ans += a[i + 1] - a[i];
a[i + 1] = a[i];
}
if (a[i] < a[i + 1] + a[i - 1]) {
ans += a[i + 1] + a[i - 1] - a[i];
a[i + 1] -= a[i + 1] + a[i - 1] - a[i];
}
}
cout << ans << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
|
D - Sliding Tree
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
| #include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector adj(n + 1, vector<int>{});
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
vector<int> d, p;
auto bfs = [&](int s) -> int {
d.assign(n + 1, -1);
p.assign(n + 1, -1);
queue<int> q;
q.push(s);
d[s] = 0;
while (not q.empty()) {
int u = q.front();
q.pop();
for (auto v : adj[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
p[v] = u;
q.push(v);
}
}
}
return max_element(d.begin(), d.end()) - d.begin();
};
int s = bfs(1);
int t = bfs(s);
if (d[t] == n - 1) {
cout << "-1\n";
return;
}
int u = t;
int fa = -1;
while (adj[u].size() <= 2) {
fa = u;
u = p[u];
}
for (auto v : adj[u]) {
if (v != fa and v != p[u]) {
cout << p[u] << " " << u << " " << v << "\n";
return;
}
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
|