Hướng dẫn giải của Lớn nhất (Đề HSG KonTum 2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có m bài toán (mỗi dòng là một bài) và n đội (mỗi cột là một đội). Cần tính tổng phần thưởng của từng đội rồi lấy tổng lớn nhất. Giá trị mỗi phần thưởng không quá 300 nên tổng không vượt quá 300 · m, dùng long long cho chắc.
Sub 1: Vét cạn — ~O(m^2 \cdot n)~
Với mỗi đội j, mỗi lần xét bài i lại cộng lại toàn bộ các phần thưởng từ bài 1 đến i để tính tổng, rồi so sánh với tổng lớn nhất. Cách này đúng nhưng tính lặp lại nhiều lần.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("LONNHAT.INP", "r")) { freopen("LONNHAT.INP", "r", stdin); freopen("LONNHAT.OUT", "w", stdout); }
int m, n; // m bai toan (so dong), n doi (so cot)
cin >> m >> n;
vector<vector<long long>> a(m, vector<long long>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) cin >> a[i][j];
// Vet can: voi moi doi j, tinh tong bang cach cong lai tu dau moi lan (tinh lai tong tien to)
long long best = LLONG_MIN;
for (int j = 0; j < n; j++) {
long long total = 0;
for (int i = 0; i < m; i++) {
total = 0;
for (int k = 0; k <= i; k++) total += a[k][j]; // tinh lai tong tu dau den bai i
}
best = max(best, total);
}
cout << best << "\n";
return 0;
}
Sub 2: Cộng dồn theo cột — ~O(m \cdot n)~
Đọc từng dòng và cộng giá trị vào sum[j] của đội tương ứng, mỗi phần thưởng chỉ được cộng đúng một lần. Sau khi đọc hết, đáp án là phần tử lớn nhất của mảng sum.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("LONNHAT.INP", "r")) { freopen("LONNHAT.INP", "r", stdin); freopen("LONNHAT.OUT", "w", stdout); }
int m, n; // m bai toan (so dong), n doi (so cot)
cin >> m >> n;
// sum[j] = tong phan thuong cua doi j sau khi cong don tung bai
vector<long long> sum(n, 0);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
long long v;
cin >> v;
sum[j] += v;
}
cout << *max_element(sum.begin(), sum.end()) << "\n";
return 0;
}
Bình luận