当前栏目
杭电OJ2070-2079
杭电 OJ2070-2079
写在前面
本文记录了刷杭电 OJ2070-2079 的过程和一些想法，代码仅供参考！
2070 Fibbonacci Number
Problem Description
Your objective for this question is to develop a program which will generate a fibbonacci number.The fibbonacci function is defined as such: f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) Your program should be able to handle values of n in the range 0 to 50.
Input
Each test case consists of oneinteger n in a single line where 0≤n≤50.The input is terminated by -1.
Output
Print out the answer in a single line for each test case.
Sample Input
3 4 5 -1
Sample Output
2 3 5
解题思路
题目大意：计算 fibbonacci 数列
直接按公式计算
参考源码
#include <iostream>
using namespace std;
int main() {
int n;
__int64 f[51] = {0, 1};
for (int i = 2; i < 51; i++) {
f[i] = f[i - 1] + f[i - 2];
}
while (cin >> n && n != -1) {
cout << f[n] << endl;
}
return 0;
}2071 Max Num
Problem Description
There are some students in a class, Can you help teacher find the highest student .
Input
There are some cases. The first line contains an integer t, indicate the cases;Each case have an integer n ( 1 ≤ n ≤ 100 ) , followed n students’ height.
Output
For each case output the highest height, the height to two decimal plases;
Sample Input
2 3 170.00 165.00 180.00 4 165.00 182.00 172.00 160.00
Sample Output
180.00 182.00
解题思路
题目大意：找最大值
参考源码
#include <iostream>
using namespace std;
int main() {
int t, n;
cin >> t;
while (t--) {
cin >> n;
double height, max = 0;
for (int i = 0; i < n; i++) {
cin >> height;
if (height > max) max = height;
}
printf("%.2f\n", max);
}
return 0;
}2072 单词数
Problem Description
lily 的好朋友 xiaoou333 最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助 xiaoou333 解决这个问题。
Input
有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到 #时表示输入结束。
Output
每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。
Sample Input
you are my friend #
Sample Output
4
解题思路
stringstream 分割字符串，再使用 set 容器计数
参考源码
#include <iostream>
#include <set>
#include <sstream>
#include <string>
using namespace std;
int main() {
string s;
set<string> st;
while (getline(cin, s)) {
if (s == "#") break;
stringstream ss(s);
string c;
while (ss >> c) st.insert(c);
cout << st.size() << endl;
st.clear();
}
return 0;
}2073 无限的路
Problem Description
甜甜从小就喜欢画图画，最近他买了一支智能画笔，由于刚刚接触，所以甜甜只会用它来画直线，于是他就在平面直角坐标系中画出如右的图形： 甜甜的好朋友蜜蜜发现上面的图还是有点规则的，于是他问甜甜：在你画的图中，我给你两个点，请你算一算连接两点的折线长度（即沿折线走的路线长度）吧。
Input
第一个数是正整数 N（≤100）。代表数据的组数。每组数据由四个非负整数组成 x1，y1，x2，y2；所有的数都不会大于 100。
Output
对于每组数据，输出两点(x1,y1),(x2,y2)之间的折线距离。注意输出结果精确到小数点后 3 位。
Sample Input
5 0 0 0 1 0 0 1 0 2 3 3 1 99 99 9 9 5 5 5 5
Sample Output
1.000 2.414 10.646 54985.047 0.000
解题思路
点（0，i）到原点距离 f（i）= f（i - 1）+ m + n ，f(1) = 1 点（x，y）到原点的距离公式为 d = f（x + y）+ x × sqrt（2.0）
参考源码
#include <cmath>
#include <iostream>
using namespace std;
double f[210] = {0, 1};
void dis() {
for (int i = 2; i < 201; i++) {
double m = (double)sqrt(2 * (i - 1) * (i - 1));
double n = (double)sqrt(i * i + (i - 1) * (i - 1));
f[i] = f[i - 1] + m + n;
}
}
int main() {
int x1, y1, x2, y2, n;
double sum1, sum2;
dis();
cin >> n;
while (n--) {
cin >> x1 >> y1 >> x2 >> y2;
sum1 = f[x1 + y1] + x1 * sqrt(2.0);
sum2 = f[x2 + y2] + x2 * sqrt(2.0);
printf("%.3f\n", fabs(sum1 - sum2));
}
return 0;
}2074 叠筐
Problem Description
需要的时候，就把一个个大小差一圈的筐叠上去，使得从上往下看时，边筐花色交错。这个工作现在要让计算机来完成，得看你的了。
Input
输入是一个个的三元组，分别是，外筐尺寸 n（n 为满足 0<n<80 的奇整数），中心花色字符，外筐花色字符，后二者都为 ASCII 可见字符；
Output
输出叠在一起的筐图案，中心花色与外筐花色字符从内层起交错相叠，多筐相叠时，最外筐的角总是被打磨掉。叠筐与叠筐之间应有一行间隔。
Sample Input
11 B A 5 @ W
Sample Output
AAAAAAAAA ABBBBBBBBBA ABAAAAAAABA ABABBBBBABA ABABAAABABA ABABABABABA ABABAAABABA ABABBBBBABA ABAAAAAAABA ABBBBBBBBBA AAAAAAAAA
@@@ @WWW@ @W@W@ @WWW@ @@@
解题思路
参考源码
2075 A|B?
Problem Description
正整数 A 是否能被正整数 B 整除，不知道为什么 xhd 会研究这个问题，来帮帮他吧。
Input
输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据有两个正整数 A 和 B(A,B<10^9)。
Output
对于每组输入数据，输出"YES"表示可以被整除，"NO"表示不能被整除。
Sample Input
2 4 2 5 3
Sample Output
YES NO
解题思路
简单题，整除
参考源码
#include <iostream>
using namespace std;
int main() {
int n, a, b;
cin >> n;
while (n--) {
cin >> a >> b;
if (a % b == 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}2076 夹角有多大(题目已修改,注意读题)
Problem Description
时间过的好快，一个学期就这么的过去了，xhd 在傻傻的看着表，出于对数据的渴望，突然他想知道这个表的时针和分针的夹角是多少。现在 xhd 知道的只有时间，请你帮他算出这个夹角。注：夹角的范围[0，180]，时针和分针的转动是连续而不是离散的。
Input
输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据有三个整数 h(0 <= h < 24)，m(0 <= m < 60)，s(0 <= s < 60)分别表示时、分、秒。
Output
对于每组输入数据，输出夹角的大小的整数部分。
Sample Input
2 8 3 17 5 13 30
Sample Output
138 75
解题思路
时针走 30°/小时，分针走 6°/分钟，然后分别计算时针和分针的角度即可
参考源码
#include <cmath>
#include <iostream>
using namespace std;
int main() {
int n;
double h, m, s, harg, marg, arg;
cin >> n;
while (n--) {
cin >> h >> m >> s;
if (h > 12) h = h - 12;
harg = 30 * h + m / 2 + s / 120; //时针角度
marg = 6 * m + s / 10; //分针角度
arg = fabs(harg - marg);
if (arg > 180) arg = 360 - arg;
printf("%d\n", (int)arg);
}
return 0;
}2077 汉诺塔 IV
Problem Description
还记得汉诺塔 III 吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd 在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。
Input
输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据有一个正整数 n(1 <= n <= 20)，表示有 n 个盘子。
Output
对于每组输入数据，最少需要的摆放次数。
Sample Input
2 1 10
Sample Output
2 19684
解题思路
对于前 n-1 个的移动，2064 和一样，但是将 n-1 个移动只到中间，最大从最左到中间到最右，n-1 移动到最右即可 相邻杆移动递推 f [i] = f [i-1] × 3 + 1，f(1) = 1（前 n-2 个与 2064 一样，第 n-1 个移动到中间）
对于这个规则来说，搬 n 个盘就需要 f(n) = 2 × f(n-1) + 2
参考源码
#include <iostream>
using namespace std;
int main() {
int n, num, s, f[21] = {0};
f[1] = 1;
for (int i = 2; i < 21; i++) {
f[i] = 3 * f[i - 1] + 1;
}
cin >> n;
while (n--) {
cin >> num;
s = 2 * f[num - 1] + 2;
if (num == 1)
cout << "2" << endl;
else
cout << s << endl;
}
return 0;
}2078 复习时间
Problem Description
为了能过个好年，xhd 开始复习了，于是每天晚上背着书往教室跑。xhd 复习有个习惯，在复习完一门课后，他总是挑一门更简单的课进行复习，而他复习这门课的效率为两门课的难度差的平方,而复习第一门课的效率为 100 和这门课的难度差的平方。xhd 这学期选了 n 门课，但是一晚上他最多只能复习 m 门课，请问他一晚上复习的最高效率值是多少？
Input
输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据的第一行是两个整数 n(1 <= n <= 40)，m(1 <= m <= n)。接着有 n 行，每行有一个正整数 a(1 <= a <= 100)，表示这门课的难度值。
Output
对于每组输入数据，输出一个整数，表示最高效率值。
Sample Input
2 2 2 52 25 12 5 89 64 6 43 56 72 92 23 20 22 37 31
Sample Output
5625 8836
解题思路
如果前一门复习的课程的难度为 m，后一门为 n。那他复习后一门的效率就为(m-n)×(m-n)，m 最大值为初始状态 100，那么选最简单的一门课效率最高
参考源码
#include <iostream>
using namespace std;
int main() {
int t, n, m, a;
cin >> t;
while (t--) {
cin >> n >> m;
m = 100;
for (int i = 0; i < n; i++) {
cin >> a;
if (m > a) m = a;
}
cout << (100 - m) * (100 - m) << endl;
}
return 0;
}2079 选课时间(题目已修改,注意读题)
Problem Description
又到了选课的时间了，xhd 看着选课表发呆，为了想让下一学期好过点，他想知道学 n 个学分共有多少组合。你来帮帮他吧。（xhd 认为一样学分的课没区别）
Input
输入数据的第一行是一个数据 T，表示有 T 组数据。每组数据的第一行是两个整数 n(1 <= n <= 40)，k(1 <= k <= 8)。接着有 k 行，每行有两个整数 a(1 <= a <= 8),b(1 <= b <= 10)，表示学分为 a 的课有 b 门。
Output
对于每组输入数据，输出一个整数，表示学 n 个学分的组合数。
Sample Input
2 2 2 1 2 2 1 40 8 1 1 2 2 3 2 4 2 5 8 6 9 7 6 8 8
Sample Output
2 445
解题思路
暴力破解法，母函数法
参考源码
//方法一：暴力破解
#include <cstring>
#include <iostream>
using namespace std;
int main() {
int k, n, c[9], t[9]; //c[i]表示选择学分为i的课程数量
int a, b;
int count,total;
cin >> k;
while (k--) {
cin >> total >> n;
count = 0;
memset(t, 0, sizeof(t));
for (int i = 0; i < n; i++) {
cin >> a >> b;
t[a] = b;
}
for (c[8] = 0; c[8] <= t[8] && c[8] * 8 <= total; c[8]++)
for (c[7] = 0; c[7] <= t[7] && c[8] * 8 + c[7] * 7 <= total; c[7]++)
for (c[6] = 0; c[6] <= t[6] && c[8] * 8 + c[7] * 7 + c[6] * 6 <= total; c[6]++)
for (c[5] = 0; c[5] <= t[5] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 <= total; c[5]++)
for (c[4] = 0; c[4] <= t[4] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 <= total; c[4]++)
for (c[3] = 0; c[3] <= t[3] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 <= total; c[3]++)
for (c[2] = 0; c[2] <= t[2] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 + c[2] * 2 <= total; c[2]++) {
c[1] = total - (c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 + c[2] * 2);
if (c[1] >= 0 && c[1] <= t[1]) count++;
}
cout << count << endl;
}
return 0;
}
// 方法二：母函数
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int ans[1000], temp[1000];
struct course {
int s, num;
} cou[10];
bool cmp(course a, course b) { return a.s < b.s; }
int main() {
int t, n, k;
cin >> t;
while (t--) {
memset(cou, 0, sizeof(cou));
cin >> n >> k;
for (int i = 0; i < k; i++) {
cin >> cou[i].s >> cou[i].num;
}
sort(cou, cou + k, cmp);
memset(ans, 0, sizeof(ans));
memset(temp, 0, sizeof(temp));
for (int i = 0; i <= n && i <= cou[0].s * cou[0].num; i += cou[0].s) {
ans[i] = 1; //初始化第一个多项式
}
for (int i = 1; i < k; i++) {
for (int j = 0; j <= n; j++)
for (int p = 0; j + p <= n && p <= cou[i].s * cou[i].num; p += cou[i].s)
temp[j + p] += ans[j];
for (int j = 0; j <= n; j++) { // 将临时的结果覆盖当前结果，同时把临时结果置零
ans[j] = temp[j];
temp[j] = 0;
}
}
cout << ans[n] << endl;
}
return 0;
}