当前位置: 代码迷 >> 综合 >> Codeforces Round #306 (Div. 2) B. Preparing Olympiad (状态压缩)
  详细解决方案

Codeforces Round #306 (Div. 2) B. Preparing Olympiad (状态压缩)

热度:69   发布时间:2023-12-17 03:37:16.0

题意:

给你n个数字,挑出任意多个,要求最小和最大的差值不小于x且总和在l和r之间,问有多少种方案

思路:

由于n极小,那么我们可以直接状态压缩,用二进制表示每个数字的使用状态,然后看是否符合要求即可

错误及反思:

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;
long long arr[maxn];
int n;
long long l,r,x;
int main()
{scanf("%d%lld%lld%lld",&n,&l,&r,&x);for(int i=0;i<n;i++)scanf("%lld",&arr[i]);long long xx=1;for(int i=0;i<n;i++)xx*=1ll*2;int ans=0;for(long long i=0;i<xx;i++){long long temp=i;vector<long long> v;long long all=0;int now=0;while(temp){if(temp%2){v.push_back(arr[now]);all+=arr[now];}now++;temp/=2;}if(all>=l&&all<=r){sort(v.begin(),v.end());if(v[v.size()-1]-v[0]>=x)ans++;}}printf("%d\n",ans);
}
  相关解决方案