A 小苯接雨水

不难想到，左右两边放上最大和次大的板子能接的水最多。

void solve() {
    int n, mx = 0, smx = 0;
    cin >> n;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        if (x > mx) smx = mx, mx = x;
        else if (x > smx) smx = x;
    }
    cout << 1ll * smx*(n - 1) << "\n";
}

B 小芳与残骸

对于一个 $0/1$ 串， $|a-b|=a\oplus b$ ，所以 $Ans = \bigoplus\limits_{i=0}^{n-1}\binom{n-1}{i}. a_i \pmod 2$ 。

在 $\mathbb{F}_2$ 上，这个等式是线性方程，因为系数向量非 $0$ ，所以等式等于 $1$ 的解空间大小为 $2^{n-1}$ 。

void solve() {
    int n;
    cin >> n;
    cout << ksm(Z(2), n - 1) << "\n";
}

C 小苯的棋盘游戏

策略是走蛇形，在一个维度上走蛇形另一个维度的长度就没有意义，横着长度或者竖着长度为奇数即可。

void solve() {
    int n, m;
    cin >> n >> m;
    cout << (n & 1 || m & 1 ? "YES" : "NO") << "\n";
}

D 暴暴龙的防奶龙要塞

删除任意一条边仍保持连通 $\rightarrow$ 无桥

存在删除一个顶点会使图不连通 $\rightarrow$ 有割点

所以让两个环共享一个顶点即可。

void solve() {
    int n;
    cin >> n;
    if (n < 5) {
        cout << -1 << "\n";
        return;
    }

    vector<PII> E;
    E.eb(1, 2);
    E.eb(2, 3);
    E.eb(3, 1);

    int prev = 1;
    for (int i = 4; i <= n; ++i) {
        E.eb(prev, i);
        prev = i;
    }
    E.eb(prev, 1);

    cout << E.size() << "\n";
    for (auto [u, v] : E) cout << u << " " << v << "\n";
}

E 奶龙与奥利奥自动机

把最终字符串记为长度 $m$ 的二进制串。拼接段可以是 $0$ 、$1$ 或 $01$ 。若字符串中存在 $p$ 个不重叠的 $01$ 段，把它们作为 $01$ 段，其余字符各自作为单字符段，则总段数为 $m-p$。需要段数 $\le n$，即
$m – p \le n \iff p \ge m – n$ 。

令字符串中 $01$ 的数量为 $k$。可被生成的条件为 $k \ge m – n$。

已知：长度为 $m$ 的二进制串中恰有 $k$ 个 $01$ 的串数为$\binom{m+1}{2k+1}.$

因此总数为 $\sum_{m=0}^{2n} \sum_{k=\max(0,m-n)}^{\lfloor m/2\rfloor} \binom{m+1}{2k+1}$ 。

对求和域进行变换与化简，可得闭式：$Ans = \sum_{k=0}^{n} \binom{n+k+2}{2k+2}$.

卡常，但是为了观看方便，这里还是放了使用自动取模的代码。

void solve() {
    int n;
    cin >> n;
    Z ans = 0;
    for (int i = 0; i <= n; ++i)  ans += C.C(n + i + 2, 2 * i + 2);
    cout << ans << "\n";
}

F 奶龙智斗暴暴龙

最优解是把 $1$ 份鱼放到 $A$ 桶（ $A$ 中只有这一份鱼），把其余的 $n−1$ 份鱼和 $n$ 个鸡腿放到 $B$​ 桶， $P = \frac{1}{2}+\frac{1}{2}\cdot\frac{n-1}{2n-1}$ 。

void solve() {
    ll n;
    cin >> n;
    double ans;
    cout << 0.5 + 0.5 * (n - 1) / (2 * n - 1) << "\n";
}

G 小红的抛物线

抛物线的导数线性 $y’ = 2ax + b$ ；随 x 单调变化方向由 $a$ 决定。因此把点按 $x$ 升序排列，比较前后两段平均斜率是否递增：若斜率增大则 $a>0$（ $UP$ ），否则 $a<0$（ $DOWN$ ）。

void solve() {
    ll x[3], y[3];
    for (int i = 0; i < 3; ++i) cin >> x[i] >> y[i];
    vector<int> id = {0, 1, 2};
    sort(all(id), [&](int a, int b) {
        return x[a] < x[b];
    });

    int A = id[0], B = id[1], C = id[2];

    if ((y[B] - y[A]) * (x[C] - x[B]) < (y[C] - y[B]) * (x[B] - x[A])) cout << "UP" << "\n";
    else cout << "DOWN" << "\n";
}

H 小苯的序列染色

若区间 $[l,r]$ 长度为 $len=r-l+1$ 且满足条件，则必有端点之一等于 $len$（因为 $max(a_l,a_r)=len$ ），即 $len = a_l$ 或 $len = a_r$ 。因此只需要对每个位置 $i$ 以 $len=a_i$ 枚举最多两个候选区间：

• 以 $i$ 为左端：$[i, i+len-1]$（若 $i+len-1 \le n$ ），并检验 max(a[i], a[i+len-1]) == len；
• 以 $i$ 为右端：$[i-len+1, i]$（若 $i-len+1 \ge 1$），并检验 max(a[i-len+1], a[i]) == len。

这样枚举出的区间数不超过 $2n$ 。

得到所有合法区间后，问题变为：用这些区间最少次数覆盖区间 $[1,n]$ ，直接贪心即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<PII> segs;

    for (int i = 1; i <= n; ++i) {
        int len = a[i];
        if (len >= 1) {
            int r = i + len - 1;
            if (r <= n) {
                if (a[r] <= len) segs.eb(i, r);
            }
            int l = i - len + 1;
            if (l >= 1) {
                if (a[l] <= len) segs.eb(l, i);
            }
        }
    }

    if (segs.empty()) {
        cout << -1 << "\n";
        return;
    }

    sort(all(segs), [&](auto x, auto y) {
        if (x.fi != y.fi) return x.fi < y.fi;
        return x.se > y.se;
    });

    int pos = 1, idx = 0, ans = 0;
    int m = segs.size();
    while (pos <= n) {
        int best = -1;
        while (idx < m && segs[idx].fi <= pos) {
            if (segs[idx].se > best) best = segs[idx].se;
            ++idx;
        }
        if (best < pos) {
            cout << -1 << "\n";
            return;
        }
        ++ans;
        pos = best + 1;
    }

    cout << ans << "\n";
}

I 小苯的字符串构造

• 任一完全落在某个单字符块内的奇长度子串（例如 $aaa$ ）在该块中的出现次数为 block_len - sub_len + 1 ，其奇偶性与 $block_len$ 同性，因此为奇（因为 $block_len$ 是奇数）。
• 跨块的子串（至少包含两种不同字母）在整个字符串中只会以一种起点/位置出现（因为相邻字母序列唯一），因此出现次数为 $1$（奇数）。

所以只要分块使得每个块长度为奇数并且使用不同字母就可行。构造简单：

• 若 $n$ ≤ 26：使用 $n$ 个块，每块长度 $1$，即字符串为 $abc…$ 。
• 若 $n$ > 26：选 $m=26$（若 $n$ 偶）或 $m=25$（若 $n$ 奇），把前 $m-1$ 个块设为长度 $1$ ，最后一块长度为 $n-(m-1)$（这值为正奇数，因为 $m$ 与 $n$ 同奇偶）。这样块数 $\leq 26$​ 且每块奇数。

void solve() {
    int n, m;
    cin >> n;
    if (n <= 26) m = n;
    else {
        if (n % 2 == 0) m = 26;
        else m = 25;
    }
    vector<int> len;
    for (int i = 0; i < m - 1; ++i) len.pb(1);
    len.pb(n - (m - 1));

    string s;
    for (int i = 0; i < m; ++i) {
        s.append(len[i], char('a' + i));
    }
    cout << s << "\n";
}

J 小苯的运算式

把子序列的长度的奇偶性作为状态。定义：

• $odd$ ：目前能得到且长度为奇数的子序列的最大交替和（最后一个元素是“+”位）。
• $even$ ：目前能得到且长度为偶数的子序列的最大交替和（最后一个元素是“-”位）；注意空序列为偶数长度且值 $0$ 。

遍历每个元素 $x=a_i$ ，可以选择不取，也可以把它作为下一个被选元素：

• 若把它作为“+”加入（使长度变成奇数），候选值为 $even + x$（也可以保持原 $odd$ 不变）；
• 若把它作为“−”加入（使长度变成偶数），候选值为 $odd – x$（也可以保持原 $even$ 不变）。

最终答案是 $max(0, odd, even)$​ 。

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    ll o = -INF;
    ll e = 0;

    for (auto v : a) {
        ll o2 = max(o, e + v);
        ll e2 = max(e, o - v);
        o = o2;
        e = e2;
    }

    cout << max({0ll, o, e}) << "\n";
}

K 小苯的闯关游戏

若某个 $x$ 可行，则任意更大的初始战力也必然可行（因为每一步情况不会更差）。因此可以二分最小 $x$ 。

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    auto check = [&](ll p)->bool {
        ll x = p;
        for (int i = 0; i < n; ++i) {
            if (x > a[i]) ++x;
            else if (x < a[i]) --x;
        }
        return x > p;
    };

    ll l = 0, r = 1e9, ans = r;

    while (l <= r) {
        ll mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans << "\n";
}

L 小苯的序列还原

手玩一下即可，最终的数组就是 $[a_n,a_{n-2},\cdots,a_{n\&1},a_{n\oplus1},\cdots,a_{n-1}]$ 。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> p;
    for (int i = n - 1; i >= 0; i -= 2) p.pb(i);
    for (int i = n & 1; i < n; i += 2) p.pb(i);

    vector<ll> b(n);
    for (int k = 0; k < n; ++k) {
        b[p[k]] = a[k];
    }

    for (int i = 0; i < n; ++i) {
        cout << b[i] << " ";
    }
    cout << "\n";
}

M GPA Calculator

判断一下算一下即可。

void solve() {
    double x;
    cin >> x;
    cout << (x < 60 ? 0 : 1.0 + (x - 60) * 0.1) << "\n";
}

头文件

//Another
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}