题目发布于2021年9月23日上午十点。
Problem A
有形如\(ax^3+bx^2+cx+d=0\)这样的一个一元三次方程。给出该方程中各项的系数（\(a,bc,d\)均为实数），并约定该方程存在三个不同实根（根的范围为\([-100,100]\)），且根与根之差的绝对值不小于\(1\)。要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后\(2\)位。
输入数据
输入该方程中各项的系数（\(a,b,c,d\)均为浮点数）。
输出数据
由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后\(2\)位。
样例输入
样例输出
题解
二分法的题目。由于该一元三次方程必有三个实根，记\(f(x)=ax^3+bx^2+cx+d\)，则\(f'(x)\)必有两个相异实根\(x_1\)与\(x_2\)，不妨记\(x_1 <
x_2\)，由三次函数的性质及题设可知：三个实根分别在\((-100, x1),(x1, x2),(x2,
100)\)三个区间内。
对三个区间运用二分法即可。注意输出时候要设置格式。
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
33
34
35
| #include <iostream>
#include <iomanip>
using namespace std;
double a, b, c, d;
double f(double x) {
return (a * x * x * x + b * x * x + c * x + d);
}
double find_solution(double start, double end) {
if (end - start < 0.01) {
return (start + end) / 2;
}
else {
double fl = f(start);
double fm = f((start + end) / 2.0);
if (fl * fm < 0) {
return find_solution(start, (start + end) / 2.0 - 0.0001);
}
else{
return find_solution((start + end) / 2.0 + 0.0001, end);
}
}
}
int main() {
cin >> a >> b >> c >> d;
double seg1 = -100, seg4 = 100;
double seg2 = min((-b + sqrt(b * b - 3 * a * c)) / (3 * a), (-b - sqrt(b * b - 3 * a * c)) / (3 * a));
double seg3 = max((-b + sqrt(b * b - 3 * a * c)) / (3 * a), (-b - sqrt(b * b - 3 * a * c)) / (3 * a));
double x1, x2, x3;
x1 = find_solution(seg1, seg2);
x2 = find_solution(seg2, seg3);
x3 = find_solution(seg3, seg4);
cout << setiosflags(ios::fixed) << setprecision(2) << x1 << ' ' << x2 << ' ' << x3 << endl;
return 0;
}
|
Problem B
0-1背包问题的裸题。
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
| #include <iostream>
#include <vector>
using namespace std;
int main() {
int N, t;
cin >> N >> t;
vector<int> w, v;
w.push_back(0);
v.push_back(0);
for(int i = 0; i < N; i++){
int like, cost;
cin >> like >> cost;
v.push_back(like);
w.push_back(cost);
}
vector<vector<int>> dp(N + 1, vector<int>(t + 1, 0));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= t; j++) {
if (j < w[i]) {
dp[i][j] = dp[i - 1][j];
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
cout << dp[N][t] << endl;
return 0;
}
|
Problem C
暴力枚举。
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
| #include <iostream>
using namespace std;
const int N = 101;
int arr[N];
bool valid(int a, int b, int c) {
return a + b > c && a + c > b && b + c > a;
}
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
int ans = -1;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
for(int k = j + 1; k < n; k++) {
if(valid(arr[i], arr[j], arr[k])) {
ans = max(ans, arr[i] + arr[j] + arr[k]);
}
}
}
}
cout << ans << endl;
return 0;
}
|
Problem D
题目描述
在一个被分成\(n \times
n\)个格子的平原上，有一些格子有铁矿，两格铁矿如果相邻那么就认为他们属于同一个矿床，每个矿床都包含一个或更多个铁矿，问一共有几个矿床。两个格子只要有公共边或公共点就算相邻。
输入数据
输入包括\(n+1\)行。
第一行为一个正整数\(n(n \leq
1000)\)。
接下来有\(n\)行，每行有\(n\)个字符，#
表示平原的对应位置有铁矿，* 代表没有。
输出数据
矿床个数。
样例输入
1
2
3
4
5
6
7
| 6
*#*###
###*#*
*##***
*#****
***###
******
|
样例输出
题解
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
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
#include <vector>
#include <string>
using namespace std;
int totalCount = 0;
const int dx[8] = { 0, 0, -1, 1, 1, -1, 1, -1 }, dy[8] = {1, -1, 0, 0, 1, 1, -1, -1};
void traverseMap(vector<string>& field, int row, int col) {
if (row < 0 || col < 0 || row >= field.size() || col >= field.size() || field[row][col] == '*') {
return;
}
field[row][col] = '*';
for (int i = 0; i < 8; i++) {
traverseMap(field, row + dx[i], col + dy[i]);
}
}
void mineCount(vector<string>& field) {
for (int i = 0; i < field.size(); i++) {
for (int j = 0; j < field.size(); j++) {
if (field[i][j] == '#') {
totalCount++;
traverseMap(field, i, j);
}
}
}
}
int main() {
int n;
cin >> n;
if (n > 0) {
vector<string> field(n);
for (auto& str : field) cin >> str;
mineCount(field);
}
cout << totalCount << endl;
return 0;
}
|
Problem E
优先队列裸题。
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
33
34
| #include <iostream>
#include <priority_queue>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
priority_queue<int, vector<int>, greater<int>> Q;
for (int i = 0; i < N; i++) {
int temp;
cin >> temp;
Q.push(temp);
}
int ans = 0;
for (int i = 0; i < N - 1; i++) {
int tempSum = Q.top();
Q.pop();
tempSum += Q.top();
Q.pop();
Q.push(tempSum);
ans += tempSum;
}
cout << ans << endl;
return 0;
}
|
