首页 > 代码库 > codeforces Round #250 (div2)
codeforces Round #250 (div2)
a题,就不说了吧
b题,直接从大到小排序1-limit的所有数的lowbit,再从大到小贪心组成sum就行了
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #define N 200000 6 using namespace std; 7 int pos[N],a[N],s[N],f[N],la[N],b[N],i,j,k,ans,n,p,sum,lim; 8 bool fl[N]; 9 struct node{ 10 int x,y; 11 }u[N]; 12 int pow(int x, int n) 13 { 14 int result; 15 if (n == 0) 16 return 1; 17 else 18 { 19 while ((n & 1) == 0) 20 { 21 n >>= 1; 22 x *= x; 23 } 24 } 25 result = x; 26 n >>= 1; 27 while (n != 0) 28 { 29 x *= x; 30 if ((n & 1) != 0) 31 result *= x; 32 n >>= 1; 33 } 34 return result; 35 } 36 bool cmp(node a, node b) 37 { 38 return a.y>b.y; 39 } 40 int main() 41 { 42 scanf("%d%d",&sum,&lim); 43 for (i=1; i<=lim; i++) 44 { 45 j=i; 46 k=0; 47 while (j % 2==0) 48 { 49 ++k; 50 j=j / 2; 51 } 52 pos[k]=i; 53 u[i].x=i; 54 u[i].y=pow(2,k); 55 } 56 sort(u+1,u+lim+1,cmp); 57 58 i=1; 59 while (sum) 60 { 61 while (sum < u[i].y) i++; 62 sum-=u[i].y; 63 a[++ans]=u[i].x; 64 i++; 65 if (i > lim && sum) 66 { 67 printf("-1"); 68 return 0; 69 } 70 } 71 printf("%d\n",ans); 72 for (i=1; i<=ans; i++) 73 printf("%d ",a[i]); 74 return 0; 75 }
c题,直接找每连接两端中值较小的部分
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 int n,m,ans,i,x,y,a[10000]; 6 int main() 7 { 8 scanf("%d%d",&n,&m); 9 for (i=1; i<=n; i++) 10 scanf("%d",&a[i]); 11 for (i=1; i<=m; i++) 12 { 13 scanf("%d%d",&x,&y); 14 ans+=min(a[x], a[y]); 15 } 16 printf("%d",ans); 17 return 0; 18 }
d题,并查集处理
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define N 200000 5 using namespace std; 6 typedef long long LL; 7 struct edge{ 8 LL u,v,c; 9 }e[N]; 10 int n,m; 11 LL f[N],s[N],x[N],i,fa,fb; 12 double sum; 13 int find(LL x){ 14 if (x != f[x]) f[x]=find(f[x]); 15 return f[x]; 16 } 17 bool cmp(edge a,edge b){ 18 return a.c>b.c; 19 } 20 int main() 21 { 22 scanf("%d%d",&n,&m); 23 for (i=1; i<=n; i++){ 24 scanf("%I64d",&x[i]); 25 f[i]=i, s[i]=1; 26 } 27 for (i=1; i<=m; i++){ 28 scanf("%I64d%I64d",&e[i].u,&e[i].v); 29 e[i].c=min(x[e[i].u], x[e[i].v]); 30 } 31 sort(e+1,e+m+1,cmp); 32 for (i=1; i<=m; i++){ 33 fa=find(e[i].u), fb=find(e[i].v); 34 if (fa==fb) continue; 35 sum+=(s[fa] * s[fb]) * e[i].c; 36 f[fb]=fa, s[fa]+=s[fb]; 37 } 38 sum=2.0 * (sum / n) / (n-1); 39 printf("%.6lf",sum); 40 return 0; 41 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。