时间限制1 Second 内存限制 512 Mb
题目描述
你有n个问题，你已经估计了第i个问题的难度为Ci,现在你想使用这些问题去构造一个问题集。比赛的问题集必须包含至少两个问题，而且比赛的总难度必须至少为l至多为r,此外最简单的问题和最难的问题之间的差异至少为x请您找出能够选择的问题集的数量。
输入
第一行有T组输入（1 ≤ T ≤ 10接下来一行输入n, l, r, x (1 ≤ n ≤ 10, 1 ≤ l ≤ r ≤ 1e9, 1 ≤ x ≤ 1e6)然后输入n个正整数 c1, c2, c3....cn (1 ≤ ci ≤ 1e6)
输出
每组输出单独占一行,一个正整数表示答案
输入样例
2
3 5 6 1
1 2 3
4 40 50 10
10 20 30 25输出样例
2
2思路
二进制枚举，每次枚举一个状态，统计该状态下的最大难度值，最小难度值，总难度值，然后判断这些数据满不满足题目所给的条件，满足的话，问题集数量加一
因为之前不理解二进制枚举，在这个题上面卡了大概一个小时，最后把以前的模板输出了一下，顿悟，然后一遍敲过。对二进制枚举也有了更深的理解
AC代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#define ll long long
#define ull unsigned long long
#define ms(a) memset(a,0,sizeof(a))
#define pi acos(-1.0)
#define INF 0x7f7f7f7f
#define lson o<<1
#define rson o<<1|1
const double E=exp(1);
const int maxn=1e6+10;
const int mod=1e9+7;
using namespace std;
int a[maxn];
int main(int argc, char const *argv[])
{ios::sync_with_stdio(false);int t;int n,l,r,x;cin>>t;while(t--){cin>>n>>l>>r>>x;for(int i=0;i<n;i++){cin>>a[i];}int ans=0;for(int i=0;i<(1<<n);i++){int diff_min=INT_MAX;//题目的最小难度int diff_max=INT_MIN;//题目的最大难度int diff_sum=0;//题目的总难度for(int j=0;j<n;j++){if(i>>j&1){diff_min=min(diff_min,a[j]);diff_max=max(diff_max,a[j]);diff_sum+=a[j];}}if(diff_max-diff_min>=x&&diff_sum>=l&&diff_sum<=r)ans++;}cout<<ans<<endl;}return 0;
}
