Codeforces Round #415 C. Do you want a date?

题目大意:给你一个非空数集,让你求他所有子集的最大值与最小值的和。
看到题目给你两秒钟,嗯,肯定不能暴力( _ _)ノ|
昨晚做这道题的时候想了半天,这东西肯定是有个啥规律的,不然肯定TLE啊。
自己在本子上写了几个例子,似乎发现了某种规律,那就是每个数字作为最大值的次数或是最小值的次数,与其在子集sort后的排序有关,得到了这一点,很快就能写出代码啦( ^ω^)
ps.虽然代码是写出来了,但是却犯了个巨严重的错误,我在读取a[i]的时候忘了加&啊啊啊啊啊啊啊啊,搞得我一行一行调试了半天才发现为啥一直RE
#include <bits/stdc++.h> const int Max=500005; #define mod 1000000000+7 using namespace std; typedef long long ll; ll cnt[Max]; ll a[Max]; ll sum=0; int n; int main() { cnt[0]=1; for(int i=1;i<=400000;i++) { cnt[i]=cnt[i-1]*2; cnt[i]%=mod; } scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lld",&a[i]); sort(a,a+n); for(int i=1;i<n;i++) { sum+=1LL*a[i]*(cnt[i]-1);//强制转化避免数据溢出;排序后从小到大每个数字有(p[i]-1)的机会成为子集中的最大值。 sum%=mod; } for(int i=0;i<n-1;i++)//最后一个元素不可能为最小值,所以n-1 { sum-=1LL*a[i]*(cnt[n-i-1]-1);//排序后从小到大每个数字有(p[n-i-1]-1)的机会成为子集中的最小值 sum%=mod; } if(sum<0)//前面在取余求和的时候数据可能会炸掉,所以要加个mod再取余,或者是像这里写的一样取余以后再判断是否小于0 { sum+=mod; sum%=mod; } printf("%lld\n",sum); }
发表评论