题意:

给n个时间长度(秒),问这些时间是否能组成3600的倍数

--

题解:

方案1:bitset<3603>b,记录每个时间是否能够得到,枚举每个数的贡献:
图片说明
最后看b0是否为1即可
方案2:普通背包,令dp[i]表示i是否到达,然后转移即可,注意转移顺序!!


代码

1

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}

int _,n,a[maxn];
int main(){
    for(scanf("%d",&_);_;_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            a[i]%=3600;
        }
        bitset<3605>b;
        for(int i=1;i<=n;i++){
            b|=(b<<a[i])|(b>>(3600-a[i]));
            b[a[i]]=1;
        }
        if(b[0]) yes;
        else no;
    }
}

2:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 3601;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head

int n,_,v[3601],use[3601],dp[3601];

int main(){
    for(scanf("%d",&_);_;_--){
        scanf("%d",&n);
        memset(v,0,sizeof v);
        memset(dp,0,sizeof dp);
        for(int i=1,d;i<=n;i++){
            scanf("%d",&d);
            v[d%3600]++;
        }

        if(v[0]) {yes;continue;}
        dp[0]=1;
        int f=0;
        for(int i=1;i<3600;i++){
            if(!v[i]) continue;
            for(int j=1;j<=v[i];j++){
                for(int k=0;k<3600;k++){
                    if(dp[k]) {
                        int c=(k+i)%3600;
                        if(c==0){f=1;break;}
                        use[c]=1;
                    }
                }
                for(int k=0;k<3600;k++) dp[k]|=use[k];
                memset(use,0,sizeof use);
                if(f) break;
            }
            if(f) break;
        }

        if(f) yes;
        else no;
    }
}