HDU100题简要题解（2030~2039）

• HDU2030 汉字统计
  
  题目链接

Problem Description

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

Input

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

Output

对于每一段文本，输出其中的汉字的个数，每个测试实例的输出占一行。

[Hint:]从汉字机内码的特点考虑~

Sample Input

2

WaHaHa! WaHaHa! 今年过节不说话要说只说普通话WaHaHa! WaHaHa!

马上就要期末考试了Are you ready?

Sample Output

14

9

给的这个hint就很友好哇，百度得知：特点为汉字是由两个负数组成的。那就很好说了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
char a[1001];

int main() {
  while (scanf("%d", &n) != EOF) {
    getchar();
    while (n--) {
      int cnt = 0;
      gets(a);
      int len = strlen(a);
      for (int i = 0; i < len; i++)
  	 if (a[i] < 0) cnt++;
      cout << cnt / 2 << endl;
    }
  }
  return 0;
}

• HDU2021 进制转换
  
  题目链接

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

十分朴实的进制转化问题，注意一下负数的处理

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n, r;

int main() {
  while (scanf("%d%d", &n, &r) != EOF) {
    if (n < 0) {
      cout << "-";
      n = - n;
    }
    if (n == 0) cout << 0 << endl;
    else {
      int cnt = 0, a[101];
      while (n) {
  	a[cnt++] = n % r;
  	n /= r;
      }
      for (int i = cnt - 1; i >= 0; i--) {
  	if (a[i] >= 10) printf("%c", 'A' + a[i] - 10);
  	else printf("%d", a[i]);
      }
      cout << endl;
    }
  }
  return 0;
}

• HDU2032 杨辉三角
  
  题目链接

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

（排版用的填充空行的一句话qwq）

1

1 1

1 2 1

十分经典的杨辉三角问题，小孩子都知道其中的递推关系：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

但不要忘记初始化两边上的数都为1

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n, dp[101][101];

int main() {
  while (scanf("%d", &n) != EOF) {
    for (int i = 1; i <= n; i++) {
      dp[i][1] = 1;
      dp[i][i] = 1;
    }
    for (int i = 3; i <= n; i++)
      for (int j = 2; j < i; j++)
  	dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    for (int i = 1; i <= n; i++) {
      cout << dp[i][1];
      for (int j = 2; j <= i; j++)
        cout << " " << dp[i][j];
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}

• HDU2033 人见人爱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

钟表版A+B，用三个数分别记录hour,minute,second，大于60就向上进位即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n;

int main() {
  while (scanf("%d", &n) != EOF) {
    while (n--) {
      int ah, am, as, bh, bm, bs;
      scanf("%d%d%d%d%d%d", &ah, &am, &as, &bh, &bm, &bs);
      int ansh, ansm, anss;
      ansh = ansm = anss = 0;
      anss = as + bs;
      ansm = am + bm;
      ansh = ah + bh;
      if (anss >= 60) {
  	anss -= 60;
  	ansm++;
      }
      if (ansm >= 60) {
  	ansm -= 60;
  	ansh++;
      }
      printf("%d %d %d\n", ansh, ansm, anss);
    }
  }
  return 0;
}

• HDU2034 人见人爱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

用两个数组记录集合A和集合B，然后把两者重合的字的flag赋值为1，然后再用一个c数组记录a数组中flag为0的数字（也就是与B不重合的数字），排序一下然后输出~

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, a[101], b[101], c[101], flag[101];

int main() {
  while (scanf("%d%d", &n, &m) != EOF) {
    memset(flag, 0, sizeof(flag));
    int cnt = 0;
    int num = 0;
    if (n == 0 && m == 0) break;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
      for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
  	for (int i = 1; i <= n; i++)
  	  for (int j = 1; j <= m; j++)
  	    if (a[i] == b[j]) {
  	      flag[i] = 1;
		  cnt++;
  	    }
    if (cnt == n) cout << "NULL" << endl;
    else {
      for (int i = 1; i <= n; i++)
  	if (flag[i] == 0)
  	  c[++num] = a[i];
      sort(c + 1, c + 1 + num);
      for (int i = 1; i <= num; i++) cout << c[i] << " ";
      cout << endl;
    }
  }
  return 0;
}

• HDU2035 人见人爱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

就求A的B次方，大于1000了就模一下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int a, b;

int main() {
  while (scanf("%d%d", &a, &b) != EOF) {
    if (a == 0 && b == 0) break;
    int num = a;
    for (int i = 1; i < b; i++) {
      a *= num;
      if (a > 1000) a %= 1000;
    }
    printf("%d\n", a);
  }
  return 0;
}

• HDU2036 改革春风吹满地
  
  题目链接

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=0.5 * ( (x0y1-x1y0) + (x1y2-x2y1) + ... + (xny0-x0yn) )，虽然意思一样，但第二个看起来就慈祥了许多

得到代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n;

int main() {
  while (scanf("%d", &n) != EOF) {
    if (n == 0) break;
    int x1, x2, y1, y2;
    double ans = 0;
    scanf("%d%d", &x1, &y1);
    int x = x1;
    int y = y1;
    for (int i = 0; i < n - 1; i++) {
      scanf("%d%d", &x2, &y2);
      ans += x1 * y2 - x2 * y1;
      x1 = x2;
      y1 = y2;
    }
    ans += x1 * y - y1 * x;
    ans /= 2.0;
    printf("%.1lf\n", ans);
  }
  return 0;
}

• HDU2037 今年暑假不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

很经典的贪心问题，白书上的例题我忘了是哪一个了，依稀记得是什么流星雨许愿还是咋的，找了一个洛谷上的P1803 凌乱的yyy/线段覆盖相似题

以结束时间为基准从小到大排序，结束时间越早后面能够容纳的比赛也就越多，后面的比赛开始时间≥目前比赛结束时间的话，可观看场数加一，记录此比赛结束时间，依次往后查找更新即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
struct node{
  int s;
  int e;
}a[101];

int cmp(node x, node y) {
  if (x.e != y.e) return x.e < y.e;
  else return x.s < y.s;
}

int main() {
  while (scanf("%d", &n) != EOF) {
    if (n == 0) break;
    int num = 0;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
      scanf("%d%d", &a[i].s, &a[i].e);
      sort(a + 1, a + 1 + n, cmp);
      for (int i = 1; i <= n; i++) {
      if (i == 1) {
  	num = a[i].e;
  	cnt++;
      } else {
  	if (a[i].s >= num) {
  	  cnt++;
  	  num = a[i].e;
        }
      }
    }
    printf("%d\n", cnt);
  }
  return 0;
}

• HDU2039 三角形
  
  题目链接

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

判断能否组成三角形，小学数学

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int m;

int main() {
  while (scanf("%d", &m) != EOF) {
    for (int i = 1; i <= m; i++) {
      double a, b, c;
      scanf("%lf%lf%lf", &a, &b, &c);
      if (a + b > c && a + c > b && c + b > a) printf("YES\n");
      else printf("NO\n");
    }
  }
  return 0;
}