HDU100題簡要題解（2080~2089）
- 2020 年 11 月 22 日
- 筆記
//2089之前忘做了，周二C語言課上做，至於2086，寫題解的時候突然發現之前的做法是錯的，新的解法交上去CE，等周二再弄吧，其餘題目暫時可以放心
- HDU2080 夾角有多大II
題目鏈接
Problem Description
這次xhd面臨的問題是這樣的：在一個平面內有兩個點，求兩個點分別和原點的連線的夾角的大小。
註：夾角的範圍[0，180]，兩個點不會在圓心出現。
Input
輸入數據的第一行是一個數據T，表示有T組數據。
每組數據有四個實數x1,y1,x2,y2分別表示兩個點的坐標,這些實數的範圍是[-10000,10000]。
Output
對於每組輸入數據，輸出夾角的大小精確到小數點後兩位。
Sample Input
2
1 1 2 2
1 1 1 0
Sample Output
0.00
45.00
真就數學題唄，用向量去做，向量的積（ji）除以向量模的乘積（moji），再求其反函數，然後轉換為角度
用到了acos()函數，它的返回值是弧度，要求角度需要 * 180/PI（PI就是π）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const double PI = 3.1415967;
int t;
double x1, x2, z1, y2;
double ji, moji;
int main() {
while (scanf("%d", &t) != EOF) {
while (t--) {
scanf("%lf%lf%lf%lf", &x1, &z1, &x2, &y2);
moji = sqrt(x1 * x1 + z1 * z1) * sqrt(x2 * x2 + y2 * y2);
ji = x1 * x2 + z1 * y2;
printf("%.2lf\n", acos(ji / moji) / PI * 180.0);
}
}
return 0;
}
- HDU2087 手機短號
題目鏈接
Problem Description
大家都知道，手機號是一個11位長的數字串，同時，作為學生，還可以申請加入校園網，如果加入成功，你將另外擁有一個短號。假設所有的短號都是是 6+手機號的後5位，比如號碼為13512345678的手機，對應的短號就是645678。
現在，如果給你一個11位長的手機號碼，你能找出對應的短號嗎？
Input
輸入數據的第一行是一個N(N <= 200)，表示有N個數據，接下來的N行每一行為一個11位的手機號碼。
Output
輸出應包括N行，每行包括一個對應的短號，輸出應與輸入的順序一致。
Sample Input
2
13512345678
13787654321
Sample Output
645678
654321
搞笑題
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
char c[12];
int main() {
while (scanf("%d", &n) != EOF) {
while (n--) {
for (int i = 1; i <= 11; i++) cin >> c[i];
cout << 6;
for (int i = 7; i <= 11; i++) cout << c[i];
cout << endl;
}
}
return 0;
}
- HDU2082 找單詞
題目鏈接
Problem Description
假設有x1個字母A， x2個字母B,….. x26個字母Z，同時假設字母A的價值為1，字母B的價值為2,….. 字母Z的價值為26。那麼，對於給定的字母，可以找到多少價值<=50的單詞呢？單詞的價值就是組成一個單詞的所有字母的價值之和，比如，單詞ACM的價值是1+3+14=18，單詞HDU的價值是8+4+21=33。(組成的單詞與排列順序無關，比如ACM與CMA認為是同一個單詞）。
Input
輸入首先是一個整數N，代表測試實例的個數。
然後包括N行數據，每行包括26個<=20的整數x1,x2,…..x26.
Output
對於每個測試實例，請輸出能找到的總價值<=50的單詞數,每個實例的輸出佔一行。
Sample Input
2
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9
Sample Output
7
379297
多重背包，把26個字母看做26種物品，容量50
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n, num[101], val[101];
int dp[101][101];
int main() {
while (scanf("%d", &n) != EOF) {
while (n--) {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= 26; i++) {
val[i] = i;
scanf("%d", &num[i]);
}
dp[0][0] = 1;
for (int i = 1; i <= 26; i++)
for (int j = 0; j <= 50; j++)
for (int k = 0; k <= num[i]; k++)
if (val[i] * k <= j)
dp[i][j] += dp[i - 1][j - val[i] * k];
else break;
int ans = 0;
for (int i = 1; i <= 50; i++)
ans += dp[26][i];
printf("%d\n", ans);
}
}
return 0;
}
- HDU2083 簡易版之最短距離
題目鏈接
Problem Description
寒假的時候，ACBOY要去拜訪很多朋友，恰巧他所有朋友的家都處在坐標平面的X軸上。ACBOY可以任意選擇一個朋友的家開始訪問，但是每次訪問後他都必須回到出發點，然後才能去訪問下一個朋友。
比如有4個朋友，對應的X軸坐標分別為1， 2， 3， 4。當ACBOY選擇坐標為2的點做為出發點時，則他最終需要的時間為 |1-2|+|2-2|+|3-2|+|4-2| = 4。
現在給出Ｎ個朋友的坐標，那麼ACBOY應該怎麼走才會花費時間最少呢？
Input
輸入首先是一個正整數M，表示M個測試實例。每個實例的輸入有2行，首先是一個正整數N（N <= 500)，表示有N個朋友，下一行是N個正整數，表示具體的坐標(所有數據均<=10000).
Output
對於每一個測試實例，請輸出訪問完所有朋友所花的最少時間，每個實例的輸出佔一行。
Sample Input
2
2
2 4
3
2 4 6
Sample Output
2
4
二話不說，直接暴力
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define INF 1e7 + 1
using namespace std;
int m, n, a[501];
int main() {
while (scanf("%d", &m) != EOF) {
while (m--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = INF;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= n; j++)
sum += abs(a[i] - a[j]);
ans = min(ans, sum);
}
printf("%d\n", ans);
}
}
return 0;
}
- HDU2084 數塔
題目鏈接
Problem Description
在講述DP演算法的時候，一個經典的例子就是數塔問題，它是這樣描述的：
有如下所示的數塔，要求從頂層走到底層，若每一步只能走到相鄰的結點，則經過的結點的數字之和最大是多少？
已經告訴你了，這是個DP的題目，你能AC嗎?
Input
輸入數據首先包括一個整數C,表示測試實例的個數，每個測試實例的第一行是一個整數N(1 <= N <= 100)，表示數塔的高度，接下來用N行數字表示數塔，其中第i行有個i個整數，且所有的整數均在區間[0,99]內。
Output
對於每個測試實例，輸出可能得到的最大和，每個實例的輸出佔一行。
Sample Input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
既然題目都說了DP那就DP唄，從下往上推，最後輸出dp[1][1]即可
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int c, n;
int a[101][101], dp[101][101];
int main() {
while (scanf("%d", &c) != EOF) {
while (c--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
for (int i = n; i >= 1; i--)
for (int j = 1; j <= i; j++)
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j];
printf("%d\n", dp[1][1]);
}
}
return 0;
}
- HDU2085 核反應堆
題目鏈接
Problem Description
某核反應堆有兩類事件發生：
高能質點碰擊核子時，質點被吸收，放出3個高能質點和1個低能質點；
低能質點碰擊核子時，質點被吸收，放出2個高能質點和1個低能質點。
假定開始的時候（0微秒）只有一個高能質點射入核反應堆，每一微秒引起一個事件發生(對於一個事件，當前存在的所有質點都會撞擊核子)，試確定n微秒時高能質點和低能質點的數目。
Input
輸入含有一些整數n(0≤n≤33)，以微秒為單位，若n為-1表示處理結束。
Output
分別輸出n微秒時刻高能質點和低能質點的數量，高能質點與低能質點數量之間以逗號空格分隔。每個輸出佔一行。
Sample Input
5 2
-1
Sample Output
571, 209
11, 4
提示
可以使用long long int對付GNU C++，使用__int64對付VC6
算算數洒洒水，高能質點的數量就是前一微秒的高能質點 * 3 + 低能質點 * 2，低能質點的數量就是前一微秒的高能質點 + 低能質點
然後注意初始化a[0] = 1, b[0] = 0即可
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
long long a[34], b[34];
int main() {
while (scanf("%d", &n) != EOF) {
if (n == -1) break;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
a[0] = 1;
b[0] = 0;
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] * 3 + b[i - 1] * 2;
b[i] = a[i - 1] + b[i - 1];
}
printf("%lld, %lld\n", a[n], b[n]);
}
return 0;
}
- HDU2086 A1 = ?
題目鏈接
Problem Description
有如下方程：Ai = (Ai-1 + Ai+1)/2 – Ci (i = 1, 2, 3, …. n).
若給出A0, An+1, 和 C1, C2, …..Cn.
請編程計算A1 = ?
Input
輸入包括多個測試實例。
對於每個實例，首先是一個正整數n,(n <= 3000); 然後是2個數a0, an+1.接下來的n行每行有一個數ci(i = 1, ….n);輸入以文件結束符結束。
Output
對於每個測試實例，用一行輸出所求得的a1(保留2位小數).
Sample Input
1
50.00
25.00
10.00
2
50.00
25.00
10.00
20.00
Sample Output
27.50
15.00
這，是一道數學題，就由題目給的公式去推
因為：
Ai = (Ai - 1 + Ai + 1) / 2 - Ci
可得：
A1+A1 = A0+A2 - 2(C1)
A1+A2 = A0+A3 - 2(C1+C2)
A1+A3 = A0+A4 - 2(C1+C2+C3)
...
A1+An = A0+An+1 - 2(C1+C2+...+Cn)
左右均求和可得：
(n+1)A1+(A2+A3+...+An) = nA0 +(A2+A3+...+An) + An+1 - 2(nC1+(n-1)C2+...+2Cn-1+Cn)
化簡得：
A1 = [nA0 + An+1 - 2(nC1+(n-1)C2+...+2Cn-1+Cn)]/(n+1)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
double cnt, a0, an1, a1, c[3001];
int main() {
while (scanf("%d", &n) != EOF) {
scanf("%lf%lf", &a0, &an1);
cnt = 0;
for (int i = 1; i <= n; i++)
scanf("%lf", &c[i]);
for (int i = 1; i <= n; i++)
cnt += 2 * i * c[n - i + 1];
a1 = (n * a0 + an1 - cnt) / (n + 1);
printf("%.2lf\n", a1);
}
return 0;
}
- HDU2086 剪花布條
題目鏈接
Problem Description
一塊花布條，裡面有些圖案，另有一塊直接可用的小飾條，裡面也有一些圖案。對於給定的花布條和小飾條，計算一下能從花布條中儘可能剪出幾塊小飾條來呢？
Input
輸入中含有一些數據，分別是成對出現的花布條和小飾條，其布條都是用可見ASCII字元表示的，可見的ASCII字元有多少個，布條的花紋也有多少種花樣。花紋條和小飾條不會超過1000個字元長。如果遇見#字元，則不再進行工作。
Output
輸出能從花紋布中剪出的最多小飾條個數，如果一塊都沒有，那就老老實實輸出0，每個結果之間應換行。
Sample Input
abcde a3
aaaaaa aa
『#』（為了排版加了引號）
Sample Output
0
3
KMP！！不會，就普普通通的做法然後水了過去…但是！！！
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
char a[1005], b[1005];
int main() {
while (scanf("%s", a) != EOF) {
if (a[0] == '#') break;
scanf("%s", b);
int len1 = strlen(a);
int len2 = strlen(b);
int cnt = 0;
int ans = 0;
for (int i = 0; i < len1; i++) {
if (a[i] == b[cnt]) {
cnt++;
if (cnt == len2) {
ans++;
cnt = 0;
}
} else {
cnt = 0;
}
}
printf("%d\n", ans);
}
return 0;
}
但是！！！我在寫題解的時候猛然發現，這個做法肯定是不正確的！例如說輸入樣例abababc ababc，上述做法的答案是0，但實際上應該是1
所以，還是乖乖kmp吧，交上去CE了不知道為啥，但是本地是沒事的…不知道為啥
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
char a[1005], b[1005];
int len1, len2, next[1005];
void getnext() {
int cnt = 0;
int k = -1;
next[0] = -1;
while (cnt < len2) {
if(k == -1 || b[cnt] == b[k]) {
cnt++;
k++;
next[cnt]=k;
} else k = next[k];
}
}
int kmp() {
getnext();
int i = 0, j = 0;
int cnt=0;
while (i < len1) {
if (j == -1 || a[i] == b[j]) {
i++;
j++;
} else j = next[j];
if (j == len2) {
cnt++;
j = 0;
}
}
return cnt;
}
int main() {
while (scanf("%s", a) != EOF) {
if (a[0] == '#') break;
scanf("%s", b);
len1 = strlen(a);
len2 = strlen(b);
printf("%d\n", kmp());
}
return 0;
}
- HDU2088 Box of Bricks
題目鏈接
Problem Description
Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. 「Look, I’ve built a wall!」, he tells his older sister Alice. 「Nah, you should make all stacks the same height. Then you would have a real wall.」, she retorts. After a little consideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?
Input
The input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights hi of the n stacks. You may assume 1≤n≤50 and 1≤hi≤100.
The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height.
The input is terminated by a set starting with n = 0. This set should not be processed.
Output
For each set, print the minimum number of bricks that have to be moved in order to make all the stacks the same height.
Output a blank line between each set.
Sample Input
6
5 2 4 1 7 5
0
Sample Output
5
比平均高度矮的高的差值都加起來除以2就好了
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n, h[51], flag;
int main() {
while (scanf("%d", &n) != EOF) {
if (n == 0) break;
if (flag != 0) printf("\n");
flag = 1;
int sum = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i]);
sum += h[i];
}
sum /= n;
int ans = 0;
for (int i = 1; i <= n; i++)
ans += abs(sum - h[i]);
printf("%d\n", ans / 2);
}
return 0;
}
