A
题意
给出三个不同的数，求中位数。
题解
知识点：模拟。
显然。
时间复杂度 O(1)
空间复杂度 O(1)
代码
#include #define ll long long using namespace std; bool solve() { vector<int> v(3 + 1); for (int i = 1;i <= 3;i++) cin >> v[i]; sort(v.begin() + 1, v.end()); cout << v[2] << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
B
题意
给出一个小写字母字符串，求最少需要字母表前缀多少个字母才能覆盖所有出现的字母。
题解
知识点：模拟。
找到字符串里最大的字母即可。
时间复杂度 O(n)
空间复杂度 O(n)
代码
#include #define ll long long using namespace std; bool solve() { int n; cin >> n; string s; cin >> s; int mx = 0; for (char ch : s) { mx = max(mx, ch - 'a' + 1); } cout << mx << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
C
题意
给出一组数，求出每个数减去这组数中一个数后能得到的最小值。
题解
知识点：模拟。
显然，每个数减去最大的数即可得到最小值。
但注意最大的数可能只有一个，但自己不能减自己，因此我们还需要求出次大值，让所有等于最大值的数减去次大值即可。
时间复杂度 O(n)
空间复杂度 O(n)
代码
#include #define ll long long using namespace std; int a[200007]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; int mx1 = 0, mx2 = 0; for (int i = 1;i <= n;i++) { if (a[i] > mx1) mx2 = mx1, mx1 = a[i]; else if (a[i] > mx2) mx2 = a[i]; } for (int i = 1;i <= n;i++) { if (a[i] < mx1) cout << a[i] - mx1 << ' '; else cout << a[i] - mx2 << ' '; } cout << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
D
题意
给出一组数，问其中是否有且只有一个山谷。
山谷的定义是，数组中的一个连续子串 al⋯r ，满足以下条件：
- 0≤l≤r≤n−1
- al=al+1=al+2=⋯=ar
- l=0 或 al−1>al
- r=n−1 或 ar<ar+1
题解
知识点：模拟。
显然第一个山谷一定会出现在第一次严格递增前，如果没有则出现在右端点。
因此，这组数一旦有一次严格递增，之后就不能严格递减（可以相等），因为再次严格递减后必然会再出现一个山谷。
时间复杂度 O(n)
空间复杂度 O(n)
代码
#include #define ll long long using namespace std; int a[200007]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; bool dz = 0; for (int i = 2;i <= n;i++) { if (a[i] < a[i - 1] && dz) return false; dz |= a[i] > a[i - 1]; } cout << "YES" << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << '\n'; } return 0; }
E
题意
给定一个 01 串，可以选择一位翻转一次，求最大逆序数。
题解
知识点：枚举，前缀和，贪心。
我们只需要知道每位修改后变化量，取最大值即可。
变化量可以通过维护前缀后缀 1 的个数和 l1,r1 获得。在第 i 位， 1->0 ，则变化量为 l1i−1−(n−i−r1i+1) ；0->1 ，则变化量为 (n−i−r1i+1)−l1i−1 。
时间复杂度 O(n)
空间复杂度 O(n)
代码
#include #define ll long long using namespace std; bool a[200007]; int l1[200007], r1[200007]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; l1[0] = r1[n + 1] = 0; for (int i = 1;i <= n;i++) l1[i] = l1[i - 1] + a[i]; for (int i = n;i >= 1;i--) r1[i] = r1[i + 1] + a[i]; int delta = 0; ll sum = 0; for (int i = 1;i <= n;i++) { if (a[i]) delta = max(delta, l1[i - 1] - (n - i - r1[i + 1])), sum += (n - i - r1[i + 1]); else delta = max(delta, (n - i - r1[i + 1]) - l1[i - 1]); } cout << sum + delta << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
F
题意
给定 n 个任务，任务 i 完成后能得到金币 ai 个。
每天能选择一个任务完成并得到其金币，任务可以重复完成，但每个任务完成后这个任务会冷却 k 天，之后才能再次选择。
给定需求金币数 c ，以及总天数 d ，问在 d 天内获得 c 个金币的前提下， k 最大是多少。
题解
知识点：二分，贪心。
显然用二分检验求解。
令 k∈[0,d] ，k<0 则无解，k≥d 则每个任务只需要完成一次就能满足，则 k 可以无穷大。
对于一个需要检验的 k ，显然我们优先选金币数大的任务。又因为一个任务完成后 k 天又可以再完成，因此我们只需要选前 min(k+1,n) 个任务重复完成即可，能完整完成 ⌊dk+1⌋ 轮，并再多完成 min(n,d−(k+1)⋅⌊dk+1⌋) 个任务。总额大于等于 c ，这个答案就合法。
时间复杂度 O(nlogn+logd)
空间复杂度 O(n)
代码
#include #define ll long long using namespace std; int n; ll c; int d; ll a[200007]; bool check(int mid) { int cyc = d / (mid + 1); int rest = d % (mid + 1); return a[min(mid + 1, n)] * cyc + a[min(rest, n)] >= c; } bool solve() { cin >> n >> c >> d; for (int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1, a + n + 1, [&](int a, int b) {return a > b;}); for (int i = 1;i <= n;i++) a[i] += a[i - 1]; int l = 0, r = d; while (l <= r) { int mid = l + r >> 1; if (check(mid)) l = mid + 1; else r = mid - 1; } if (r < 0) cout << "Impossible" << '\n'; else if (r >= d) cout << "Infinity" << '\n'; else cout << r << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
G
题意
给一个有 n 个节点的带权树。
从节点 a 出发到节点 b ，开始时 x=0 ，经过一条边 i 时，则异或边权 wi ，即 x=x⊕wi 。当且仅当进入 b 时恰好 x=0 才能进入 b ，否则不能进入 b 。有一次传送机会，可以从任意点出发，传送到除了 b 的任意点。
问是否存在方案从 a 走到 b 。
题解
知识点：dfs，枚举，位运算。
异或有个性质，a⊕a=0 。
结合我们可以任意传送考虑，我们发现只需要两个点 i,j （除了 b ）满足 a 到 i 的异或和等于 j 到 b 的异或和，那我们就可以从 i 传送到 j 即可存在 a 到 b 的方案。
因此，先从 a 遍历每个点的异或和。注意，a 出发的路径不能跨越 b ，因为此时 b 是走不通的。当然有可能到 b 直接就能进去了，我们可以把这个归类为走到 b 前的一个点原地传送以后，再从这个点出发进入 b 。
随后，我们把 a 能到达的点的异或和放进 set 里，再从 b 出发遍历每个点的异或和，因为异或具有交换律，倒着走和正着走结果一样。
最后，在 set 中查找 b 出发每个点得到的异或和是否已经存在即可。
时间复杂度 O(nlogn)
空间复杂度 O(n)
代码
#include #define ll long long using namespace std; template<class T> struct Graph { struct edge { int v, nxt; T w; }; int idx; vector<int> h; vector e; Graph(int n, int m) :idx(0), h(n + 1), e(m + 1) {} void init(int n) { idx = 0; h.assign(n + 1, 0); } void add(int u, int v, T w) { e[++idx] = edge{ v,h[u],w }; h[u] = idx; } }; const int N = 100007, M = 100007 << 1; int n, a, b; Graph<int> g(N, M); int dis[N]; void dfs(int u, int fa) { for (int i = g.h[u];i;i = g.e[i].nxt) { int v = g.e[i].v, w = g.e[i].w; if (v == fa || v == b) continue; dis[v] = dis[u] ^ w; dfs(v, u); } } bool solve() { cin >> n >> a >> b; g.init(n); for (int i = 1;i <= n - 1;i++) { int u, v, w; cin >> u >> v >> w; g.add(u, v, w); g.add(v, u, w); } for (int i = 1;i <= n;i++) dis[i] = -1; dis[a] = 0; dfs(a, 0); set<int> st; for (int i = 1;i <= n;i++) if (dis[i] != -1)st.insert(dis[i]); dis[b] = 0; dfs(b, 0); for (int i = 1;i <= n;i++) { if (i != b && st.count(dis[i])) { cout << "YES" << '\n'; return true; } } cout << "NO" << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }