https://anoth3r.top/solution/bistu17/

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 小芳与残骸

对于一个 串， ，所以 。

在 上，这个等式是线性方程，因为系数向量非 ，所以等式等于 的解空间大小为 。

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 暴暴龙的防奶龙要塞

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

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

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

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 奶龙与奥利奥自动机

把最终字符串记为长度 的二进制串。拼接段可以是 、 或 。若字符串中存在 个不重叠的 段，把它们作为 段，其余字符各自作为单字符段，则总段数为 。需要段数 ，即 。

令字符串中 的数量为 。可被生成的条件为 。

已知：长度为 的二进制串中恰有 个 的串数为

因此总数为 。

对求和域进行变换与化简，可得闭式：.

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

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 奶龙智斗暴暴龙

最优解是把 份鱼放到 桶（ 中只有这一份鱼），把其余的 份鱼和 个鸡腿放到 ​ 桶， 。

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

G 小红的抛物线

抛物线的导数线性 ；随 x 单调变化方向由 决定。因此把点按 升序排列，比较前后两段平均斜率是否递增：若斜率增大则 （ ），否则 （ ）。

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 小苯的序列染色

若区间 长度为 且满足条件，则必有端点之一等于 （因为 ），即 或 。因此只需要对每个位置 以 枚举最多两个候选区间：

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

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

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

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 小苯的字符串构造

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

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

• 若 ≤ 26：使用 个块，每块长度 ，即字符串为 。
• 若 > 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 小苯的运算式

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

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

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

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

最终答案是 ​ 。

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 小苯的闯关游戏

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

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 小苯的序列还原

手玩一下即可，最终的数组就是 。

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;
}

自动取模

template<class T>
constexpr T ksm(T a, ll b) {
	T res = 1;
	while (b) {
		if (b & 1) res *= a;
		b >>= 1;
		a *= a;
	}
	return res;
}

template<int P>
struct MInt {
	int x;
	constexpr MInt(): x() {}
	constexpr MInt(ll x) : x{norm(x % getMod())} {}
	static int Mod;
	constexpr static int getMod() {
		if (P > 0) {
			return P;
		} else {
			return Mod;
		}
	}
	constexpr static void setMod(int Mod_) {
		Mod = Mod_;
	}
	constexpr int norm(int x) const {
		if (x < 0) {
			x += getMod();
		}
		if (x >= getMod()) {
			x -= getMod();
		}
		return x;
	}
	constexpr int val() const {
		return x;
	}
	explicit constexpr operator int() const {
		return x;
	}
	constexpr MInt operator-() const {
		MInt res;
		res.x = norm(getMod() - x);
		return res;
	}
	constexpr MInt inv() const {
		assert(x != 0);
		return ksm(*this, getMod() - 2);
	}
	constexpr MInt &operator*=(MInt rhs) & {
		x = 1LL * x * rhs.x % getMod();
		return *this;
	}
	constexpr MInt &operator+=(MInt rhs) & {
		x = norm(x + rhs.x);
		return *this;
	}
	constexpr MInt &operator-=(MInt rhs) & {
		x = norm(x - rhs.x);
		return *this;
	}
	constexpr MInt &operator/=(MInt rhs) & {
		return *this *= rhs.inv();
	}
	friend constexpr MInt operator*(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res *= rhs;
		return res;
	}
	friend constexpr MInt operator+(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res += rhs;
		return res;
	}
	friend constexpr MInt operator-(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res -= rhs;
		return res;
	}
	friend constexpr MInt operator/(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res /= rhs;
		return res;
	}
	friend constexpr istream &operator>>(istream &is, MInt &a) {
		ll v;
		is >> v;
		a = MInt(v);
		return is;
	}
	friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
		return os << a.val();
	}
	friend constexpr bool operator==(MInt lhs, MInt rhs) {
		return lhs.val() == rhs.val();
	}
	friend constexpr bool operator!=(MInt lhs, MInt rhs) {
		return lhs.val() != rhs.val();
	}
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;

组合数学

struct Comb {
    int n;
    vector<Z> _fac, _inv;

    Comb() : _fac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _inv[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _inv[i - 1] = _inv[i] * i;
        }
        n = m;
    }
    Z fac(int x) {
        if (x > n) init(x);
        return _fac[x];
    }
    Z inv(int x) {
        if (x > n) init(x);
        return _inv[x];
    }
    Z C(int x, int y) {
        if (x < 0 || y < 0 || x < y) return 0;
        return fac(x) * inv(y) * inv(x - y);
    }
    Z A(int x, int y) {
        if (x < 0 || y < 0 || x < y) return 0;
        return fac(x) * inv(x - y);
    }
};