题解 | #牛客周赛 Round 138#

link

A

显然，都输出 YES。

。

#include "bits/stdc++.h"
using namespace std;
void solve() {
    int x, y;
    cin >> x >> y;
    cout << "YES\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

暴力枚举。

。

#include "bits/stdc++.h"
using namespace std;
void solve() {
    int x, y;
    cin >> x >> y;
    int ans = 0;
    for (int i = x; ; i /= 2) {
        for (int j = y; ; j /= 2) {
            ans = max(ans, (i ^ j));
            if (j == 0) {
                break;
            }
        }
        if (i == 0) {
            break;
        }
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

倒着贪心。
。

#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
void solve() {
    int n;
    cin >> n;
    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    auto get = [&](i64 &x) {
        string s = to_string(x);
        int r = 0;
        for (auto &si : s) {
            r += si - '0';
        }
        return r;
    };
    int ans = 0;
    for (int i = n - 2; i >= 0; i--) {
        while (a[i] > a[i + 1]) {
            i64 g = get(a[i]);
            if (g == a[i] && g > a[i + 1]) {
                cout << "-1\n";
                return;
            } 
            a[i] = g;
            ans += 1;
        }
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

dfs。

。

#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
void solve() {
    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u -= 1, v -= 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> dp(n);
    dp[0] = 1;
    i64 ans = 0;
    function<void(int, int)> dfs = [&](int x, int p) {
        if (c[p] == c[x]) {
            dp[x] = dp[p] + 1;
        } else {
            dp[x] = 1;
        }
        ans += dp[x] - 1;
        for (auto y : adj[x]) {
            if (y != p) {
                dfs(y, x);
            }
        }
    };
    dfs(0, -1);
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

dp。

。

#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    const i64 inf = 1E18;
    i64 dp = 0;
    i64 b[2] = {-inf, -inf};
    for (int i = 0; i < n; i++) {
        int p = abs(a[i]) % 2;
        i64 cand = -inf;
        if (b[p] != -inf) {
            cand = b[p] + a[i];
        }
        i64 ndp = max(dp, cand);
        b[p] = max(b[p], dp + a[i]);
        dp = ndp;
    }
    cout << dp << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

枚举和 ，找到所有 。

问题转化为找到最长嵌套链，这里用了 个树状数组。

。

#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
template <class T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(int n) : n(n), a(n, T()) {}
    void modify(int i, T x) {
        for (i++; i <= n; i += i & -i) {
            a[i - 1] += x;
        }
    }
    T get(int i) {
        T res = T();
        for (; i > 0; i -= i & -i) {
            res += a[i - 1];
        }
        return res;
    }
};
struct Max {
    int x;
    Max(int x = 0) : x(x) {}
    Max &operator+=(const Max &a) {
        x = max(a.x, x);
        return *this;
    }
};
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> pre(n + 1, vector<int>(1001));
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i];
        pre[i + 1][a[i]]++;
    }
    int ans = 1;
    vector<Fenwick<Max>> f(2001, Fenwick<Max>(n + 1));
    for (int i = 0; i < n; i++) {
        vector<array<int, 3>> p;
        for (int j = i + 1; j < n; j++) {
            int s = a[i] + a[j];
            int pos = n - j;
            int dp = f[s].get(pos - 1).x + 1;
            ans = max(ans, dp * 2);
            if (s % 2 == 0) {
                int mid = s / 2;
                if (mid <= 1000 && pre[j][mid] - pre[i + 1][mid] > 0) {
                    ans = max(ans, dp * 2 + 1);
                }
            }
            p.push_back({s, pos, dp});
        }
        for (auto &x : p) {
            f[x[0]].modify(x[1] - 1, x[2]);
        }
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}