离散题目7

缺乏、安全感 2022-10-01 02:53 131阅读 0赞

think:  
1用01字符串表示集合B即默认集合A的输入顺序，将其所有位置标记置为0，然后根据集合B中出现的元素，将出现的元素的标记位置置为1，然后根据集合A中的元素输入顺序进行输出  
2一开始自己用双重for循环暴力求解超时，想到今天从身边同学哪里学习到的如何存储负坐标，将负坐标的处理与桶排序思想结合起来，进而基本达到一种线性复杂度增长

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

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

以下为time limit exceed代码——暴力for循环

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int main()
    {
        int n, m, i, j, v, a[100000], vid[100000];
        while(scanf("%d %d", &n, &m) != EOF)
        {
            memset(vid, 0, sizeof(vid));
            for(i = 0; i < n; i++)
            {
                scanf("%d", &a[i]);
            }
            for(i = 0; i < m; i++)
            {
                scanf("%d", &v);
                for(j = 0; j < n; j++)
                {
                    if(a[j] == v)
                        break;
                }
                vid[j] = 1;
            }
            for(i = 0; i < n; i++)
            {
                printf("%d", vid[i]);
            }
            printf("\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Time Limit Exceeded
    Take time: 1010ms
    Take Memory: 0KB
    Submit time: 2017-03-25 20:37:41
    ****************************************************/

以下为accepted代码——优化桶排序—负坐标

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    
    using namespace std;
    
    int main()
    {
        int n, m, i, v, x[100004], vid[200004];
        while(scanf("%d %d", &n, &m) != EOF)
        {
            for(i = 0; i < n; i++)
            {
                scanf("%d", &x[i]);
                vid[x[i]+100000] = 0;
            }
            for(i = 0; i < m; i++)
            {
                scanf("%d", &v);
                vid[v+100000] = 1;
            }
            for(i = 0; i < n; i++)
            {
                printf("%d", vid[x[i]+100000]);
            }
            printf("\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 112ms
    Take Memory: 1236KB
    Submit time: 2017-03-25 20:44:36
    ****************************************************/