【牛客算法周练2】B
Music Problem
http://www.nowcoder.com/questionTerminal/7d1948ec26b5429c82f3a4cf48784612
题意有t个样例，每个样例是给你n个数，问你能不能凑出来3600的倍数。
那么这道题属于是背包问题，就是看每个数能不能取到。
这里提供用bitset的一种做法（比较厉害），bitset上面每个数代表这个数能不能被取到，当然我们首先会对所有的a[i]取模3600，这样的话，每个a[i]都在0-3599范围里，
具体 我们考虑每一个a[i]的时候，答案只可能增多或者不变，因此使用|或运算符就可以，但是我们还要特别考虑的是溢出问题，因为你可能向右右移了a[i]位之后溢出了，那么我们就在|上一个向左移3600位的结果，就可以确保万无一失，然后就快乐ac啦~~
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],a[i]%=3600;
bitset<7500> dp;
for(int i=1;i<=n;i++)
{
dp|=(dp<<a[i])|((dp<<a[i])>>3600);
dp[a[i]]=1;
}
if(dp[0]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
北京云智软通信息技术有限公司西安分公司HR面53人在聊
