C. AtCoder Riko

最多有两种长度，一种是\(A\) 的最大值，另一种是 \(A\) 的最小值和 \(A\) 的最大值之和

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

void judge(vector<int> a, int l) {
    while (a.size() and a.back() == l) a.pop_back();
    int n = a.size();
    if (n%2 == 1) return;
    rep(i, n/2) if (a[i]+a[n-1-i] != l) return;
    cout << l << '\n';
}

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    sort(a.begin(), a.end());
    
    judge(a, a.back());
    judge(a, a[0]+a.back());
    
    return 0;
}

D. Many Repunit Sum

每个 \(B_i\) 是由 \(A_i\) 个连续的 1 组成的十进制数（最低位为第 \(0\) 位）。
对任意位 \(p\)，该位为 \(1\) 的 \(B_i\) 的个数恰好是满足 \(A_i > p\) 的数量。
于是，我们可以对每个位 \(p\) 统计出有多少个 \(1\)（记作 \(d[p]\)，这里 \(p=0\) 为最低位），把这些按十进制位累加并处理进位，就能得到最终的大整数和的每一位。

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    const int M = 200010;
    vector<int> c(M);
    rep(i, n) c[a[i]]++;
    
    vector<int> d(M);
    int rem = n;
    rep(i, M) {
        rem -= c[i];
        d[i] = rem;
    }
    
    int carry = 0;
    rep(i, M-1) {
        d[i] += carry;
        carry = d[i]/10;
        d[i] %= 10;
    }
    while (d.back() == 0) d.pop_back();
    reverse(d.begin(), d.end());
    
    for (int x : d) cout << x;
    
    return 0;
}

E. Sparse Range

用 std::set 来维护滑动窗口内的数
一个数能否被加入窗口，只需看它在加入窗口后，对窗口内的数做升序排序，和它前后的两个数做比较即可。如果不能加入就将窗口最左端的数移除掉。

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n, d;
    cin >> n >> d;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    set<int> s;
    s.insert(-d);
    s.insert(1001001001+d);
    
    ll ans = 0;
    int l = 0;
    rep(r, n) {
        while (1) {
            auto it = s.lower_bound(a[r]);
            if (*it-a[r] >= d and a[r]-*prev(it) >= d) break;
            s.erase(a[l]); l++;
        }
        s.insert(a[r]);
        ans += r-l+1;
    }
    
    cout << ans << '\n';
    
    return 0;
}

F. Half and Median

二分答案
假设中位数为 \(x\)
对每根棒子先尽量分出 \(≥x\) 的段，收集这些段并通过对过多的大段进行逐步切分来转化为小段，最后检查能否凑够 \(N+M\) 段与至少 \(\frac{N+M}{2}+1\) 段 \(≥x\) 。

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

void solve() {
    int n; ll m;
    cin >> n >> m;
    
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    
    ll h = (n+m)/2+1;
    
    const int INF = 1001001001;
    auto f = [&](int x) -> bool {
        {
            int big = 0;
            rep(i, n) if (a[i] >= x) big++;
            if (big+m < h) return false;
        }
        
        ll one = 0, big = 0;
        map<int, ll> mp;
        auto add = [&](int len, ll num) {
            if (len < x) one += len*num;
            else mp[len] += num, big += num;
        };
        auto cut = [&](int len, ll num) {
            mp[len] -= num; if (mp[len] == 0) mp.erase(len);
            big -= num;
            add(len/2, num);
            add(len-len/2, num);
        };
        
        rep(i, n) {
            int len = a[i], num = 1;
            while ((len+1)/2 >= x) len /= 2, num *= 2;
            ll r = a[i] - len*num, l = num-r;
            add(len, l);
            if (r) {
                add(len+1, r);
                if (len+1 == x*2-1) cut(len+1, r);
            }
        }
        if (big < h) return false;
        
        while (big > h) {
            auto [len, num] = *mp.rbegin();
            cut(len, min(num, big-h));
        }
        return one+big >= n+m;
    };
    
    int ac = 1, wa = INF;
    while (ac+1 < wa) {
        int wj = (ac+wa)/2;
        if (f(wj)) ac = wj; else wa = wj;
    }
    
    cout << ac << '\n';
}

int main() {
    int t;
    cin >> t;
    
    while (t--) solve();
    
    return 0;
}