洛谷P3237 [HNOI2014]米特运输

2019-11-08 03:08:15

字体：大中小

来源：转载

供稿：网友

我是先讲题目呢，还是先骂人呢? 算了，先讲题目；

https://www.luogu.org/PRoblem/show?pid=3237 题目意思是遍地可找的，但是我们怎么去记录某个点值确定时根节点的值呢？我一开始想到一个dfs n次的算法，时间复杂度n^2，炸！其实你画个图自己推一下，规律显而易见这里写图片描述 sum指的是其儿子的数量；当5号点=x确定，2好点是x*2，根节点是x*2*3 七号点同理；这样时间复杂度就好办了；但是我们可以想到一个问题，根节点的值会炸飞！！，那我们怎么办呢？网上一查， 1.hash 2.log 我两个都不懂啊；但是log比较简单我们看看 http://baike.baidu.com/link?url=Yz3vcXnnxobAelyzmrml8uaThp4w8uX2ztNT49JB5aesfYgVBdnKOJsBxdUxxml2 loga(MN)=logaM+logaN 这不就好办了嘛，我们只要把上图中根节点的各个值log再加起来，完美压缩了空间啊！；

#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;struct cs{ int to,next;}a[500000];int head[500001],sum[500001],vv[500001];double s[500001];int n,m,x,y,ll,ans;void init(int x,int y){ ll++; a[ll].to=y; a[ll].next=head[x]; head[x]=ll; sum[x]++;}void dfs(int x,double y){ s[x]=y+log(double(vv[x])); for(int k=head[x];k;k=a[k].next)dfs(a[k].to,y+log(double(sum[x])));}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&vv[i]); for(int i=2;i<=n;i++)scanf("%d%d",&x,&y),init(x,y); dfs(1,double(log(1.0))); sort(s+1,s+n+1); m=ans=1; for(int i=2;i<=n;i++) if(s[i]-s[i-1]<1e-8)m++,ans=max(ans,m);else m=1; printf("%d",n-ans);}

好了开始骂人

这道题目我一开始看不懂题解，便去问同学，同学十分含糊的解释，隐约听到3个词 1.水题2.爆搜3.排序；其实你懂了的话这道题目是很水的，但是爆搜和排序，我想凡是看见过标程的一定是知道的吧 dfs,sort写在哪里，哪怕不懂题意的人也会说爆搜排序吧？但是这道题的一个关键点是优化内存吧，他什么也没提；然后又说了两句话大意 1.这题我不看程序（只看分析，特指hzwer的博客）就自己打出来了； 2.我这智商真教不了你；不管他，我们先看看hzwer的AC程序在洛谷的运行信息这里写图片描述再看看这个同学的呵呵；我们看看他的详细信息做贼心虚啊他之前有过一次CE，看看 read（）函数，呵呵，这很hzwer 为什么这会CE 恐怕是copy了黄学长的代码，删头文件时多删了几个吧这个同学是我好朋友，我表示惋惜，如果你生气了，或者我说的是假的，我删除这段，并请你吃一顿午饭；

然后我又问了另一个同学，问的问题的中心再那个log上面；其实我的程序的log部分写的是相当不错的，相当精简的；因为我懂了；但我问第二个同学为什么log要加起来 A:标程就是怎么写的；唉！！！！！懵逼的我就自己寻找log的规律发现了log(a*b)=log(a)+log(b) 我并不知道为什么会这样，然后百度了一下，”基本性质“

我们现在是初三，如果你知道这个基本性质，你一定会和我说的啊唉，这个同学的代码我看过，也研究过（研究结论：太繁琐），也许他是没有讲清楚吧；但对于第一个同学不懂还copy，我很失望啊，因为他是我的朋友；

现在机房里处处是不真实，我也一天比一天颓废；但我心中清楚，我现在放弃文化课是为了什么；我知道我不可能冲进省队，拿到金牌，但是我不希望我辜负我的梦想和我父母对我的付出；我不希望我坐在电脑前用尖刀刺自己的胸口；我不希望我以后蜷缩再教室的角落被傻逼嘲笑；愿我能凭借自己的努力，去扭转那命中注定的失败；就是这句话，我的头像变了，然后一直不变；

上一篇：Codeforces Round #396 (Div. 2) D. Mahmoud and a Dictionary （并查集）

下一篇：4、编写一个程序，计算两个日期之间所经过的天数