A 孰0孰1

$T$ 组数据简单判断一下即可。

void solve(){
    int n;
    cin >> n;
    if (n == 0) cout << "Sakuraba Ema" << "\n";
    if (n == 1) cout << "Nikaido Hiro" << "\n";
}

B 约会

简单区间规划问题，对每个区间按照结束时间排序，贪心放置即可。

void solve() {
    int n, x;
    cin >> n >> x;
    vector<PLL> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(all(a), [&](auto a, auto b) {
        if (a.second != b.second) return a.second < b.second;
        return a.first < b.first;
    });
    ll last = 0, cnt = 0;
    for (auto [s, e] : a) {
        if (s >= last) {
            ++cnt;
            last = e;
        }
    }
    if (cnt * 100 >= x * n) cout << "AX99" << "\n";
    else cout << "oTATo" << "\n";
}

C 艾玛的三种美德

带多重优先级判定的 $0-1$ 背包+路径回溯。

定义：

pr[w] = 当前最大奖励
pc[w] = 达到最大奖励所需的任务数量

对于任务 i：

不选 → 保留上一个状态；
选 → 从 w - a[i] 转移来：
$Cr=pr[w−a[i]]+b[i]$
$Cc=pc[w−a[i]]+1$

比较时：

若 Cr > cr[w] → 直接更新；
若 Cr == cr[w] 且 Cc < cc[w] → 更新；
若 Cr == cr[w] && Cc == cc[w] → 需要比较字典序。

void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }
    vector<ll> pr(k + 1, -INF), cr(k + 1, -INF), pc(k + 1, INF), cc(k + 1, INF);

    pr[0] = pc[0] = 0;

    vector<vector<bool>> vis(n + 1, vector<bool>(k + 1));

    auto calc = [&](int x, int w) {
        vector<int> seq;
        for (int i = x; i >= 1; --i) {
            if (vis[i][w]) {
                seq.push_back(i);
                w -= a[i];
            }
        }
        reverse(all(seq));
        return seq;
    };

    for (int i = 1; i <= n; ++i) {
        cr = pr;
        cc = pc;

        for (int w = a[i]; w <= k; ++w) {
            if (pr[w - a[i]] == -INF) continue;
            ll Cr = pr[w - a[i]] + b[i];
            int Cc = pc[w - a[i]] + 1;

            if (cr[w] == -INF) {
                cr[w] = Cr;
                cc[w] = Cc;
                vis[i][w] = 1;
            } else if (Cr > cr[w]) {
                cr[w] = Cr;
                cc[w] = Cc;
                vis[i][w] = 1;
            } else if (Cr == cr[w]) {
                if (Cc < cc[w]) {
                    cc[w] = Cc;
                    vis[i][w] = 1;
                } else if (Cc == cc[w]) {
                    vector<int> ex = calc(i, w);
                    vector<int> cand = calc(i - 1, w - a[i]);
                    cand.push_back(i);
                    if (cand < ex) {
                        cr[w] = Cr;
                        cc[w] = Cc;
                        vis[i][w] = 1;
                    }
                }
            }
        }
        pr.swap(cr);
        pc.swap(cc);
    }

    ll R = -INF, C = INF, W = -1;
    for (int w = 0; w <= k; ++w) {
        if (pr[w] == -INF) continue;
        if (pr[w] > R) {
            R = pr[w];
            C = pc[w];
            W = w;
        } else if (pr[w] == R) {
            if (pc[w] < C) {
                C = pc[w];
                W = w;
            } else if (pc[w] == C) {
                if (calc(n, w) < calc(n, W)) W = w;
            }
        }
    }

    if (R == -INF) {
        cout << 0 << "";
        return;
    }
    vector<int> ans = calc(n, W);
    cout << R << "\n";
    if (!ans.empty()) {
        for (auto v : ans) {
            cout << v << " ";
        }
    }
    cout << "\n";
}

D 礼物

空读名字直接求和即可，注意数据范围。

void solve() {
    int n;
    ll ans = 0;
    cin >> n;
    while (n--) {
        string s;
        ll x;
        cin >> s >> x;
        ans += x;
    }
    cout << ans << "\n";
}

E 魔法数

如果数组 $gcd$ 不为 $1$ ，必然不可行。

如果已经有 $1$ ，用 $1$ 感染其他元素即可。

否则使用 $dp$ 计算得到 $1$ 的最少操作数，动态维护以当前位置结尾的所有可能的 $gcd$ 值及其对应最短区间长度，每往右一个元素，就更新这些 $gcd$ 的结果。

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

    if (g > 1) {
        cout << -1 << "\n";
        return 0;
    }

    if (c1 > 0) {
        cout << (n - c1) << "\n";
        return 0;
    }

    unordered_map<int, int> dp;
    for (int x : a) {
        unordered_map<int, int> ndp = dp;
        ndp[x] = min(ndp.count(x) ? ndp[x] : INT_MAX, 1);
        for (auto &[gval, len] : dp) {
            int ng = gcd(gval, x);
            if (!ndp.count(ng) || ndp[ng] > len + 1)
                ndp[ng] = len + 1;
        }
        dp = move(ndp);
    }

    cout << (n + dp[1] - 2) << "\n";
}

F 魔法能量柱

单调栈板子题，如果求的是该元素最近的左边（上一个）的最值：就从前往后循环，将栈底向左，栈顶向右。如果求的是该元素最近的右边（下一个）的最值：就从后往前循环，将栈底向右，栈顶向左。

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

    vector<ll> L(n + 1), R(n + 1);
    vector<int> st;

    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && h[st.back()] <= h[i]) st.pop_back();
        L[i] = st.empty() ? 0 : st.back();
        st.pb(i);
    }

    while (!st.empty()) st.pop_back();
    for (int i = n; i >= 1; --i) {
        while (!st.empty() && h[st.back()] <= h[i]) st.pop_back();
        R[i] = st.empty() ? 0 : st.back();
        st.pb(i);
    }

    for (int i = 1; i <= n; ++i) {
        cout << L[i] * R[i] << " ";
    }
    cout << "\n";
}

G 艾玛的高考冲刺

对分数排序后求前缀和，二分分数找临界点即可。

void solve() {
    ll n, k, m;
    cin >> n >> k >> m;

    vector<PLL> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i].second >> a[i].first;
    }
    sort(all(a));

    vector<ll> pre(n + 1);
    for(int i = 0; i < n; ++i) pre[i + 1] = pre[i] + a[i].second;

    if (pre[n] < m) {
        cout << -1 << "\n";
        return;
    }

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

    while (l <= r) {
        ll mid = (l + r) / 2;
        ll p = k + mid;

        int idx = upper_bound(all(a), make_pair(p, INF)) - a.begin();

        ll score = pre[idx];

        if (score >= m) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

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

H 甜品分享

滑动窗口判一下即可。

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

    ll sum = 0;
    int l = 0, ans = 0;
    for (int r = 0; r < n; ++r) {
        sum += a[r];
        while (sum > S) {
            sum -= a[l++];
        }
        ans = max(ans, r - l + 1);
    }
    cout << ans << "\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); cout.tie(0);

    init();

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

鞭尸合集

赛时 $E, F$ , $H$ 数据全水了。

$E$ 题 hack 样例 ,$\texttt{10 6 15}$。(WA hack)

两两不互质，用多个数字构造 $1$ 。

$F$ 题 hack 样例, $\texttt{1 2 3 …. 4999 5000 5000 4999 … 3 2 1}$（TLE hack)

$H$ 题 hack 样例, $n = 10^5, s = 10^{12}, a = \texttt{1….1}(10^5 个 1)$。

global

$T$ 不读

试图 $O(n^2)$ 排序

scanf(“%d%d”, &a, b) 第二个&呢？

A:

$\texttt{Sakura}$ 打成 $\texttt{Saura}$

$\texttt{Ema}$ 打成 $\texttt{Em}$

D :

$1000 \times 10^9 = 10^{12} > INT\_MAX = 2^{31} – 1$， c++ 要开 64位整数。

$10^9$ $1$ 后面有 $9$ 个 $0$。

F:

$10^5 \times 10^5 = 10^{10} > INT\_MAX = 2^{31} – 1$ ， c++ 要开 64位整数。

G:

试图开 $10^9$ 的数组。

H:

max 不初始化。（狗运过了）