Atcoder Beginner Contest 366

传送门

A - Election 2

时间限制：2秒内存限制：1024MB

分数：100分

问题描述

在 AtCoder 市举行市长选举。候选人是 Takahashi 和 Aoki。

目前有 N 张有效选票投给了这两个候选人，并且计票正在进行中。这里，N 是一个奇数。

目前的票数为 Takahashi 得 T 票，Aoki 得 A 票。

确定在这个时候选举的结果是否已经确定。

限制

$1 \le N \le 99$
N 是奇数
$0 \le T, A \le N$
$T + A \le N$
所有输入都是整数

输入格式

输入以以下格式从标准输入给出：

$N \hspace{1em} T \hspace{1em} A$

输出格式

如果选举结果已经确定，则输出“Yes”，否则输出“No”。

样例输入输出

样例输入1

$7 \hspace{0.5em} 4 \hspace{0.5em} 2$

样例输出1

$Yes$

即使剩下的一票投给 Aoki，Takahashi 仍然会获胜。也就是说，他的胜利已经确定，所以打印“Yes”。

样例输入2

$99 \hspace{0.5em} 12 \hspace{0.5em} 48$

样例输出2

$No$

虽然 Aoki 目前获得的票数更多，但如果 Takahashi 获得剩下的39票，他就会获胜。因此，打印“No”。

样例输入3

$1 \hspace{0.5em} 0 \hspace{0.5em} 0$

样例输出3

$No$

思路

只有 T 或者 A 大于等于 N 的一半的时候输出 Yes，否则输出 No。

代码

#include <bits/stdc++.h>
using namespace std;inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}int main() {int n = read(), t = read(), a = read();if (t > n / 2 || a > n / 2) puts("Yes");else puts("No");return 0;
}

B - Vertical Writing

时间限制：2秒内存限制：1024MB

分数：200分

问题描述

给定一个水平书写的文本，将其转换为垂直书写，并用 * 填充空白。

你有 N 个字符串 $S_1, S_2, \ldots, S_N$ ，它们由小写英文字母组成。令 M 为这些字符串的最大长度。

请打印 M 个字符串 $T_1, T_2, \ldots, T_N$ ，满足以下条件：

1. 每个 $T_i$ 由小写英文字母和 * 组成。
2. 每个 $T_i$ 的末尾不应为 *。
3. 对于每一个 1 ≤ i ≤ N，满足以下条件：
对于每一个 1 ≤ j ≤ ∣ $S_i$ ∣， $T_j$ 的第 (N - i + 1) 个字符存在，并且 $T_1, T_2, \ldots, T_{|S_i|}$ 的第 (N - i + 1) 个字符依次连接等于 $S_i$ 。
对于 ∣ $S_i$ ∣+1 ≤ j ≤ M， $T_j$ 的第 (N - i + 1) 个字符要么不存在，要么为 *。

这里，∣ $S_i$ ∣表示字符串 $S_i$ 的长度。

限制

N 是一个在 1 到 100 之间（包括 1 和 100）的整数。
每个 $S_i$ 是一个由小写英文字母组成的字符串，长度在 1 到 100 之间（包括 1 和 100）。

输入格式

输入以以下格式从标准输入给出：

$N\\ S_1\\ S_2\\ \vdots\\ S_N$

输出格式

按照以下格式打印答案：

$T_1\\T_2\\ \vdots\\ T_N$

样例输入输出

样例输入1

$3\\ abc\\ de\\ fghi$

样例输出1

$fda\\ geb\\ h*c\\ i$

将 * 作为 $T_3$ 的第 2 个字符放置，可以将 c 放在正确的位置。另一方面，将 * 作为 $T_4$ 的第 2 和第 3 个字符放置会使 $T_4$ 以 * 结尾，这违反了条件。

样例输入2

$3\\ atcoder\\ beginner\\ contest$

样例输出2

$cba\\ oet\\ ngc\\ tio\\ end\\ sne\\ ter\\ *r$

思路

按照题意模拟

代码

#include <bits/stdc++.h>
using namespace std;int n, len = 0;
string s[105];int main() {ios::sync_with_stdio(false); cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> s[i];int size = s[i].size();len = max(len, size); // 记录最大长度}for (int i = 0; i < len; i++) {int num = 0;for (int j = n; j; j--) {int size = s[j].size();if (i < size) {for (int i = 1; i <= num; i++) putchar('*');num = 0;putchar(s[j][i]);}else num++; // 避免*出现在字符串末尾}putchar('\n');}return 0;
}

C - Balls and Bag Query

时间限制：2秒内存限制：1024MB

分数：300分

问题描述

你有一个空袋子。你需要处理 Q 个查询，这些查询必须按顺序进行。

查询有三种类型：

1. 1 x：将一个写有整数 x 的球放入袋子。
2. 2 x：从袋子中移除一个写有整数 x 的球并丢弃。保证在执行此查询时，袋子中有一个写有整数 x 的球。
3. 3：打印袋子中球上写着的不同整数的数量。

限制

$1 \le Q \le 2 \times 10^5$
$1 \le x \le 10^6$
当给出第二类查询时，袋子中有一个写有整数 x 的球。
至少有一个第三类查询。
所有输入值均为整数。

输入格式

输入以以下格式从标准输入给出：

$Q\\ query_1\\ query_2\\ \vdots\\ query_Q$

第 i 个查询 $query_i$ 以以下三种格式之一给出：

$1 \hspace{0.5em} x\\ 2 \hspace{0.5em} x\\ 3$

输出格式

如果有 K 个第三类查询，打印 K 行。第 i 行 ( $1 \le i \le K$ ) 应包含第 i 个第三类查询的答案。

样例输入输出

样例输入1

$8\\ 1 \hspace{0.5em} 3\\ 1 \hspace{0.5em} 1\\ 1 \hspace{0.5em} 4\\ 3\\ 2 \hspace{0.5em} 1\\ 3\\ 1 \hspace{0.5em} 5\\ 3$

样例输出1

$3\\ 2\\ 3$

初始时，袋子是空的。

对于第一个查询 1 3，一个写有整数 3 的球进入袋子。

对于第二个查询 1 1，一个写有整数 1 的球进入袋子。

对于第三个查询 1 4，一个写有整数 4 的球进入袋子。

对于第四个查询 3，袋子里有写有整数 1、3、4 的球，因此输出 3。

对于第五个查询 2 1，一个写有整数 1 的球从袋子中被移除。

对于第六个查询 3，袋子里有写有整数 3、4 的球，因此输出 2。

对于第七个查询 1 5，一个写有整数 5 的球进入袋子。

对于第八个查询 3，袋子里有写有整数 3、4、5 的球，因此输出 3。

样例输入2

$8\\ 1 \hspace{0.5em} 2\\ 1 \hspace{0.5em} 2\\ 3\\ 2 \hspace{0.5em} 2\\ 1 \hspace{0.5em} 4\\ 1 \hspace{0.5em} 4\\ 2 \hspace{0.5em} 2\\ 3$

样例输出2

$1\\ 1$

思路

用数组记录写有 x 的球个数，同时记录有多少种不同的球。

代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int q, vis[N], num = 0;inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}int main() {for (int i = 0; i <= 1000000; i++) vis[i] = 0;q = read();for (int i = 1; i <= q; i++) {int opt = read();if (opt == 3) printf("%d\n", num);else {int x = read();if (opt == 1) {if (!vis[x]) num++;vis[x]++;}if (opt == 2) {vis[x]--;if (!vis[x]) num--;}}}return 0;
}

D - Cuboid Sum Query

时间限制：3秒内存限制：1024MB

分数：400分

问题描述

给定一个正整数 N，以及每个整数三元组 (x, y, z) 对应的整数 $A_{x, y, z}$ ，其中 1 ≤ x, y, z ≤ N。

你将会收到 Q 个查询，必须按顺序处理。

对于第 i 个查询 (1 ≤ i ≤ Q)，你将得到一个整数元组 $(L_{x_i}, R_{x_i}, L_{y_i}, R_{y_i}, L_{z_i}, R_{z_i})$ ，其中 $1 \le L_{x_i} \le R_{x_i} \le N, 1 \le L_{y_i} \le R_{y_i} \le N, 1 \le L_{z_i} \le R_{z_i} \le N$ 。要求找到以下和：

$\sum_{x = L_{x_i}}^{R_{x_i}}\sum_{x = L_{y_i}}^{R_{y_i}}\sum_{x = L_{z_i}}^{R_{z_i}}A_{x, y, z}$

限制

$1 \le N \le 100$
$1 \le Q \le 2 \times 10^5$
$0 \le A_{x, y, z} \le 999 (1 \le x, y, z \le N)$
$1 \le L_{x_i} \le R_{x_i} \le N$
$1 \le L_{y_i} \le R_{y_i} \le N$
$1 \le L_{z_i} \le R_{z_i} \le N$
所有输入都是整数

输入格式

输入以以下格式从标准输入给出：

输出格式

打印 Q 行。第 i 行应包含第 i 个查询的答案。

$N\\ A_{1, 1, 1}, A_{1, 1, 2}, \ldots, A_{1, 1, N}\\ A_{1, 2, 1}, A_{1, 2, 2}, \ldots, A_{1, 2, N}\\ \vdots\\ A_{1, N, 1}, A_{1, N, 2}, \ldots, A_{1, N, N}\\ A_{2, 1, 1}, A_{2, 1, 2}, \ldots, A_{2, 1, N}\\ A_{2, 2, 1}, A_{2, 2, 2}, \ldots, A_{2, 2, N}\\ \vdots\\ A_{2, N, 1}, A_{2, N, 2}, \ldots, A_{2, N, N}\\ \vdots\\ A_{N, 1, 1}, A_{N, 1, 2}, \ldots, A_{N, 1, N}\\ A_{N, 2, 1}, A_{N, 2, 2}, \ldots, A_{N, 2, N}\\ \vdots\\ A_{N, N, 1}, A_{N, N, 2}, \ldots, A_{N, N, N}\\ Q\\ L_{x_1} \hspace{1em} R_{x_1} \hspace{1em} L_{y_1} \hspace{1em} R_{y_1} \hspace{1em} L_{z_1} \hspace{1em} R_{z_1}\\ L_{x_2} \hspace{1em} R_{x_2} \hspace{1em} L_{y_2} \hspace{1em} R_{y_2} \hspace{1em} L_{z_2} \hspace{1em} R_{z_2}\\ \vdots\\ L_{x_Q} \hspace{1em} R_{x_Q} \hspace{1em} L_{y_Q} \hspace{1em} R_{y_Q} \hspace{1em} L_{z_Q} \hspace{1em} R_{z_Q}\\$

样例输入输出

样例输入1

$2\\ 1 \hspace{0.5em} 2 \\ 3 \hspace{0.5em} 4\\ 5 \hspace{0.5em} 6\\ 7 \hspace{0.5em} 8\\ 2\\ 1 \hspace{0.5em} 2 \hspace{0.5em} 2 \hspace{0.5em} 2 \hspace{0.5em} 1 \hspace{0.5em} 1\\ 2 \hspace{0.5em} 2 \hspace{0.5em} 1 \hspace{0.5em} 2 \hspace{0.5em} 1 \hspace{0.5em} 2$

样例输出1

$10\\ 26$

对于第一个查询，所求的值是 $A_{1, 2, 1} + A_{2, 2, 1} = 3 + 7 = 10$ 。因此，输出 10。

对于第二个查询，所求的值是 $A_{2, 1, 1} + A_{2, 1, 2} + A_{2, 2, 1} + A_{2, 2, 2} = 5 + 6 + 7 + 8 = 26$ 。因此，输出 26。

样例输入2

$3\\ 733 \hspace{0.5em} 857 \hspace{0.5em} 714\\ 956 \hspace{0.5em} 208 \hspace{0.5em} 257\\ 123 \hspace{0.5em} 719 \hspace{0.5em} 648\\ 840 \hspace{0.5em} 881 \hspace{0.5em} 245\\ 245 \hspace{0.5em} 112 \hspace{0.5em} 746\\ 306 \hspace{0.5em} 942 \hspace{0.5em} 694\\ 58 \hspace{0.5em} 870 \hspace{0.5em} 849\\ 13 \hspace{0.5em} 208 \hspace{0.5em} 789\\ 687 \hspace{0.5em} 906 \hspace{0.5em} 783\\ 8\\ 3 \hspace{0.5em} 3 \hspace{0.5em} 3 \hspace{0.5em} 3 \hspace{0.5em} 1 \hspace{0.5em} 1\\ 1 \hspace{0.5em} 3 \hspace{0.5em} 2 \hspace{0.5em} 3 \hspace{0.5em} 3 \hspace{0.5em} 3\\ 2 \hspace{0.5em} 2 \hspace{0.5em} 2 \hspace{0.5em} 3 \hspace{0.5em} 1 \hspace{0.5em} 1\\ 1 \hspace{0.5em} 3 \hspace{0.5em} 1 \hspace{0.5em} 1 \hspace{0.5em} 1 \hspace{0.5em} 1\\ 2 \hspace{0.5em} 3 \hspace{0.5em} 2 \hspace{0.5em} 3 \hspace{0.5em} 2 \hspace{0.5em} 3\\ 1 \hspace{0.5em} 2 \hspace{0.5em} 1 \hspace{0.5em} 1 \hspace{0.5em} 1 \hspace{0.5em} 2\\ 3 \hspace{0.5em} 3 \hspace{0.5em} 2 \hspace{0.5em} 2 \hspace{0.5em} 1 \hspace{0.5em} 3\\ 1 \hspace{0.5em} 2 \hspace{0.5em} 2 \hspace{0.5em} 3 \hspace{0.5em} 2 \hspace{0.5em} 3$

样例输出2

$687\\ 3917\\ 551\\ 1631\\ 5180\\ 3311\\ 1010\\ 4326$

思路

三维数组的前缀和，具体实现看代码

代码

#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 105;
int n, q, a[N][N][N], b[N][N], sum[N][N][N];inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}signed main() {n = read();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] = read();b[i][j] += a[i][j][k];sum[i][j][k] = sum[i - 1][j][k] + sum[i][j - 1][k] - sum[i - 1][j - 1][k] + b[i][j];}}}q = read();while (q--) {int l1 = read(), r1 = read(), l2 = read(), r2 = read(), l3 = read(), r3 = read();l1--, l2--, l3--;int ans = sum[r1][r2][r3] - sum[l1][r2][r3] - sum[r1][l2][r3] - sum[r1][r2][l3] + sum[l1][l2][r3] + sum[l1][r2][l3] + sum[r1][l2][l3] - sum[l1][l2][l3];printf("%lld\n", ans);}return 0;
}