Codeforces Round 995 (Div. 3)

A.
M和 S准备竞赛。M可以任意天训练，S则在 M训练的下一天训练。求 M 最大化两者的题目数差值 m−s。
题解：从后向前遍历，计算每天 M训练的收益 a[i] 减去 S的损失 b[i+1]。如果差值为正，则 M 训练，累加收益并减去 S 的收益。最后输出总差值。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for(int i=0; i<n; ++i) cin >> a[i];
        for(int i=0; i<n; ++i) cin >> b[i];

        int m = 0;
        for(int i=0; i<n; ++i) {
            if(i == n - 1 || a[i] > b[i + 1]) {
                maxDiff += a[i];
                if(i < n - 1) {
                    m-= b[i + 1];
                }
            }
        }

        cout <<m<< endl;
    }
    return 0;
}

B
题目：
m计划进行一次远足，第一天走 a 公里，第二天走 b 公里，第三天走 c 公里，之后循环。问他完成至少 n 公里时是第几天？
题解：
计算一个周期（三天）的总距离 s=a+b+c。
计算完整周期数 k=⌊sn​⌋，总天数为 3k。
剩余距离 r=n−k×s，若 r≤a，再走1天；若 r≤a+b，再走2天；否则再走3天。
总天数为 3k+额外天数。

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t; 

    while (t--) {
        long long n, a, b, c;
        cin >> n >> a >> b >> c; 
        long long s = a + b + c; 
        long long k = n / s; 
        long long d = k * s; 
        long long remain= n - d; 

        long long extra= 0;
        if (remain > 0) {
            if (remain <= a) {
                extra = 1; 
            } else if (remain <= a + b) {
                extra = 2;
            } else {
                extra = 3; 
            }
        }

        long long total = k*3 + extra; 
        cout << total << endl; 
    }

    return 0;
}

C
题目：
m准备考试，考试有 n 个问题，编号1到 n。有 m 个问题列表，每个列表缺少一个问题，用 ai​ 表示。Monocarp知道 k 个问题的答案，编号为 q1​,q2​,…,qk​。判断m能否通过每个问题列表的考试。
题解：
使用布尔数组 known 标记Monocarp知道的问题。
遍历每个问题列表的缺失编号 ai​，判断 ai​ 是否在 known 中。
若 ai​ 在 known 中，输出 ‘0’（不能通过）；否则输出 ‘1’（可以通过）。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t; 

    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;

        vector<int> a(m);
        for (int i = 0; i < m; ++i) {
            cin >> a[i]; 
        }

        vector<int> q(k);
        for (int i = 0; i < k; ++i) {
            cin >> q[i];
        }
        vector<bool> known(n + 1, false);
        for (int i = 0; i < k; ++i) {
            known[q[i]] = true;
        }
        for (int i = 0; i < m; ++i) {
            if (known[a[i]]) {
                cout << '0'; 
            } else {
                cout << '1';
            }
        }
        cout << endl;
    }

    return 0;
}

如果m不知道任何问题的答案，他将无法通过任何问题列表的考试，输出结果为全 ‘0’。
D
题目：
商店需定价圣诞树，顾客有 ai​ 和 bi​ 两个价格限制，分别对应正面和负面评价。求在不超过 k 条负面评价的情况下，商店的最大收益。
题解：排序,使用优先队列存储 bi​，维护不超过 k 条负面评价。
遍历顾客，计算当前价格下的最大收益。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        long long x, y;
        cin >> n >> x >> y;
        vector<long long> a(n);
        for (int i=0; i<n; ++i) cin >> a[i];
        long long S = 0;
        for (int i=0; i<n; ++i) S += a[i];
        sort(a.begin(), a.end());
        long long count = 0;
        for (int i = 0; i < n - 1; ++i) {
            int left = i + 1, right = n - 1;
            while (left <= right) {
                long long sum = a[i] + a[left];
                if (S - y <= sum && sum <= S - x) {
                    count += right - left + 1;
                    break;
                } else if (sum < S - y) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}

E
题目：
商店需定价圣诞树，顾客有 ai​ 和 bi​ 两个价格限制，分别对应正面和负面评价。求在不超过 k 条负面评价的情况下，商店的最大收益。
题解：
将顾客按 ai​ 排序。
使用优先队列存储 bi​，维护不超过 k 条负面评价。
遍历顾客，计算当前价格下的最大收益。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n), b(n);
        for (int i= 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> b[i];

        vector<pair<int, int>> c;
        for (int i = 0; i < n; ++i) {
            c.push_back({a[i], b[i]});
        }

        sort(c.begin(), c.end());

        long long m = 0, p = 0;
        priority_queue<int> q;

        for (int i = 0; i < n; ++i) {
            p += c[i].first;
            q.push(c[i].second);

            if (q.size() > k) {
                p -= q.top();
                q.pop();
            }

            m = max(m, p);
        }

        cout << m << endl;
    }
    return 0;
}

F
南南南
题意：给一个包含n张牌的牌堆，joker初始在第 m 个位置。有 q 次操作，每次操作将第 ai​ 张牌移到开头或末尾。任务是计算每次操作后joker可能的不同位置数量。
题解：使用区间 [l,r] 表示Joker的可能位置，初始为 [m,m]。
对于每次操作：
若 ai​<l，区间左移：l−=1。
若 ai​>r，区间右移：r+=1。
若 ai​ 在区间内，直接将区间扩展到 [1,n]。
每次操作后，输出区间长度 r−l+1。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void s() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> v = {{m, m}}; 

    for (int i = 1; i<= q; i++) {
        int f;
        cin >> f;

        vector<pair<int, int>> w;
        for (auto &u : v) {
            int a = u.first, b = u.second;
            if (f < a) {
                w.push_back({a - 1, b}); // 左移
            } else if (b < f) {
                w.push_back({a, b + 1}); // 右移
            } else {
                w.push_back({1, n});
            }
        }
        sort(w.begin(), w.end());
        vector<pair<int, int>> x;
        for (auto &u : w) {
            if (x.empty() || x.back().second < u.first) {
                x.push_back(u);
            } else {
                x.back().second = max(x.back().second, u.second);
            }
        }

        v = x;
        int r = 0;
        for (auto &u : v) {
            r += u.second - u.first + 1;
        }
        cout << r << " ";
    }
    cout << "\n";
}

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

G
题目： 蛇的最小占据格子编号
格子有n条蛇，每条蛇初始占据一个格子。进行q次操作，每次操作是蛇的扩展或收缩。求最小的可能得分，即所有蛇占据的最大格子编号。
题解：根据q次操作计算最小的可能得分，即所有蛇占据的最大格子编号。合理安排蛇的初始位置，避免碰撞，并动态调整位置和长度。用贪心，尽量将蛇放置在靠左的位置，如果蛇需要扩展且尚未放置，则将其放置在当前最大位置的右侧。

#include <stdio.h>

#define max1 288
#define max2 88888

int n, q;
int l[max1];
int p[max2]; 
int m;

void opr(char ops[max2][5]) {
    for (int i = 0; i < q; i++) {
        int s;
        char op;
        sscanf(ops[i], "%d %c", &s, &op);
        s--;   

        if (op == '+') {
            if (p[s] == 0) {
                p[s] = m + 1;
                m = p[s] + l[s];
            }
            l[s]++;
            m = (p[s] + l[s] - 1 > m) ? (p[s] + l[s] - 1) : m;
        } else {
            l[s]--;
        }
    }
}

int main() {
    scanf("%d %d", &n, &q);
    char ops[max2][5];
    for (int i = 0; i < q; i++) {
        scanf("%s", ops[i]);
    }

    for (int i = 0; i < n; i++) {
        l[i] = 1;
        p[i] = 0;
    }
    m = 0;

    opr(ops);

    printf("%d\n", m);
    return 0;
}