首页 > 移动平台 > 详细

HDU 6682 Make Rounddog Happy

时间:2019-08-21 22:24:04      阅读:94      评论:0      收藏:0      [点我收藏+]

题意:给你一个集合,求它的所有子集的子集和中数字4出现了多少次

例如

4

4 4 44 44

中4(1),4(2),44(3),44(4),48(1,3),48(1,4),48(2,3),48(2,4),总共有10个数字4

 

思路:

明显数据范围就是要拆开来做,先将子集尽可能平均分

这样就有两个大小不超过220的子集和集合。

考虑集合里所有数字的每一位对答案的贡献

只有两种可能,一种是当前位数两位相加没有进位,一种是当前位数两位相加有进位

分别统计就是答案

而如果将当前位之后的那一部分数字从小到大有序排列好,就可以用两个指针分别从两边去扫

然而直接排序会超时

所以考虑类似于归并的思想,转移时候将当前位拆开按顺序重新丢入大集合里

就可以保证答案的正确性了

注意卡常

 1 #include<bits/stdc++.h>
 2 #define pb push_back
 3 using namespace std;
 4 int read(){
 5     int x=0,f=1;char c=getchar();
 6     for(;!isdigit(c);c=getchar())if(c==-)f=-1;
 7     for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
 8     return x*f;
 9 }
10 typedef long long ll;
11 struct data{ll fi,se;};
12 data mp(ll a,ll b){
13     data ret;
14     ret.fi=a;ret.se=b;
15     return ret;
16 }
17 typedef data pll;
18 int n,li[50];
19 vector<pll> X,Y,A[10],B[10];
20 
21 void get_X(int dep,ll sum){
22     if(dep>(n/2)){X.pb(mp(sum,0));return;}
23     get_X(dep+1,sum);get_X(dep+1,sum+li[dep]);
24 }
25 void get_Y(int dep,ll sum){
26     if(dep>n){Y.pb(mp(sum,0));return;}
27     get_Y(dep+1,sum);get_Y(dep+1,sum+li[dep]);
28 }
29 
30 ll get0(vector<pll> &a,vector<pll> &b,ll Base){
31     ll ret=0;int p=b.size()-1;
32     for(int i=0;i<a.size();ret+=p+1,++i)
33         for(;p>=0&&b[p].se+a[i].se>=Base;--p);
34     return ret;
35 }
36 ll get1(vector<pll> &a,vector<pll> &b,ll Base){
37     ll ret=0;int p=0;
38     for(int i=a.size()-1;~i;ret+=b.size()-p,--i)
39         for(;p<b.size()&&b[p].se+a[i].se<Base;++p);
40     return ret;
41 }
42 
43 void solve(){
44     X.clear();Y.clear();
45     
46     n=read();
47     for(int i=1;i<=n;++i)li[i]=read();
48     get_X(1,0);get_Y(n/2+1,0);
49     //get two set
50     ll ans=0,Base=1,tmp;
51     pll x,y,a,b; 
52     for(int i=0;i<11;++i,Base*=10){
53         for(int j=0;j<10;++j)A[j].clear(),B[j].clear();
54         
55         for(int j=0;j<X.size();++j)
56             x=X[j],A[x.fi%10].pb(mp(x.fi/10,x.se));
57         for(int j=0;j<Y.size();++j)
58             y=Y[j],B[y.fi%10].pb(mp(y.fi/10,y.se));
59         //get this digit
60         for(int j=0,k;j<10;++j){
61             k=(14-j)%10;
62             ans+=get0(A[j],B[k],Base);
63             k=(13-j)%10;
64             ans+=get1(A[j],B[k],Base);
65         }
66         //Calc the ans
67         for(int j=0,now=0;j<10;++j){
68             tmp=Base*j;
69             for(int k=0;k<A[j].size();++k)
70                 a=A[j][k],X[now++]=mp(a.fi,a.se+tmp);
71         }
72         for(int j=0,now=0;j<10;++j){
73             tmp=Base*j;
74             for(int k=0;k<B[j].size();++k)
75                 b=B[j][k],Y[now++]=mp(b.fi,b.se+tmp);
76         }
77     }
78     printf("%lld\n",ans);
79 }
80 
81 int main(){
82     for(int T=read()+1;--T;)solve();
83     return 0;
84 }

 

HDU 6682 Make Rounddog Happy

原文:https://www.cnblogs.com/ndqzhang1111/p/11391302.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!