zcmimi's blog
查看原题

点击跳转

一个数有三种情况:

  1. 放左边
  2. 放右边
  3. 不选

折半搜索

还是一样的套路

分前部分和后部分搜索

但是有可能出现前后选的数出现重叠状况

我们可以用状压并开一个桶来记录是否重复出现过

最后答案记得-1,因为空集不算

#include<bits/stdc++.h>
using namespace std;
#define N 1000011
int n,v[40],ans=0;
struct node{
    int s,sta;    
}a[1<<22],b[1<<22];
bool cmp(node x,node y){
    return x.s<y.s;
}
bool CMP(node x,node y){
    return x.s>y.s;
}
int dep=0,ta=0,tb=0;
inline void dfs(int d,int s,int now,bool f){
    if(d==dep+1){
        if(f)a[++ta]=node{s,now};
        else b[++tb]=node{s,now};
        return;
    }
    dfs(d+1,s,now,f);
    dfs(d+1,s+v[d],(now+(1<<(d-1))),f);
    dfs(d+1,s-v[d],(now+(1<<(d-1))),f);
}
bool vis[1<<22];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>v[i];
    dep=n/2;
    dfs(1,0,0,1);
    dep=n;
    dfs(n/2+1,0,0,0);
    sort(a+1,a+ta+1,cmp);
    sort(b+1,b+tb+1,CMP);
    int p=1,q=1;
    while(p<=ta&&q<=tb){
        while(-a[p].s<b[q].s&&q<=tb)++q;
        int pos=q;
        while(q<=tb&&-a[p].s==b[q].s){
            if(!vis[a[p].sta|b[q].sta])
                vis[a[p].sta|b[q].sta]=1,++ans;
            ++q;
        }
        if(p<ta&&a[p].s==a[p+1].s)q=pos;
        ++p;
    }
    cout<<ans-1<<endl; 
}
LG 3067 [USACO12OPEN]平衡的奶牛群Balanced-Cow
comment评论
Search
search