366

很久没打 ABC 了，非常不习惯，居然 ABC 各 wa 一发，离谱的

A - Election 2

AtCoder 市正在举行市长选举。候选人是高桥和青木。

有 $N$ 张有效选票投给两位候选人中的任何一位，目前正在进行计票。这里， $N$ 是奇数。

目前的计票结果是：高桥 $T$ 票，青木 $A$ 票。

请判断此时选举结果是否已经确定。

若当前票数已经过半则没希望了，否则有希望

void solve() {
    int n, a, b;cin >> n >> a >> b;
    if (a > n / 2 || b > n / 2) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

B - Vertical Writing

给你一个横向书写的文本。将其转换为竖写，用 * 填充空格。

给你 $N$ 个由小写英文字母组成的字符串 $S_{1}, S_{2}, \dots, S_{N}$ 。设 $M$ 为这些字符串的最大长度。

请打印 $M$ 个满足以下条件的字符串 $T_{1}, T_{2}, \dots, T_{M}$ ：

每个 $T_{i}$ 由小写英文字母和 * 组成。
每个 $T_{i}$ 都不以 * 结尾。
每个 $1 \leq i \leq N$ 都满足以下条件：
- 对于每个 $1 \leq j \leq | S_{i} |$ ， $T_{j}$ 的 $(N - i + 1)$ 个字符存在， $T_{1}, T_{2}, \dots, T_{| S_{i} |}$ 的 $(N - i + 1)$ 个字符按此顺序连接等于 $S_{i}$ 。
- 对于每个 $| S_{i} | + 1 \leq j \leq M$ ， $T_{j}$ 的 $(N - i + 1)$ -th 字符要么不存在，要么是 *。

这里， $| S_{i} |$ 表示字符串 $S_{i}$ 的长度。

题目意思太复杂看不懂... 意思就是要竖着写过来，且需要对齐

void solve() {
    int n;cin >> n;
    string s[n];
    int mx = 0;
    for (int i = 0;i < n;i++)cin >> s[i], mx = max(mx, (int)s[i].size());
    string ans[mx];

    for (int i = n - 1;i >= 0;i--) {
        for (int j = 0;j < mx;j++) {
            if (j < s[i].size()) {
                ans[j].push_back(s[i][j]);
            } else {
                ans[j].push_back('*');
            }
        }
    }

    for (int i = 0;i < mx;i++) {
        string ss = ans[i];
        for (int i = ss.size() - 1;i >= 0;i--) {
            if (ss[i] == '*')ss.pop_back();
            else break;
        }
        cout << ss << '\n';
    }
}

C - Balls and Bag Query

你有一个空袋子。给你 $Q$ 个查询，必须按顺序处理。

有三种查询。

1 x ：将一个写有整数 $x$ 的球放入袋子中。
2 x : 从袋子中取出一个写有整数 $x$ 的球并丢弃。当给出这个查询时，可以保证袋子中有一个写着整数 $x$ 的球。
3 : 打印袋中写有不同整数的球的个数。

送的，我想用 multiset 解决怎么说

void solve() {
    int q;cin >> q;
    map<int, int>mp;
    int cnt = 0;
    while (q--) {
        int op;cin >> op;
        if (op == 1) {
            int x;cin >> x;if (!mp[x])cnt++;
            mp[x]++;
        } else if (op == 2) {
            int x;cin >> x;if (!mp[x])cnt--;
            mp[x]--;
        } else {
            cout << cnt << '\n';
        }
    }
}

D - Cuboid Sum Query

给你一个正整数 $N$ ，以及每个整数 $(x, y, z)$ 的三元组 $1 \leq x, y, z \leq N$ 的整数 $A_{x, y, z}$ 。

你将得到以下格式的 $Q$ 个查询，必须按顺序处理。

对于 $i$ -th 查询 $(1 \leq i \leq Q)$ ，您将得到一个整数元组 $(L x_{i}, R x_{i}, L y_{i}, R y_{i}, L z_{i}, R z_{i})$ ，其中 $1 \leq L x_{i} \leq R x_{i} \leq N$ , $1 \leq L y_{i} \leq R y_{i} \leq N$ , 和 $1 \leq L z_{i} \leq R z_{i} \leq N$ 。求

$\sum_{x = L x_{i}}^{R x_{i}} \sum_{y = L y_{i}}^{R y_{i}} \sum_{z = L z_{i}}^{R z_{i}} A_{x, y, z}$ .

高维前缀和/容斥原理

即求三维前缀和，顺便一提有个 SOS DP 没有补 1995(961div2)-D

为了方便书写，可以提前将 $x_{1}, y_{1}, z_{1}$ 减去 1

若是使用容斥原理则可以将代码更加简化... 等我打完 div2 再说

#define int long long
int a[110][110][110];
void solve() {
    int n;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];
            }
        }
    }
    int q;cin >> q;
    //--与下面的等价
    // for (int i = 1;i <= n;i++) {
    //     for (int j = 1;j <= n;j++) {
    //         for (int k = 1;k <= n;k++) {
    //             b[i][j][k] =
    //                 a[i][j][k]
    //                 + b[i - 1][j][k] + b[i][j - 1][k] + b[i][j][k - 1]
    //                 - b[i - 1][j - 1][k] - b[i - 1][j][k - 1] - b[i][j - 1][k - 1]
    //                 + b[i - 1][j - 1][k - 1];
    //         }
    //     }
    // }
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            for (int k = 1;k <= n;k++)
                a[i][j][k] += a[i - 1][j][k];
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            for (int k = 1;k <= n;k++)
                a[i][j][k] += a[i][j - 1][k];
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            for (int k = 1;k <= n;k++)
                a[i][j][k] += a[i][j][k - 1];

    while (q--) {
        int x1, x2, y1, y2, z1, z2;cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        int sum = a[x2][y2][z2]
            - a[x1 - 1][y2][z2]
            - a[x2][y1 - 1][z2]
            - a[x2][y2][z1 - 1]
            + a[x1 - 1][y1 - 1][z2]
            + a[x1 - 1][y2][z1 - 1]
            + a[x2][y1 - 1][z1 - 1]
            - a[x1 - 1][y1 - 1][z1 - 1];
        cout << sum << '\n';
    }
}

E - Manhattan Multifocal Ellipse

给你一个二维平面上的 $N$ 点 $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})$ 和一个非负整数 $D$ 。

求 $(x, y)$ 使得 $\sum_{i = 1}^{N} (| x - x_{i} | + | y - y_{i} |) \leq D$ 的整数对 $(x, y)$ 的个数。

Solution

1998(965div2) 补了继续补