欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[luogu3067 USACO12OPEN] 平衡的奶牛群

程序员文章站 2022-06-02 22:09:00
...

[luogu3067 USACO12OPEN] 平衡的奶牛群

传送门

Solution

折半搜索模板题
考虑枚举每个点在左集合和右集合或者不在集合中,然后排序合并即可

Code

//By Menteur_Hxy
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Re register
#define Ms(a,b) memset(a,(b),sizeof(a))
#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)
#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<16,stdin)),p1==p2?EOF:*p1++)
using namespace std;
typedef long long LL;

char buf[1<<16],*p1,*p2;
inline int read() {
    int x=0,f=1; char c=getchar();
    while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
    return x*f;
}

inline void writ(int x) {
    if(x>9) writ(x/10);
    putchar(x%10+'0');
}

const int N=25,M=1e8+5;
int n,ans,tt1,tt2;
bool vis[1<<N];
int da[N];
struct Data{int val,cur;}T1[1<<N],T2[1<<N];

void dfs(int pos,int ed,int sum,int S) {
    if(pos>ed) {
        if(ed==n/2) T1[++tt1].val=sum,T1[tt1].cur=S;
        else T2[++tt2].val=sum,T2[tt2].cur=S;//1
        return ;
    }
    dfs(pos+1,ed,sum,S);
    dfs(pos+1,ed,sum+da[pos],S|(1<<(pos-1)));
    dfs(pos+1,ed,sum-da[pos],S|(1<<(pos-1)));
}

bool cmp1(Data a,Data b) {return a.val<b.val;}
bool cmp2(Data a,Data b) {return a.val>b.val;}

int main() {
    n=read();
    Fo(i,1,n) da[i]=read();
    dfs(1,n/2,0,0); dfs(n/2+1,n,0,0);
    sort(T1+1,T1+1+tt1,cmp1);
    sort(T2+1,T2+1+tt2,cmp2);
    int l=1,r=1,las;
    while(l<=tt1&&r<=tt2) {
        while(r<=tt2&&T1[l].val+T2[r].val>0) r++;//2
        las=r;
        while(r<=tt2&&T1[l].val+T2[r].val==0) {
            if(!vis[T1[l].cur|T2[r].cur])
                vis[T1[l].cur|T2[r].cur]++,ans++;
            r++;
        }
        l++;
        if(T1[l-1].val==T1[l].val) r=las;//3
    }
    writ(ans-1);
    return 0;
}
posted @ 2018-10-22 17:00 Menteur_Hxy 阅读(...) 评论(...) 编辑 收藏