题目链接
题意:题意很简单,就是在给定的n个数里找到m个数之和,求其在给定区间的范围内的数量。
题解:首先我们要找到的是一个范围内的数,这样做的话因为有左边界,也有右边界,所以做起来很不方便,但是根据容斥定理得,假设f[r]为小于等于r的种类数,则f[r]-f[l-1]即[l,r]内的种类数,这样做起来就方便一点了,但是m个数相加仍然很不方便,这就是题中条件的应用,重量大的是小的最少倍,哪么我们可以知道是假设当前是w,则前面所有的数相加一定小于,w即 w/2+w/4+……<w,所以我们可以排序后从后往前找满足情况的条件。
下面AC代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N=55;
int c[N][N];
int a[N];
int n,k;
void init(){
c[0][0] = 1;
for(int i=1;i<=50;i++)
for(int j=0;j<=i;j++)
{
if( j==0 ) c[i][j] = 1;
else c[i][j] = c[i-1][j-1]+c[i-1][j];
}//得出组合数
}
bool cmp(int a,int b)
{
return a>b;
}
int solve(int x)
{
int ans=0;
int num=k;
for(int i=1;i<=n;i++)
{
if(x<a[i]) continue;//大于的话不用算
ans+=c[n-i][num];//小于的话在前面的数中随便选
if(num==0) return ans;
x-=a[i];//减去这个值
num--;
}
return ans+(num==0);//答案加上C[0][0]后返回
}
signed main()
{
int l,r;
init();
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n,cmp);/从小到大排序
cin>>l>>r;
cout<<solve(r)-solve(l-1)<<endl;
}