page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_bx
问题名称:操作集合
一组最大到
問題文
0减去49的整数 有A, B。
根据程序模板,设置 请实现一个在A, B上运行的函数。
要实现的操作如下。 返回
| 操作 | 説明 | 例 |
|---|---|---|
intersection |
A和 按字典顺序比较B中通常包含的一组元素。 返回至少包含在 | A: {1, 2, 3}, B:{2, 3, 4} 結果:{2, 3} |
union_set |
A和 按字典顺序比较B之一中的一组元素。 返回仅包含在 | A: {1, 2, 3}, B:{2, 3, 4} 結果:{1, 2, 3, 4} |
symmetric_diff |
A和 按字典顺序比较B之一中的一组元素。 从 | A: {1, 2, 3}, B:{2, 3, 4} 結果:{1, 4} |
subtract x |
集合A中删除值 x。x保证存在。 将 | A: {1, 2, 3}, x: 2 結果:{1, 3} |
increment |
集合A中包含的所有元素加 1。 但是, 运算前设定中包含的49在运算后假定为0。 从。 |
A: {1, 2, 49} 結果:{2, 3, 0} |
decrement |
集合A中包含的所有元素中减去 1。 但是, 运算前设定中包含的操作前的集合中包含的 0 在操作后变为 49。。 |
A: {0, 1, 2} 結果:{49, 0, 1} |
程序模板
#include <bits/stdc++.h>
using namespace std;
// 各操作を行う関数を実装する
// AとBに共通して含まれる要素からなる集合を返す
bitset<50> intersection(bitset<50> A, bitset<50> B) {
}
// AとBのうち少なくとも一方に含まれる要素からなる集合を返す
bitset<50> union_set(bitset<50> A, bitset<50> B) {
}
// AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す
bitset<50> symmetric_diff(bitset<50> A, bitset<50> B) {
}
// Aから値xを除く
bitset<50> subtract(bitset<50> A, int x) {
}
// Aに含まれる要素に1を加える(ただし、要素49が含まれる場合は0になるものとする)
bitset<50> increment(bitset<50> A) {
}
// Aに含まれる要素から1を引く(ただし、要素0が含まれる場合は49になるものとする)
bitset<50> decrement(bitset<50> A) {
}
// Sに値xを加える
bitset<50> add(bitset<50> S, int x) {
S.set(x, 1); // xビット目を1にする
return S;
}
// 集合Sの内容を昇順で出力する(スペース区切りで各要素の値を出力する)
void print_set(bitset<50> S) {
vector<int> cont;
for (int i = 0; i < 50; i++) {
if (S.test(i)) {
cont.push_back(i);
}
}
for (int i = 0; i < cont.size(); i++) {
if (i > 0) cout << " ";
cout << cont.at(i);
}
cout << endl;
}
// これより下は書き換えない
int main() {
bitset<50> A, B;
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
A = add(A, x);
}
int M;
cin >> M;
for (int i = 0; i < M; i++) {
int x;
cin >> x;
B = add(B, x);
}
// 操作
string com;
cin >> com;
if (com == "intersection") {
print_set(intersection(A, B));
} else if (com == "union_set") {
print_set(union_set(A, B));
} else if (com == "symmetric_diff") {
print_set(symmetric_diff(A, B));
} else if (com == "subtract") {
int x;
cin >> x;
print_set(subtract(A, x));
} else if (com == "increment") {
print_set(increment(A));
} else if (com == "decrement") {
print_set(decrement(A));
}
}
制約
- A中的元素数量为N元素是A_1, A_2, \cdots, A_N。
-
B中的元素数量为M元素是B_1, B_2, \cdots, B_M。
-
1 \leq N, M \leq 50
- 0 \leq A_i \leq 49 (1 \leq i \leq N)
- 0 \leq B_i \leq 49 (1 \leq i \leq M)
- \mathrm{command}是以下之一
intersectionunion_setsymmetric_diffsubtract x- 0 \leq x \leq 49
- 集合A至 该值是x保证存在
incrementdecrement
入力
输入由标准输入按以下格式给出:
N
A_1 A_2 \cdots A_N
M
B_1 B_2 \cdots B_M
\mathrm{command}
出力
对于一组运算结果,将包含的元素按升序输出,并以空格分隔,共一行。 请注意,后面没有空格。
Judge还测试了除下面输入示例之外的情况。注意。
入力例1
3 0 1 2 3 1 2 3 intersection
出力例1
1 2
集合A是 {0, 1, 2} 包含在内,并且设置B是 {1, 2, 3} 包含在内,因此通常包含在其中的元素是 {1, 2}。
入力例2
3 0 1 2 3 1 2 3 union_set
出力例2
0 1 2 3
入力例3
3 0 1 2 3 1 2 3 symmetric_diff
出力例3
0 3
入力例4
3 0 1 2 3 1 2 3 subtract 2
出力例4
0 1
入力例5
3 0 1 49 3 1 2 3 increment
出力例5
0 1 2
入力例6
3 0 1 49 3 1 2 3 decrement
出力例6
0 48 49
提示
点击打开提示
intersection可以使用按位AND运算来实现。union_set可以使用按位或运算来实现。-
symmetric_diff可以使用按位异或运算来实现。 对于 -
subtract x,只需将表示S的位串的第x位设置为0即可。 -
increment,decrement可以使用逻辑移位运算,因为所有元素都加(减)1。
测试输入/输出
只有当你写的程序没有变成AC并且你找不到原因时,请看这个。
单击查看测试输入/输出
测试输入 1
3 0 1 2 3 10 11 12 intersection
测试输出 1
测试输入 2
50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 3 1 2 3 increment
测试输出 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
测试输入 3
50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 3 1 2 3 decrement
测试输出 3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
解答例
在观看之前一定要自己尝试一下问题。
点击查看示例答案
#include <bits/stdc++.h>
using namespace std;
// 各操作を行う関数を実装する
// AとBに共通して含まれる要素からなる集合を返す
bitset<50> intersection(bitset<50> A, bitset<50> B) {
return A & B;
}
// AとBのうち少なくとも一方に含まれる要素からなる集合を返す
bitset<50> union_set(bitset<50> A, bitset<50> B) {
return A | B;
}
// AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す
bitset<50> symmetric_diff(bitset<50> A, bitset<50> B) {
return A ^ B;
}
// Aから値xを除く
bitset<50> subtract(bitset<50> A, int x) {
A.set(x, 0);
return A;
}
// Aに含まれる要素に1を加える(ただし、要素49が含まれる場合は0になるものとする)
bitset<50> increment(bitset<50> A) {
bitset<50> ret = A << 1; // 左シフトでまとめて+1する
if (A.test(49)) {
ret.set(0, 1);
}
return ret;
}
// Aに含まれる要素から1を引く(ただし、要素0が含まれる場合は49になるものとする)
bitset<50> decrement(bitset<50> A) {
bitset<50> ret = A >> 1; // 右シフトでまとめて-1する
if (A.test(0)) {
ret.set(49, 1);
}
return ret;
}
// Sに値xを加える
bitset<50> add(bitset<50> S, int x) {
S.set(x, 1); // xビット目を1にする
return S;
}
// 集合Sの内容を昇順で出力する(スペース区切りで各要素の値を出力する)
void print_set(bitset<50> S) {
vector<int> cont;
for (int i = 0; i < 50; i++) {
if (S.test(i)) {
cont.push_back(i);
}
}
for (int i = 0; i < cont.size(); i++) {
if (i > 0) cout << " ";
cout << cont.at(i);
}
cout << endl;
}
// これより下は書き換えない
int main() {
bitset<50> A, B;
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
A = add(A, x);
}
int M;
cin >> M;
for (int i = 0; i < M; i++) {
int x;
cin >> x;
B = add(B, x);
}
// 操作
string com;
cin >> com;
if (com == "intersection") {
print_set(intersection(A, B));
} else if (com == "union_set") {
print_set(union_set(A, B));
} else if (com == "symmetric_diff") {
print_set(symmetric_diff(A, B));
} else if (com == "subtract") {
int x;
cin >> x;
print_set(subtract(A, x));
} else if (com == "increment") {
print_set(increment(A));
} else if (com == "decrement") {
print_set(decrement(A));
}
}