【暴力预处理+剪枝/bitset】Golf Bot UVALive - 6886

àì夳堔傛蜴生んèń 2022-06-10 06:17 135阅读 0赞

Think:  
1知识点：暴力预处理+剪枝/bitset  
2题意：输入n个数，查询m次，每次查询输入一个元素，判断这个元素是否可以由最初输入的n个数通过两个数相加或单独一个数得到，两个数相加时可选择同一元素进行相加

[vjudge题目链接][vjudge]

以下为Accepted代码——暴力预处理+剪枝-9363ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 201400;
    
    int a[N], b[N], vis[N<<1];
    
    int main(){
        int n, m, i, j, mav, t, num;
        while(~scanf("%d", &n)){
            mav = 0;
            memset(vis, 0, sizeof(vis));
            for(i = 0; i < n; i++){
                scanf("%d", &a[i]);
                vis[a[i]] = vis[a[i]<<1] = 1;
            }
            scanf("%d", &m);
            for(i = 0; i < m; i++){
                scanf("%d", &b[i]);
                mav = max(mav, b[i]);
            }
            sort(a, a+n);
            for(i = 1; i < n; i++){
                if(a[i] == a[i-1])
                    continue;
                for(j = 0; j < i; j++){
                    if(a[j]+a[i] > mav)
                        break;
                    t = a[j]+a[i];
                    vis[t] = 1;
                }
                if(a[i] > mav)
                    break;
            }
            num = 0;
            for(i = 0; i < m; i++){
                t = b[i];
                if(vis[t])
                    num++;
            }
            printf("%d\n", num);
        }
        return 0;
    }

以下为Accepted代码——bitset-4729ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <bitset>
    
    using namespace std;
    
    const int N = 201400;
    
    bitset <N> x, y;
    
    int a[N];
    
    int main(){
        int n, i, m, t, num;
        while(~scanf("%d", &n)){
            x.reset();
            y.reset();
            for(i = 0; i < n; i++){
                scanf("%d", &a[i]);
                x[a[i]] = 1;
            }
            y = x;
            for(i = 0; i < n; i++){
                y |= x << a[i];
            }
            scanf("%d", &m);
            num = 0;
            for(i = 0; i < m; i++){
                scanf("%d", &t);
                if(y[t])
                    num++;
            }
            printf("%d\n", num);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/contest/175297#problem/C