首页 > 代码库 > 洛谷 P2415 集合求和 题解
洛谷 P2415 集合求和 题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.luogu.org/problem/show?pid=2415
题目描述
给定一个集合s（集合元素数量<=30），求出此集合所有子集元素之和。
输入输出格式
输入格式：集合中的元素（元素<=1000）
输出格式：和
输入输出样例
输入样例#1：
2 3
输出样例#1：
10
说明
子集为：
[] [2] [3] [2 3] 2+3+2+3=10
保证结果在10^18以内。
分析：
手写容易发现
集合元素数量为2时，每个元素各出现了2次
集合元素数量为3时，每个元素各出现了4次
集合元素数量为4时，每个元素各出现了8次
可以推知，当集合元素数量为n时，每个元素各出现了2^(n-1)次。
虽然不会证明，但是这就是对的...
AC代码：
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 int note[35]; 7 long long x = 1; 8 int n; 9 10 inline void find()11 {12 x = x<<(n-1);13 }14 15 int main()16 {17 while(scanf("%d",¬e[n]) != EOF)18 n ++;19 if(n == 1)20 {21 printf("%d\n",note[0]);22 return 0;23 }24 long long ans = 0;25 find();26 for(int i = 0;i < n;++ i)27 ans += note[i]*x;28 printf("%lld\n",ans);29 return 0;30 }
代码应该很好理解...需要注意的就是读入元素的数目不确定，要写一个while判断。
洛谷 P2415 集合求和 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。