3 条题解

  • 0
    @ 2024-5-4 9:24:56

    课堂演示代码:

    状态压缩枚举子集,时间复杂度 O(2n×n)O(2^n \times n)

    #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
    上传者