SUBSUMS - Subset Sums
Given a sequence of N (1 ≤ N ≤ 34) numbers S1, ..., SN (-20,000,000 ≤ Si ≤ 20,000,000), determine how many subsets of S (including the empty one) have a sum between A and B (-500,000,000 ≤ A ≤ B ≤ 500,000,000), inclusive.
Input
The first line of standard input contains the three integers N, A, and B. The following N lines contain S1 through SN, in order.
Output
Print a single integer to standard output representing the number of subsets satisfying the above property. Note that the answer may overflow a 32-bit integer.
Example
Input:
3 -1 2
1
-2
3
Output:
5
The following 5 subsets have a sum between -1 and 2:
0 = 0 (the empty subset)
1 = 1
1 + (-2) = -1
-2 + 3 = 1
1 + (-2) + 3 = 2
Submit solution!
思路：折半枚举+二分；
复杂度O（(2^ frac{n}{2}*log(2^ frac{n}{2}))）
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<string.h>
#include<map>
typedef long long LL;
using namespace std;
int ans[50];
int aa[20],bb[20];
int a1[200000],a2[200000];
int low(int l,int r,int ask);
int high(int l,int r,int ask);
int main(void)
{
int n,a,b;
scanf("%d %d %d",&n,&a,&b);
for(int i = 1; i <= n; i++)
{
scanf("%d",&ans[i]);
}
int cn = 0;
for(int i = 1; i <= (n/2); i++)
{
aa[cn++] = ans[i];
}
cn = 0;
for(int i = n/2+1; i <= n; i++)
{
bb[cn++] = ans[i];
}
int x1 = n/2,x2 = n-x1;
int cx1 = 0;
for(int i = 0; i < (1<<x1); i++)
{
int sum = 0;
for(int j = 0; j < x1; j++)
{
if(i&(1<<j))
sum+= aa[j];
}
a1[cx1++] = sum;
}
int cx2 = 0;
for(int i = 0; i < (1<<x2); i++)
{
int sum = 0;
for(int j = 0; j < x2; j++)
{
if(i&(1<<j))
sum += bb[j];
}
a2[cx2++] = sum;
}
sort(a1,a1+cx1);
sort(a2,a2+cx2);
LL acc = 0;
for(int i = 0; i < cx1; i++)
{
int asl = a-a1[i];
int asr = b-a1[i];
int ll = low(0,cx2-1,asl);
int rr = high(0,cx2-1,asr);
if(rr >= ll&&ll!=-1&&rr!=-1)
{
acc += (LL)(rr-ll+1);
}
}
printf("%lld
",acc);
return 0;
}
int low(int l,int r,int ask)
{
int id = -1;
while(l <= r)
{
int mid = (l+r)/2;
if(a2[mid] >= ask)
{
id = mid;
r = mid-1;
}
else l = mid+1;
}
return id;
}
int high(int l,int r,int ask)
{
int id = -1;
while(l <= r)
{
int mid = (l+r)/2;
if(a2[mid] <= ask)
{
id = mid;
l = mid+1;
}
else r = mid-1;
}
return id;
}