← 返回题目列表

AtCoder · APG4b_bx

EX25. 第3.05节

中文机器翻译题面 查看原题
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}是以下之一
    • intersection
    • union_set
    • symmetric_diff
    • subtract x
      • 0 \leq x \leq 49
      • 集合A至 该值是x保证存在
    • increment
    • decrement

入力

输入由标准输入按以下格式给出:

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));
  }
}