离散7

客官°小女子只卖身不卖艺 2022-06-15 04:24 96阅读 0赞

### 离散题目7 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

DaYu在新的学习开始学习新的数学知识，一天DaYu学习集合的时候遇到一个问题，他有一个集合A和A的子集B，他想用一个二进制串表示集合B。

#### Input ####

多组输入，每组的第一行有两个数n,m，（0< m < n < 10^5）.

第二行输入n个数表示集合A，第三行输入m个数表示集合B,|data\_i|< 10^5

#### Output ####

输出一个01字符串表示集合B

#### Example Input ####

10 5
    1 2 3 4 5 6 7 8 9 10
    1 3 5 7 8

#### Example Output ####

1010101100

#### Hint ####

#### Author ####

MeiK

代码：

#include <bits/stdc++.h>  
    using namespace std;  
    int main()  
    {  
        int n, m, i, x, a[111111], b[222222];  
        while(scanf("%d %d", &n, &m) != EOF)  
        {  
            for(i = 0; i < n; i++)  
            {  
                scanf("%d", &a[i]);  
                b[a[i]+100000] = 0;//需要考虑负数的情况  
            }  
            for(i = 0; i < m; i++)  
            {  
                scanf("%d", &x);  
                b[x+100000] = 1;  
            }  
            for(i = 0; i < n; i++)  
            {  
                printf("%d", b[a[i]+100000]);  
            }  
            printf("\n");  
        }  
        return 0;  
    }

自己做的时候先是wa了，后来用两个for循环，time limit。。。然后百度一下，发现了这个大神的做法。。真的好简单。是时候开拓一下自己的、

思维了。

用到的思想：桶排序。还有输入时候的巧妙。b【a【i】+100000】，自己开始想把输入、a【i】换成x；输出才发现a【i】中没有值，最后输出是个

问题。

ps：自己做只会暴力查找。暴力排序。班里一巨巨说。孩子学点算法吧。果然，还是有许多要学的东西。

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2083/pid/3801.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2083/pid/3801.html