A
代码
#include <bits/stdc++.h>using namespace std;using ll = long long;bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) { int x; cin >> x; cout << n - x + 1 << " \n"[i == 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
代码
#include <bits/stdc++.h>using namespace std;using ll = long long;int lena[400007], lenb[400007];bool solve() { int n; cin >> n; for (int i = 1;i <= 2 * n;i++) lena[i] = lenb[i] = 0; int pre = 0, len = 0; for (int i = 1;i <= n;i++) { int x; cin >> x; if (x != pre) { lena[pre] = max(lena[pre], len); len = 0; pre = x; } len++; } lena[pre] = max(lena[pre], len); len = 0; pre = 0; for (int i = 1;i <= n;i++) { int x; cin >> x; if (x != pre) { lenb[pre] = max(lenb[pre], len); len = 0; pre = x; } len++; } lenb[pre] = max(lenb[pre], len); int ans = 0; for (int i = 1;i <= 2 * n;i++) ans = max(ans, lena[i] + lenb[i]); cout << ans << '\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
题意
一棵树有 \(n\) 个节点，一开始只有根节点 \(1\) 。
现在给出加边的顺序，每次操作按顺序从头到尾依次加边。
一次操作中，当且仅当一条边还没被加，且一个端点已经存在，才能加这条边。
问要最少操作几次，所有边才能都被加入。
题解
知识点：树形dp，DFS。
可以用树型dp求出每个点出现需要的最少操作次数。
点的出现时间取决于边的顺序，我们将边的顺序记录到边权中，dfs过程中将边权当作孩子的出现时间。
若一个点出现时间比它孩子出现时间要晚，那么它孩子出现需要的操作次数就是它的操作次数加 \(1\) ，否则可以在同一次操作中处理完。
设 \(f_u\) 表示节点 \(u\) 出现需要的最少操作次数， \(rk_u\) 表示节点 \(u\) 的出现时间，转移即上述所说。
最后答案为 \(f_u\) 的最大值。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>using namespace std;using ll = long long;vector<pair<int, int>> g[200007];int rk[200007], f[200007];void dfs(int u, int fa) { for (auto [v, w] : g[u]) { if (v == fa) continue; rk[v] = w; f[v] = f[u] + (w < rk[u]); dfs(v, u); }}bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) g[i].clear(); for (int i = 1;i <= n - 1;i++) { int u, v; cin >> u >> v; g[u].push_back({ v,i }); g[v].push_back({ u,i }); } rk[1] = n; dfs(1, 0); cout << *max_element(f + 1, f + n + 1) << '\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
题意
给定长度为 \(n\) 的数组 \(a,b\) ，求出所有满足 \(a_i \cdot a_j = b_i + b_j (1 \leq i<j \leq n)\) 的 \((i,j)\) 对数。
题解
知识点：数学，枚举。
注意到 \(1 \leq a_i,b_i \leq n (1\leq i \leq n)\) ，因此 \(a_i \cdot a_j \leq 2n\) ，即 \(\min(a_i,a_j) \leq \sqrt{2n}\) 。此时，我们设 \(a_j \leq \sqrt{2n}\) 。
因此，我们先将 \(a_i,b_i\) 打包，以 \(a\) 为关键字从小到大排序，这是为了之后从左到右枚举 \(a_i,b_i\) 时，保证满足 \(a_j \leq a_i(1 \leq j < i)\) 这个条件，此时 \(a_j\) 的范围才是 \([1,\sqrt{2n}]\) 。
随后，我们枚举 \(A \in [1,\sqrt{2n}]\) ，作为一轮枚举中 \(a_j\) 满足的值。接下来，从左到右枚举 \(a_i,b_i\) ，有 \(B = A \cdot a_i - b_i\) ，其中 \(B\) 就是在 \(a_j = A\) 时我们希望的 \(b_j\) ，而 \(a_i,b_i\) 的贡献即为 \(1 \leq j <i\) 满足 \(a_j = A\) 的位置中，出现过的 \(b_j = B\) 的位置数。
因此，我们在过程中记录 \(1 \leq j <i\) 满足 \(a_j = A\) 的位置中，出现过的 \(b_j\) 的个数 \(cnt_{b_j}\)。那么，当 \(1 \leq B \leq n\) 时， \(cnt_B\) 即为 \(a_i,b_i\) 的贡献。
时间复杂度 \(O(n \sqrt n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<int, int> c[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++)cin >> c[i].first;
for (int i = 1;i <= n;i++)cin >> c[i].second;
sort(c + 1, c + n + 1);
ll ans = 0;
for (int A = 1;A * A <= 2 * n;A++) {
vector<int> cnt(n + 1);
for (int i = 1;i <= n;i++) {
auto [a, b] = c[i];
int B = A * a - b;
if (1 <= B && B <= n) ans += cnt[B];
if (a == A) cnt[b]++;
}
}
cout << ans << '\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;
}
