离散题目8——位集描述子集

曾经终败给现在 2022-06-16 08:58 110阅读 0赞

Think:  
1桶排序思想  
2输入数据过滤空格

离散题目8  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
现有一个全集U，U=\{ x | x>=1 && x<=N \} 。  
对于U的任意子集A，现在定义一种位集（bitset）Abit用来描述U的子集A： 该位集由1,0组成，长度为N，对于集合A中的任意元素x，集合Abit 在第x位且仅在第x位有对应的1存在，其余位置为0。  
例如： 对于全集U，其对应的描述位集Ubit = \{ 111…1 \} （N个1）； 对于集合A = \{ 1,2,3,N \}，其对应的描述位集Abit = \{ 1110…01 \}；

Input  
多组输入，每组输入包括三行，第一行为集合U的指标参数N( 0< N < = 64 )，第二行为集合A的元素，第三行为集合B的元素，元素之间用空格分割，具体参考示例输入。

Output  
每组输入对应两行输出，第一行为A、B的交集的描述位集。第二行为A、B的并集的描述位集。

Example Input  
10  
1 3 5 7 8  
2 5 6

Example Output  
0000100000  
1110111100

Hint

Author

以下为Wrong Answer代码——未过滤n后面的空格

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int n, i, x;
        int a[104], b[104];
        string st1;
    
        while(scanf("%d", &n) != EOF){
            memset(a, 0, sizeof(a));
            memset(b, 0, sizeof(b));
            getline(cin, st1);
            istringstream k(st1);
            while(k >> x){
                a[x] = 1;
            }
            getline(cin, st1);
            istringstream k1(st1);
            while(k1 >> x){
                b[x] = 1;
            }
            for(i = 1; i <= n; i++){
                if(a[i] && b[i])
                    printf("1");
                else
                    printf("0");
            }
            printf("\n");
            for(i = 1; i <= n; i++){
                if(a[i] || b[i])
                    printf("1");
                else
                    printf("0");
            }
            printf("\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Wrong Answer
    Take time: 0ms
    Take Memory: 196KB
    Submit time: 2017-05-11 15:22:01
    ****************************************************/

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int n, i, x;
        int a[104], b[104];//记录位集中当前元素是否存在
        string st1;
        while(getline(cin, st1)){
            istringstream is(st1);///istringstream作用是从string对象st1中读取
            is >> n;///以整数形式读取n，既可以以整数形式读取也可以以字符形式读取
    
            memset(a, 0, sizeof(a));///初始化
            memset(b, 0, sizeof(b));///初始化
    
            getline(cin, st1);///字符串输入
            istringstream k(st1);
            while(k >> x)///以整数形式读取
                a[x] = 1;
            getline(cin, st1);///字符串输入
            istringstream k1(st1);
            while(k1 >> x)///以整数形式读取
                b[x] = 1;
    
            for(i = 1; i <= n; i++){
                if(a[i] && b[i])
                    printf("1");
                else
                    printf("0");
            }
            printf("\n");
            for(i = 1; i <= n; i++){
                if(a[i] || b[i])
                    printf("1");
                else
                    printf("0");
            }
            printf("\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 196KB
    Submit time: 2017-05-11 15:49:36
    ****************************************************/