第一题:T1子集和(七)
标签:折半搜索、二分
题意:给定 n n n个数字 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,…,an构成一个集合(本题中所指的集合元素允许相等),请计算有多少子集的和大于 0 0 0?( 1 ≤ n ≤ 40 1≤n≤40 1≤n≤40, − 1 0 9 ≤ a i ≤ 1 0 9 -10^9≤a_i≤10^9 −109≤ai≤109)
题解: n n n的数据范围是 40 40 40,直接暴力搜索时间复杂度会到达 2 40 2^{40} 240,肯定会超时,所以得先分成两个集合,折半搜索处理一下,然后对两个集合进行排序。对第一个集合进行遍历,通过二分,去第二个集合中找到第一个大于 − s 1 [ i ] -s1[i] −s1[i]的位置 j j j,因为已经排序过了,从 j j j到第二个集合最后一个元素都是能够加起来和大于 0 0 0的。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e6;
ll n, a[50], ans = 0;
ll s1[N], s2[N], c1 = 0, c2 = 0;
void dfs1(ll p, ll sum) {
if (p == n / 2 + 1) {
s1[c1++] = sum;
return ;
}
dfs1(p + 1, sum + a[p]);
dfs1(p + 1, sum);
}
void dfs2(ll p, ll sum) {
if (p == n + 1) {
s2[c2++] = sum;
return ;
}
dfs2(p + 1, sum + a[p]);
dfs2(p + 1, sum);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
dfs1(1, 0);
dfs2(n / 2 + 1, 0);
sort(s1, s1 + c1);
sort(s2, s2 + c2);
for (int i = 0; i < c1; i++) {
ll j = upper_bound(s2, s2 + c2, -s1[i]) - s2;
ans += c2 - j;
}
cout << ans;
return 0;
}