当前栏目
杭电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
参考源码
#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 存余数，当然其他方法也可以
参考源码
#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)
参考源码
#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 进制的加法运算
参考源码
#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 中，然后将第二个集合元素依次插入、删除，若为相同元素，则会被删除 也可以使用数组存放元素，每读入一个数字，做一次遍历，如果找到就删除
参考源码
#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中若干项的乘积
参考源码
//方法一：迭代
#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| S=21∣∣i=1∑n(xiyi+1−xi+1yi)∣∣
参考源码
#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
解题思路
区间贪心问题，可以创建一个结构体，根据开始时间从大到小进行排序，选择第一个（也就是最晚的节目）作为开始，比较当前节目的开始时间和上一个节目的结束时间，若当前节目的开始时间 >= 上一个节目的结束时间，则满足条件 当然也可以根据结束时间从小到大进行排序，从第一个节目开始选择，原理相同
参考源码
#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
解题思路
参考源码
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
参考源码
#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;
}