BZOJ 3573 [Hnoi2014]米特运输 数学

题意: 真·语文题 解析: 做这道题一定要一个字一个字的读完题。 然后发现这题好蠢..否则就是你好蠢.. 读完题我们发现，特喵的确定了根节点所有的点都确定了。 因为每一层节点的值都需要一样… 反之，，确定了一个点根节点就确定了。 所以我们bfs枚举确定的点，并且把计算出来的根节点的值压入栈中，然后最后在栈里找众数的个数。 答案就是n-众数个数。 需要注意的是。 这道题是爆long long的。 那怎么处理呢? 取对数或者mod 多个大素数？ 后者好麻烦显然前者。 代码:

;int n;int val[N];int head[N];int size[N];double if_not_change[N];int cnt;struct node{int from,to,next;}edge[N];void init(){memset(head,-1,sizeof(head));cnt=1;}void edgeadd(int from,int to){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}struct element{int now;double val;};void bfs(){queue<element>q;element fir;fir.now=1;fir.val=0;q.push(fir);while(!q.empty()){element u=q.front();q.pop();for(int i=head[u.now];i!=-1;i=edge[i].next){int to=edge[i].to;element tmp;tmp.now=to;if_not_change[to]=u.val+log2(size[u.now])+log2(val[to]);tmp.val=u.val+log2(size[u.now]);q.push(tmp);}}}int main(){init();scanf(“%d”,&n);for(int i=1;i<=n;i++)scanf(“%d”,&val[i]);for(int i=1;i<n;i++){int x,y;scanf(“%d%d”,&x,&y);edgeadd(x,y);size[x]++;}bfs();if_not_change[1]=log2(val[1]);sort(if_not_change+1,if_not_change+n+1);int la=1;int ans=0;for(int i=2;i<=n+1;i++){if(fabs(if_not_change[i]-if_not_change[i-1])>eps){ans=max(ans,i-la);la=i;}}printf(“%d\n”,n-ans);}

你的脸是为了呈现上帝赐给人类最贵重的礼物–微笑，