题意:小马哥有 杯盐水,第 杯有 单位的盐和 单位的水。小马哥很无聊,于是他想知道有多少种这 杯盐水的非空子集,倒在一起之后盐和水的比是 ,范围
这道题比赛没A出来,要是A了就能两个人分900块辣
//隔了一天才突然想到,我太菜了
折半枚举过程如下
分两个桶A,B,分别装前一半杯子的子集和后一半杯子的子集
先暴力枚举A桶所有组合,装入一个排好序的vec,这部分时间复杂度是
再暴力枚举B桶的方案,二分找出能和A匹配的方案个数,这部分时间复杂度也是
最后统计A、B自身符合条件的方案就行了
至于如何二分,可以考虑假设A的某个集合本身不能匹配,
设该状态盐总和为,水总和为,那么就有
设B桶枚举的集合中盐总和为,水总和为,那么有
简单移项后得出
按这条式子就能二分了
PS.实现是dalao写的,自己写的翻车了,思路没错..
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 40;
const int maxm = (1<<18)+5;
int elema[maxn],elemb[maxn];
int zka[maxm],zkb[maxm];
void ZHANGKAI(int val[],int elem[],int size)
{
val[0] = 0;
for(int i = 1;i<=size;i++)
{
int st = 1<<(i-1);
int ed = 1<<i;
for(int k = st;k<ed;k++)
{
val[k] = val[k-st]+elem[i];
}
}
}
int main()
{
int kase;cin>>kase;
for(int i = 0;i<kase;i++)
{
int n,x,y;
int a,b;
cin>>n>>x>>y;
int half = n>>1;
for(int i = 1;i<=half;i++)
{
cin>>a>>b;
elema[i] = y*a-x*b;
}
for(int i = half+1;i<=n;i++)
{
cin>>a>>b;
// elemb[i-half] = elema[i];
elemb[i-half] = x*b-y*a;
}
ZHANGKAI(zka,elema,half);
ZHANGKAI(zkb,elemb,n-half);
int sizeb = (1<<(n-half));
sort(zkb+1,zkb+sizeb);
long long ans = 0;
int end = 1<<half;
for(int i = 1;i<end;i++)
{
int*a = lower_bound(zkb+1,zkb+sizeb,zka[i]);
int*b = upper_bound(zkb+1,zkb+sizeb,zka[i]);
int k = b-a;
ans+=k;
}
for(int i = 1;i<end;i++) if(zka[i]==0) ans++;
for(int i = 1;i<sizeb;i++) if(zkb[i]==0) ans++;
cout<<ans<<endl;
}
return 0;
}