题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6533

You need to construct a full n-ary tree(n叉树) with m layers.All the edges in this tree have a weight.But this weight cannot be chosen arbitrarily you can only choose from set S，the size of S is k，each element in the set can only be used once.Node 0 is the root of tree.

 We use d(i) for the distance from root to node i.Our goal is to minimize the following expression:

min∑i=0Nd(i)

 Please find the minimum value of this expression and output it.Because it may be a big number,you should output the answer modul p.

题意是说给出一个m层的满n叉数和一个大小为k的集合S，从S中不重复的选择值作为边权，使得每一个结点到根节点的总权值最小。输出总权值模p。

比赛的时候以为根节点不算一层，再加上题意看错了，一直陷在只有3条边，但是集合S里有5个值里面，没有做出来。实际上这道题是一个很简单的贪心。越低层的边使用的次数越少，就安排大的权值，越上层的边使用的次数越多，就安排小的权值。

#include#include#include#includeusingnamespacestd;constint maxn=2e5+5;longlong weight[maxn],ans[maxn],st[maxn];voidli(longlong x){st[0]=1;for(int i=1;i<=60;i++){if(st[i-1]*x<1e15)st[i]=st[i-1]*x;}}longlongquickpow(longlong res,longlong ti){longlong ans=1;while(ti){if(ti&1)ans*=res;res*=res;ti>>=1;}return ans;}intmain(){    //freopen("in.txt","r",stdin);longlong k,m,n,p;while(~scanf("%lld%lld%lld%lld",&k,&m,&n,&p)){memset(ans,0,sizeof(ans));li(n);//for(int i=0;i<10;i++)//            printf("%d %lld\n",i,st[i]);for(int i=0;iscanf("%lld",&weight[i]);sort(weight,weight+k);longlong sum=1LL*(longlong)(quickpow(n,m)-1)*1.0/(n-1);//printf("%lld\n",sum);int pos=1,co=0;for(int i=0;i-1;i++){if(co1LL*(quickpow(n,m-pos)-1)*1.0/(n-1);//printf("%lld\n",ans[i]);co++;}if(co==st[pos]){pos++;co=0;}}longlong res=0;for(int i=0;i-1;i++)res=(res+weight[i]*ans[i]%p)%p;printf("%lld\n",res);}return0;}

下次加油！