首页 > 代码库 > codeforces Round #250 (div2)

codeforces Round #250 (div2)

2024-07-07 10:07:37   231人阅读

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 }

 


联系
我们