HDU Page11(2041~2050)递推

2041 超级楼梯

超级楼梯
需要重视
递推求解

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
//f[i]表示到达台阶i的方案数,由于只能从i-1或者i-2到达台阶 i 因此f[i]=f[i-1]+f[i-2] 。

#include <stdio.h>

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

int n, m, steps[105], maxM = 2;
steps[1] = 1;
steps[2] = 1;
// steps[3] = 2;

scanf("%d", &n);

while (n--) {
scanf("%d", &m);

if (maxM < m) {
for (int i=3; i<=m; i++) {
steps[i] = steps[i-1] + steps[i-2];
}
maxM = m;
}

printf("%d\n", steps[m]);
}

return 0;
}

2043 密码

密码不是递推

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
#include <stdio.h>
#include <string.h>

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

int n;
char s[105];

scanf("%d", &n);

while (n--) {
int check[4] = {0, 0, 0, 0};
scanf("%s", s);
if (strlen(s) >= 8 && strlen(s) <= 16) {
for (int i=0; i<strlen(s); i++) {
if (s[i] >= 'A' && s[i] <= 'Z')
check[0] = 1;
else if (s[i] >= 'a' && s[i] <= 'z')
check[1] = 1;
else if (s[i] >= '0' && s[i] <= '9')
check[2] = 1;
else if (s[i] == '~' || s[i] == '!' || s[i] == '@' || s[i] == '#' || s[i] == '$' || s[i] == '%' || s[i] == '^')
check[3] = 1;
}

if ((check[0] + check[1] + check[2] + check[3]) >= 3)
printf("YES\n");
else
printf("NO\n");
} else
printf("NO\n");


}

return 0;
}

2044 一只小蜜蜂

2044 一只小蜜蜂

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>
#include <string.h>

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

int n, a, b;
//注意这个1-50就会很长,用long int都是错误的
long long int f[105];

scanf("%d", &n);

while (n--) {
scanf("%d %d", &a, &b);

f[a] = 1;
f[a+1] = 1;

for (int i=a+2; i<=b; i++) {
f[i] = f[i-1] + f[i-2];
}

printf("%lld\n", f[b]);
}

return 0;
}

//#include <stdio.h>
//int main(){
// long long dp[51];
// int a, b, z, i;
// scanf("%d", &z);
// dp[1] = 1;
// dp[2] = 2;
// for ( i=3; i<=50; ++i ){
// dp[i] = dp[i-2]+dp[i-1];
// }
// while (z--){
// scanf("%d%d", &a, &b);
// printf("%lld\n", dp[b-a]);
// }
// return 0;
//}

2045 不容易系列之(3)—— LELE的RPG难题

不容易系列之(3)—— LELE的RPG难题

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
//注意题目要求,首尾也不相同
//有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色
/*
 n个格子合乎题目要求的涂色时(即称之为合法)对应一个映射f  使f(n)即为所求值。那么接下来分析,当涂
第n个格子的时候,即要求f(n)时,受到第n-1个格子是否与第一个格子相同的制约。那么接下来的问题是对第
n-1个格子分两种情况:假定其和第一个格子不同颜色,那么也就是说前n-1个格子是合法的涂法可以写为f(n-1),
再涂最后一个格子只有一种涂法。第二种第n-1个格子和第一个相同,那么前n-1不合法,且此时第n-2个格子一定和
第一个不同,那么此时前n-2个格子必定又是合法的,且第n个格子2种涂法。那么对f(n)的贡献为f(n-2)*2,那么
f(n)来源于前两种情况的和,由加法原理。f(n)=f(n-1)+f(n-2)*2;
n>3(注意是如何确定的)
前面的1, 2, 3要自己考虑
*/

#include <stdio.h>

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

int n;
//注意递归的其实数字马上很大的,要long long
long long res[105] = {3, 6, 6};

while (scanf("%d", &n) != EOF) {
for (int i=3; i<n; i++) {
res[i] = res[i-1] + res[i-2] * 2;
}
printf("%lld\n", res[n-1]);
}

return 0;
}

2046 骨牌铺方格

骨牌铺方格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

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

int n, maxN = 2;
long long int f[60];
f[1] = 1;
f[2] = 2;

while(scanf("%d", &n) != EOF) {
if (maxN < n) {
for (int i=maxN+1; i<=n; i++) {
f[i] = f[i-1] + f[i-2];
}
maxN = n;
}
printf("%lld\n", f[n]);
}

return 0;
}

2047阿牛的EOF牛肉串

2047阿牛的EOF牛肉串
注意思想与2045 不容易系列之(3)—— LELE的RPG难题

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
/*
关于这道题我们直接考虑n为‘o’时候的情况,因为题目说只要‘oo’不相邻就算一组题解,当n为‘o’的时候,n-1只能是‘e’或者‘f’,n-2则是每组‘e’,‘o’,‘f’都可以取,
能够得到f(n)=2f(n-2);
然后考虑n不为‘0’,n为‘e’或者‘f’,则n-1对于‘e’,‘o’,‘f’都可选取,择有f(n)=2*f(n-1),
然后换位思考,站在‘e’‘f’的角度看问题你会发现‘e’关于‘f’是对称的,即f(n)=2*(f(n-1)+f(n))
*/

#include <stdio.h>

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

int n, maxN = 2;
long long int f[60];
f[1] = 3;
f[2] = 8;

while(scanf("%d", &n) != EOF) {
if (maxN < n) {
for (int i=maxN+1; i<=n; i++) {
f[i] = 2*(f[i-1] + f[i-2]);
}
maxN = n;
}
printf("%lld\n", f[n]);
}

return 0;
}

2048 神、上帝以及老天爷

神、上帝以及老天爷

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
/*
题意是给出抽奖的人数,抽中自己的名字算中奖,计算没有一个人中奖的概率
可以用错排+递推
分析:
全错的概率 = 全错数 / 全部情况。
全部情况就是N的阶乘。
全错数:
1.将第N个数放在k位置,有n-1种。
2.将第k个位置的数拿出来考虑,如果第k个数放在第N个位置,则剩下就是n-2个数全部排错情况;
如果第k个数不是放在第N个位置,则就是n-1个数全部排错情况(这是对的,可把k看成n,n不会放到N位置,所以算错排?)
因此全错数就是a(n) = (n-1)*(a(n-1) + a(n-2))
*/

#include <stdio.h>

long long int jieceng(int n) {
long long sum = 1;
while (n) {
sum *= n;
n--;
}
// printf("%lld\n", sum);
return sum;
}

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

int n, m, maxN = 2;
double f[60];
f[1] = 0;
f[2] = 1;

scanf("%d", &m);
while (m--) {
scanf("%d", &n);
if (maxN < n) {
for (int i=maxN+1; i<=n; i++) {
f[i] = (i-1)*(f[i-1] + f[i-2]);
}
maxN = n;
}
// printf("%.2lf\n", f[n]);
printf("%.2lf%%\n", f[n]*100.0/jieceng(n));
}

return 0;
}

2049 不容易系列之(4)——考新郎

不容易系列之(4)——考新郎

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
/*
这道题是n个人,错了m个,那我们就转化为m个人全错排好了,那n-m个人坐对了,m个人全错排,
n-m个人坐对的方式有c(m,n-m)(组合数)种,那n个人m个人坐对的种数就是c(m,n-m)*f(m),
当然,有几个特殊情况需要另外讨论。比如说n=m时,组合数计算需要返回一个1,结果就是f(m),
还有m=1时,f(1)=0,计算结果是0,而事实上计算结果是c(n,1)种,所以我们在计算完f(i)的
值以后可以把f(1)赋为1,(因为1<m<=n<=20,所以不用考虑用到f(1)计算结果不正确)
*/

#include <stdio.h>

long long int jieceng(int n) {
long long sum = 1;
while (n) {
sum *= n;
n--;
}
return sum;
}

long long CMethod(int n, int a) {
long long int sum = 1;

for (int i=n; i>n-a; i--) {
sum *= i;
}

for (int i=1; i<=a; i++) {
sum /= i;
}

return sum;
}

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

int c, n, m, maxN = 2;
long long int f[60];

scanf("%d", &c);

while (c--) {
f[1] = 0;
f[2] = 1;
scanf("%d %d", &n, &m);

if (maxN < m) {
for (int i=maxN+1; i<=m; i++) {
f[i] = (i-1)*(f[i-1] + f[i-2]);
}
maxN = m;
}

f[1] = 1;
printf("%lld\n", CMethod(n, n-m) *f[m]);
}

return 0;
}

2050 折线分割平面

折线分割平面
折线分割平面

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
/*
先看N条相交的直线最多能把平面分割成多少块
当添加第N条只显示,为了使平面最多, 则第N条直线要与前面的N-1条直线都相交,且没有任何三条直线教育一个点。
则第N条直线有N-1个交点。由于每增加N个交点,就增加N+1个平面,所以用N条直线来分隔平面,
最多的数是1+1+2+3+…+n=1+n*(n+1)/2, 第一个1是原先就有一个平面
*/

/*
再看每次增加两条相互平行的直线
当第N次添加时,前面已经有2N-2条直线了,所以第N次添加时,第2N-1条直线和第2N条直线都各能增加2*(n-1)+1 个平面。
所以第N次添加增加的面数是2[2(n-1) + 1] = 4n - 2 个。因此,总面数应该是
1 + 4n(n+1)/2 - 2n = 2n2 + 1
*/

/*
如果把每次加进来的平行边让它们一头相交
则平面1、3已经合为一个面,因此,每一组平行线相交后,就会较少一个面,
所以所求就是平行线分割平面数减去N,为2n2 -n + 1
利用上述总结公式f(n)=2n2 - n + 1
*/


#include <stdio.h>

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

int c, n;

scanf("%d", &c);

while (c--) {
scanf("%d", &n);

printf("%d\n", 2 * n * n - n + 1);
}

return 0;
}

Author: Jcwang

Permalink: http://example.com/2020/03/15/HDU-Page11-2041%EF%BD%9E2050%E9%80%92%E6%8E%A8/