杭电 OJ2080-2089

写在前面

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

2080 夹角有多大 II

Problem Description

这次 xhd 面临的问题是这样的：在一个平面内有两个点，求两个点分别和原点的连线的夹角的大小。
注：夹角的范围[0，180]，两个点不会在圆心出现。

Input

输入数据的第一行是一个数据 T，表示有 T 组数据。
每组数据有四个实数 x1,y1,x2,y2 分别表示两个点的坐标,这些实数的范围是[-10000,10000]。

Output

对于每组输入数据，输出夹角的大小精确到小数点后两位。

Sample Input

2
1 1 2 2
1 1 1 0

Sample Output

0.00
45.00

解题思路

向量点积：a・b=|a||b|cosα，使用反函数求出来的为弧度，还要转化为度数

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cmath>
#include <iostream>
#define PI 3.1415926
using namespace std;
int main() {
    double t, x1, y1, x2, y2;
    cin >> t;
    while (t--) {
        cin >> x1 >> y1 >> x2 >> y2;
        double ans = (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) * sqrt(x2 * x2 + y2 * y2));
        printf("%.2f\n", acos(ans) * 180 / PI);
    }
    return 0;
}

2081 手机短号

Problem Description

大家都知道，手机号是一个 11 位长的数字串，同时，作为学生，还可以申请加入校园网，如果加入成功，你将另外拥有一个短号。假设所有的短号都是是 6+手机号的后 5 位，比如号码为 13512345678 的手机，对应的短号就是 645678。现在，如果给你一个 11 位长的手机号码，你能找出对应的短号吗？

Input

输入数据的第一行是一个 N(N <= 200)，表示有 N 个数据，接下来的 N 行每一行为一个 11 位的手机号码。

Output

输入数据的第一行是一个 N(N <= 200)，表示有 N 个数据，接下来的 N 行每一行为一个 11 位的手机号码。

Sample Input

2
13512345678
13787654321

Sample Output

645678
654321

解题思路

输出 6，再提取手机号后 5 位即可

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main() {
    int n;
    char c[12];
    cin >> n;
    getchar();
    while (gets(c)) {
        cout << "6";
        for (int i = 6; i < 11; i++) {
            cout << c[i];
        }
        cout << endl;
    }
    return 0;
}

2082 找单词

Problem Description

假设有 x1 个字母 A， x2 个字母 B,… x26 个字母 Z，同时假设字母 A 的价值为 1，字母 B 的价值为 2,…字母 Z 的价值为 26。那么，对于给定的字母，可以找到多少价值<=50 的单词呢？单词的价值就是组成一个单词的所有字母的价值之和，比如，单词 ACM 的价值是 1+3+14=18，单词 HDU 的价值是 8+4+21=33。(组成的单词与排列顺序无关，比如 ACM 与 CMA 认为是同一个单词）。

Input

输入首先是一个整数 N，代表测试实例的个数。
然后包括 N 行数据，每行包括 26 个<=20 的整数 x1,x2,…x26.

Output

对于每个测试实例，请输出能找到的总价值<=50 的单词数,每个实例的输出占一行。

Sample Input

2
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9

Sample Output

7
379297

解题思路

母函数问题

参考源码

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 <cstring>
#include <iostream>
using namespace std;
int main() {
    int n, num[27];
    int ans[51], temp[51];
    cin >> n;
    while (n--) {
        memset(ans, 0, sizeof(ans));
        memset(temp, 0, sizeof(temp));
        for (int i = 1; i <= 26; i++) cin >> num[i];  //字母数量
        for (int i = 0; i <= 50 && i <= num[1]; i++) {
            ans[i] = 1;  //初始化第一个多项式(A的多项式)
        }
        for (int i = 2; i <= 26; i++) {  //从第二个字母开始，遍历每个字母的多项式
            for (int j = 0; j <= 50; j++)  // 遍历当前结果多项式的每一项（当前结果的第j项）
                for (int k = 0; k + j <= 50 && k <= num[i] * i; k += i)  // 遍历第i个多项式的每一项
                    temp[j + k] += ans[j];                               //幂运算
            for (int j = 0; j <= 50; j++) {  // 将临时的结果覆盖当前结果，同时把临时结果置零
                ans[j] = temp[j];
                temp[j] = 0;
            }
        }
        int sum = 0;
        for (int i = 1; i <= 50; i++) {  //累加
            sum += ans[i];
        }
        cout << sum << endl;
    }
    return 0;
}

2083 简易版之最短距离

Problem Description

寒假的时候，ACBOY 要去拜访很多朋友，恰巧他所有朋友的家都处在坐标平面的 X 轴上。ACBOY 可以任意选择一个朋友的家开始访问，但是每次访问后他都必须回到出发点，然后才能去访问下一个朋友。比如有 4 个朋友，对应的 X 轴坐标分别为 1， 2， 3， 4。当 ACBOY 选择坐标为 2 的点做为出发点时，则他最终需要的时间为 |1-2|+|2-2|+|3-2|+|4-2| = 4。现在给出Ｎ个朋友的坐标，那么 ACBOY 应该怎么走才会花费时间最少呢？

Input

输入首先是一个正整数 M，表示 M 个测试实例。每个实例的输入有 2 行，首先是一个正整数 N（N <=500)，
表示有 N 个朋友，下一行是 N 个正整数，表示具体的坐标(所有数据均<=10000).

Output

对于每一个测试实例，请输出访问完所有朋友所花的最少时间，每个实例的输出占一行。

Sample Input

2
2
2 4
3
2 4 6

Sample Output

2
4

解题思路

从 n/2 开始最短，当然首先要排下序

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int m, n, t, num[501];
    cin >> m;
    while (m--) {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> num[i];
        sort(num, num + n);
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += abs(num[j] - num[n / 2]);
        }
        cout << sum << endl;
    }
    return 0;
}

2084 数塔

Problem Description

在讲述 DP 算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？已经告诉你了，这是个 DP 的题目，你能 AC 吗?

Input

输入数据首先包括一个整数 C,表示测试实例的个数，每个测试实例的第一行是一个整数 N(1 <= N <= 100)，
表示数塔的高度，接下来用 N 行数字表示数塔，其中第 i 行有个 i 个整数，且所有的整数均在区间[0,99]内。

Output

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

Sample Input

1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30

解题思路

DP 经典问题
状态转移方程 dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j]

参考源码

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
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int c, n, num[101][101], dp[101][101];
    cin >> c;
    while (c--) {
        memset(num, 0, sizeof(num));
        memset(dp, 0, sizeof(dp));
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                cin >> num[i][j];
            }
        }
        for (int i = 1; i <= n; i++) {  //边界
            dp[n][i] = num[n][i];
        }
        for (int i = n - 1; i >= 1; i--) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + num[i][j];
            }
        }
        cout << dp[1][1] << endl;
    }
    return 0;
}

2085 核反应堆

Problem Description

某核反应堆有两类事件发生：
高能质点碰击核子时，质点被吸收，放出 3 个高能质点和 1 个低能质点；
低能质点碰击核子时，质点被吸收，放出 2 个高能质点和 1 个低能质点。
假定开始的时候（0 微秒）只有一个高能质点射入核反应堆，每一微秒引起一个事件发生
(对于一个事件，当前存在的所有质点都会撞击核子)，试确定 n 微秒时高能质点和低能质点的数目。

Input

输入含有一些整数 n(0≤n≤33)，以微秒为单位，若 n 为-1 表示处理结束。

Output

分别输出 n 微秒时刻高能质点和低能质点的数量，高能质点与低能质点数量之间以逗号空格分隔。每个输出占一行。

Sample Input

5 2
-1

Sample Output

571, 209
11, 4
提示可以使用 long long int 对付 GNU C++，使用__int64 对付 VC6

解题思路

分析高能和低能的来源，即可写出表达式
g[n] = 3 _ g[n - 1] + 2 _ d[n - 1]
d[n] = g[n - 1] + d[n - 1]

参考源码

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

2086 A1 = ?

Problem Description

有如下方程：Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, … n).若给出 A0, An+1, 和 C1, C2, …Cn.请编程计算 A1 = ?

Input

输入包括多个测试实例。
对于每个实例，首先是一个正整数 n,(n <= 3000); 然后是 2 个数 a0, an+1.接下来的 n 行每行有一个数 ci(i = 1,
…n); 输入以文件结束符结束。

Output

对于每个测试实例，用一行输出所求得的 a1(保留 2 位小数).

Sample Input

1
50.00
25.00
10.00
2
50.00
25.00
10.00
20.00

Sample Output

27.50
15.00

解题思路

数学归纳法可以得到 A1 的计算方程
A1 = (n × A0 + An+1 - 2 × Cn - 4 × Cn-1 - … - 2 × i × Cn-i+1 - 2 × n × C1) / (n + 1)

参考源码

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;
    double a0, a1, an1, c[3002];
    while (cin >> n) {
        cin >> a0 >> an1;
        for (int i = 1; i <= n; i++) {
            cin >> c[i];
        }
        a1 = n * a0 + an1;
        for (int i = 1; i <= n; i++) {
            a1 -= 2 * i * c[n - i + 1];
        }
        a1 /= (n + 1);
        printf("%.2f\n", a1);
    }
    return 0;
}

2087 剪花布条

Problem Description

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

Input

输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见 ASCII 字符表示的，可见的 ASCII 字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过 1000 个字符长。如果遇见#字符，则不再进行工作。

Output

输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出 0，每个结果之间应换行。

Sample Input

abcde a3
aaaaaa aa
#

Sample Output

0
3

解题思路

调用库函数 strstr()
功能：函数返回一个指针，它指向字符串 str2 首次出现于字符串 str1 中的位置，如果没有找到，返回 NULL。

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int count;
    char a[1001], b[1001];
    char *p;
    while (cin >> a && a[0] != '#') {
        cin >> b;
        count = 0;
        for (p = a; p = strstr(p, b); p += strlen(b)) {
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

2088 Box of Bricks

Problem Description

Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. “Look, I’ve built a wall!”, he tells his older sister Alice. “Nah, you should make all stacks the same height. Then you would have a real wall.”, she retorts. After a little consideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?

Input

The input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights hi of the n stacks. You may assume 1≤n≤50 and 1≤hi≤100. The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height. The input is terminated by a set starting with n = 0. This set should not be processed.

Output

For each set, print the minimum number of bricks that have to be moved in order to make all the stacks the same height. Output a blank line between each set.

Sample Input

6
5 2 4 1 7 5
0

Sample Output

5

解题思路

题目大意：小鲍勃喜欢玩他的方盒子。他把那些盒子叠成不同高度的栈。他对他的姐姐艾丽丝说：“看，我砌成了一堵墙！” “你只有把所有的栈调整成相同的高度，那样才算是一堵真正的墙。”她回应道。经过短暂的思考，鲍勃觉得她是对的。为了使栈能一样高，他只好一个一个地搬盒子。但是鲍勃很懒，他想搬最小的次数来达到目的。你能帮助他吗？

求平均数，再计算超出平均数个数

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main() {
    int n, num[50], sum, c = 0;
    while (cin >> n && n) {
        if (c++) cout << endl;
        sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> num[i];
            sum += num[i];
        }
        int ave = sum / n;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (num[i] > ave) {
                count += num[i] - ave;
            }
        }
        cout << count << endl;
    }
    return 0;
}

2089 不要 62

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为 62（音：laoer）。 杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，
这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有 4 或 62 的号码。例如：62315 73418 88914 都属于不吉利号码。但是，61152 虽然含有 6 和 2，但不是 62 连号，所以不属于不吉利数字之列。你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对 n、m（0<n≤m<1000000），如果遇到都是 0 的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

1 100
0 0

Sample Output

80

解题思路

判断余数是否是 4 或 62

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
using namespace std;
bool number(long long a) {
    while (a != 0) {
        if (a % 10 == 4 || a % 100 == 62) return false;  //若尾数不是4或者62
        a /= 10;
    }
    return true;
}
int main() {
    long long n, m, count;
    while (cin >> n >> m && (n || m)) {
        count = 0;
        for (int i = n; i <= m; i++) {
            if (number(i)) count++;
        }
        cout << count << endl;
    }
    return 0;
}

相关内容