3 条题解
-
0
课堂演示代码:
状态压缩枚举子集,时间复杂度
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=21,mod=998244353; int n,l,r,x,c[N]; ll ans,jie[N]; bool check(int s) //检查x中 1的数量 、最低分、最高分、总分是否合法 { int num=0,small=1e9,big=0,sum=0; for(int i=0;i<n;i++) if((s>>i)&1) //第i道是被选中的 { num++; small=min(small,c[i]); big=max(big,c[i]); sum=sum+c[i]; } if(num>=4 && small<=l && big>=r && sum>=x)return true; return false; } int cal(int s) { int num=0; for(int i=0;i<n;i++) if((s>>i)&1)num++; return jie[num]; } int main() { ios::sync_with_stdio(0);cin.tie(0); cin>>n>>l>>r>>x; for(int i=0;i<=n-1;i++)cin>>c[i]; //题目编号从0开始 jie[0]=1; for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod; for(int s=0;s<(1<<n);s++) if(check(s)) { ans=(ans+cal(s))%mod; } cout<<ans; return 0; }
信息
- ID
- 1413
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 181
- 已通过
- 30
- 上传者