# HPU team competition B Questions [Binary enumeration || dfs] Dreamers

2022-12-31   ES

Time limit 1 Second memory limit 512 MB

You have n questions, you have estimated that the difficulty of the i -i problem is CI, and now you want to use these problems to construct a problem set. The issue of the competition must include at least two problems, and the total difficulty of the game must be at least L. At least R. In addition quantity.

First line with T group input (1 ≤ t ≤ 10 Next input n, L, R, x (1 ≤ n ≤ 10, 1 ≤ l ≤ 1e9, 1 ≤ x ≤ 1E6), then enter n Positive integer C1, C2, C3 …. CN (1 ≤ Ci ≤ 1E6)

Each group of outputs separate alone, a positive integer indicates the answer

Input sample

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

output sample

``````
2
2``````

Thinking 1): Just make a binary enumeration, don’t have to whisty!

``````#include <cStdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#Define Maxn 0x3F3F3F3F
#Define minn 0xc0c0c0c0
int a ;
int Main ()
{{
int T;
scanf ("%d", & t);
While (t--)
{{
Int n, L, R, x, ANS = 0; // ANS Record answer
scanf (" %d %d %d %d", & n, & l, & r, & x);
for (int i = 0; i <n; i ++)
scanf ("%d", & a [i]);
for (int i = 0; i <(1 <(1 <(1 <); i ++)
{{
int di_easy = maxn; // Used to record the simplest problem difficulty
int di_diff = minn; // It is difficult to record the most difficult problem
int Sum = 0; // The total difficulty of recording the game
for (int j = 0; j <n; j ++)
{{
if (i & (1 << j)) // Each state of enumeration
{{
di_easy = min (a [j], di_easy);
di_diff = max (a [j], di_diff);
sum+= a [j];
}
}
If (SUM> = L && SUM <= R && di_diff -di_easy> = x) // Determine whether it meets the conditions
ANS ++;
}
Printf ("%d \ n", aNS);
}
Return 0;
}``````

Thinking: 2) DFS, simple and rude. The marker is as follows:

``````#include <bits/stdc++.h>
using namespace std;
const int MAXN=20;
int a[MAXN];
int n,l,r,x;
int ans=0;
void dfs(int sum,int s,int p,int cnt)
{
if(cnt>=2&&sum>=l&&sum<=r&&a[s]-a[p]>=x)
{
ans++;
}
for (int i = s+1; i <n ; ++i) {
if(sum+a[i]<=r)
dfs(sum+a[i],i,p,cnt+1);
}

}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%d%d%d%d",&n,&l,&r,&x);
for (int i = 0; i <n ; ++i) {
scanf("%d",&a[i]);
}
sort(a,a+n);
for (int i = 0; i <n ; ++i) {
dfs(a[i],i,i,1);
}
printf("%d\n",ans);
}

return 0;
}``````

source