题意:
给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; } }