洛谷P3067 [USACO12OPEN]平衡的奶牛群Balanced Cow S…
程序员文章站
2022-06-02 21:48:49
...
https://www.luogu.org/problem/show?pid=3067
我们考虑折半搜索;
我们发现一个性质,对于每一个数,其实就是有一个权值{1,0,-1}
那么每一个数乘权值乘系数加起来是0就是一个解
那我们这般搜索,然后排序匹配一下就好啦;
当然我们还要记录一下状态,因为要判重;
还有一个都不取不能算答案的;
#include<bits/stdc++.h>
#define Ll long long
using namespace std;
struct cs{Ll x;int y;}A[60000],B[60000];
Ll ans;
bool vi[1048579];
int a[25];
int n,ta,tb,l,r;
bool cmp(cs a,cs b){return a.x<b.x;}
void dfs1(int x,int y,Ll sum,int k){
if(!y)A[++ta].x=sum,A[ta].y=k;else
dfs1(x+1,y-1,sum,k),dfs1(x+1,y-1,sum+a[x],k+(1<<(x-1))),dfs1(x+1,y-1,sum-a[x],k+(1<<(x-1)));
}
void dfs2(int x,int y,Ll sum,int k){
if(!y)B[++tb].x=sum,B[tb].y=k;else
dfs2(x+1,y-1,sum,k),dfs2(x+1,y-1,sum+a[x],k+(1<<(x-1))),dfs2(x+1,y-1,sum-a[x],k+(1<<(x-1)));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
dfs1(1,n/2,0,0);
dfs2(n/2+1,n-n/2,0,0);
sort(A+1,A+ta+1,cmp);
sort(B+1,B+tb+1,cmp);
// for(int i=1;i<=ta;i++)cout<<A[i].x<<'('<<A[i].y<<") ";cout<<endl;
// for(int i=1;i<=tb;i++)cout<<B[i].x<<'('<<B[i].y<<") ";cout<<endl;
r=1;B[tb+1].x=1e12;l=tb+1;
for(int i=ta;i;i--){
if(B[l].x+A[i].x==0){
for(int j=l;j<r;j++)
if(!vi[A[i].y+B[j].y])vi[A[i].y+B[j].y]=1,ans++;
continue;
}
// cout<<B[r].x<<' '<<A[i].x<<"||||";
while(B[r].x+A[i].x<0)r++;
// cout<<B[r].x<<' '<<A[i].x<<"\n";
if(r>tb)break;
if(B[r].x+A[i].x==0)l=r;else continue;
while(B[r].x+A[i].x==0)r++;
for(int j=l;j<r;j++)
if(!vi[A[i].y+B[j].y])vi[A[i].y+B[j].y]=1,ans++;
}printf("%lld",ans-1);
}