18 华工校赛 - 小马哥的超级盐水 折半枚举

题意：小马哥有 \(n\) 杯盐水，第 \(i\) 杯有 \(a_i\)单位的盐和 \(b_i\) 单位的水。小马哥很无聊，于是他想知道有多少种这 \(n\) 杯盐水的非空子集，倒在一起之后盐和水的比是 \(\frac{x}{y}\)，范围 \(2<n<35\)

这道题比赛没 A 出来，要是 A 了就能两个人分 900 块辣

//隔了一天才突然想到，我太菜了

折半枚举过程如下

分两个桶 A,B，分别装前一半杯子的子集和后一半杯子的子集

先暴力枚举 A 桶所有组合，装入一个排好序的 vec，这部分时间复杂度是 \(O(2^{n/2}log_22^{n/2})\)

再暴力枚举 B 桶的方案，二分找出能和 A 匹配的方案个数，这部分时间复杂度也是 \(O(2^{n/2}log_22^{n/2})\)

最后统计 A、B 自身符合条件的方案就行了

至于如何二分，可以考虑假设 A 的某个集合本身不能匹配，

设该状态盐总和为 \(a\)，水总和为 \(b\)，那么就有 \(ay≠bx\)

设 B 桶枚举的集合中盐总和为 \(c\)，水总和为 \(d\)，那么有 \((a+c)y=(b+d)x\)

简单移项后得出 \(ay-bx=dx-cy\)

按这条式子就能二分了

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;
}