陕西省住房和城乡建设厅网站上查询,网站好玩新功能,wordpress评论时选填,普通个人简历电子版免费传送门 文章目录目录题意#xff1a;思路#xff1a;目录
题意#xff1a;
给你nnn个数#xff0c;从中任意选出一组数#xff0c;使这些数能分成和相等的两组#xff0c;问有多少种选数方案。 2≤n≤20,1≤ai≤1e92\le n\le 20,1\le a_i\le 1e92≤n≤20,1≤ai≤1e9 …传送门 文章目录目录题意思路目录
题意
给你nnn个数从中任意选出一组数使这些数能分成和相等的两组问有多少种选数方案。
2≤n≤20,1≤ai≤1e92\le n\le 20,1\le a_i\le 1e92≤n≤20,1≤ai≤1e9
思路
注意审题是选出一组能分成两组和相等的即可也就是说如果是同一组但是分成两个部分的时候有多种方案那么也算一种。
看到nnn很小不难想到爆搜但是每个数有三种情况复杂度3n3^n3n但是我们可以使用meetinmiddlemeet\ \ in\ \ middlemeet in middle先搜一半让后对于另一半直接使用其搜出来的信息由于对于每一个选出来数相同的方案都视为一个方案所以对于每个状态我们需要记一个state代表当前选了哪几个让后去重即可。
考虑如何计算方案假设当前两边差值的绝对值是xxx那么需要另一半两边插值绝对值也为xxx是否只需要加入另一半插值也为xxx的方案即可答案是否定的还需要判断当前这一半状态与另一半状态拼起来是否已经计算过所以需要存下来遍历这样复杂度有点高但是吸氧能过。。
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N1000010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;
typedef pairLL,LL PII;int n;
int a[N];
mapLL,vectorintmp;
mappairLL,LL,intst,vis;void dfs(int u,LL l,LL r,LL state) {if(un/2) {LL nowabs(r-l);if(st.count({state,now})) return;st[{state,now}]1;mp[now].pb(state);//coutnow**l rendl;return;}dfs(u1,l,r,state);dfs(u1,la[u],r,state(1u));dfs(u1,l,ra[u],state(1u));
}LL ans0;
void solve(int u,LL l,LL r,LL state) {if(un) {LL nowabs(l-r);if(st.count({state,now})) return;st[{state,now}]1;//ansmp[now];for(auto x:mp[now]) {if(vis.count({x,state})) continue;vis[{x,state}]1;ans;}return;}solve(u1,l,r,state);solve(u1,la[u],r,state(1u));solve(u1,l,ra[u],state(1u));
}void solve() {scanf(%d,n);for(int i0;in;i) scanf(%d,a[i]);if(n1) {puts(0);return;}dfs(0,0,0,0);st.clear(); vis[{0,0}]1;//for(auto x:mp) coutx.X x.Yendl;solve(n/2,0,0,0);printf(%lld\n,(ans));
}int main() {int _1;while(_--) {solve();}return 0;
}
