cf 250 div2

a題，就不說了吧

b題，直接從大到小排序1-limit的所有數的lowbit，再從大到小貪心組成sum就行了

#include
#include
#include
#include
#define N 200000
using namespace std;
int pos[N],a[N],s[N],f[N],la[N],b[N],i,j,k,ans,n,p,sum,lim;
bool fl[N];
struct node{
		int x,y;
		}u[N];
int pow(int x, int n)
{
    int result;
    if (n == 0)
        return 1;
    else
    {
        while ((n & 1) == 0)
        {
            n >>= 1;
            x *= x;
        }
    }
    result = x;
    n >>= 1;
    while (n != 0)
    {    
        x *= x;
        if ((n & 1) != 0)
            result *= x;
        n >>= 1;
    }
    return result;
}
bool cmp(node a, node b)
{
	return a.y>b.y;
}
int main()
{
	scanf("%d%d",&sum,&lim);
	for (i=1; i<=lim; i++)
	{
		j=i;
		k=0;
		while (j % 2==0)
		{
			++k;
			j=j / 2;
		}
		pos[k]=i;
		u[i].x=i;
		u[i].y=pow(2,k);
	}
	sort(u+1,u+lim+1,cmp);

	i=1;
	while (sum)
	{
		while  (sum < u[i].y)	i++;
		sum-=u[i].y;
		a[++ans]=u[i].x;
		i++;
		if (i > lim && sum) 
		{
			printf("-1");
			return 0;
		}
	}
	printf("%d\n",ans);
	for (i=1; i<=ans; i++)
		printf("%d ",a[i]);
	return 0;
}

#include
#include
#include
using namespace std;
int n,m,ans,i,x,y,a[10000];
int main()
{
	scanf("%d%d",&n,&m);
	for (i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		ans+=min(a[x], a[y]);
	}
	printf("%d",ans);
	return 0;
}

#include
#include
#include
#define N 200000
using namespace std;
typedef long long LL;
struct edge{
	LL u,v,c;
	}e[N];
int n,m;
LL f[N],s[N],x[N],i,fa,fb;
double sum;
int find(LL x){
	if (x != f[x]) f[x]=find(f[x]);
	return f[x];
}
bool cmp(edge a,edge b){
	return a.c>b.c;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (i=1; i<=n; i++){
		scanf("%I64d",&x[i]);
		f[i]=i, s[i]=1;
	}
	for (i=1; i<=m; i++){
		scanf("%I64d%I64d",&e[i].u,&e[i].v);
		e[i].c=min(x[e[i].u], x[e[i].v]);
	}
	sort(e+1,e+m+1,cmp);
	for (i=1; i<=m; i++){
		fa=find(e[i].u), fb=find(e[i].v);
		if (fa==fb) continue;
		sum+=(s[fa] * s[fb]) * e[i].c;
		f[fb]=fa, s[fa]+=s[fb];
	}
	sum=2.0 * (sum / n) / (n-1);
	printf("%.6lf",sum);
	return 0;	
}