A. Painting With Two Colors
题意：一个长度为\(n\)的数组，先把一段长度为\(a\)的子数组染为红色，再把一段长度为\(b\)的子数组染为蓝色，蓝色会覆盖红色。求能不能使得数组是回文。
因为要左右对称，所以肯定是染色的两个子数组的中心位置应该相同。
那么如果\(a > b\)且\(a\)和\(n\)的奇偶性不同则无解，因为红色部分不能对称，而蓝色又无法覆盖红色。
如果\(a < b\)且\(b\)和\(n\)的奇偶性不同则无解，因为蓝色一定覆盖红色，此时只需关注蓝色能不能构成回文。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, a, b;std::cin >> n >> a >> b;if (b % 2 == n % 2 && (b > a || a % 2 == n % 2)) {std::cout << "YES\n";} else {std::cout << "NO\n";}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
B. Add 0 or K
题意：一个数组，每次让数组每个数要么加上\(0\)要么加上\(k\)。求能不能使得数组\(gcd > 1\)。
简单做法是猜出\(gcd = k + 1\)。然后遍历一遍就行了。
我的写法是求一个不是\(k\)的因子的质数，设它为\(gcd\)，那么有\(a_i + tk \equiv 0 \mod (p)\)。那么有\(t \equiv -a_i \times k^{-1} \mod(p)\)。因为\(p\)是质数，可以用费马小定理求\(k\)的逆元求出\(t\)。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29
};int power(int a, int b, int p) {int res = 1;for (;b;b >>= 1, a = (i64)a * a % p) {if (b & 1) {res = (i64)res * a % p;}}return res;
}void solve() {int n, k;std::cin >> n >> k;std::vector<i64> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}int p = 0;for (auto & x : primes) {if (k % x) {p = x;break;}}int inv = power(k % p, p - 2, p);for (int i = 0; i < n; ++ i) {i64 x = a[i] % p;i64 b = (p - x) * inv % p;a[i] += b * k;}for (int i = 0; i < n; ++ i) {std::cout << a[i] << " \n"[i == n - 1];}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
C. Even Larger
题意：一个数组，每次操作使得一个数减一，不能小于\(0\)。求所有子数组的偶数位和大于等于奇数位和的最小操作。
发现只要\(a_i \geq a_{i-1} + a_{i+1}\)就行，其中\(i\)是偶数。
那么考虑怎么减，从左到右做，显然应该尽量减\(a_{i+1}\)，因为它对后面有影响。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<i64> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}i64 ans = 0;for (int i = 1; i < n; i += 2) {i64 x = a[i - 1];if (i + 1 < n) {x += a[i + 1];} i64 t = std::max(0ll, x - a[i]);ans += t;if (i + 1 < n) {i64 t1 = std::min(a[i + 1], t);a[i + 1] -= t1;t -= t1;}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
D. Sliding Tree
题意：一棵树，每次选择\(a, b, c\)满足\(b\)和\(a, c\)都有边，然后把\(b\)除\(a\)外的所有两边接到\(c\)上。需要把树变为链，求一个最小操作方案的第一次操作。
链的直径长度为\(n\)，最小操作方案一定是每次让树的直径加一。
那么只需要找到一次让直径长度加一的操作。
考虑找出一条树的直径，然后枚举其中的点，找到一个度数大于等于\(3\)的点，拿它当\(b\)，然后用直径上它左右两个点中距离端点最近的点当作\(a\)，然后再选一个不在直径上的邻点作为\(c\)。那么直径长度就会加一。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<std::vector<int>> adj(n);for (int i = 1; i < n; ++ i) {int u, v;std::cin >> u >> v;-- u, -- v;adj[u].push_back(v);adj[v].push_back(u);}int max = 0;for (int i = 0; i < n; ++ i) {max = std::max<int>(max, adj[i].size());}if (max <= 2) {std::cout << -1 << "\n";return;}auto bfs = [&](int s) -> int {std::vector<int> d(n, -1);std::queue<int> q;q.push(s);d[s] = 0;while (q.size()) {int u = q.front(); q.pop();for (auto & v : adj[u]) {if (d[v] == -1) {d[v] = d[u] + 1;q.push(v);}}}return std::max_element(d.begin(), d.end()) - d.begin();};int U = bfs(0);int V = bfs(U);std::vector<int> path;auto dfs = [&](auto & self, int u, int fa) -> bool {if (u == V) {path.push_back(u);return true;}for (auto & v : adj[u]) {if (v == fa) {continue;}if (self(self, v, u)) {path.push_back(u);return true;}}return false;};dfs(dfs, U, -1);int a = -1, b = -1, c = -1;for (int i = 0; i < path.size(); ++ i) {int u = path[i];if (adj[u].size() >= 3) {b = u;a = i < (int)path.size() - 1 - i ? path[i - 1] : path[i + 1];for (auto & v : adj[u]) {if (v != path[i - 1] && v != path[i + 1]) {c = v;break;}}break;}}std::cout << a + 1 << " " << b + 1 << " " << c + 1 << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}