上海计算机学会2024年7月月赛C++丙组T4子集归零
发布时间
阅读量：
阅读量
子集归零
内存限制: 256 Mb时间限制: 1000 ms
题目描述
设有n个整数a₁,a₂,…,aₙ，请计算在1至n范围内有多少个不同的索引子集（S），使得这些索引对应的数值之和等于零。
注意空集与全集也是子集中的一种。
输入格式
- 第一行，单个整数表示 n
- 第二行，n 个整数表示 a1,a2,…,an
输出格式
- 单个整数：表示归零子集的数量。
数据范围
- 对于 30% 的数据，1≤n≤5
- 对于 60% 的数据，1≤n≤10
- 对于 100% 的数据，1≤n≤22
- 对于 100% 的数据，−1,000,000≤ai≤1,000,000
样例数据
输入:
4
2 -1 -2 1
输出:
4
说明:
{}
{1 -1}
{2 -2}
{1 2 -1 -2}
解析：
将所有可能的子集视为从0到 2^{22} - 1 范围内的整数值，并通过二进制编码的方式表示每个元素的存在状态（其中未被选中的位对应的数值不加到总和中）以及选取的状态（被选中的位对应的数值则加到总和中）。为了求解问题的目标值（此处为零），需要遍历所有可能的子集组合，并计算每个子集中元素的总和值；特别地，在上述过程中需要统计满足总和等于零的情况的数量；以上操作的具体实现细节请参考以下代码。
#include<bits/stdc++.h>
using namespace std;
int n;
int a[25];
int ans = 0;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 0; i < (1 << n); i++) {//枚举0到2的n次方
int t = i;//临时变量
int sum = 0;//子集和
for(int j = 1; j <= n; j++) {//循环二进制每一位
sum += (t % 2) * a[j];//加入子集和
t /= 2;//去掉二进制末位
}
if (sum == 0) ans++;//判断，计数
}
cout << ans;
return 0;
}也可以使用深搜解决，详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[25];
int ans = 0;
void dfs(int step, int sum) {
if(step > n) {
if (sum == 0) ans++;
return;
}
dfs(step + 1, sum); //不加当前数
dfs(step + 1, sum + a[step]); //加当前数
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
dfs(1, 0); //深搜
cout << ans;
return 0;
}全部评论 (0)
还没有任何评论哟~