我有这个问题:
你有问题。您已经估计了第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。