比赛链接

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 a_i$ ，那么 $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;}