HPU team match B: questions (binary enumeration)

Time limit 1 Second memory limit 512 Mb

Title Description


You have n questions. You have estimated that the difficulty of the ith question is Ci. Now you want to use these questions to construct a question set. The question set of the competition must contain at least two questions, and the total difficulty of the competition must be at least l and at most r. in addition, the difference between the simplest question and the most difficult question is at least x. please find out the number of question sets you can choose.

input

The first line has T group input (1 ≤ T ≤ 10, next line input n, l, r, x (1 ≤ n ≤ 10, 1 ≤ L ≤ r ≤ 1e9, 1 ≤ x ≤ 1e6), then input n positive integers c1, c2, c3....cn (1 ≤ ci ≤ 1e6)

output

Each group of output takes up a single line, and a positive integer represents the answer

sample input

2
3 5 6 1
1 2 3
4 40 50 10
10 20 30 25

sample output

2
2

thinking

Binary enumeration: enumerate one state at a time, count the maximum difficulty value, the minimum difficulty value and the total difficulty value under this state, and then judge whether these data meet the conditions given by the topic. If they meet the requirements, add one to the number of problem sets

Because I didn't understand binary enumeration before, I stuck on this topic for about an hour, and finally output the previous template for a while, and then I realized it, and then I typed it again and again. We also have a deeper understanding of binary enumeration

AC code

#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;//Minimum difficulty of the topic
			int diff_max=INT_MIN;//Maximum difficulty of the topic
			int diff_sum=0;//Total difficulty of the topic
			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;
}


 

Tags: iOS

Posted on Mon, 06 Jan 2020 12:59:02 -0800 by pedromau