正解:搜索
解题报告:
先放下传送门QwQ
这题就,双向搜索经典题鸭
首先dfs应该挺好想到的我jio得?就是我们不用记录左右分别得分多少只要记下差值就好了嘛能get?
然后就先搜左边,记录下每个得分的数量
然后再搜右边,每搜出一个ans+=之前左边的可能得分数量
然后就欧克克了!
啊对了,,,还有一个细节卡了我好久QAQ
就是,要判重
因为注意题意它只是问选数的方案
所以我举个eg哦,假如选出了3 3 3 3,那它就会被枚举24=16次
所以为了避免这种情况
就用个状压
就over了!
具体一点细节晚上写趴,,,QAQ
(还有就是,这题有个双倍经验,,,只是好像要加一点儿细节什么的QwQ我有时间把细节什么的补上来QAQ
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,x,y) for(register ll i=x;i<=y;++i) const ll N=;
ll n,m,as,gg[N],cnta,cntb,l=,r=;
struct node{ll sm,zt;}a[<<N],b[<<N];
bool vis[<<N]; inline ll read()
{
register char ch=getchar();register ll x=;register bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=getchar();
if(ch=='-')ch=getchar(),y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();
return y?x:-x;
}
void dfs1(ll x,ll y,ll zt)
{
if(x>(n>>)){a[++cnta].sm=y;a[cnta].zt=zt;return;}
dfs1(x+,y,zt);dfs1(x+,y+gg[x],zt|(<<x));dfs1(x+,y-gg[x],zt|(<<x));
return;
}
void dfs2(ll x,ll y,ll zt)
{
if(x>n){b[++cntb].sm=y;b[cntb].zt=zt;return;}
dfs2(x+,y,zt);dfs2(x+,y+gg[x],zt|(<<x));dfs2(x+,y-gg[x],zt|(<<x));
return;
}
inline bool cmp1(node gd,node gs){return gd.sm<gs.sm;}
inline bool cmp2(node gd,node gs){return gd.sm>gs.sm;} int main()
{
n=read();rp(i,,n)gg[i]=read();
dfs1(,,);dfs2((n>>)+,,);
sort(a+,a++cnta,cmp1);sort(b+,b++cntb,cmp2);
while(l<=cnta && r<=cntb)
{
while(a[l].sm+b[r].sm> && r<=cntb)++r;
ll wz=r;
while(r<=cntb && b[r].sm+a[l].sm==){if(!vis[a[l].zt|b[r].zt])vis[a[l].zt|b[r].zt]=,++as;++r;}
if(l<cnta && a[l].sm==a[l+].sm)r=wz;
++l;
}
printf("%lld\n",as-);
return ;
}
这是写了好久还有一个点T了最后吸氧苟过去的代码!