A. In the Dream
题意：比赛上半场比分为\(a:b\)，下半场为\(c:d\)，没有一个队伍能连续赢三次，求这个比分可不可能。
一方每赢两次另一方就要断他连胜，然后最后还可以接两次胜利然后结束，那么有\(a * 2 + 2 \leq b\)，\(b * 2 + 2 \leq a\)。同理处理下半场，下半场双方得分就是\(c-a, d- b\)。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int a, b, c, d;std::cin >> a >> b >> c >> d;if (a * 2 + 2 < b || b * 2 + 2 < a || (c - a) * 2 + 2 < (d - b) || (d - b) * 2 + 2 < (c - a)) {std::cout << "NO\n";} else {std::cout << "YES\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. Like the Bitset
题意：构造一个排列，如果\(s_i\)是\(1\)，代表所有覆盖这个位置的长度至少为\(k\)的子数组的最大值不是\(p_i\)。
直接从小到大填，先把\(1\)的位置填了，然后填\(0\)的位置。如果连续的\(1\)大于等于\(k\)个无解。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::string s;std::cin >> s;int x = 1;std::vector<int> a(n);for (int i = 0, cnt = 0; i < n; ++ i) {if (s[i] == '1') {a[i] = x ++ ;++ cnt;} else {cnt = 0;}if (cnt >= k) {std::cout << "NO\n";return;}}std::cout << "YES\n";for (int i = 0; i < n; ++ i) {if (a[i] == 0) {a[i] = x ++ ;}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. Against the Difference
题意：一个块是好的，那么每个元素都等于块长，一个数组是好的，那么可以分成若干好块。给你一个数组，求一个最长的好子序列。
考虑\(dp\)。记\(f_i\)表示前\(i\)个能选出的最长子序列，那么不选\(i\)的话\(f_i = f_{i-1}\)，否则记\(j\)为\(i\)前面第\(a_i\)个和它相同数的位置，有\(f_i = \max(f_i, f_{j-1} + a_i)\)。给每个元素记录位置，然后每个\(i\)记录它在相同元素里是第几位。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n + 1);std::vector<std::vector<int>> pos(n + 1);std::vector<int> p(n + 1);for (int i = 1; i <= n; ++ i) {std::cin >> a[i];p[i] = pos[a[i]].size();pos[a[i]].push_back(i);}std::vector<int> f(n + 1);for (int i = 1; i <= n; ++ i) {f[i] = f[i - 1];if (p[i] + 1 >= a[i]) {f[i] = std::max(f[i], f[pos[a[i]][p[i] - a[i] + 1] - 1] + a[i]);}}std::cout << f[n] << "\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. For the Champion
题意：交互题。二维平面上开始你有一个坐标\((X, Y)\)，但你不知道。有\(n\)个点，你每次可以让直接上下左右选一个方向移动\([1, 10^9]\)步，然后得到所有点和你的曼哈顿距离的最小值。\(10\)次移动求出坐标。
和一个点曼哈顿距离为\(k\)的点其实是围绕这个点的一个菱形，可以看作四条线段。可以记录每个点\(45\)度和\(135\)度的对角线，分别是\(x_i + y_i\)和\(x_i - y_i\)。那么可以每次移动\(K=1e9\)，先移动到右上，此时距离它最近的点的\(x_i, y_i\)都小于它，那么一定是最大的\(x_i + y_i\)这条线上，记为\(max1\)。设返回距离为\(d1\)，则有\(X+Y+4K-max1 = d1\)，然后再移动到右下，记此时距离为\(d2\)，距离它最近的点为\(i\)，那么有\(X+2K - x_i + y_i - (Y - 2K) = d2\)，得\(X+Y+4K - (x_i - y_i)= d2\)，那么记\(max2\)为最大的\(x_i - y_i\)。
则有
\begin{cases}
X + Y + 4K + max1 = d1 \\
X - Y + 4K - max2 = d2
\end{cases}
解方程即可。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<i64> x(n), y(n);i64 max1 = -1e18, max2 = -1e18;for (int i = 0; i < n; ++ i) {std::cin >> x[i] >> y[i];max1 = std::max(max1, x[i] + y[i]);max2 = std::max(max2, x[i] - y[i]);}auto ask = [&](char c, i64 k) -> i64 {std::cout << "? " << c << " " << k << std::endl;i64 res;std::cin >> res;return res;};constexpr i64 K = 1e9;ask('R', K);ask('R', K);ask('U', K);i64 d1 = ask('U', K);ask('D', K);ask('D', K);ask('D', K);i64 d2 = ask('D', K);i64 sum1 = d1 - 4 * K + max1;i64 sum2 = d2 - 4 * K + max2;i64 X = (sum1 + sum2) / 2, Y = (sum1 - sum2) / 2;std::cout << "! " << X << " " << Y << std::endl;
}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;
}
E. By the Assignment
题意：一个无向图，每个点有点权，但有些点的点权还没确定。权域为\([1, V]\)。要求任意两个点的所有路径的点权异或和都相同。求有多少方案。
如果两个点有两条以上路径，那么显然成环，且这两条路径值相同，同时环上任意两点的两条路径的值相同，可以得到每个点的权值相同，如果环长是奇数，则每个点点权必须是\(0\)。
那么求边双，如果边双里有奇环，则每个点权值都相同，如果只有偶环，如果每个点都没确定有\(V\)种填法，如果只有一个点且没有确定也是随便填。
代码省略取模类。
点击查看代码
constexpr int P = 998244353;
using Z = MInt<P>;void solve() {int n, m, V; std::cin >> n >> m >> V;std::vector<i64> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}std::vector<std::vector<std::pair<int,int>>> adj(n);for (int i = 0; i < m; ++ i) {int u, v;std::cin >> u >> v;-- u; -- v;adj[u].emplace_back(v, i);adj[v].emplace_back(u, i);}std::vector<int> dfn(n, -1), low(n, 0), stk, bel(n, -1), bridge(m);stk.reserve(n);int dcc_cnt = 0;int idx = 0;auto tarjan = [&](auto && self, int u, int fa) -> void {dfn[u] = low[u] = idx ++ ;stk.push_back(u);for (auto & [v, id] : adj[u]) {if (dfn[v] == -1) {self(self, v, id);low[u] = std::min(low[u], low[v]);if (low[v] > dfn[u]) {bridge[id] = 1;}} else if (id != fa) {low[u] = std::min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {int v;do {v = stk.back();stk.pop_back();bel[v] = dcc_cnt;} while (v != u);++ dcc_cnt;}};tarjan(tarjan, 0, -1);std::vector<int> c(n, -1);bool flag = true;Z ans = 1;for (int i = 0; i < n; ++ i) {if (c[i] != -1) {continue;}int val = -1;auto dfs = [&](auto && self, int u, int color, int fa) -> bool {c[u] = color;if (a[u] != -1) {if (val == -1) {val = a[u];} else if (val != a[u]) {flag = false;}}bool odd_cycle = false;for (auto & [v, id] : adj[u]) {if (id == fa || bel[v] != bel[i] || bridge[id]) {continue;}if (c[v] == -1) {odd_cycle |= self(self, v, color ^ 1, id);} else if (c[u] == c[v]) {odd_cycle = true;}}return odd_cycle;};if (dfs(dfs, i, 0, -1)) {if (val != -1 && val != 0) {flag = false;} } else if (val == -1) {ans *= V;}if (!flag) {std::cout << 0 << "\n";return;}}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;
}