Music Problme

https://ac.nowcoder.com/acm/problem/13885

bitset可以用于那些选举个别元素进行组合进行求和，积等问题，以求和为例如下题所示，我们可以用bitset去求出素组中元素的所有组合的和存放在bitste里面，求得的值是多少，我们就让这个位置的上的值设为1，比如有3个数1，2，3，任意两个数的和有3，4，5，假设有定义bitset<7500>p,那么p[3] = 1,p[4] = 1,p[5] = 1,三个数也是类似，然后又可以发现我们可以用移位来完成这个加法操作，比如有1，p[1] = 1,那么2的话可以是1左移了两位，3是左移了三位，然后这里我们可以使用或操作来完成，每次我们将这个数与它左移n位后的数进行或操作，比如现在是0010，加上2，左移两位1000，或操作后得到1010，这样一来1和3都被选到了，相当于这前有的数依然保持在那，加上后的数的位置置为1。

这道题可以用bitset来优化，只要选出3600的倍数即可。

#include <bits/stdc++.h>
#include <iostream>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
const int mod = 1e9+7;
//const int inx = INT_MAX; 
using namespace std;
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

//定义i i(A) i+n i+n(B) i+n+n i+n+n(C) 
//bitset<Max>s,q;

int a[100005];
int main()
{
    int T,n,i;
    cin >> T;
    while(T--){
        bitset<7500>p;
        cin >> n;
        for(i = 1; i <= n; i++){
            cin >> a[i];
            a[i] %= 3600;
        }
        for(i = 1; i <= n; i++){
            p |= (p << a[i]) | ((p << a[i]) >> 3600);
            p[a[i]] = 1;
        }
        if(p[0]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}