无法理解部分代码

Question

我有这个问题：

You have n problems. You have estimated the difficulty of the i-th one as integer ci. Now you want to prepare a problemset for a contest, using some of the problems you've made.

A problemset for the contest must consist of at least two problems. You think that the total difficulty of the problems of the contest must be at least l and at most r. Also, you think that the difference between difficulties of the easiest and the hardest of the chosen problems must be at least x.

Find the number of ways to choose a problemset for the contest.

Input The first line contains four integers n, l, r, x (1 ≤ n ≤ 15, 1 ≤ l ≤ r ≤ 109, 1 ≤ x ≤ 106) — the number of problems you have, the minimum and maximum value of total difficulty of the problemset and the minimum difference in difficulty between the hardest problem in the pack and the easiest one, respectively.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 106) — the difficulty of each problem.

Output Print the number of ways to choose a suitable problemset for the contest.

我试图解决它，但不幸的是我做不到。我问了一个朋友给我一个想法，他帮我解决了，但我有点不明白:

代码：

#include <stdio.h>
int a[25], l, r, x, i, j, n, ans;
int main(){
    scanf("%d %d %d %d", &n, &l, &r, &x);
    for(i=0; i<n; i++) scanf("%d", &a[i]);
    for(i=0; i<(1<<n); i++){
        int s = 0;
        int max = 0, min = 1e9;
        for(j=0; j<n; j++){
            if((i>>j)&1){
                if(a[j] > max) max = a[j];
                if(min > a[j]) min = a[j];
                s += a[j];
            }
        }
        if(l <= s && s <= r && max-min >= x) ans++;
    }
    printf("%d", ans);
    return 0;
}

如果他只有 n 个元素，为什么他要遍历那个数组直到 i<(1<<n)？
他为什么这样做：if((i>>j)&1) ?

我知道 1<<n 相当于乘以 2 的幂，1>>n 相当于整数除以 2^n 但这里没有意义。

Answer 1

您有 n 个可能的问题，每个问题都可以包含在问题集中或从问题集中排除。这意味着每个问题都有 2 个选项，因此对于 n 个问题，有 2^n 个选项用于创建可能的问题集。

行 for(i=0; i<(1<<n); i++) 迭代所有这些可能的问题集，每个问题集由 0 到 2^n - 1 之间的整数标识。接下来，我们需要确定哪些问题属于某个问题设置，我们有代表它的整数。

为此，我们采用该整数的二进制表示。它将有 n 位，假设每个位对应一个问题：如果它是 1，则问题包括在内，否则不是。这就是if((i>>j)&1)行所做的：它检查整数i中位置j的位是否等于1，这意味着包含了相应的问题。

剩下的就更简单了：从所有包含的问题中，您计算最小值、最大值和总和。然后，检查总和s是否在有效范围内，最大值和最小值之差是否至少为x.

无法理解部分代码

Having trouble understanding a portion of code

c

algorithm

bit