NC 13885. Music Problem

发表于 分类于

链接

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

题意

问在 $n$ 个数中是否能找出几个数，让它们的和是 $3600$ 的倍数

思路

我们只要判断是否能找到一些数的和取模后是 $0$ 就可

取模后有 $3600$ 个值，我们用 bitset 存储，第 $x$ 位为 $1$ 表示当前存在一些数的和取模后为 $x$

当我们加入一个数 $a$ 时：$b|=(b<<a)|(b>>(3600-a))$，前者记录当前值加上 $a$ 后不超过 $3600$ 的和，后者记录超过 $3600$ 取模后的和

最后判断 $b[0]$ 是否为 $1$ 即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--) {
        int n;
        cin>>n;
        bitset<3600>b;
        for(int i=1;i<=n;i++) {
            int x;
            cin>>x;
            x%=3600;
            b|=(b<<x)|(b>>(3600-x));
            b.set(x);
        }
        if(b.test(0)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}