A

题目链接

给定总票数 n、候选人 A 当前得票 a、候选人 B 当前得票 b，剩余未投票数为 s = n - a - b。若票数少的人加上剩余票数后仍无法超越另一人，则胜负已定；否则结果不确定。

#include <iostream>
using namespace std;
int main() {
    int n, a, b;
    cin >> n >> a >> b;
    int rem = n - a - b;
    if (a < b) {
        if (a + rem > b) cout << "No";
        else cout << "Yes";
    } else {
        if (b + rem > a) cout << "No";
        else cout << "Yes";
    }
    return 0;
}

B

题目链接

将 n 个字符串按列从下至上输出，每列从右向左输出。若某个位置无字符但上方有字符，则输出 *；若上方无字符则结束该列。记录每列最上方字符的索引（即该列最初出现的位置），以及所有字符串的最大长度。

#include <iostream>
#include <string>
using namespace std;
int n;
string s[105];
int colTop[105], maxLen;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        if ((int)s[i].size() > maxLen) maxLen = s[i].size();
        for (int j = 0; j < (int)s[i].size(); ++j)
            if (colTop[j] == 0) colTop[j] = i;
    }
    for (int c = 0; c < maxLen; ++c) {
        for (int r = n; r >= 1 && r >= colTop[c]; --r) {
            if (c < (int)s[r].size()) cout << s[r][c];
            else cout << '*';
        }
        cout << endl;
    }
    return 0;
}

C

题目链接

维护一个桶记录每个数字出现的次数。遇到类型 1 插入数字，若该数字首次出现则总数加 1；类型 2 删除数字，若删除后次数为 0 则总数减 1；类型 3 输出当前不同数字的个数。

#include <iostream>
using namespace std;
int Q, cnt[1000005], distinct;

int main() {
    cin >> Q;
    while (Q--) {
        int op, x;
        cin >> op;
        if (op == 1) {
            cin >> x;
            if (++cnt[x] == 1) distinct++;
        } else if (op == 2) {
            cin >> x;
            if (--cnt[x] == 0) distinct--;
        } else {
            cout << distinct << endl;
        }
    }
    return 0;
}

D

题目链接

三维前缀和。方法一：直接使用容斥原理递推，构造 sum[i][j][k] = sum[i-1][j][k] + sum[i][j-1][k] + sum[i][j][k-1] - sum[i-1][j-1][k] - sum[i-1][j][k-1] - sum[i][j-1][k-1] + sum[i-1][j-1][k-1] + a[i][j][k]；查询同样用容斥。

#include <iostream>
using namespace std;
int n, q, a[105][105][105], sum[105][105][105];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k) {
                cin >> a[i][j][k];
                sum[i][j][k] = sum[i-1][j][k] + sum[i][j-1][k] + sum[i][j][k-1]
                             - sum[i-1][j-1][k] - sum[i-1][j][k-1] - sum[i][j-1][k-1]
                             + sum[i-1][j-1][k-1] + a[i][j][k];
            }
    cin >> q;
    while (q--) {
        int x1, x2, y1, y2, z1, z2;
        cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        int ans = sum[x2][y2][z2]
                - sum[x1-1][y2][z2] - sum[x2][y1-1][z2] - sum[x2][y2][z1-1]
                + sum[x1-1][y1-1][z2] + sum[x1-1][y2][z1-1] + sum[x2][y1-1][z1-1]
                - sum[x1-1][y1-1][z1-1];
        cout << ans << endl;
    }
    return 0;
}

方法二：分层处理。先计算每一层（即固定第三维）的二维前缀和，再沿第三维方向做一维前缀和。查询时对二维范围做差分，再结合第三维区间求和。

#include <iostream>
using namespace std;
int n, q, a[105][105][105], sum[105][105][105];

int main() {
    cin >> n;
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                cin >> a[i][j][k];
                sum[i][j][k] = sum[i-1][j][k] + sum[i][j-1][k] - sum[i-1][j-1][k] + a[i][j][k];
            }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
                sum[i][j][k] += sum[i][j][k-1];
    cin >> q;
    while (q--) {
        int x1, x2, y1, y2, z1, z2;
        cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        int ans = sum[x2][y2][z2] - sum[x2][y2][z1-1];
        ans -= sum[x2][y1-1][z2] - sum[x2][y1-1][z1-1];
        ans -= sum[x1-1][y2][z2] - sum[x1-1][y2][z1-1];
        ans += sum[x1-1][y1-1][z2] - sum[x1-1][y1-1][z1-1];
        cout << ans << endl;
    }
    return 0;
}

E

题目链接

求满足 Σ|x - x_i| + Σ|y - y_i| ≤ D 的整数点 (x,y) 个数。D ≤ 1e6，可枚举 t = Σ|x - x_i|（0 ≤ t ≤ D），则另一部分 ≤ D-t。分别对 x 和 y 计算代价频数数组，再用乘法/前缀和统计。计算 Σ|x - x_i| 时，将 x_i 排序，利用前缀和快速得到任意 x 的代价。

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n, d, x[200005], y[200005];
int f[1000005], g[1000005];

void calc(int arr[], int freq[]) {
    sort(arr + 1, arr + n + 1);
    arr[0] = -2e6; arr[n+1] = 2e6 + 1;
    int pre = 0, suf = 0;
    for (int i = 1; i <= n; ++i) suf += arr[i];
    for (int i = 0; i <= n; ++i) {
        if (i) { pre += arr[i]; suf -= arr[i]; }
        for (int v = arr[i]; v < arr[i+1]; ++v) {
            int cost = (2 * i - n) * v - pre + suf;
            if (cost <= d) freq[cost]++;
        }
    }
}

signed main() {
    cin >> n >> d;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
    calc(x, f); calc(y, g);
    for (int i = 1; i <= d; ++i) g[i] += g[i-1];
    int ans = 0;
    for (int i = 0; i <= d; ++i) ans += f[i] * g[d - i];
    cout << ans;
    return 0;
}

F

题目链接

有 n 个函数 f_i(x) = A_i * x + B_i，要求选出恰好 k 个并按一定顺序嵌套，使最终值最大。先确定顺序：比较相邻两个 i 和 i+1，若 B_i * (A_{i+1} - 1) < B_{i+1} * (A_i - 1) 则交换更优，据此排序。再用 DP 求解：dp[i][j] 表示前 i 个中选 j 个的最大函数值，转移为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] * A_i + B_i)。

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n, k, dp[200005][15];
struct Func { int a, b; } fs[200005];

bool cmp(Func l, Func r) {
    return l.b * (r.a - 1) > r.b * (l.a - 1);
}

signed main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> fs[i].a >> fs[i].b;
    sort(fs + 1, fs + n + 1, cmp);
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= min(i, k); ++j) {
            dp[i][j] = dp[i-1][j];
            if (j)
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] * fs[i].a + fs[i].b);
        }
    }
    cout << dp[n][k];
    return 0;
}