杭电 OJ2030-2039

写在前面

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

2030 汉字统计

Problem Description

统计给定文本文件中汉字的个数。

Input

输入文件首先包含一个整数 n，表示测试实例的个数，然后是 n 段文本。

Output

对于每一段文本，输出其中的汉字的个数，每个测试实例的输出占一行。
[Hint:] 从汉字机内码的特点考虑～

Sample Input

2
WaHaHa! WaHaHa! 今年过节不说话要说只说普通话 WaHaHa! WaHaHa!
马上就要期末考试了 Are you ready?

Sample Output

14
9

解题思路

汉字占双字节，高位的字节里都是<0,所以只要统计小于 0 的字符的个数，最后除以 2

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    getchar();
    while (n--) {
        getline(cin, s);  //读取一行
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] < 0) count++;  //若小于0，就是汉字
        }
        cout << count / 2 << endl;  //双字节除以2
    }
    return 0;
}

2031 进制转换

Problem Description

输入一个十进制数 N，将它转换成 R 进制数输出。

Input

输入数据包含多个测试实例，每个测试实例包含两个整数 N(32 位整数)和 R（2<=R<=16,R<>10）。

Output

为每个测试实例输出转换后的数，每个输出占一行。如果 R 大于 10，则对应的数字规则参考 16 进制（比如，10 用 A 表示，等等）。

Sample Input

7 2
23 12
-4 3

Sample Output

111
1B
-11

解题思路

整除求余，余数按倒序输出，然后输出对应字符，我这里用了 vector 存余数，当然其他方法也可以

参考源码

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 <iostream>
#include <vector>
using namespace std;
int main() {
    int n, r;
    vector<int> vt;
    char type[16] = {'0', '1', '2', '3', '4', '5', '6', '7',
                     '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    while (cin >> n >> r) {
        if (n < 0) {  //若为负则添加 - 号
            cout << "-";
            n = -n;
        }
        if (!n) cout << "0";  //若n为0则输出0
        while (n != 0) {
            vt.push_back(n % r);
            n /= r;
        }
        for (int i = vt.size() - 1; i >= 0; i--) {
            cout << type[vt[i]];  //余数对应type输出
        }
        cout << endl;
        vt.clear();
    }
    return 0;
}

2032 杨辉三角

Problem Description

还记得中学时候学过的杨辉三角吗？具体的定义这里不再描述，你可以参考以下的图形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Input

输入数据包含多个测试实例，每个测试实例的输入只包含一个正整数 n（1<=n<=30），表示将要输出的杨辉三角的层数。

Output

对应于每一个输入，请输出相应层数的杨辉三角，每一层的整数之间用一个空格隔开，每一个杨辉三角后面加一个空行。

Sample Input

2 3

Sample Output

1
1 1

1
1 1
1 2 1

解题思路

利用公式
f(i, i) = f(i, 1) = 1 (i > 0)
f(i, j) = f(i-1, j) + f(i-1, j-1) (j < i)

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int main() {
    int n, num[30][30] = {0};
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            num[i][0] = 1;
            num[i][i] = 1;
            for (int j = 1; j < i; j++) {
                num[i][j] = num[i - 1][j] + num[i - 1][j - 1];  //按公式计算
            }
            for (int k = 0; k <= i; k++) {
                if (k == 0)
                    cout << num[i][k];
                else
                    cout << " " << num[i][k];
                if (i == k) cout << endl;  //换行
            }
        }
        cout << endl;
    }
    return 0;
}

2033 人见人爱 A+B

Problem Description

HDOJ 上面已经有 10 来道 A+B 的题目了，相信这些题目曾经是大家的最爱，希望今天的这个 A+B 能给大家带来好运，也希望这个题目能唤起大家对 ACM 曾经的热爱。这个题目的 A 和 B 不是简单的整数，而是两个时间，A 和 B 都是由 3 个整数组成，分别表示时分秒，比如，假设 A 为 34 45 56，就表示 A 所表示的时间是 34 小时 45 分钟 56 秒。

Input

输入数据有多行组成，首先是一个整数 N，表示测试实例的个数，然后是 N 行数据，每行有 6 个整数 AH,AM,AS,BH,BM,BS，分别表示时间 A 和 B 所对应的时分秒。题目保证所有的数据合法。

Output

对于每个测试实例，输出 A+B，每个输出结果也是由时分秒 3 部分组成，同时也要满足时间的规则（即：分和秒的取值范围在 0~59），每个输出占一行，并且所有的部分都可以用 32 位整数表示。

Sample Input

2
1 2 3 4 5 6
34 45 56 12 23 34

Sample Output

5 7 9
47 9 30

解题思路

从秒到分到时，整除求余，就是做一个 60 进制的加法运算

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main() {
    int n, ah, am, as, bh, bm, bs, h, m, s;
    cin >> n;
    while (n--) {
        cin >> ah >> am >> as >> bh >> bm >> bs;
        s = (as + bs) % 60;                             //秒
        m = (am + bm + (as + bs) / 60) % 60;            //分
        h = ah + bh + (am + bm + (as + bs) / 60) / 60;  //时
        cout << h << " " << m << " " << s << endl;
    }
    return 0;
}

2034 人见人爱 A-B

Problem Description

参加过上个月月赛的同学一定还记得其中的一个最简单的题目，就是{A}+{B}，那个题目求的是两个集合的并集，今天我们这个 A-B 求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）
呵呵，很简单吧？

Input

每组输入数据占 1 行，每行数据的开始是 2 个整数 n (0<=n<=100) 和 m (0<=m<=100),分别表示集合 A 和集合 B 的元素个数，然后紧跟着 n+m 个元素，前面 n 个元素属于集合 A，其余的属于集合 B. 每个元素为不超出 int 范围的整数，元素之间有一个空格隔开. 如果 n=0 并且 m=0 表示输入的结束，不做处理。

Output

针对每组数据输出一行数据，表示 A-B 的结果，如果结果为空集合，则输出 “NULL”,否则从小到大输出结果，为了简化问题，每个元素后面跟一个空格.

Sample Input

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

Sample Output

2 3
NULL

解题思路

应用 set 的性质，有序不含重复元素，首先将第一个集合插入 set 中，然后将第二个集合元素依次插入、删除，若为相同元素，则会被删除
也可以使用数组存放元素，每读入一个数字，做一次遍历，如果找到就删除

参考源码

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 <iostream>
#include <set>
using namespace std;
int main() {
    int n, m, num;
    set<int> st;
    while (cin >> n >> m && (n || m)) {
        while (n--) {
            cin >> num;
            st.insert(num);
        }
        while (m--) {
            cin >> num;
            st.insert(num);  //插入元素
            st.erase(num);   //删除插入元素
        }
        set<int>::iterator it;
        for (it = st.begin(); it != st.end(); it++) {
            cout << *it << " ";
        }
        if (st.size() == 0)
            cout << "NULL" << endl;
        else
            cout << endl;
        st.clear();
    }
    return 0;
}

2035 人见人爱 A^B

Problem Description

求 A^B 的最后三位数表示的整数。
说明：A^B 的含义是 “A 的 B 次方”

Input

输入数据包含多个测试实例，每个实例占一行，由两个正整数 A 和 B 组成（1<=A,B<=10000），如果 A=0,B=0，则表示输入数据的结束，不做处理。

Output

对于每个测试实例，请输出 A^B 的最后三位表示的整数，每个输出占一行。

Sample Input

2 3
12 6
6789 10000
0 0

Sample Output

8
984
1

解题思路

这里给出两种方法
方法一：迭代 b 次，%1000 求最后三位，比较简单
方法二：快速幂
这里简要说一下快速幂的原理
举个例子：a13=a8+4+1=a8×a4×a1
那么我们也可以考虑将 ab表示为 a2k,···,a8,a4,a2,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
//方法一：迭代
#include <iostream>
using namespace std;
int main() {
    int a, b, sum;
    while (cin >> a >> b && (a || b)) {
        sum = a;
        for (int i = 1; i < b; i++) {
            sum = sum * a % 1000;
        }
        cout << sum % 1000 << endl;
    }
    return 0;
}

//方法二：快速幂
#include <iostream>
using namespace std;
int main() {
    int a, b, sum;
    while (cin >> a >> b && (a || b)) {
        sum = 1;
        while (b > 0) {
            if (b % 2) sum = sum * a % 1000;
            a = a * a % 1000;
            b /= 2;
        }
        cout << sum << endl;
    }
    return 0;
}

2036 改革春风吹满

Problem Description

“ 改革春风吹满地，
不会 AC 没关系；
实在不行回老家，
还有一亩三分地。
谢谢！（乐队奏乐）”
话说部分学生心态极好，每天就知道游戏，这次考试如此简单的题目，也是云里雾里，而且，还竟然来这么几句打油诗。好呀，老师的责任就是帮你解决问题，既然想种田，那就分你一块。这块田位于浙江省温州市苍南县灵溪镇林家铺子村，多边形形状的一块地，原本是 linle 的，现在就准备送给你了。不过，任何事情都没有那么简单，你必须首先告诉我这块地到底有多少面积，如果回答正确才能真正得到这块地。发愁了吧？就是要让你知道，种地也是需要 AC 知识的！以后还是好好练吧…

Input

输入数据包含多个测试实例，每个测试实例占一行，每行的开始是一个整数 n(3<=n<=100)，它表示多边形的边数（当然也是顶点数），然后是按照逆时针顺序给出的 n 个顶点的坐标（x1, y1, x2, y2… xn,yn）, 为了简化问题，这里的所有坐标都用整数表示。 输入数据中所有的整数都在 32 位整数范围内，n=0 表示数据的结束，不做处理。

Output

对于每个测试实例，请输出对应的多边形面积，结果精确到小数点后一位小数。
每个实例的输出占一行。

Sample Input

3 0 0 1 0 0 1
4 1 0 0 1 -1 0 0 -1
0

Sample Output

0.5
2.0

解题思路

利用多边形求面积公式：

S=12∣∑i=1n(xiyi+1−xi+1yi)∣\text{S}=\frac{1}{2}\left| \sum_{\text{i}=1}^{\text{n}}{\left( \text{x}_{\text{i}}\text{y}_{\text{i}+1}-\text{x}_{\text{i}+1}\text{y}_{\text{i}} \right)} \right|

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main() {
    int n, x[100], y[100];
    double s;
    while (cin >> n && n) {
        for (int i = 0; i < n; i++) {
            cin >> x[i];
            cin >> y[i];
        }
        s = x[n - 1] * y[0] - x[0] * y[n - 1];//处理首尾
        for (int i = 0; i < n - 1; i++) {
            s = s + x[i] * y[i + 1] - x[i + 1] * y[i];
        }
        printf("%.1f\n", s / 2);
    }
    return 0;
}

2037 今年暑假不 AC

Problem Description

“今年暑假不 AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%…”
确实如此，世界杯来了，球迷的节日也来了，估计很多 ACMer 也会抛开电脑，奔向电视了。作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常 6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

Input

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数 n(n<=100)，表示你喜欢看的节目的总数，然后是 n 行数据，每行包括两个数据 Ti_s,Ti_e(1<=i<=n)，分别表示第 i 个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0 表示输入结束，不做处理。

Output

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

Sample Input

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
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
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <iostream>
using namespace std;
struct TV {
    int start, end;
} tv[101];
bool cmp(TV a, TV b) {
    if (a.start != b.start)
        return a.start > b.start;  //按开始时间从大到小排序
    else                           //若开始时间相同
        return a.end < b.end;      //按结束时间从小到大排序
}
int main() {
    int n, count;
    TV temp;
    while (cin >> n && n) {
        for (int i = 0; i < n; i++) {
            cin >> tv[i].start >> tv[i].end;
        }
        sort(tv, tv + n, cmp);  //排序
        temp = tv[0];
        count = 1;
        for (int i = 1; i < n; i++) {
            if (temp.start >= tv[i].end) {  //若没有重叠
                temp = tv[i];
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

2038 test

解题思路

参考源码

1

2039 三角形

Problem Description

给定三条边，请你判断一下能不能组成一个三角形。

Input

输入数据第一行包含一个数 M，接下有 M 行，每行一个实例，包含三个正数 A,B,C。其中 A,B,C <1000;

Output

对于每个测试实例，如果三条边长 A,B,C 能组成三角形的话，输出 YES，否则 NO。

Sample Input

2
1 2 3
2 2 2

Sample Output

NO
YES

解题思路

需要满足条件 a + b > c && a + c > b && b + c > a

参考源码

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

相关内容