HDU-Page11(2059~2062)

2059 龟兔赛跑

龟兔赛跑
解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
https://blog.csdn.net/sr_19930829/article/details/18802543
动态规划题目。dp[i]数组用来保存从起点到当前第i个充电站所用的最短时间.  它等于dp[j] (j<i) 所用的时间加上从j到i所用的时间取最小的那个值。   在计算的时候,可以认为乌龟都是在充电站j充满电以后再走向充电站i的,可能会有疑问,题目中不是说充电站可以充电也可以选择不充电吗,
的确是这样,这就要提前面说的最小的那个值,比如要求dp[4], 比如要从节点2(充电站2)到4,在2充满电,经过3,这时候在节点3是不充电的,后来要从节点3到4,在3充满电,再到4,
这样就考虑到了某一个充电站充电和不充电的情况,取最小值是指(0到4时间 +dp[0], 1到4时间+dp[1] ,2到4时间+dp[2], 3到4时间+dp[3]) 的最小值(就当前节点dp[4]来说)。
*/

#include <stdio.h>

int main(int argc, const char * argv[]) {
// insert code here...

int l; //跑道的总长度
int N, C, T; //充电站的个数,电动车冲满电以后能行驶的距离以及每次充电所需要的时间
int VR, VT1, VT2; //兔子跑步的速度,乌龟开电动车的速度,乌龟脚蹬电动车的速度
int path[102]; //各个充电站离跑道起点的距离
double dp[102];

while (scanf("%d", &l) != EOF) {
scanf("%d %d %d", &N, &C, &T);
scanf("%d %d %d", &VR, &VT1, &VT2);
for (int i=1; i<=N; i++) {
scanf("%d", &path[i]);
}
path[0]=0; path[N+1]=l; //每个充电站看作一个节点,把起点和终点也看作节点
dp[0] = 0;

for (int i=1; i<=N+1; i++) {
double min = 1000000; //从第J到第I个充电站的最短时间

for (int j = 0; j<i; j++) {
double temp; //temp是指从起点到节点i所用的时间
//从节点j到节点i的距离大于等于C的话
if (path[i] - path[j] > C)
//时间是起点到节点j加上从j到i这一段所用的时间(分为两部分)
temp = dp[j] + C * 1.0 / VT1 + (path[i]-path[j]-C) * 1.0 / VT2;
else
temp = dp[j] + (path[i] - path[j]) * 1.0 / VT1;

// 和带着充满电的电动车的乌龟并列站在起跑线上, 一开始充满电
if (j > 0)
temp += T; //在节点j充电的时间,计算的时候看作每次都是在节点j充满电再走向节点i
if (temp < min)
min = temp;
}

dp[i] = min;
}

double rt;
rt = l * 1.0 / VR;//兔子用的时间
if(dp[N+1] < rt)
printf("What a pity rabbit!\n");
else
printf("Good job,rabbit!\n");
}

return 0;
}

2060 Snooker

Snooker
解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
我觉得英文的看规则的题目,不会难,难的是弄懂和逻辑
12 * 1 (12 red-ball in one shoot) + 7 * 12(after hit a red ball, a black ball which was the most valuable ball should be the target)
+ 2 + 3 + 4 + 5 + 6 + 7(when no red ball left, make all the color ball in hole).
然后它说的是可能赢,那么就给飞利浦第二个加数中的最好的colorball,给对手最差的喽???(不对,题目都有点误解)
好吧,题目中现在给的是所有ball的数量而不是红球的数量了
看一下解析
*/

/*
https://www.cnblogs.com/webmen/p/5739262.html
桌上有n个球,一人得分为a,另一人为b,问如果第一个人将n个球都打进洞后,得分能否超过(或等于)第二个人。
总共有15个红球,和6个有颜色的球,每个红球的得分为1 ,6
个有颜色的球分别为2 , 3, 4 ,5, 6, 7 ;

分析:
① 如果n>6 ,
那么桌上有6个彩球和n-6个红球,但是由于有色球全部打进洞后,每个球需要额外增加黑球(最高得分)的得分;所以打进n个球的得分为:
(n-6)*1+(n-6)*7+2+3+4+5+6+7
② 当 m <= 6 时,
应该由价值最高的黑球( 7 分) 向前依
次增加求和,又因为有色球满足等差数列 ,由前6项减去前 6 - m项和,所以
求得为( 7 - m + 1 + 7 ) * m / 2 ( 这里直接通过得分来计算的)。因
此,第二种情况的得分为( 15 - m ) *m/ 2 ;
*/

#include <stdio.h>

int main(int argc, const char * argv[]) {
// insert code here...

int n, pScore, oScore, leftBallNum;

scanf("%d", &n);
while (n--) {
scanf("%d %d %d", &leftBallNum, &pScore, &oScore);

if (leftBallNum > 6)
pScore += (leftBallNum-6) + (leftBallNum-6) * 7 + (2 + 7) * 6 / 2;
else
pScore += (8-leftBallNum + 7) * leftBallNum / 2;

if (pScore >= oScore)
printf("Yes\n");
else
printf("No\n");
}

return 0;
}

2061 Treasure the new start, freshmen!

Treasure the new start, freshmen!
解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>

int main(int argc, const char * argv[]) {
// insert code here...

int n, m;
// int blankFlag = 0;
double credit, score;
char className[100];

scanf("%d", &n);
while (n--) {
// if (blankFlag)
// printf("\n");
// else
// blankFlag = 1;

scanf("%d", &m);
int flag = 1;
// int creditSum = 0; //都是浮点呀, 因为这个wa了好久
double sum = 0.0, creditSum = 0.0;

while (m--) {
scanf("%s %lf %lf", className, &credit, &score);

if (score < 60)
flag = 0;
// printf("Sorry!\n")
// 
; //这里不能直接
的,因为后面还有需要读取的课程和学分,难道不读取了吗???
//也不能直接print, 因为这里直接print的话不用回车就会输出了

creditSum += credit;
sum += credit * score;
}

if (flag) printf("%.2lf\n", sum * 1.0 / creditSum);
else printf("Sorry!\n");

if (n != 0)
printf("\n");
}

return 0;
}

2062 Subset sequence

Subset sequence
解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
{1}
{1,2}
{1,2,3}
{1,3}
{1,3,2}

{2}
{2,1}
{2,1,3}
{2,3}
{2,3,1}

{3}
{3,1}
{3,1,2}
{3,2}
{3,2,1}
*/

/*
https://blog.csdn.net/qq_33266889/article/details/53468509
①设f(n)是n个数字按照字典序所产生的子集个数,f(n) = n*( f(n-1) + 1 ),f(1)=1
这里需要强调按照字典序生成的子集,一个含有n个元素的集合真子集的个数是2^n-1,为什么按照字典序生成的子集却不符合这一规律?
因为在按字典序生成时{1,2}和{2,1}认为是两个不同的集合,所以 f(n) >> 2^n-1。
②设g(n)是每一组子集的个数,g(n)=f(n)/n
g(n-1)=f(n-1)/(n-1),f(n) = n*( f(n-1) + 1 ),g(n)=(n-1)*g(n-1)+1

从上面子集顺序可以得到一个思路,我们可以先输出开头数字,然后把问题规模缩小到( n-1 , m-(t-1)*g(n)-1 ),不断缩小规模直至找到答案。

主要步骤:
1、求出所在组t
2、输出所在组t的首元素s[t](同一组首元素相同)
3、将该子集的下一个元素到最后一个的值+1,注意这个规律:在第i组,首元素为i,删除首元素后,在第i个子集后首元素均变大+1.
4、缩减问题规模继续执行步骤1~3
*/

#include <stdio.h>
#include <string.h>

int main(int argc, const char * argv[]) {
// insert code here...

int n;
int t; // 所求子集位于分组后的第几组
long long m; // m:位于某一组的第几个子集
long long g[21] = {0}; // 后面将子集分组后平均每组个数,如:c[2]表示n=2时的分组每组中子集数
int s[21]; // 每组首元素元素,组数<=20

for (int i=1; i<=20; i++) {
g[i] = (i - 1) * g [i -1] + 1;
}

while (scanf("%d %lld", &n, &m) != EOF) {
for(int i=0;i<21;i++)
s[i]=i; // 每循环一次就重新归位每组首元素

while (m && n) {
//以下要适当加括号, 不然优先级不对的, 特别是三目出现的时候
// 得到第m个子集在分组后的第t组
t = (int)((m / g[n]) + (m % g[n] > 0 ? 1 : 0));
printf("%d", s[t]);

for (int i=t; i<=n; i++) {
// s[i]++; // 当去掉开头数字后,大于开头数字的数+1
s[i]=s[i+1]; //在第n组中,第2个元素在第n个时变为它的下一个数, 而并不一定是++
}
m -= ((t - 1) * g[n] + 1); // 减去(t-1组总子集数+1), m变为表示在剩余子集中位于第几个
printf(m == 0 ? "\n" : " ");

n--; // 规模减小, 依次递减, 直到执行上面的if代码或退出
}
}

return 0;
}

Author: Jcwang

Permalink: http://example.com/2020/03/30/HDU-Page11(2059%EF%BD%9E2062)/