上海计算机学会2023年9月月赛C++乙组T1子集和（七）
发布时间
阅读量：
阅读量
子集和（七）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n 个数字 a1,a2,…,an 构成一个集合（本题中所指的集合元素允许相等），请计算有多少子集的和大于 0？
输入格式
- 第一行：单个整数 n
- 第二行：n 个整数 a1,a2,…,an
输出格式
- 单个数字，表示有多少子集的和超过 0
数据范围
- 50% 的数据，1≤n≤20，−1000≤ai≤1000
- 100% 的数据，1≤n≤40，−109≤ai≤109
样例数据
输入:
3
-1 -2 4
输出:
4
说明:
4>0
4-1>0
4-2>0
4-2-1>0
解析：折半搜索，将数组分成两半，分别用深度优先搜索，找到所有子集（包括空集），并计算出子集和。
对两个子集和排序。
遍历第一个子集和，找到第二个子集和中和自己相加大于0的子集个数，，求和即为答案；
详见代码：
#include <bits/stdc++.h>
using namespace std;
int n;
int a[50];
long long q[1050000];//保存前半部分子集和
int cntq=0;//前半部分子集数量
long long h[1050000];//保存后半部分子集和
int cnth=0;//后半部分子集数量
long long ans=0;//答案
//搜索前半部分所有子集
void dfsq(int step,long long sum){
if (step>n/2){//超过一半
cntq++;//子集数量加一
q[cntq]=sum;//保存子集和
return;//返回
}
dfsq(step+1,sum+a[step]);//加当前数
dfsq(step+1,sum);//不加当前数
}
void dfsh(int step,long long sum){
if (step>n){//超过n
cnth++;//子集数量加一
h[cnth]=sum;//保存子集和
return;//返回
}
dfsh(step+1,sum+a[step]);//加当前数
dfsh(step+1,sum);//不加当前数
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
dfsq(1,0);//从第一个数开始搜索
dfsh(n/2+1,0);//从后半部分第一个数开始搜索
//前半部分从小到大排序
sort(q+1,q+cntq+1,greater<long long>());
sort(h+1,h+cnth+1);//后半部分从大到小排序
for(long long i=1,j=1;i<=cntq;i++){//都从第一个数开始
//对于前半部分第i个数，找到第一个跟它相加大于0的数
while (q[i]+h[j]<=0&&j<=cnth){
j++;
}
ans+=cnth-j+1;//加上可以组合出来的大于零的子集数
}
cout<<ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~