月度归档:2016年10月

hdu 5950 Recursive sequence(矩阵快速幂)

Problem Description
Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.

 

Input
The first line of input contains an integer t, the number of test cases. t test cases follow.
Each case contains only one line with three numbers N, a and b where N,a,b < 231 as described above.

 

Output
For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.

 

Sample Input
2
3 1 2
4 1 10
Sample Output
85
369

Hint

In the first case, the third number is 85 = 2*1十2十3^4. In the second case, the third number is 93 = 2*1十1*10十3^4 and the fourth number is 369 = 2 * 10 十 93 十 4^4.

矩阵快速幂。

 

hdu 5935 Car(贪心)

Problem Description
Ruins is driving a car to participating in a programming contest. As on a very tight schedule, he will drive the car without any slow down, so the speed of the car is non-decrease real number.

Of course, his speeding caught the attention of the traffic police. Police record N positions of Ruins without time mark, the only thing they know is every position is recorded at an integer time point and Ruins started at 0.

Now they want to know the minimum time that Ruins used to pass the last position.

 

Input
First line contains an integer T, which indicates the number of test cases.

Every test case begins with an integers N, which is the number of the recorded positions.

The second line contains N numbers a1, a2, , aN, indicating the recorded positions.

Limits
1T100
1N105
0<ai109
ai<ai+1

 

Output
For every test case, you should output ‘Case #x: y’, where x indicates the case number and counts from 1 and y is the minimum time.

 

Sample Input
1
3
6 11 21

Sample Output

Case #1: 4
给出n个时间点(时间点必须是整数)的车的位置,为到n号时间点记录的位置时最少通过的时间。
clearY,老司机他们说在杭州被卡精度了,然而窝表示为什么会有精度问题呢?囧
因为速度不减,所以说最后一段的速度肯定最快,那么就可以得到一个式子:,然后只要保证时间是整数就可以了。递推求解。。。

 

hdu 5934 Bomb(tarjan缩点)

Problem Description
There are N bombs needing exploding.

Each bomb has three attributes: exploding radius ri, position (xi,yi) and lighting-cost ci which means you need to pay ci cost making it explode.

If a un-lighting bomb is in or on the border the exploding area of another exploding one, the un-lighting bomb also will explode.

Now you know the attributes of all bombs, please use the minimum cost to explode all bombs.

 

Input
First line contains an integer T, which indicates the number of test cases.

Every test case begins with an integers N, which indicates the numbers of bombs.

In the following N lines, the ith line contains four intergers xi, yi, ri and ci, indicating the coordinate of ith bomb is (xi,yi), exploding radius is ri and lighting-cost is ci.

Limits
1T20
1N1000
108xi,yi,ri108
1ci104

 

Output
For every test case, you should output ‘Case #x: y’, where x indicates the case number and counts from 1 and y is the minimum cost.

 

Sample Input
1
5
0 0 1 5
1 1 6
0 1 1 7
3 0 2 10
5 0 1 4
Sample Output
Case #1: 15
tarjan求出强连通分量后缩点,从入度为0的连通块内取代价最小的引爆即可。水题一道,结果我沙茶的求距离用的double、、、、