A

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e3 + 5;
 
int n, m, _, k;
int a[105];
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n; m = -1;
        rep(i, 0, 100) a[i] = 0;
        rep(i, 1, n) cin >> k, a[k]++;
        rep(i, 0, 101)
            if (a[i] == 0 && m == -1) { m = i * 2; break; }
            else if (a[i] == 1 && m == -1) m = i;
            else if (a[i] == 0) { m += i; break; }
        cout << m << '\n';
    }
    return 0;
}

B

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e5 + 5;
 
int n, m, _, k;
VI a;
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n; a.resize(n);
        for (auto &i : a) cin >> i;
        sort(all(a));
        ll ans = -1e18;
        rep (i, 0, 5) {
            ll cur = 1;
            rep (j, 0, i - 1) cur *= a[j];
            rep (j, 1, 5 - i) cur *= a[n - j];
            ans = max(ans, cur);
        }
        cout << ans << '\n';
    }
    return 0;
}

C

wa 到自闭, 没考虑到 1 -2 不一定有边, 一直在找其他错误

最多两个重心, 必定是相连接的, 从一个重心连接的其他子树中抽一个 叶子节点, 连在另一个重心即可

一个重心, 随便段意条边在连接, 1-2不一定有边!!!!!!

代码有点丑, c为啥这么长啊

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e5 + 5;
 
int n, m, _, k;
int h[N], to[N << 1], ne[N << 1], tot;
int siz[N], mx;
VI a;
 
void add(int u, int v) {
    ne[++tot] = h[u]; to[h[u] = tot] = v;
}
 
void dfs(int x, int fa) {
    siz[x] = 1;
    int mxs = 0;
    for (int i = h[x]; i; i = ne[i]) {
        int y = to[i];
        if (y == fa) continue;
        dfs(y, x);
        mxs = max(mxs, siz[y]);
        siz[x] += siz[y];
    }
    mxs = max(mxs, n - siz[x]);
    if (mxs < mx) mx = mxs, a.resize(0), a.pb(x);
    else if (mx == mxs) a.pb(x);
}
 
int dfss(int x, int fa) {
    if (!ne[h[x]]) {
        cout << x << ' ' << fa << '\n';
        return x;
    }
    for (int i = h[x]; i; i = ne[i]) {
        int y = to[i];
        if (y == fa) continue;
        return dfss(y, x);
    }
    return 0;
}
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n; tot = 0; mx = 1e9;
        a.resize(0);
        rep(i, 1, n) h[i] = siz[i] = 0;
        rep(i, 2, n) {
            int u, v; cin >> u >> v;
            add(u, v); add(v, u);
        }
 
        dfs(1, 0);
        if (a.size() == 2) {
            if (ne[h[a[0]]]) {
                int c = dfss(a[0], a[1]);
                cout << c << ' ' << a[1] << '\n';
            }
            else {
                int c = dfss(a[1], a[0]);
                cout << c << ' ' << a[0] << '\n';
            }
        }
        else {
            int c = to[h[1]];
            cout << c << ' ' << "1\n1 " << c << '\n';
        }
    }
    return 0;
}

D

好题, 差分和前缀和都用到了

首先要想清楚一点, a[i + 1] - a[i] < 0, 则存在 b[i] == b[i + 1] (不懂得接着往下看, 应该也能理解)

b[i + 1] - b[i] >= d[i](d[i] >= 0), c[i] = a[i] - b[i] >= a[i + 1] - b[i + 1] = c[i + 1]

所以 a[i + 1] - a[i] <= d[i](d[i] > 0, 第一句话也应该能理解了)

\(max(b[n], c[1]) = max(b[1] + \sum_{i=1}^{n - 1} d[i], a[1] - b[1])\)

式子中变量只有 b[1], $ min(b[1] + \sum_{i=1}^{n - 1} d[i], a[1] - b[1]) $ 因为奇偶问题 要么相差0, 要么相差1

那 d[i] 怎么取值呢, 想要最大值最小 当然是 d[i] = a[i + 1] - a[i],

区间修改, 只是修改了两个点的 d[l - 1], d[r], 判断合法区间 和 处理两个点的修改就行了, 具体看代码

ps: 不要想着弄个 d[0] = a[1], 把 a[1] 从式子去掉, d[i] 的前缀和加上 d[0], 要注意到我们不论 d[0] 是都大于0我们都要取得, 其他 d[i], 我们是要取 max(0, d[i])的

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e5 + 5;
 
int n, m, _, k;
ll a[N], d[N], s;
 
int main() {
    IOS; cin >> n;
    rep (i, 1, n) cin >> a[i], d[i - 1] = a[i] - a[i - 1];
    rep (i, 1, n - 1) s += max(d[i], 0ll);
    cout << (a[1] + s + 1 >> 1) << '\n';
    for (cin >> _; _; --_) {
        int l, r, x; cin >> l >> r >> x;
        if (l > 1) {
            s -= max(d[l - 1], 0ll); d[l - 1] += x;
            s += max(0ll, d[l - 1]);
        }
        if (r < n) {
            s -= max(d[r], 0ll); d[r] -= x;
            s += max(0ll, d[r]);
        }
        if (l == 1) a[1] += x;
        cout << (a[1] + s + 1 >> 1) << '\n';
    }
    return 0;
}