比赛链接

A

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    int n, m, k, H;    cin >> n >> m >> k >> H;    int cnt = 0;    for (int i = 1;i <= n;i++) {        int h;        cin >> h;        if (abs(h - H) % k) continue;        int d = abs(h - H) / k;        cnt += 1 <= d && d <= m - 1;    }    cout << cnt << '\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 a[200007];bool odd[200007];bool solve() {    int n;    cin >> n;    for (int i = 1;i <= n;i++) cin >> a[i], odd[i] = a[i] & 1;    sort(a + 1, a + n + 1);    for (int i = 1;i <= n;i++) if ((a[i] & 1) != odd[i]) return false;    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;}

C

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int c[200007];bool solve() {    int n, k;    cin >> n >> k;    for (int i = 1;i <= n;i++) cin >> c[i];    int l = 1, cntl = 0;    while (cntl < k) {        if (l > n) return false;        cntl += c[1] == c[l];        l++;    }    l--;    int r = n, cntr = 0;    while (cntr < k) {        if (r < 1) return false;        cntr += c[n] == c[r];        r--;    }    r++;    if (l < r || c[1] == c[n]) cout << "YES" << '\n';    else return false;    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;}

D

题意

给定长度为 $n-1$ 的前缀和 $a$ ，问原数组是否可能为一个长度为 $n$ 的排列。

题解

知识点：枚举。

考虑还原各个元素，即 $a_1,a_2-a_1,\cdots,a_{n-1}-a_{n-2}$ ，记为数组 $b$ 。

我们记还原过程中重复的数字，或超出范围排列的数字为坏数。

我们发现，如果前缀和是由排列得到的，那么至多有一个坏数，我们分类讨论：

1. 若没有坏数，那么一定可能。
2. 若有一个坏数，则枚举排列中还未出现的数字，当且仅当未出现的数字的和等于坏数才可能。
3. 若有多个坏数，则一定不可能。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; ll a[200007];bool vis[200007];bool solve() {    int n;    cin >> n;    for (int i = 1;i <= n;i++) vis[i] = 0;    for (int i = 1;i <= n - 1;i++) cin >> a[i];    ll bad = 0;    for (int i = 1;i <= n - 1;i++) {        ll d = a[i] - a[i - 1];        if (d > n || vis[d]) {            if (bad) return false;            bad = d;        }        else vis[d] = 1;    }    if (bad) {        int sum = 0;        for (int i = 1;i <= n;i++) {            if (!vis[i]) sum += i;        }        if (sum != bad) return false;    }    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

题意

有 $n$ 种药以及它们的价格 $c_i$ ，现在其中 $k$ 种免费供应，并给出每种药的合成配方（有些药只能买），每次合成需要的药会消耗掉之后要用就要再买，保证配方自己不能合成自己（直接或者间接都不能）。

问合成每种药的最少花费是多少。

题解

知识点：DAG上dp。

把关系建图，在dag上dp即可。

时间复杂度 $O(n+k+n\sum m_i)$

空间复杂度 $O(n+k+n\sum m_i)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; vector<int> g[200007];int c[200007];int f[200007];void dfs(int u) {    if (f[u] != -1) return;    f[u] = c[u];    ll sum = 0;    for (auto v : g[u]) {        dfs(v);        sum += f[v];    }    if (g[u].size()) f[u] = min(sum, (ll)f[u]);} bool solve() {    int n, k;    cin >> n >> k;    for (int i = 1;i <= n;i++) cin >> c[i], f[i] = -1, g[i].clear();    for (int i = 1;i <= k;i++) {        int x;        cin >> x;        c[x] = 0;    }    for (int i = 1;i <= n;i++) {        int m;        cin >> m;        for (int j = 1;j <= m;j++) {            int v;            cin >> v;            g[i].push_back(v);        }    }     for (int i = 1;i <= n;i++) if (f[i] == -1) dfs(i);    for (int i = 1;i <= n;i++) cout << f[i] << " \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;}

F

题意

给定 $k$ 和 $n$ 个数字的数组 $a(a_i<2^k)$ 。

找到两个不同的位置 $i,j$ 和数字 $x < 2^k$ 使得 $(a_i \oplus x) \& (a_j \oplus x)$ 最大。

题解

方法一

知识点：位运算，贪心。

考虑 $x$ 异或 $a_i,a_j$ 对最后答案的影响。我们发现，对于某一位，只要 $a_i,a_j$ 是同 $1$ ，那么 $x$ 只需要 $0$ ；如果是同 $0$ ，那么 $x$ 只需要 $1$ ，其他情况无论 $x$ 这一位是什么最后结果都是 $0$ 。

那么问题变为，找到同或 $a_i \odot a_j$ 最大的即可（也可以是异或最小，两者是对称的）。

这里需要一个结论：一组数字同或最大（异或最小）的一对，一定出现在大小相邻的两个数字中。

感性的理解就是，大小相邻数字同 $0,1$ 且出现在高位的情况比与其他数字匹配的情况多。

因此我们对数字从小到大排序，枚举每一对即可。

时间复杂度 $O(n \log n)$

空间复杂度 $O(n)$

方法二

知识点：位运算，Trie，贪心。

如果得不到上面的结论，我们可以考虑类似最大异或和问题一样用Trie解决。

显然，对于同或最大，从高位到低位贪心地保证数字相同即可，和异或最大刚好相反。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

方法一

#include <bits/stdc++.h>using namespace std;using ll = long long; pair<int, int> a[200007];bool solve() {    int n, k;    cin >> n >> k;    for (int i = 1;i <= n;i++) cin >> a[i].first, a[i].second = i;    sort(a + 1, a + n + 1);     int mx = -1;    array<int, 3> ans{};    for (int i = 2;i <= n;i++) {        int res = ~(a[i - 1].first ^ a[i].first) & ((1 << k) - 1);        if (res > mx) {            mx = res;            ans[0] = a[i - 1].second;            ans[1] = a[i].second;            ans[2] = (~a[i - 1].first & ~a[i].first) & ((1 << k) - 1);        }    }    cout << ans[0] << ' ' << ans[1] << ' ' << ans[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;}

方法二

#include <bits/stdc++.h>using namespace std;using ll = long long; class Trie {    struct Node {        array<int, 2> nxt;        int val;        int id;    };     int bit;    vector<Node> node;    Node NIL; public:    Trie(int _bit = 0) { init(_bit); }     void init(int _bit) {        bit = _bit;        NIL = { {0,0},0 };        node.assign(1, NIL);    }     void insert(int s, int id) {        int p = 0;        for (int i = bit - 1;i >= 0;i--) {            int c = (s >> i) & 1;            if (!node[p].nxt[c]) {                node[p].nxt[c] = node.size();                node.push_back(NIL);            }            p = node[p].nxt[c];        }        node[p].val = s;        node[p].id = id;    }     pair<int, int> find_max(int s) {        int p = 0;        for (int i = bit - 1;i >= 0;i--) {            int c = (s >> i) & 1;            if (node[p].nxt[c]) p = node[p].nxt[c];            else p = node[p].nxt[c ^ 1];        }        return { node[p].val,node[p].id };    }}; bool solve() {    int n, k;    cin >> n >> k;     Trie trie(k);    int mx = -1;    array<int, 3> ans{};    for (int i = 1, x;i <= n;i++) {        cin >> x;        if (i == 1) {            trie.insert(x, i);            continue;        }        auto [y, id] = trie.find_max(x);        int res = ~(x ^ y) & ((1 << k) - 1);        if (res > mx) {            mx = res;            ans[0] = i;            ans[1] = id;            ans[2] = (~x & ~y) & ((1 << k) - 1);        }        trie.insert(x, i);    }    cout << ans[0] << ' ' << ans[1] << ' ' << ans[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;}

G

题意

有 $n$ 个点，每个点的高度为 $h_i$ ，有 $m$ 条双向路径。

若 $i,j$ 存在路径，则从 $i$ 到 $j$ 需要的体力是 $h_i - h_j$ （负数则恢复体力），若没有足够的体力就不能走。

有 $q$ 个询问，每个询问包含起点 $a$ ，终点 $b$ ，以及初始体力 $e$ ，问能否从起点到终点。

题解

知识点：并查集，离线。

我们发现从 $i$ 到 $j$ 所需的体力一定为 $h_i - h_j$ 。因此从 $a$ 能不能走到 $b$ ，取决于是否存在于一条路径使得，路径上的所有点的高度不超过 $e + h_a$ 。

对于边 $(i,j)$ ，当且仅当能到达的高度大于等于两个端点时，这条边才有用，因此设边权为 $\max(h_i,h_j)$ 。

此时，我们可以最小生成树+倍增在线求路径最大值（典中典），也可以离线+启发式合并+DSU处理询问，但这里采用离线+排序+DSU求，比较容易。

考虑对 $e+h_a$ 从小到大排序，对边权从小到大排序，那么每次询问先将边权不超过 $e+h_a$ 的边加入dsu再询问即可。

时间复杂度 $O(n + m \log m + q(\log q + \log n))$

空间复杂度 $O(n + m + q)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; struct DSU {    vector<int> fa;     DSU(int n = 0) { init(n); }     void init(int n) {        fa.assign(n + 1, 0);        iota(fa.begin(), fa.end(), 0);    }     int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }     bool same(int x, int y) { return find(x) == find(y); }     void merge(int x, int y) { fa[find(x)] = find(y); }}; int h[200007];tuple<int, int, int> e[200007];tuple<int, int, int, int> Q[200007];bool ans[200007]; bool solve() {    int n, m;    cin >> n >> m;    for (int i = 1;i <= n;i++) cin >> h[i];    for (int i = 1;i <= m;i++) {        int u, v;        cin >> u >> v;        e[i] = { u,v, max(h[u],h[v]) };    }    sort(e + 1, e + m + 1, [&](auto a, auto b) {return get<2>(a) < get<2>(b);});     int q;    cin >> q;    for (int i = 1;i <= q;i++) {        int u, v, w;        cin >> u >> v >> w;        Q[i] = { u,v,w + h[u], i };    }    sort(Q + 1, Q + q + 1, [&](auto a, auto b) {return get<2>(a) < get<2>(b);});     int pos = 1;    DSU dsu(n);    for (int i = 1;i <= q;i++) {        while (pos <= m && get<2>(e[pos]) <= get<2>(Q[i])) {            dsu.merge(get<0>(e[pos]), get<1>(e[pos]));            pos++;        }        ans[get<3>(Q[i])] = dsu.same(get<0>(Q[i]), get<1>(Q[i]));    }    for (int i = 1;i <= q;i++) cout << (ans[i] ? "YES" : "NO") << '\n';    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;}