11052: 【原1052】二哥学集合论

题目

题目描述

author: yyd 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1052

Description

沈老师给二哥上了一节生动的集合论课，课后老师布置了一道作业题：

实现一个算法来维护一些集合，支持以下三种操作：

\( + \) A B （将集合B并入集合A）

\( - \) A B （将A中的同时出现在A和B中的元素去掉）

\( * \) A B （将A变为A交B）

这题很坑爹，请看清输出要求！，输入的集合中可能包含重复的元素，要注意处理！

Input Format

读入一个数字N，代表你需要维护集合的数目\( N \leq 100 \)

接下来N个数字，代表每个集合中元素的个数\( \leq 200 \) 。接下来N行，每行包含了第i个集合中的元素每个数字\( 0 \leq x \leq 200 \)，会重复！。一个数\( M \leq 1000 \)，表示操作的数目下面M行，每行一个操作，详见样例。

Output Format

n行，输出最后每个集合的元素，从小到大排序！如果这个集合不是空集，行的最后会有一个空格！如果是空集，直接输出一个空行！

说明

操作过程中每个集合的元素个数不超过200个

Sample Input

Sample Output

FineArtz's solution

/* 二哥学集合论 */
#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    bool a[105][205];
    int N, M, n[105], t;
    cin >> N;
    for (int i = 1; i <= N; ++i)
        cin >> n[i];
    for (int i = 1; i <= N; ++i){
        for (int j = 1; j <= n[i]; ++j){
            cin >> t;
            a[i][t] = true;
        }
    }
    cin >> M;
    char ch;
    int x, y;
    while (M--){
        cin >> ch >> x >> y;
        switch(ch){
        case '+':
            for (int i = 0; i <= 200; ++i){
                if (a[y][i])
                    a[x][i] = true;
            }
            break;
        case '-':
            for (int i = 0; i <= 200; ++i){
                if (a[y][i])
                    a[x][i] = false;
            }
            break;
        case '*':
            for (int i = 0; i <= 200; ++i){
                if (!a[y][i])
                    a[x][i] = false;
            }
            break;
        }
    }
    for (int i = 1; i <= N; ++i){
        for (int j = 0; j <= 200; ++j)
            if (a[i][j]) cout << j << ' ';
        cout << '\n';
    }
    return 0;
}

ligongzzz's solution

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<set<int>> vdata(n);
    vector<int> vsize(n);

    for (int i = 0; i < n; ++i)
        cin >> vsize[i];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < vsize[i]; ++j) {
            int temp;
            cin >> temp;
            vdata[i].insert(temp);
        }
    }

    int m;
    cin >> m;
    for (; m; --m) {
        char op;
        int a, b;
        cin.get();
        cin >> op >> a >> b;
        --a;
        --b;
        if (op == '+') {
            vdata[a].insert(vdata[b].begin(), vdata[b].end());
        }
        else if (op == '-') {
            for (auto p = vdata[a].begin(); p != vdata[a].end();) {
                if (vdata[b].find(*p) != vdata[b].end()) {
                    vdata[a].erase(p++);
                }
                else
                    ++p;
            }
        }
        else {
            for (auto p = vdata[a].begin(); p != vdata[a].end();) {
                if (vdata[b].find(*p) == vdata[b].end()) {
                    vdata[a].erase(p++);
                }
                else
                    ++p;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (auto p : vdata[i]) {
            cout << p << " ";
        }
        cout << "\n";
    }

    return 0;
}

yyong119's solution

#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 100, MAXNUM = 200;

int main() {

    ios::sync_with_stdio(false);
    int num[MAXN + 1];
    bool element[MAXN + 1][MAXNUM + 1];
    int n, opnum, tmp;
    char op;
    memset(num, 0, sizeof(num)); memset(element, false, sizeof(element));
    // scanf("%d", &n);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        // scanf("%d", &num[i]);
        cin >> num[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= num[i]; ++j) {
            // scanf("%d", &tmp);
            cin >> tmp;
            element[i][tmp] = true;
        }
    // scanf("%d", &opnum);
    cin >> opnum;
    while (opnum--) {
        int temp1, temp2;
        // scanf("%s%d%d", &op, &temp1, &temp2);
        cin >> op >> temp1 >> temp2;
        if (op == '+') {
            for (int i = 0; i <= MAXNUM; ++i)
                if (element[temp2][i]) element[temp1][i] = true;
        }
        else if (op == '-') {
            for (int i = 0; i <= MAXNUM; ++i)
                if ((element[temp1][i])&&(element[temp2][i])) element[temp1][i] = false;
        }
        else {
            for (int i = 0; i <= MAXNUM; ++i)
                if ((element[temp1][i])&&(element[temp2][i])) element[temp1][i] = true;
                else element[temp1][i] = false;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= MAXNUM; ++j)
            // if (element[i][j]) printf("%d ", j);
            if (element[i][j]) cout << j << ' ';
        // printf("\n");
        cout << endl;
    }
    return 0;
}