我有这个问题:


  你有问题。您已经估计了第i个难度
  作为整数ci。现在,您要为比赛准备问题集,
  使用您所遇到的一些问题。
  
  竞赛的问题集必须至少包含两个问题。
  您认为比赛问题的总难度
  必须至少为l,最大为r。另外,您认为差异
  在选择的最容易和最困难的困难之间
  问题必须至少为x。
  
  查找为竞赛选择问题集的方法数量。
  
  输入第一行包含四个整数n,l,r,x(1≤n≤15,
  1≤l≤r≤109,1≤x≤106)—您遇到的问题数量
  问题集的总难度的最小值和最大值
  最困难的问题之间的最小难度差异
  包装和最简单的包装。
  
  第二行包含n个整数c1,c2,...,cn(1≤ci≤106)—
  每个问题的难度。
  
  输出打印选择适合的问题集的方法数量
  比赛。


我试图解决它,但不幸的是我做不到。我请一个朋友给我一个主意,他为我解决了一个主意,但我不明白:

码:

#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的整数除法,但这在这里没有意义。

最佳答案

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

在行for(i=0; i<(1<<n); i++)中,您正在迭代所有这些可能的问题集,每个问题集都由介于0和2 ^ n-1之间的整数标识。接下来,我们需要确定哪些问题属于某个问题集,并且我们有一个整数代表它。

为此,我们采用该整数的二进制表示形式。它具有n位,并且可以说每个位对应一个问题:如果为1,则包含该问题,否则为不包含。这就是行if((i>>j)&1)的操作:它检查整数j中位置i中的位是否等于1,这意味着包括相应的问题。

其余的则更容易:从所有包含的问题中,计算出最小值,最大值和总和。然后,检查总和s是否在有效范围内,并且最大值和最小值之间的差是否至少为x。

09-13 11:11