杭电 OJ2070-2079

写在前面

本文记录了刷杭电 OJ2070-2079 的过程和一些想法，代码仅供参考！

2070 Fibbonacci Number

Problem Description

Your objective for this question is to develop a program which will generate a fibbonacci number.The fibbonacci function is defined as such: f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) Your program should be able to handle values of n in the range 0 to 50.

Input

Each test case consists of oneinteger n in a single line where 0≤n≤50.The input is terminated by -1.

Output

Print out the answer in a single line for each test case.

Sample Input

3
4
5
-1

Sample Output

2
3
5

解题思路

题目大意：计算 fibbonacci 数列

直接按公式计算

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main() {
    int n;
    __int64 f[51] = {0, 1};
    for (int i = 2; i < 51; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    while (cin >> n && n != -1) {
        cout << f[n] << endl;
    }
    return 0;
}

2071 Max Num

Problem Description

There are some students in a class, Can you help teacher find the highest student .

Input

There are some cases. The first line contains an integer t, indicate the cases;Each case have an integer n ( 1 ≤ n ≤ 100 ) , followed n students’ height.

Output

For each case output the highest height, the height to two decimal plases;

Sample Input

2
3 170.00 165.00 180.00
4 165.00 182.00 172.00 160.00

Sample Output

180.00
182.00

解题思路

题目大意：找最大值

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main() {
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        double height, max = 0;
        for (int i = 0; i < n; i++) {
            cin >> height;
            if (height > max) max = height;
        }
        printf("%.2f\n", max);
    }
    return 0;
}

2072 单词数

Problem Description

lily 的好朋友 xiaoou333 最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助 xiaoou333 解决这个问题。

Input

有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到 #时表示输入结束。

Output

每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。

Sample Input

you are my friend
#

Sample Output

4

解题思路

stringstream 分割字符串，再使用 set 容器计数

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set>
#include <sstream>
#include <string>
using namespace std;
int main() {
    string s;
    set<string> st;
    while (getline(cin, s)) {
        if (s == "#") break;
        stringstream ss(s);
        string c;
        while (ss >> c) st.insert(c);
        cout << st.size() << endl;
        st.clear();
    }
    return 0;
}

2073 无限的路

Problem Description

甜甜从小就喜欢画图画，最近他买了一支智能画笔，由于刚刚接触，所以甜甜只会用它来画直线，于是他就在平面直角坐标系中画出如右的图形：
甜甜的好朋友蜜蜜发现上面的图还是有点规则的，于是他问甜甜：在你画的图中，我给你两个点，请你算一算连接两点的折线长度（即沿折线走的路线长度）吧。

Input

第一个数是正整数 N（≤100）。代表数据的组数。每组数据由四个非负整数组成 x1，y1，x2，y2；所有的数都不会大于 100。

Output

对于每组数据，输出两点(x1,y1),(x2,y2)之间的折线距离。注意输出结果精确到小数点后 3 位。

Sample Input

5
0 0 0 1
0 0 1 0
2 3 3 1
99 99 9 9
5 5 5 5

Sample Output

1.000
2.414
10.646
54985.047
0.000

解题思路

点（0，i）到原点距离 f（i）= f（i - 1）+ m + n ，f(1) = 1
点（x，y）到原点的距离公式为 d = f（x + y）+ x × sqrt（2.0）

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cmath>
#include <iostream>
using namespace std;
double f[210] = {0, 1};
void dis() {
    for (int i = 2; i < 201; i++) {
        double m = (double)sqrt(2 * (i - 1) * (i - 1));
        double n = (double)sqrt(i * i + (i - 1) * (i - 1));
        f[i] = f[i - 1] + m + n;
    }
}
int main() {
    int x1, y1, x2, y2, n;
    double sum1, sum2;
    dis();
    cin >> n;
    while (n--) {
        cin >> x1 >> y1 >> x2 >> y2;
        sum1 = f[x1 + y1] + x1 * sqrt(2.0);
        sum2 = f[x2 + y2] + x2 * sqrt(2.0);
        printf("%.3f\n", fabs(sum1 - sum2));
    }
    return 0;
}

2074 叠筐

Problem Description

需要的时候，就把一个个大小差一圈的筐叠上去，使得从上往下看时，边筐花色交错。这个工作现在要让计算机来完成，得看你的了。

Input

输入是一个个的三元组，分别是，外筐尺寸 n（n 为满足 0<n<80 的奇整数），中心花色字符，外筐花色字符，后二者都为 ASCII 可见字符；

Output

输出叠在一起的筐图案，中心花色与外筐花色字符从内层起交错相叠，多筐相叠时，最外筐的角总是被打磨掉。叠筐与叠筐之间应有一行间隔。

Sample Input

11 B A
5 @ W

Sample Output

 AAAAAAAAA
ABBBBBBBBBA
ABAAAAAAABA
ABABBBBBABA
ABABAAABABA
ABABABABABA
ABABAAABABA
ABABBBBBABA
ABAAAAAAABA
ABBBBBBBBBA
 AAAAAAAAA

 @@@
@WWW@
@W@W@
@WWW@
 @@@

解题思路

参考源码

1

2075 A|B?

Problem Description

正整数 A 是否能被正整数 B 整除，不知道为什么 xhd 会研究这个问题，来帮帮他吧。

Input

输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据有两个正整数 A 和 B(A,B<10^9)。

Output

对于每组输入数据，输出"YES"表示可以被整除，"NO"表示不能被整除。

Sample Input

2
4 2
5 3

Sample Output

YES
NO

解题思路

简单题，整除

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    while (n--) {
        cin >> a >> b;
        if (a % b == 0)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

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

Problem Description

时间过的好快，一个学期就这么的过去了，xhd 在傻傻的看着表，出于对数据的渴望，突然他想知道这个表的时针和分针的夹角是多少。现在 xhd 知道的只有时间，请你帮他算出这个夹角。注：夹角的范围[0，180]，时针和分针的转动是连续而不是离散的。

Input

输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据有三个整数 h(0 <= h < 24)，m(0 <= m < 60)，s(0 <= s < 60)分别表示时、分、秒。

Output

对于每组输入数据，输出夹角的大小的整数部分。

Sample Input

2
8 3 17
5 13 30

Sample Output

138
75

解题思路

时针走 30°/小时，分针走 6°/分钟，然后分别计算时针和分针的角度即可

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n;
    double h, m, s, harg, marg, arg;
    cin >> n;
    while (n--) {
        cin >> h >> m >> s;
        if (h > 12) h = h - 12;
        harg = 30 * h + m / 2 + s / 120;  //时针角度
        marg = 6 * m + s / 10;            //分针角度
        arg = fabs(harg - marg);
        if (arg > 180) arg = 360 - arg;
        printf("%d\n", (int)arg);
    }
    return 0;
}

2077 汉诺塔 IV

Problem Description

还记得汉诺塔 III 吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd 在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。

Input

输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据有一个正整数 n(1 <= n <= 20)，表示有 n 个盘子。

Output

对于每组输入数据，最少需要的摆放次数。

Sample Input

2
1
10

Sample Output

2
19684

解题思路

对于前 n-1 个的移动，2064 和一样，但是将 n-1 个移动只到中间，最大从最左到中间到最右，n-1 移动到最右即可
相邻杆移动递推 f [i] = f [i-1] × 3 + 1，f(1) = 1（前 n-2 个与 2064 一样，第 n-1 个移动到中间）

对于这个规则来说，搬 n 个盘就需要 f(n) = 2 × f(n-1) + 2

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main() {
    int n, num, s, f[21] = {0};
    f[1] = 1;
    for (int i = 2; i < 21; i++) {
        f[i] = 3 * f[i - 1] + 1;
    }
    cin >> n;
    while (n--) {
        cin >> num;
        s = 2 * f[num - 1] + 2;
        if (num == 1)
            cout << "2" << endl;
        else
            cout << s << endl;
    }
    return 0;
}

2078 复习时间

Problem Description

为了能过个好年，xhd 开始复习了，于是每天晚上背着书往教室跑。xhd 复习有个习惯，在复习完一门课后，他总是挑一门更简单的课进行复习，而他复习这门课的效率为两门课的难度差的平方,而复习第一门课的效率为 100 和这门课的难度差的平方。xhd 这学期选了 n 门课，但是一晚上他最多只能复习 m 门课，请问他一晚上复习的最高效率值是多少？

Input

输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据的第一行是两个整数 n(1 <= n <= 40)，m(1 <= m <= n)。接着有 n 行，每行有一个正整数 a(1 <= a <= 100)，表示这门课的难度值。

Output

对于每组输入数据，输出一个整数，表示最高效率值。

Sample Input

2
2 2
52
25
12 5
89
64
6
43
56
72
92
23
20
22
37
31

Sample Output

5625
8836

解题思路

如果前一门复习的课程的难度为 m，后一门为 n。那他复习后一门的效率就为(m-n)×(m-n)，m 最大值为初始状态 100，那么选最简单的一门课效率最高

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main() {
    int t, n, m, a;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        m = 100;
        for (int i = 0; i < n; i++) {
            cin >> a;
            if (m > a) m = a;
        }
        cout << (100 - m) * (100 - m) << endl;
    }
    return 0;
}

2079 选课时间(题目已修改,注意读题)

Problem Description

又到了选课的时间了，xhd 看着选课表发呆，为了想让下一学期好过点，他想知道学 n 个学分共有多少组合。你来帮帮他吧。（xhd 认为一样学分的课没区别）

Input

输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据的第一行是两个整数 n(1 <= n <= 40)，k(1 <= k <= 8)。接着有 k 行，每行有两个整数 a(1 <= a <= 8),b(1 <= b <= 10)，表示学分为 a 的课有 b 门。

Output

对于每组输入数据，输出一个整数，表示学 n 个学分的组合数。

Sample Input

2
2 2
1 2
2 1
40 8
1 1
2 2
3 2
4 2
5 8
6 9
7 6
8 8

Sample Output

2
445

解题思路

暴力破解法，母函数法

参考源码

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
//方法一：暴力破解
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int k, n, c[9], t[9]; //c[i]表示选择学分为i的课程数量
    int a, b;
    int count,total;
    cin >> k;
    while (k--) {
        cin >> total >> n;
        count = 0;
        memset(t, 0, sizeof(t));
        for (int i = 0; i < n; i++) {
            cin >> a >> b;
            t[a] = b;
        }
        for (c[8] = 0; c[8] <= t[8] && c[8] * 8 <= total; c[8]++)
            for (c[7] = 0; c[7] <= t[7] && c[8] * 8 + c[7] * 7 <= total; c[7]++)
                for (c[6] = 0; c[6] <= t[6] && c[8] * 8 + c[7] * 7 + c[6] * 6 <= total; c[6]++)
                    for (c[5] = 0; c[5] <= t[5] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 <= total; c[5]++)
                        for (c[4] = 0; c[4] <= t[4] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 <= total; c[4]++)
                            for (c[3] = 0; c[3] <= t[3] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 <= total; c[3]++)
                                for (c[2] = 0; c[2] <= t[2] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 + c[2] * 2 <= total; c[2]++) {
                                    c[1] = total - (c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 + c[2] * 2);
                                    if (c[1] >= 0 && c[1] <= t[1]) count++;
                                }
        cout << count << endl;
    }
    return 0;
}

// 方法二：母函数
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int ans[1000], temp[1000];
struct course {
    int s, num;
} cou[10];
bool cmp(course a, course b) { return a.s < b.s; }
int main() {
    int t, n, k;
    cin >> t;
    while (t--) {
        memset(cou, 0, sizeof(cou));
        cin >> n >> k;
        for (int i = 0; i < k; i++) {
            cin >> cou[i].s >> cou[i].num;
        }
        sort(cou, cou + k, cmp);
        memset(ans, 0, sizeof(ans));
        memset(temp, 0, sizeof(temp));
        for (int i = 0; i <= n && i <= cou[0].s * cou[0].num; i += cou[0].s) {
            ans[i] = 1;  //初始化第一个多项式
        }
        for (int i = 1; i < k; i++) {
            for (int j = 0; j <= n; j++)
                for (int p = 0; j + p <= n && p <= cou[i].s * cou[i].num; p += cou[i].s)
                    temp[j + p] += ans[j];
            for (int j = 0; j <= n; j++) {  // 将临时的结果覆盖当前结果，同时把临时结果置零
                ans[j] = temp[j];
                temp[j] = 0;
            }
        }
        cout << ans[n] << endl;
    }
    return 0;
}

相关内容