杭电 OJ2050-2059

写在前面

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

2050 折线分割平面

Problem Description

我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是 n 条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成 7 部分，具体如右所示。

Input

输入数据的第一行是一个整数 C,表示测试实例的个数，然后是 C 行数据，每行包含一个整数 n(0<n<=10000),表示折线的数量。

Output

对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。

Sample Input

2
1
2

Sample Output

2
7

解题思路

先来看看 n 条相交的直线最多能把平面分割成几块：当添加第 n 条直线时，为了使平面最多，则第 n 条直线要与前面 n-1 条直线都相交

对折线来说，分割平面的个数 = 交点个数 + 顶点个数 + 1
令 f (n-1) 为前 n-1 条折线分割的平面数，当添加第 n 条折线时。
因为每一条边与前 n-1 条折线的两条边都相交，故增加的交点数为 22(n-1)，顶点增加 1，故
f(n) = f(n - 1) + 4(n - 1) + 1
可以得出公式 f (n) = 2n2 - n + 1（直接用上面的递归式计算也可）

参考源码

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main() {
    int c, n;
    cin >> c;
    while (c--) {
        cin >> n;
        cout << 2 * n * n - n + 1 << endl;
    }
    return 0;
}

2051 Bitset

Problem Description

Give you a number on base ten,you should output it on base two.(0 < n < 1000)

Input

For each case there is a postive number n on base ten, end of file.

Output

For each case output a number on base two.

Sample Input

1
2
3

Sample Output

1
10
11

解题思路

题目大意：将十进制转换成二进制
整除取余

参考源码

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

2052 Picture

Problem Description

Give you the width and height of the rectangle,darw it.

Input

Input contains a number of test cases.For each case ,there are two numbers n and m (0 < n,m < 75) indicate the width and height of the rectangle.Iuput ends of EOF.

Output

For each case,you should draw a rectangle with the width and height giving in the input. after each case, you should a blank line.

Sample Input

3 2

Sample Output

±–+
|   |
|   |
±–+

解题思路

题目大意：打印矩形
按照要求按行打印即可

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        cout << "+";
        for (int i = 0; i < n; i++) cout << "-";
        cout << "+" << endl;
        for (int i = 0; i < m; i++) {
            cout << "|";
            for (int j = 0; j < n; j++) {
                cout << " ";
            }
            cout << "|" << endl;
        }
        cout << "+";
        for (int i = 0; i < n; i++) cout << "-";
        cout << "+" << endl << endl;
    }
    return 0;
}

2053 Switch Game

Problem Description

There are many lamps in a line. All of them are off at first. A series of operations are carried out on these lamps. On the i-th operation, the lamps whose numbers are the multiple of i change the condition ( on to off and off to on ).
有一些灯排成一条直线。所有的灯在刚开始都是关闭的，在对灯进行一系列操作后:在第 i 次操作的时候，
调整所有标号是 i 的倍数的灯的状态(原本打开的灯将它关闭，原本关闭的将它打开)。

Input

Each test case contains only a number n ( 0< n<= 10^5) in a line.

Output

Output the condition of the n-th lamp after infinity operations ( 0 - off, 1 - on).

Sample Input

1
5

Sample Output

1
0

Hint
hint
Consider the second test case:
The initial condition : 0 0 0 0 0 …
After the first operation : 1 1 1 1 1 …
After the second operation : 1 0 1 0 1 …
After the third operation : 1 0 0 0 1 …
After the fourth operation : 1 0 0 1 1 …
After the fifth operation : 1 0 0 1 0 …
The later operations cannot change the condition of the fifth lamp any more. So the answer is 0.

解题思路

题目大意：有一些灯排成一条直线。所有的灯在刚开始都是关闭的，在对灯进行一系列操作后:在第 i 次操作的时候，调整所有标号是 i 的倍数的灯的状态(原本打开的灯将它关闭，原本关闭的将它打开)。
可以数变化的次数，然后奇偶数判断
另外也可以判断输入的数是否为完全平方数

参考源码

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
// 方法一
#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n;
    while (cin >> n) {
        int c = 0;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                c++;  //变化的次数
            }
        }
        cout << (c & 1) << endl;  //奇数次变化则为1，偶数次变化即为2
    }
    return 0;
}

// 方法二
#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n;
    while (cin >> n) {
        if ((int)sqrt(n) * (int)sqrt(n) == n)
            cout << "1" << endl;
        else
            cout << "0" << endl;
    }
    return 0;
}

2054 A == B ?

Problem Description

Give you two numbers A and B, if A is equal to B, you should print “YES”, or print “NO”.

Input

each test case contains two numbers A and B.

Output

for each case, if A is equal to B, you should print “YES”, or print “NO”.

Sample Input

1 2
2 2
3 3
4 3

Sample Output

NO
YES
YES
NO

解题思路

题目大意：比较两个数是否相等
注意数字可能很大，需要用字符串存储，另外注意小数点后无效 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
25
26
#include <cstring>
#include <iostream>
using namespace std;
void cut(char a[]) {
    int len = strlen(a);
    if (strchr(a, '.')) {                          //是否有小数点
        for (int i = len - 1; a[i] == '0'; i--) {  //去除多余0
            a[i] = '\0';
            len--;
        }
    }
    if (a[len - 1] == '.') a[len - 1] = '\0';  //若小数点后没有0，去除小数点
}
int main() {
    char a[1000000], b[1000000];
    while (cin >> a) {
        cin >> b;
        cut(a);
        cut(b);
        if (strcmp(a, b) == 0)  //比较是否相等
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

2055 An easy problem

Problem Description

we define f(A) = 1, f(a) = -1, f(B) = 2, f(b) = -2, … f(Z) = 26, f(z) = -26; Give you a letter x and a number y , you should output the result of y+f(x).

Input

On the first line, contains a number T.then T lines follow, each line is a case.each case contains a letter and a number.

Output

for each case, you should the result of y+f(x) on a line.

Sample Input

6
R 1
P 2
G 3
r 1
p 2
g 3

Sample Output

19
18
10
-17
-14
-4

解题思路

题目大意：计算 y + f(x)
按照题目说的式子直接运算即可

参考源码

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, m;
    char c;
    cin >> n;
    while (n--) {
        cin >> c;
        cin >> m;
        if (isupper(c))
            cout << c - 'A' + 1 + m << endl;  //大写字母
        else
            cout << -(c - 'a' + 1) + m << endl;  //小写字母
    }
    return 0;
}

2056 Rectangles

Problem Description

Given two rectangles and the coordinates of two points on the diagonals of each rectangle,you have to calculate the area of the intersected part of two rectangles. its sides are parallel to OX and OY .

Input

Input The first line of input is 8 positive numbers which indicate the coordinates of four points that must be on each diagonal.The 8 numbers are x1,y1,x2,y2,x3,y3,x4,y4.That means the two points on the first rectangle are(x1,y1),(x2,y2);the other two points on the second rectangle are (x3,y3),(x4,y4).

Output

Output For each case output the area of their intersected part in a single line.accurate up to 2 decimal places.

Sample Input

1.00 1.00 3.00 3.00 2.00 2.00 4.00 4.00
5.00 5.00 13.00 13.00 4.00 4.00 12.50 12.50

Sample Output

1.00
56.25

解题思路

题目大意：求出相交的矩形重叠部分的面积
计算相交的矩形对角的顶点即可

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    double n, x[4], y[4], a[2], b[2];
    while (cin >> x[0] >> y[0] >> x[1] >> y[1]) {
        cin >> x[2] >> y[2] >> x[3] >> y[3];
        if (x[0] > x[1]) swap(x[0], x[1]);  //输入的顶点可能是左下右上，也有可能是左上右下，注意统一
        if (y[0] > y[1]) swap(y[0], y[1]);
        if (x[2] > x[3]) swap(x[2], x[3]);
        if (y[2] > y[3]) swap(y[2], y[3]);
        a[0] = max(x[0], x[2]);  //统一顶点之后，相交矩形的顶点就好求了
        b[0] = max(y[0], y[2]);
        a[1] = min(x[1], x[3]);
        b[1] = min(y[1], y[3]);
        if (a[0] < a[1] && b[0] < b[1])
            printf("%.2f\n", (a[1] - a[0]) * (b[1] - b[0]));  //计算面积
        else
            printf("0.00\n");  //无重叠
    }
    return 0;
}

2057 A + B Again

Problem Description

There must be many A + B problems in our HDOJ , now a new one is coming.Give you two hexadecimal integers , your task is to calculate the sum of them,and print it in hexadecimal too. Easy ? AC it !

Input

The input contains several test cases, please process to the end of the file.Each case consists of two hexadecimal integers A and B in a line seperated by a blank. The length of A and B is less than 15.

Output

For each test case,print the sum of A and B in hexadecimal in one line.

Sample Input

+A -A
+1A 12
1A -9
-1A -12
1A -AA

Sample Output

0
2C
11
-2C
-90

解题思路

题目大意：十六进制数加减
计算机中不能直接显示 16 进制的负数，所以需要将负数转为正数输出，在输出时要将 16 进制数的字母变成大写，默认是小写的。应该使用 uppercase 关键字

参考源码

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

2058 The sum problem

Problem Description

Given a sequence 1,2,3,…N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.

Input

Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.

Output

For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.

Sample Input

20 10
50 30
0 0

Sample Output

[1,4]
[10,10]

[4,8]
[6,9]
[9,11]
[30,30]

解题思路

题目大意：在 1，2，···，N 的串中，找到和为一个字串，使得这个字串中的数字之和为 M
可以遍历字串的长度，如果首项为 i，项数为 j，那么最后一项为 i+j-1
确定了项数 j 和 m，可以确定首项 i = ((2 * m) / j - j + 1) / 2
那么通过 m = (i + (i + j - j)) * j / 2 进行判断这个子串是否满足条件
由于 j * j + 2 * i * j - j = 2m，因此有 j <sqrt (2 * m) 从而可以减小项数 j 的范围，而不用遍历 n 项

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n, m, i, j;
    while (cin >> n >> m && (n || m)) {
        for (j = (int)sqrt(2.0 * m); j >= 1; j--) {  //遍历可能的项数
            i = ((2 * m) / j - j + 1) / 2;           //首项
            if ((i + (i + j - 1)) * j / 2 == m) {    //若以i为首项的j项之和为m
                cout << "[" << i << "," << i + j - 1 << "]" << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

2059 龟兔赛跑

Problem Description

据说在很久很久以前，可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后，心中郁闷，发誓要报仇雪恨，于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼，终于练成了绝技，能够毫不休息得以恒定的速度(VRm/s)一直跑。兔子一直想找机会好好得教训一下乌龟，以雪前耻。
最近正值 HDU 举办 50 周年校庆，社会各大名流齐聚下沙，兔子也趁此机会向乌龟发起挑战。虽然乌龟深知获胜希望不大，不过迫于舆论压力，只能接受挑战。
比赛是设在一条笔直的道路上，长度为 L 米，规则很简单，谁先到达终点谁就算获胜。无奈乌龟自从上次获胜以后，成了名龟，被一些八卦杂志称为“动物界的刘翔”，广告不断，手头也有了不少积蓄。为了能够再赢兔子，乌龟不惜花下血本买了最先进的武器——“"小飞鸽"牌电动车。这辆车在有电的情况下能够以 VT1m/s 的速度“飞驰”，可惜电池容量有限，每次充满电最多只能行驶 C 米的距离，以后就只能用脚来蹬了，乌龟用脚蹬时的速度为 VT2m/s。更过分的是，乌龟竟然在跑道上修建了很多很多（N 个)的供电站，供自己给电动车充电。其中，每次充电需要花费 T 秒钟的时间。当然，乌龟经过一个充电站的时候可以选择去或不去充电。比赛马上开始了，兔子和带着充满电的电动车的乌龟并列站在起跑线上。你的任务就是写个程序，判断乌龟用最佳的方案进军时，能不能赢了一直以恒定速度奔跑的兔子。

Input

本题目包含多组测试，请处理到文件结束。每个测试包括四行：
第一行是一个整数 L 代表跑道的总长度
第二行包含三个整数 N，C，T，分别表示充电站的个数，电动车冲满电以后能行驶的距离以及每次充电所需要的时间
第三行也是三个整数 VR，VT1，VT2，分别表示兔子跑步的速度，乌龟开电动车的速度，乌龟脚蹬电动车的速度
第四行包含了 N(N<=100)个整数 p1,p2…pn,分别表示各个充电站离跑道起点的距离，其中 0<p1<p2<…其中每个数都在 32 位整型范围之内。

Output

当乌龟有可能赢的时候输出一行 “What a pity rabbit!“。否则输出一行"Good job,rabbit!”;
题目数据保证不会出现乌龟和兔子同时到达的情况。

Sample Input

100
3 20 5
5 8 2
10 40 60
100
3 60 5
5 8 2
10 40 60

Sample Output

Good job,rabbit!
What a pity rabbit!

解题思路

一维数组的动态规划问题，可以把起点和终点，以及中间的 n 个充电站看做 n+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
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#define INF 0x3fffffff
using namespace std;
int main() {
    int l, n, c, t, p[102];
    int vr, vt1, vt2;
    double dt[102], min, temp;  // dt存储到达第i站的最短时间
    while (cin >> l) {
        cin >> n >> c >> t;
        cin >> vr >> vt1 >> vt2;
        p[0] = 0;  //起点距离为0
        for (int i = 1; i <= n; i++) cin >> p[i];
        p[n + 1] = l;                      //终点距离为l
        dt[0] = 0;                         //到起点不需要时间
        for (int i = 1; i < n + 2; i++) {  //遍历每个站点
            min = INF;
            for (int j = 0; j < i; j++) {  //遍历从起点到第 i-1 站
                int len = p[i] - p[j];     //两站之间的距离
                if (len < c) {
                    temp = 1.0 * len / vt1;  //开的到
                } else {
                    temp = 1.0 * c / vt1 + 1.0 * (len - c) / vt2;  //开不到
                }
                temp += dt[j];  //到达下一站所需的时间 = 开车时间 + 到达本站的最短时间
                if (j) temp += t;  //充电时间
                if (min > temp) min = temp;
            }
            dt[i] = min;
        }
        if (dt[n + 1] > 1.0 * l / vr)
            cout << "Good job,rabbit!" << endl;
        else
            cout << "What a pity rabbit!" << endl;
    }
    return 0;
}

相关内容