HDU-Page11(2081~2099)

2082 找单词(母函数问题)

母函数(对于初学者的最容易理解的)
母函数(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
84
85
//[母函数(对于初学者的最容易理解的)](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;
//a为计算结果,b为中间结果。
int a[100], b[100];

scanf("%d", &T);
while (T--) {
memset(a, 0, sizeof(a));
a[0] = 1;

//v为字母,每个字母最多n2个,最少是0,所以不用n1了
int v[27], n2[27];
for (int i=1; i<=26; i++) {
v[i] = i;
scanf("%d", &n2[i]);
}

//相乘
for (int i=1; i<=26; i++) { //26个字母,每个字母最多n2[i]种
memset(b, 0, sizeof(b));
for (int j=0; j<=n2[i]&&j*v[i]<=51; 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]<=51; k++) {
b[k+j*v[i]] += a[k];
}
}
memcpy(a, b, sizeof(b));
}

int sum = 0;
for (int i=1; i<=50; i++) {
sum += a[i];
}
printf("%d\n", sum);
}

// //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;
}

2083 简易版之最短距离

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
//最短距离的问题,排序后取中位数就可以了
//而不是取平均数🙈

#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, a[505];

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

qsort(a, n, sizeof(int), cmp);
int average = a[n/2];

int totalTime = 0;
for (int i=0; i<n; i++) {
totalTime += abs(a[i] - average);
}
printf("%d\n", totalTime);
}

return 0;
}

2084 数塔

数塔
解析

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

int myMAX(int a, int b) {
return a > b ? a : b;
}

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

int T, n, dp[101][101];

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

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

for (int i=n-1; i>=1; i--) {
for (int j=1; j<=i; j++) {
dp[i][j] += myMAX(dp[i+1][j], dp[i+1][j+1]);
}
}
printf("%d\n", dp[1][1]);
}

return 0;
}

2085 核反应堆

核反应堆

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

long long* bang(long long num, int isHigh) {
long long *nums;
nums = (long long *)malloc(sizeof(long long)*2);
nums[0] = 1;
nums[1] = 0;

if (isHigh) {
nums[0] = num * 3;
nums[1] = num;
} else {
nums[0] = num * 2;
nums[1] = num;
}

return nums;
}

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

int n;

while (scanf("%d", &n) && n != -1) {
long long *mynum;
mynum = (long long *)malloc(sizeof(long long)*2);
mynum[0] = 1;
mynum[1] = 0;

while (n--) {
long long *nums1 = bang(mynum[0], 1);
long long *nums2 = bang(mynum[1], 0);
mynum[0] = nums1[0] + nums2[0];
mynum[1] = nums1[1] + nums2[1];
}
printf("%lld, %lld\n", mynum[0], mynum[1]);
}

return 0;
}

2086 A1 = ?

A1 = ?
解析

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
/*
https://blog.csdn.net/m0_37433751/article/details/55550031
因为 Ai = (Ai-1 + Ai+1) / 2 - Ci

A1 = (A0 + A2) / 2 - C1;
A2 = (A1 + A3) / 2 - C2;
=> A1 + A2 = (A0 + A2 + A1 + A3) / 2 - (C1 + C2);
=> A1 + A2 = (A0 + A3) - 2(C1 + C2);
同理: A1 + A1 = (A0 + A2) - 2C1;
A1 + A2 = (A0 + A3) - 2(C1 + C2 + C3);
A1 + A3 = (A0 + A4) - 2(C1 + C2 + C3 + C4);
...
A1 + An = (A0 + An+1) - 2(C1 + C2 + ... + Cn);
对上式求和:
nA1 + A1 + (A2 + A3 + ... + An) = nA0 + (A2 + A3 + ... + An) + An+1 - 2(nC1 + (n-1)C2 + ... + 2Cn-1 + Cn);
=> (n+1)A1 = nA0 + An+1 - 2(nC1 + (n-1)C2 + ... + 2Cn-1 + Cn);
综上: A1 = [nA0 + An+1 - 2(nC1 + (n-1)C2 + ... + 2Cn-1 + Cn)] / (n + 1)。
*/

#include <stdio.h>

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

int n;
double a[4000], c[4000];

while (scanf("%d", &n) != EOF) {
double sum = 0.0;
scanf("%lf %lf", &a[0], &a[n+1]);
sum += n * a[0] + a[n+1];

for (int i=1; i<=n; i++) {
scanf("%lf", &c[i]);

sum -= 2 * (n - i + 1) * c[i];
}

printf("%.2lf\n", sum * 1.0 / (n + 1));
}



return 0;
}

2087 剪花布条

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

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

char str[1005], *p;
char *sourceStr;

sourceStr = (char *)malloc(sizeof(char) * 1005);

while (scanf("%s", sourceStr) && sourceStr[0] != '#') {
scanf("%s", str);

int sum = 0, strLength = (int)strlen(str);

while ((p = strstr(sourceStr, str))) {
sum++;
sourceStr += (p-sourceStr) + strLength;
}

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

return 0;
}

2088 Box of Bricks

Box of Bricks

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

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

int n, heights[105], flag = 0;

while (scanf("%d", &n) && n) {
if (flag)
printf("\n");
else
flag = 1;
int sum = 0;
for (int i=1; i<=n; i++) {
scanf("%d", &heights[i]);
sum += heights[i];
}

int average = sum / n;
sum = 0;
for (int i=1; i<=n; i++) {
if (heights[i] > average)
sum += heights[i] - average;
}

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

return 0;
}

2089 不要62

不要62
C语言字符串,字符转数字,数字转字符

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
//C语言字符串,字符转数字,数字转字符
//https://blog.csdn.net/wuruixn/article/details/8296300

//这个超时
//#include <stdio.h>
//#include <string.h>
//
//int main(int argc, const char * argv[]) {
// // insert code here...
//
// int n, m;
// char s[100005];
//
// while (scanf("%d %d", &n, &m) && (n != 0 || m != 0)) {
// int sum = m - n + 1;
// for (int i=n; i<=m; i++) {
// sprintf(s, "%d", i);
// if (strstr(s, "62") || strstr(s, "4"))
// sum--;
// }
//
// printf("%d\n", sum);
// }
//
// return 0;
//}

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

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

int n, m, result[1000005];
char s[1000005];

int sum = 0;
for (int i=1; i<1000005; i++) {
sprintf(s, "%d", i);
if (strstr(s, "62") || strstr(s, "4"))
sum++;
result[i] = sum;
}

while (scanf("%d %d", &n, &m) && (n != 0 || m != 0)) {

printf("%d\n", m - n + 1 - (result[m] - result[n-1]));
}

return 0;
}

2090 算菜价

算菜价

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

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

char s[100];
double num, price;

double sum = 0;
while (scanf("%s %lf %lf", s, &num, &price) != EOF) {
sum += num * price;
}


printf("%.1lf\n", sum);

return 0;
}

2091 空心三角形

空心三角形

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

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

char c;
int n, flag = 0;;

while (scanf("%c", &c) && c != '@') {
scanf("%d", &n);
getchar();

if (flag)
printf("\n");
else
flag = 1;

for (int i=1; i<=n; i++) {
for (int j=n-i-1; j>=0; j--)
printf(" ");
printf("%c", c);
if (i == n)
for (int j=2*(n-1)-1; j>=0; j--)
printf("%c", c);
else if (i != 1) {
int num = 2 * (i - 2) + 1;
while (num--) {
printf(" ");
}
printf("%c", c);
}
printf("\n");
}
}

return 0;
}

2092 整数解

整数解

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
//韦达定理 x^2 + -bx + c (a = 1)
//则 -b = n, c = m
//x1, x2 = (-b +- sqrt(b^2-4c)) / 2

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

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

int n, m;

while (scanf("%d %d", &n, &m) && (n != 0 || m != 0)) {
int sum = sqrt(n * n - 4 * m);
if (sum * sum != n * n - 4 * m) {
printf("No\n");
continue;
}
sum += n;

if (sum % 2 == 0)
printf("Yes\n");
else
printf("No\n");
}

return 0;
}

2093 考试排名

考试排名

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

typedef struct Person {
char name[20];
int correctNum;
int totalTime;
}Person;

int cmp(const void* a, const void* b) {
Person aa = *(Person *)a;
Person 百度翻译 = *(Person *)b;

if (aa.correctNum != 百度翻译.correctNum)
return 百度翻译.correctNum - aa.correctNum;
else if (aa.totalTime != 百度翻译.totalTime)
return aa.totalTime - 百度翻译.totalTime;
else
return strcmp(aa.name, 百度翻译.name);
}

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

Person persons[1000];
char input[20];
int n, m;

scanf("%d %d", &n, &m);
int i = 0;
while (scanf("%s", persons[i].name) != EOF) {
i++;
//名字复制
persons[i-1].correctNum = 0;
persons[i-1].totalTime = 0;

//此处一开始写成了i<=n, 退不出循环了
for (int j=1; j<=n; j++) {
scanf("%s", input);

//若没有做出,不用加时间
if (input[0] == '-' || input[0] == '0')
continue;

int length = (int)strlen(input), startKuoHaoIndex = length;

//找到该AC题的做错的次数
int wrongTimes = 0;
if (input[length-1] == ')') {
//找到做括号起始位置
startKuoHaoIndex--;
while (input[startKuoHaoIndex] != '(') {
startKuoHaoIndex--;
}
for (int k = startKuoHaoIndex+1; k<=length-2; k++) {
wrongTimes = wrongTimes * 10 + (input[k]-48);
}
}

//得到正确题目的正确做对的时间
int correctTime = 0;
for (int k = 0; k<=startKuoHaoIndex-1; k++) {
correctTime = correctTime * 10 + (input[k]-48);
}

persons[i-1].correctNum++;
persons[i-1].totalTime += correctTime + wrongTimes * m;
}
}

//因为排序是从第0个开始的, 我要是从1号开始存就会出现问题
qsort(persons, i, sizeof(Person), cmp);

//注意格式
//%10s和%-10s区别是一个是左边空格,一个是右边空格
for (int j = 0; j<i; j++) {
printf("%-10s %2d %4d\n", persons[j].name, persons[j].correctNum, persons[j].totalTime);
}

return 0;
}

2094 产生冠军

产生冠军
解析

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
/*
https://blog.csdn.net/weixin_34418883/article/details/93739779?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
拓扑排序+Hash
输入A 战胜 B时,就让B指向A,最后,指向空的就说明没有人战胜过他。如果这样的人只存在一个,那他就是冠军了。
不过其实也没有真的指向,而是给输的都加了个索引,正好只有一个没有索引时有冠军 (注意任意两个人只能比赛一场)
*/

/*
https://blog.csdn.net/qq_42391248/article/details/81234805?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
这一题很水,说是用到拓扑排序,其实根本不用,构建出一个图,只要记录所有点的入度,
如果只有一个入度为0,那么他就是冠军。不过构建图的时候有一个技巧,如果单是用字符
串去处理构建图,过程会有点繁琐,如果用STL中map就简单很多了。用map好处在于自带
查找功能,能够查找某个字符串是否在map中,而且查找的复杂度是很低的。
*/

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

//***把名字变成数字***
unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;
while (*str)
hash = (*str++) + (hash << 6) + (hash << 16) - hash;

return (hash & 0x7FFFFFFF);
}

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

int v[10001]; //标记该人员是否已经存在
int s[10001]; //标记该人员是否输过
int hashName[1001]; //记录人员名字
char name[20];

int n, t;

while (scanf("%d", &n) && n != 0) {
t = 0;
memset(v, 0, sizeof(v));
memset(s, 0, sizeof(s));

while (n--) {
scanf("%s", name);
int tempHashName = SDBMHash(name) % 10000;

//若该人员还没有j出现过,加入
if (!v[tempHashName]) {
v[tempHashName]++;
hashName[t++] = tempHashName;
}

scanf("%s", name);
tempHashName = SDBMHash(name) % 10000;
if (!v[tempHashName]) {
v[tempHashName]++;
hashName[t++] = tempHashName;
}
//表示这个人输了
s[tempHashName]++;
}

//记录多少人没输过
int tot = 0;
for (int i=0; i<t; i++) {
if (s[hashName[i]] == 0) {
tot++;
if (tot >= 2)

;
}
}

printf("%s\n", tot == 1 ? "Yes" : "No");
}

return 0;
}

2095 find your present (2)

find your present (2)
解析

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
//用异或即可解决, 不同为1,相同为0
//因为其他的数字都是偶数,所以以其运算后都会为0

//https://blog.csdn.net/qq_38238041/article/details/78536304?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

#include <stdio.h>

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

int n, m, ans;

while (scanf("%d", &n) && n != 0) {
ans = 0;

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

ans ^= m;
}

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

return 0;
}

2097 Sky数

Sky数

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

int radixSum(int n, int radix) {
int sum = 0;

while (n) {
sum += n % radix;
n /= radix;
}

return sum;
}

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

int n;

while (scanf("%d", &n) && n) {
int decimalSum = radixSum(n, 10);
int hexaDecimalSum = radixSum(n, 16);
int twelveSum = radixSum(n, 12);

if (decimalSum == hexaDecimalSum && decimalSum == twelveSum)
printf("%d is a Sky Number.\n", n);
else
printf("%d is not a Sky Number.\n", n);
}

return 0;
}

2098 分拆素数和

分拆素数和

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
//我的方法比较暴力,找出素数,枚举实现
//0和1不是质数
//题目说把一个偶数拆成两个不同素数的和, 拆成两个,所以枚举比较简单

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

int isSuShu(int n) {
int i;

for (i=2; i<=sqrt(n); i++) {
if (n % i == 0) {
i = 0;

;
}
}

if (i)
return 1;
else
return 0;
}

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

int n, nums[10001];

// int index = 0;
// for (int i=2; i<10001; i++) {
// if (isSuShu(i))
// nums[index++] = i;
// }

while (scanf("%d", &n) && n) {
int index = 0, sum = 0;
for (int i=2; i<10001; i++) {
if (isSuShu(i))
nums[index++] = i;
}

for (int i=0; i<index; i++) {
//比如3+13y和13+#是同一个,所以j从i+1开始
for (int j=i+1; j<index; j++) {
if (nums[i] + nums[j] == n)
sum++;
}
}

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

return 0;
}

2099 整除的尾数

整除的尾数

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
//我的方法比较暴力,找出素数,枚举实现
//0和1不是质数
//题目说把一个偶数拆成两个不同素数的和, 拆成两个,所以枚举比较简单

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

int isSuShu(int n) {
int i;

for (i=2; i<=sqrt(n); i++) {
if (n % i == 0) {
i = 0;

;
}
}

if (i)
return 1;
else
return 0;
}

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

int a, b;

while (scanf("%d %d", &a, &b) && (a != 0 || b != 0)) {
a = a * 100;

int i;
for (i=0; i<100; i++) {
if ((a + i) % b == 0) {

;
}
}

//注意题目中说的格式
printf("%02d", i);
while (i + b < 100) {
printf(" %02d", i + b);
i = i + b;
}
printf("\n");
}

return 0;
}

Author: Jcwang

Permalink: http://example.com/2020/03/25/HDU-Page11(2081%EF%BD%9E2099)/