HDU Page11(2067~2080)

2067 小兔的棋盘

小兔的棋盘
递推解析
该数正好为卡特兰数,卡特兰是什么

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
//https://blog.csdn.net/guduyibeizi/article/details/8740896
//https://blog.csdn.net/wu_tongtong/article/details/78161211
//题目其实说的挺清楚了,走棋盘,走的时候路线不能越过对角线
//那么其实在对角线上面走和下面走是一样的,我现在计算下面,到时候乘以2即可
/*
用一个2维数组a[i][j]储存到达(i,j)处走法数,(i,j)表示棋盘点的位置,可以发现:
当i=j时,只能是从(i,j-1)走来,即a[i][j]=a[i][j-1];(没有越过对角线限制的话,这个要加两个,最后不用乘以2了)
当i!=j时,可以从(i-1,j)或(i,j-1)走来,所以a[i][j]=a[i-1][j]+a[i][j-1];
*/

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

const int myMAX = 36;

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

int n;
long long int a[36][36];
memset(a, 0, sizeof(a));

for (int i=1; i<myMAX; i++) {
a[i][1] = 1;
}

//注意下面a[i][j]是+
for (int i=1; i<myMAX; i++) {
for (int j=1; j<myMAX; j++) {
if (i==j)
a[i][j] += a[i][j-1];
else
a[i][j] += a[i-1][j] + a[i][j-1];
}
}

int index = 0;
while (scanf("%d", &n) && n != -1) {
printf("%d %d %lld\n", ++index, n, a[n][n]*2);
}

return 0;
}

2068 RPG的错排

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//与2048、2048有类似之处、全错排
//注意答对+另外全错排有特殊点,在全部答对时a[0] = 1

#include <stdio.h>

long long CMethod(int bottom, int top) {
long long sum = 1;

for (int i=0; i<top; i++) {
// sum *= (bottom-i) / (i+1);
//上面会先算除法而出错
sum = sum * (bottom-i) / (i+1);
}

return sum;
}

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

int n;
long long a[26];

//由于错排的也是递推算法,所以要先有初始值
//一个人不会错,为0,两个人能错1次
a[0] = 1; //特殊情况: a[0]=1是因为所有人都是对的,那么结果为C(n,1),否则为0了
a[1] = 0;
a[2] = 1;

for (int i=3; i<26; i++) {
a[i] = (i-1) * (a[i-1] + a[i-2]);
}

while (scanf("%d", &n) && n) {
long long sum = 0;
// //答对的一半或者以上, 一下答对的为i
// //答对的人可用组合方式选出,剩余的人要全错排
// //答对一半或以上有时奇数,有时偶数,不好弄
// //所以用答错的方便
// int m = n / 2;
// if (n % 2 == 1)
// m = n / 2 + 1;
// for (int i=m; i<=n; i++) {
// sum += CMethod(n, i) * a[n-i];
// }
//答错的人为i,从0开始
for (int i=0; i<=n/2; i++) {
sum += CMethod(n, n-i) * a[i];
}
printf("%lld\n", sum);
}


return 0;
}

2069 CoinChange

CoinChange
解析

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
//https://blog.csdn.net/chao1983210400/article/details/14047485
//我用了暴力求解
//不知道母函数是个啥情况,下面的例子是母函数所有有限硬币能列出的money
//https://blog.csdn.net/yu121380/article/details/79914529

#include <stdio.h>

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

int n;

while (scanf("%d", &n) != EOF) {
int sum = 0;
for (int i=n/50; i>=0; i--) {
for (int j=(n-i*50)/25; j>=0; j--) {
for (int k=(n-i*50 - j*25)/10; k>=0; k--) {
for (int l=(n-i*50 - j*25 - k*10)/5; l>=0; l--) {
// for (int m=(n-i*50 - j*25 - k*10 - l*5);m>=0; m++) {
//
// }
//Your program should be able to handle up to 100 coins
int a = n - i * 50 - j * 25 - k * 10 - l * 5;
if (a + i + j +k +l <= 100) {
sum++;
}
}
}
}
}

printf("%d\n", sum);
}

return 0;
}

2070 Fibbonacci Number

注意用long long

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

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

int n;
long long f[51];

f[0] = 0;
f[1] = 1;

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

while (scanf("%d", &n) && n != -1) {
printf("%lld\n", f[n]);
}

return 0;
}

2072 单词数

单词数

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
//char *strtok(char *str, const char *delim) 分解字符串 str 为一组字符串,delim 为分隔符。
//该函数返回被分解的第一个子字符串,如果没有可检索的字符串,则返回一个空指针。
/*int strcmp(const char *str1, const char *str2) 把 str1 所指向的字符串和 str2 所指向的字符串进行比较。
如果返回值小于 0,则表示 str1 小于 str2。
如果返回值大于 0,则表示 str1 大于 str2。
如果返回值等于 0,则表示 str1 等于 str2。
*/
//char *strcpy(char *dest, const char *src) 把 src 所指向的字符串复制到 dest。
//char *strstr(const char *haystack, const char *needle) 在字符串 haystack 中查找第一次出现字符串 needle 的位置,不包含终止符 '\0'。

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

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

char str[500000];//存放输入数据
char splitedStr[10000][50];//存放分割后的单词
int des[10000];//计算splitedStr中的单词不同的置一下1

//读取
while (gets(str) && str[0] != '#') {
int index = 0;
memset(des, 0, sizeof(des));

//分隔
/* 获取第一个子字符串 */
char *p = strtok(str, " ");
while (p != NULL) {
strcpy(splitedStr[index++], p);
/* 继续获取其他的子字符串 */
p = strtok(NULL, " ");
}

//比较
for (int i=0; i<index; i++) {
for (int j=i+1; j<index; j++) {
//若有一次相等
if (!strcmp(splitedStr[i], splitedStr[j])) {
des[i] = 1;

;
}
}
}

//计数
int count = 0;
for (int i=0; i<index; i++) {
if (!des[i]) count++;
}

printf("%d\n" , count) ;
}

return 0;
}

2073 无限的路

无限的路
解析

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
//两个都只要算从原点到该点的距离,然后相减即可
//然后规律在于x+y, 而不能单独看x或者y

#include <stdio.h>
#include <math.h>

double distanceFromOriginal(int x, int y) {
double sum = 0;
int n = x + y;
double s2 = sqrt(2);

for (int i=1; i<n; i++) {
sum += i * s2;
}

for (int i=1; i<=n; i++) {
sum += sqrt((i-1) * (i-1) + i * i);
}

//最后一段不完整的只要看x即可
sum += x * s2;

return sum;
}

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

int n, x1, y1, x2, y2;

scanf("%d", &n);
while (n--) {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

printf("%.3lf\n", fabs(distanceFromOriginal(x1, y1) - distanceFromOriginal(x2, y2)));
}

return 0;
}

2074 叠筐

叠筐

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
/*
1.四个角是空格
2.每一组示例输出之间有空行。
3.输入n=1的时候,按照1四个角是空格的处理,会输出空格,但应该输出第二个字符。
4.最外面一圈是中心符号还是外筐符号要注意
*/

#include <stdio.h>

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

int n, flag=0;
char out, in;

//有要读取c这种的一定要注意回车的问题,不过这里前面读取了个d,所以可能会把回车已经弄掉了
while (scanf("%d %c %c", &n, &in, &out) != EOF) {
//叠筐与叠筐之间应有一行间隔
//是之间有相隔,注意显示空行的格式,否则Presentation Error
if (flag) printf("\n");
else flag = 1;

if (n==1){
printf("%c\n", in);
continue;
} else if ((n+1)/2%2) {
char temp = in;
in = out;
out = temp;
}

for (int i=1; i<=(n+1)/2; i++) {
if (i==1) {
printf(" ");
for (int j=2; j<=n-1; j++) printf("%c", out);
printf(" \n");
} else {
for (int j=1; j<=i-1; j++) printf("%c", j % 2 ? out : in);
for (int j=1; j<=n-2*(i-1); j++) printf("%c", i % 2 ? out : in);
for (int j=i-1; j>=1; j--) printf("%c", j % 2 ? out : in);
printf("\n");
}
}
for (int i=(n+1)/2-1; i>=1; i--) {
if (i==1) {
printf(" ");
for (int j=2; j<=n-1; j++) printf("%c", out);
printf(" \n");
} else {
for (int j=1; j<=i-1; j++) printf("%c", j % 2 ? out : in);
for (int j=1; j<=n-2*(i-1); j++) printf("%c", i % 2 ? out : in);
for (int j=i-1; j>=1; j--) printf("%c", j % 2 ? out : in);
printf("\n");
}
}

}

return 0;
}

2076 夹角有多大(题目已修改,注意读题)

夹角有多大(题目已修改,注意读题)

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
/*
求分针与时针的夹角,先分别求时针与0(即12)的夹角、分针与0(即12)的夹角,
二者求得后再相减取绝对值,如果大于180,则再用360。
首先明确一下,一个小时时针转了30度;一分钟时针转动 0.5 度;一秒时针转动1/120度。
一分钟分针转动6度;一秒钟分针转动0.1度。
所以在h(h<12)时m分s秒时,时针与‘12’的夹角tan1=h*30+m*0.5+s*1/120.0;
分针与‘12’d的夹角 tan2= m*6.0+s*0.1;
*/

#include <stdio.h>
#include <math.h>

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

int T, h, m, s;

scanf("%d", &T);

while (T--) {
scanf("%d %d %d", &h, &m, &s);

double hourAngle = (h % 12) * 30 + m * 0.5 + s * 1 / 120.0;
double minuteAngle = m * 6 + s * 0.1;

double angle = fabs(hourAngle - minuteAngle) > 180 ? (360 - fabs(hourAngle - minuteAngle)) : fabs(hourAngle - minuteAngle);

//输出夹角的大小的整数部分
//因为是直接舍弃而不是四舍五入的
printf("%.0lf\n", angle-0.5);
}

return 0;
}

2077 汉诺塔IV

汉诺塔IV

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
/*
https://blog.csdn.net/huqiaolong/article/details/80546995
在普通汉诺塔中,关注整体的终止位置,n-1个移动到最右边,最大的移动到中间,n-1个再有最右边移动到最左边,
最大的移动到最右边,n-1个再有最左边移动到最右边。n-1个进行了三次初始到终止的移动,加两次最大的移动。
递推为a[i] = a[i-1]*3 + 2;

在这个最大的可放在最上面的汉诺塔中,就不能关注整体的终止位置了,而要关注一根杆到相邻杆。n-1从最左到中间,
再到最右,最大的从最左到中间,n-1再从最右回到中间。这样,n个完成移动到相邻杆。相邻杆移动递推a[i] = a[i-1]*3 + 1;
d从第二杆到第三杆也可以推得是a[i] = a[i-1]*3 + 1;
回到原始问题,n-1个移动到中间,最大的到中间再到最右边,n-1个从中间到最右边。答案即为a[i]*2 + 2;
*/
/*
https://www.cnblogs.com/gcczhongduan/p/4508705.html
在汉若塔3的基础上,改条件:同意最大的盘子放到最上面(仅仅同意最大的放在最上面)当然最后须要的结果还是盘子从小到大排在最右边。
A,B,C三个塔,方程:ans[n]=ab[n-1]+1+1+bc[n-1]. (ab表示a到b)
DP思路:先把n-1个搬到b,再用俩步般最大的到C,再把n-1个从B到C。这里又要求出ac[n]和bc[n]:求其递推方程:bc[n]=bc[n-1]+1+ac[n-1],
会发现bc[]方程和ab[n]一样的。所以总方程ans[n]=2*ab[n-1]+2.
*/

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

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

int n, m;
long long int a[21];

a[0] = 0;
a[1] = 1;//从第一杆到相邻杆第二杆只要一次
for (int i=2; i<21; i++) {
a[i] = 3 * a[i-1] + 1;
}

scanf("%d", &n);

while (n--) {
scanf("%d", &m);
printf("%lld\n", 2 * a[m-1] + 2);
}


return 0;
}

2078 复习时间

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
/*
这是一题求最大效率的问题,那么我们用贪心算法是很容易的,由题意我们知道每当他复习完一门课时我们需要找一个更简单课的来复习
,所以,我们根据贪心的规则来说我们只需要第一个就求出最大效率就行,如果我们第一个求出来的不是最大的效率,那么在复习后面课
时我们的效率将会不断递减,从而得出的效率就不是最高的效率了。
言外之意是只要找到s难度最小的一门课,每晚就复习这一门,就是最大的效率了
https://blog.csdn.net/a1036810809/article/details/69855677
*/

//https://blog.csdn.net/qq_44754132/article/details/104461279

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) {
return *(int *)a - *(int *)b;
}

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

int T, n, m, a[50];

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

for (int i=0; i<n; i++) {
scanf("%d", &a[i]);
}

qsort(a, n, sizeof(int), cmp);

printf("%d\n", (100-a[0]) * (100-a[0]));
}


return 0;
}

2079 选课时间(母函数、 动态规划多重背包、或暴力枚举)

母函数(对于初学者的最容易理解的)
母函数(Generating function)详解 — TankyWoo
母函数详解和史上最通用最高效的母函数模板

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
77
78
79
80
81
82
83
//[母函数(对于初学者的最容易理解的)](https://blog.csdn.net/yu121380/article/details/79914529)
//[母函数(Generating function)详解 --- TankyWoo](http://www.wutianqi.com/blog/596.html)
//[母函数详解和史上最通用最高效的母函数模板](https://blog.csdn.net/xiaofei_it/article/details/17042651)

/*
解题时,首先要写出表达式,通常是多项的乘积,每项由多个x^y组成。如(1+x+x^2)(1+x^4+x^8)(x^5+x^10+x^15)。
通用表达式为
(x^(v[0]*n1[0])+x^(v[0]*(n1[0]+1))+x^(v[0]*(n1[0]+2))+...+x^(v[0]*n2[0]))
(x^(v[1]*n1[1])+x^(v[1]*(n1[1]+1))+x^(v[1]*(n1[1]+2))+...+x^(v[1]*n2[1]))
...
(x^(v[K]*n1[K])+x^(v[K]*(n1[K]+1))+x^(v[K]*(n1[K]+2))+...+x^(v[K]*n2[K]))
K对应具体问题中物品的种类数。
v[i]表示该乘积表达式第i个因子的权重,对应于具体问题的每个物品的价值或者权重。
n1[i]表示该乘积表达式第i个因子的起始系数,对应于具体问题中的每个物品的最少个数,即最少要取多少个。
n2[i]表示该乘积表达式第i个因子的终止系数,对应于具体问题中的每个物品的最多个数,即最多要取多少个。
对于表达式(1+x+x^2)(x^8+x^10)(x^5+x^10+x^15+x^20),v[3]={1,2,5},n1[3]={0,4,1},n2[3]={2,5,4}。
解题的关键是要确定v、n1、n2数组的值。
通常n1都为0,但有时候不是这样。
n2有时候是无限大。
之后就实现表达式相乘,从第一个因子开始乘,直到最后一个为止。此处通常使用一个循环,循环变量为i。每次迭代的计算结果放在数组a中。计算结束后,a[i]表示权重i的组合数,对应具体问题的组合数。
循环内部是把每个因子的每个项和a中的每个项相乘,加到一个临时的数组b的对应位(这里有两层循环,加上最外层循环,总共有三层循环),之后就把b赋给a。
P是可能的最大指数。拿钞票组合这题来说,如果要求15元有多少组合,那么P就是15;如果问最小的不能拼出的数值,那么P就是所有钱加起来的和。P有时可以直接省略。
如果n2是无穷,那么第二层循环条件j<=n2[i]可以去掉。
*/

//C 库函数 void *memcpy(void *str1, const void *str2, size_t n) 从存储区 str2 复制 n 个字符到存储区 str1。

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

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

int T, n, m;
//a为计算结果,b为中间结果。
int a[100], b[100];

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

memset(a, 0, sizeof(a));
a[0] = 1;

//v为第i类学分,每类学分最多n2种,做少是0,所以不用n1了
int v[9], n2[9];
for (int i=1; i<=m; i++) {
scanf("%d %d", &v[i], &n2[i]);
}

//相乘
for (int i=1; i<=m; i++) { //m类学分,每一类多门n2
memset(b, 0, sizeof(b));
for (int j=0; j<=n2[i]&&j*v[i]<=80; j++) { //该一类同一学分的
//j*v[i]即比如v[i]g砝码n2[i]个,有x(v[i]*1)+x(v[i]*2)+x(v[i]*3)+...+x(v[i]*n2[i])
//这下面几句话就涉及到了多个多项式相承,要一个个多项式s相乘吧
for (int k=0; k+j*v[i]<=80; k++) {
b[k+j*v[i]] += a[k];
}
}
memcpy(a, b, sizeof(b));
}

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

//普通母函数模版
// //a为计算结果,b为中间结果。
// int a[MAX],b[MAX];
// //初始化
// memset(a,0,sizeof(a));
// a[0]=1;
// for (int i=1;i<=17;i++)//循环每个因子
// {
// memset(b,0,sizeof(b));
// for (int j=n1[i];j<=n2[i]&&j*v[i]<=P;j++)//循环每个因子的每一项
// for (int k=0;k+j*v[i]<=P;k++)//循环a的每个项
// b[k+j*v[i]]+=a[k];//把结果加到对应位
// memcpy(a,b,sizeof(b));//b赋值给a
// }

return 0;
}

2080 夹角有多大II

夹角有多大II

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
//余弦定理:cosA=(b^2+c^2-a^2)/2bc
//acos返回的参数为弧度,三角函数中所有参数貌似都为弧度?
/*
最近写的东西用到了数学库中的acos函数,但是代码在运行的时候有时候会出莫名其妙的错误,比如返回值是个特别大的数。
最后在debug 的时候发现acos返回的数据很奇怪,但是传入的参数明明没有问题,可以保证是(-1,1)。
回想起,double类型的末尾数据时不确定的,当double类型数据alpha = 1.0时其真实值可能是1.00001;这明明是很早就知道的,
但是在写代码的时候有时候却很容易忘记。所以在acos部分加入界限判别部分
*/

#include <stdio.h>
#include <math.h>

double distanceSquare(double x1, double y1, double x2, double y2) {
return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
}

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

int n;
double x1, y1, x2, y2;

scanf("%d", &n);
while (n--) {
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);

double a2 = distanceSquare(x1, y1, 0, 0);
double b2 = distanceSquare(x2, y2, 0, 0);
double c2 = distanceSquare(x1, y1, x2, y2);
double a = sqrt(a2);
double b = sqrt(b2);

double angle = acos((a2+b2-c2)/2/a/b) /3.1415926 * 180;

printf("%.2lf\n", angle);
}

return 0;
}

Author: Jcwang

Permalink: http://example.com/2020/03/22/HDU-Page11(2067%EF%BD%9E2080)%20/