月度归档:2016年11月

BZOJ 1726: [Usaco2006 Nov]Roadblocks第二短路(次短路)

Description

贝茜把家搬到了一个小农场,但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路,每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1,她的朋友们居住在农场N(即贝茜每次旅行的目的地)。 贝茜选择的第二短的路径中,可以包含任何一条在最短路中出现的道路,并且,一条路可以重复走多次。当然咯,第二短路的长度必须严格大于最短路(可能有多条)的长度,但它的长度必须不大于所有除最短路外的路径的长度。

Input

* 第1行: 两个整数,N和R,用空格隔开

* 第2..R+1行: 每行包含三个用空格隔开的整数A、B和D,表示存在一条长度为 D(1 <= D <= 5000)的路连接农场A和农场B

Output

* 第1行: 输出一个整数,即从农场1到农场N的第二短路的长度

Sample Input

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

输出说明:

最短路:1 -> 2 -> 4 (长度为100+200=300)
第二短路:1 -> 2 -> 3 -> 4 (长度为100+250+100=450)

次短路也可以通过spfa维护出来,(但是复杂度我就不确定了囧)。
分三种情况松弛吧(可能有些不同,设dis1为最短路,dis2为次短路):
1.如果dis1[next]>dis1[now]+len,那么dis1肯定要被更新。dis2[next]也要被更新,和原来的dis1[next]相比较。
2.如果dis1[next]<dis1[now]+len,如果dis2[next]>dis1[now]+len,那么更新次短路,也就是说从now可以松弛一条次短路出来。
3.如果dis1[next]=dis1[now]+len,那么也就是说从now松弛到next也是可以的,但是不会改变最短路。但是如果能更新此段路的话那么就得从Now松弛了。
然后一开始起点的次短路为inf,因为起点根本就木有次短路哇。然后这个没注意一直调不出样例。
最近忙于补作业,身体也不舒服只能划水了。。。欠了一堆题目

 

hdu 5884 Sort(二分+K叉哈夫曼树)

Problem Description
Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.
Alice will give Bob N sorted sequences, and the i-th sequence includes ai elements. Bob need to merge all of these sequences. He can write a program, which can merge no more than k sequences in one time. The cost of a merging operation is the sum of the length of these sequences. Unfortunately, Alice allows this program to use no more than T cost. So Bob wants to know the smallest k to make the program complete in time.

 

Input
The first line of input contains an integer t0, the number of test cases. t0 test cases follow.
For each test case, the first line consists two integers N (2N100000) and T (Ni=1ai<T<231).
In the next line there are N integers a1,a2,a3,...,aN(i,0ai1000).

 

Output
For each test cases, output the smallest k.

 

Sample Input
1
5 25
1 2 3 4 5
Sample Output
3
这道题是很久写的了,然后最近碰到一个类似合并果子的题目,于是一时兴起想写个O(n)的方法,于是就把这个题回顾了一下。
这个题目一开始是直接手写堆+读入优化的做法,但是一直T,然后我换O(n)的做法来求K叉哈夫曼树,疯狂的WA。和原来的拍也拍不出错。。。比完赛才知道原来是处理K叉树未满的情况下,我的贪心错了。懊恼不已。。。
二分然后验证的思路很显然。然后O(n)求K叉哈夫曼树即可。注意如果不是正好K叉,我们需要选择最小的那几个先合并(放到哈夫曼树的底部)。

 

BZOJ 2048: [2009国家集训队]书堆(调和级数+推公式)

Description

Input

第一行正整数 N M

Output

一行(有换行符),L,表示水平延伸最远的整数距离 (不大于答案的最大整数)

Sample Input

样例
#1
Input: 1 100
Output: 49

#2
Input: 2 100
Output: 74

Sample Output

N <= 10^18
数据保证答案 < 10^6
经典中学题?推一推公式发现,答案是.这样就发现是调和级数的形式,而调和级数的极限的公式是。那么就小范围暴力,大范围套公式好了。。。怎么推得公式?弄个方程啊QAQ。。。