分类存档: ACM

最小生成树Prim算法

看Prim算法之前要先知道什么是最小生成树。

对于一个如下的图,求最小生成树的权值。

首先定义一个数组map[N][N](N根据题目决定大小)存放权值。对其进行初始化:

0 1 2 3 4 5 6
0
1 5 8
2 5 6 8
3 8 1
4 6 3 5
5 8 1 3 6
6 5 6

继续阅读 »

hdu 1284 钱币兑换问题 代码超短

http://acm.hdu.edu.cn/showproblem.php?pid=1284

Problem Description
在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input
每行只有一个正整数N,N小于32768。

Output
对应每个输入,输出兑换方法数。

Sample Input
2934
12553

Sample Output
718831
13137761

继续阅读 »

hdu 1155 Bungee Jumping 解题报告 代码超精简

 http://acm.hdu.edu.cn/showproblem.php?pid=1155

Problem Description
Once again, James Bond is fleeing from some evil people who want to see him dead. Fortunately, he has left a bungee rope on a nearby highway bridge which he can use to escape from his enemies. His plan is to attach one end of the rope to the bridge, the other end of the rope to his body and jump off the bridge. At the moment he reaches the ground, he will cut the rope, jump into his car and be gone.

Unfortunately, he had not had enough time to calculate whether the bungee rope has the right length, so it is not clear at all what is going to happen when he jumps off the bridge. There are three possible scenarios:The rope is too short (or too strong), and James Bond will never reach the ground.The rope is too long (or too weak), and James Bond will be going too fast when he touches the ground. Even for a special agent, this can be very dangerous. You may assume that if he collides at a speed of more than 10 m/s, he will not survive the impact.The rope’s length and strength are good. James Bond touches the ground at a comfortable speed and can escape.As his employer, you would like to know whether James Bond survives or whether you should place a job ad for the soon-to-be vacant position in the local newspaper. Your physicists claim that:The force with which James is pulled towards the earth is9.81 * w,where w is his weight in kilograms and 9.81 is the Earth acceleration in meters over squared seconds.Mr. Bond falls freely until the rope tautens. Then the force with which the bungee rope pulls him back into the sky depends on the current length of the rope and is k * Δl,where Δl is the difference between the rope’s current length and its nominal, unexpanded length, and k is a rope-specific constant.Given the rope’s strength k, the nominal length of the rope l in meters, the height of the bridge s in meters, and James Bond’s body weight w, you have to determine what is going to happen to our hero. For all your calculations, you may assume that James Bond is a point at the end of the rope and the rope has no mass. You may further assume that k, l, s, and w are non-negative and that s < 200.
The input contains several test cases, one test case per line. Each test case consists of four floating-point numbers (k, l, s, and w) that describe the situation. Depending on what is going to happen, your program must print “Stuck in the air.”, “Killed by the impact.”, or “James Bond survives.”. Input is terminated by a line containing four 0s, this line should not be processed.

Sample Input
350 20 30 75
375 20 30 75
400 20 30 75
425 20 30 75
450 20 30 75
400 20 30 50
400 20 30 80
400 20 30 85
0 0 0 0

Sample Output
Killed by the impact.
James Bond survives.
James Bond survives.
James Bond survives.
Stuck in the air.
Stuck in the air.
James Bond survives.
Killed by the impact.

继续阅读 »

hdu 1214 圆桌会议 解题报告 超短代码

http://acm.hdu.edu.cn/showproblem.php?pid=1214

Problem Description
HDU ACM集训队的队员在暑假集训时经常要讨论自己在做题中遇到的问题.每当面临自己解决不了的问题时,他们就会围坐在一张圆形的桌子旁进行交流,经过大家的讨论后一般没有解决不了的问题,这也只有HDU ACM集训队特有的圆桌会议,有一天你也可以进来体会一下哦:),在一天在讨论的时候,Eddy想出了一个极为古怪的想法,如果他们在每一分钟内,一对相邻的两个ACM队员交换一下位子,那么要多少时间才能得到与原始状态相反的座位顺序呢?(即对于每个队员,原先在他左面的队员后来在他右面,原先在他右面的队员在他左面),这当然难不倒其他的聪明的其他队友们,马上就把这个古怪的问题给解决了,你知道是怎么解决的吗?

Input
对于给定数目N(1<=N<=32767),表示有N个人,求要多少时间才能得到与原始状态相反的座位顺序(reverse)即对于每个人,原先在他左面的人后来在他右面,原先在他右面的人在他左面。

Output
对每个数据输出一行,表示需要的时间(以分钟为单位)

Sample Input
4
5
6

Sample Output
2
4
6

继续阅读 »

hdu 2184 汉诺塔VIII 解题报告

http://acm.hdu.edu.cn/showproblem.php?pid=2184

Problem Description
1,2,…,n表示n个盘子.数字大盘子就大.n个盘子放在第1根柱子上.大盘不能放在小盘上.在第1根柱子上的盘子是a[1],a[2],…,a[n]. a[1]=n,a[2]=n-1,…,a[n]=1.即a[1]是最下面的盘子.把n个盘子移动到第3根柱子.每次只能移动1个盘子,且大盘不能放在小盘上.问移动m次后的状况.

Input
第1行是整数T,表示有T组数据,下面有T行
每行2个整数n (1 ≤ n ≤ 63) ,m≤ 2^n-1

Output
输出移动m次后的状况.每组输出3行,第i行第1个数是第i根柱子上的盘子数,然后是盘子的号数.

Sample Input
3
3 2
4 5
39 183251937942

Sample Output
1 3
1 2
1 1
2 4 1
1 3
1 2
13 39 36 33 30 27 24 21 18 15 12 9 4 1
12 38 35 32 29 26 23 20 17 14 11 8 5
14 37 34 31 28 25 22 19 16 13 10 7 6 3 2

继续阅读 »

hdu 1060 Leftmost Digit 解题报告

http://acm.hdu.edu.cn/showproblem.php?pid=1060
Problem Description
Given a positive integer N,you should output the leftmost digit of N^N.

Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test casesfollow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).

Output
For each test case, you should output the leftmost digit of N^N.

Sample Input
2
3
4

Sample Output
2
2

Hint
In the first case, 3 * 3 * 3 = 27, so the leftmost digit is 2. In the second case, 4 * 4 * 4 * 4 = 256, so the leftmost digit is 2.

继续阅读 »

hdu 2117 Just a Numble 0MS 代码

http://acm.hdu.edu.cn/showproblem.php?pid=2117
Problem Description
Now give you two integers n m, you just tell me the m-th number after radix point in 1/n,for example n=4,the first numble after point is 2,the second is 5,and all 0 followed.

Input
Each line of input will contain a pair of integers for n and m(1<=n<=10^7,1<=m<=10^5).
Output
For each line of input, your program should print a numble on a line,according to the above rules.

Sample Input
4 2
5 7
123 123

Sample Output
5
0
8

继续阅读 »