Tổng kết giải đấu CSP-S ngày 2 tháng 8
1. Kết quả làm bài
- Bài 1: Làm được 20 điểm trong lúc thi, sau thi đạt AC.
- Bài 2: Làm được 0 điểm trong lúc thi, sau thi đạt AC.
- Bài 3: Làm được 0 điểm trong lúc thi, sau thi đạt AC.
- Bài 4: Làm được 0 điểm trong lúc thi, sau thi đạt 50 điểm.
- Tổng điểm thi đấu: 20/400. Sau thi đạt 350/400.
2. Tổng quan giải đấu
Giải đấu mô phỏng lần này khá khó. Bài 1 tôi đọc đề khá lâu mà không nghĩ ra cách giải, sau khi nghĩ ra thì lại tự hack được chính mình (thực ra có một cách giải đúng). Lúc đó chỉ còn 90 phút. Bài 2 thì cũng ổn, nhưng tôi không nghĩ ra được thuật toán tham lam (vì lúc đó tôi nghĩ là có thể dùng nhị phân tìm đáp án, nhưng check thì lại không ra). Bài 3 và 4 đọc qua thì thấy mình không làm được, đành phải tìm cách lấy điểm sàn. Kết quả rất tệ.
3. Báo cáo lời giải
Bài 1:
Đề bài:
(Nội dung đề bài gốc đã bị loại bỏ)
Lời giải:
Đây là bài toán dùng tiền tố tổng (prefix sum). Dãy có thể là dạng núi, tăng dần, hoặc giảm dần. Sau đó áp dụng tiền tố tổng là có thể giải quyết bài toán một cách dễ dàng.
Mã nguồn AC:
#include <iostream>
#include <vector>
#include <algorithm>
// Sử dụng `long long` cho các số nguyên lớn
using ll = long long;
int main() {
// Tối ưu hóa I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
// Mở tệp đầu vào và đầu ra
freopen("hot.in", "r", stdin);
freopen("hot.out", "w", stdout);
int n;
ll T;
std::cin >> n >> T;
// Lưu trữ mảng, và các mảng phụ để lưu vị trí đỉnh núi
std::vector<ll> arr(n + 2);
std::vector<int> left_peak(n + 1);
std::vector<int> right_peak(n + 1);
// Gán giá trị biên để xử lý trường hợp đặc biệt
arr[0] = -1;
arr[n + 1] = 2e9;
int last_peak_idx = 0;
// Tính toán vị trí đỉnh núi bên trái cho mỗi phần tử
for (int i = 1; i <= n; ++i) {
std::cin >> arr[i];
if (arr[i] > arr[i - 1]) {
last_peak_idx = i;
}
left_peak[i] = last_peak_idx;
}
last_peak_idx = n + 1;
// Tính toán vị trí đỉnh núi bên phải cho mỗi phần tử
for (int i = n; i >= 1; --i) {
if (arr[i] > arr[i + 1]) {
last_peak_idx = i;
}
right_peak[i] = last_peak_idx;
}
// Xử lý các truy vấn
while (T--) {
int query_left, query_right;
std::cin >> query_left >> query_right;
// Kiểm tra xem đỉnh núi bên phải của điểm bắt đầu có nằm trong phạm vi truy vấn
// và có lớn hơn hoặc bằng đỉnh núi bên trái của điểm kết thúc hay không
if (right_peak[query_left] >= left_peak[query_right]) {
std::cout << "Y\n";
} else {
std::cout << "N\n";
}
}
return 0;
}
Bài 2:
Đề bài:
(Nội dung đề bài gốc đã bị loại bỏ)
Lời giải:
Đây là bài toán yêu cầu tìm thuật toán tham lam. Cần tự mình suy luận ra công thức.
Mã nguồn AC:
#include <iostream>
#include <vector>
#include <numeric> // Thêm thư viện numeric cho std::accumulate nếu cần
// Sử dụng `long long` cho các số nguyên lớn
using ll = long long;
int main() {
// Tối ưu hóa I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
// Mở tệp đầu vào và đầu ra
freopen("divide.in", "r", stdin);
freopen("divide.out", "w", stdout);
int n;
std::cin >> n;
// Đọc mảng đầu vào
std::vector<ll> sequence(n);
for (int i = 0; i < n; ++i) {
std::cin >> sequence[i];
}
ll current_val = sequence.back(); // Lấy giá trị cuối cùng
ll total_operations = 0;
// Duyệt từ phần tử thứ hai từ cuối trở về đầu
for (int i = n - 2; i >= 0; --i) {
if (sequence[i] > current_val) {
// Tính số lần chia cần thiết
ll num_ops = (sequence[i] - 1) / current_val;
total_operations += num_ops;
// Cập nhật giá trị hiện tại sau khi chia
current_val = sequence[i] / (num_ops + 1);
} else {
// Nếu giá trị hiện tại nhỏ hơn hoặc bằng giá trị trước đó, chỉ cập nhật giá trị
current_val = sequence[i];
}
}
std::cout << total_operations;
return 0;
}
Bài 3:
Đề bài:
(Nội dung đề bài gốc đã bị loại bỏ)
Lời giải:
Đây là bài toán sử dụng quy hoạch động tuyến tính. Công thức chuyển trạng thái là:
dp[i1] = max(dp[i1-2] + max(0, a[i][i1-1] + a[i][i1]), dp[i1-1]). Từ đó có thể giải được.
Mã nguồn AC:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// Mở tệp đầu vào và đầu ra
freopen("tunnel.in", "r", stdin);
freopen("tunnel.out", "w", stdout);
int n_rows, m_cols;
cin >> n_rows >> m_cols;
// Ma trận giá trị
vector<vector<int>> matrix(n_rows + 1, vector<int>(m_cols + 1));
for (int i = 1; i <= n_rows; ++i) {
for (int j = 1; j <= m_cols; ++j) {
cin >> matrix[i][j];
}
}
ll total_max_value = 0;
// Tính toán theo hàng
vector<int> dp_row(m_cols + 1, 0);
for (int i = 1; i <= n_rows; ++i) {
for (int j = 2; j <= m_cols; ++j) {
// Công thức DP: chọn cặp liền kề hoặc bỏ qua phần tử hiện tại
dp_row[j] = max(dp_row[j - 2] + max(0, matrix[i][j - 1] + matrix[i][j]), dp_row[j - 1]);
}
// Cộng kết quả tối ưu của hàng vào tổng
total_max_value += dp_row[m_cols];
}
// Đặt lại DP để tính toán theo cột
fill(dp_row.begin(), dp_row.end(), 0);
// Tính toán theo cột
vector<int> dp_col(n_rows + 1, 0);
for (int j = 1; j <= m_cols; ++j) {
for (int i = 2; i <= n_rows; ++i) {
// Công thức DP: chọn cặp liền kề hoặc bỏ qua phần tử hiện tại
dp_col[i] = max(dp_col[i - 2] + max(0, matrix[i - 1][j] + matrix[i][j]), dp_col[i - 1]);
}
// Cộng kết quả tối ưu của cột vào tổng
total_max_value += dp_col[n_rows];
}
cout << total_max_value;
return 0;
}
Bài 4:
Đề bài:
(Nội dung đề bài gốc đã bị loại bỏ)
Lời giải:
Lời giải chính xác sử dụng cây đoạn (segment tree), nhưng tôi không làm được. Với 50 điểm, tôi đã thử một cách tiếp cận đơn giản hơn.
Mã nguồn (50 điểm):
#include <iostream>
#include <vector>
#include <algorithm>
const int MAXN = 2e5 + 5;
int n;
int a[MAXN]; // Mảng chứa các phần tử
int last_occurrence[MAXN]; // Vị trí xuất hiện cuối cùng của mỗi số
int next_occurrence[MAXN]; // Vị trí xuất hiện kế tiếp của cùng một số
int right_boundary[MAXN]; // Giới hạn bên phải có thể vươn tới
int occurrence_rank[MAXN]; // Thứ tự xuất hiện của phần tử tại vị trí i
struct SegmentTreeNode {
int left_bound;
int right_bound;
int min_val; // Lưu trữ giá trị nhỏ nhất (vị trí)
};
SegmentTreeNode tree[MAXN * 4];
std::vector<int> positions[MAXN]; // Lưu trữ tất cả các vị trí xuất hiện của mỗi số
// Xây dựng cây đoạn
void build_segment_tree(int node, int l, int r) {
tree[node].left_bound = l;
tree[node].right_bound = r;
tree[node].min_val = n + 1; // Khởi tạo với giá trị lớn hơn n
if (l == r) return;
int mid = (l + r) / 2;
build_segment_tree(node * 2, l, mid);
build_segment_tree(node * 2 + 1, mid + 1, r);
}
// Truy vấn cây đoạn để tìm giới hạn bên phải có thể đạt tới
int query_segment_tree(int node, int k) {
// Nếu k nằm ngoài phạm vi hoặc giá trị nhỏ nhất trong nút lớn hơn k, trả về 0
if (k < tree[node].left_bound || tree[node].min_val > k) return 0;
// Nếu là nút lá
if (tree[node].left_bound == tree[node].right_bound) return tree[node].right_bound;
// Ưu tiên cây con trái
if (k <= tree[node * 2].right_bound) {
int temp_result = query_segment_tree(node * 2, k);
// Nếu cây con trái đạt tới giới hạn cuối, thử cây con phải
if (temp_result == tree[node * 2].right_bound) {
int right_result = query_segment_tree(node * 2 + 1, k);
if (right_result) return right_result;
else return temp_result;
} else {
return temp_result;
}
}
// Nếu k nằm ngoài phạm vi cây con trái, truy vấn cây con phải
return query_segment_tree(node * 2 + 1, k);
}
// Cập nhật giá trị trong cây đoạn
void update_segment_tree(int node, int pos, int val) {
if (tree[node].left_bound == tree[node].right_bound) {
tree[node].min_val = val;
return;
}
int mid = (tree[node].left_bound + tree[node].right_bound) / 2;
if (pos <= mid) {
update_segment_tree(node * 2, pos, val);
} else {
update_segment_tree(node * 2 + 1, pos, val);
}
// Cập nhật giá trị nhỏ nhất của nút cha
tree[node].min_val = std::min(tree[node * 2].min_val, tree[node * 2 + 1].min_val);
}
int main() {
scanf("%d", &n);
// Đọc mảng và lưu trữ vị trí xuất hiện
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
positions[a[i]].push_back(i);
occurrence_rank[i] = positions[a[i]].size(); // Lưu thứ tự xuất hiện
}
// Tính toán vị trí xuất hiện kế tiếp
for (int i = n; i >= 1; --i) {
last_occurrence[i] = n + 1; // Khởi tạo với giá trị lớn
}
for (int i = n; i >= 1; --i) {
next_occurrence[i] = last_occurrence[a[i]];
last_occurrence[a[i]] = i;
}
build_segment_tree(1, 1, n); // Xây dựng cây đoạn
ll total_pairs = n; // Khởi tạo với n cặp (mỗi phần tử tự nó là một cặp)
// Duyệt từ cuối mảng lên
for (int i = n; i >= 1; --i) {
// Tính toán giới hạn bên phải dựa trên các điều kiện
if (next_occurrence[i] == n + 1 || i + 1 > next_occurrence[i] - 1 || right_boundary[i + 1] < next_occurrence[i] - 1 || a[i + 1] != a[next_occurrence[i] - 1]) {
right_boundary[i] = i;
} else {
int candidate_bound = right_boundary[next_occurrence[i]];
candidate_bound = std::min(candidate_bound, query_segment_tree(1, next_occurrence[i]));
if (candidate_bound == 0) { // Không tìm thấy giới hạn hợp lệ
right_boundary[i] = next_occurrence[i];
total_pairs++; // Tăng số cặp
} else {
// Tìm vị trí xuất hiện trước đó của số tại candidate_bound
int prev_occurrence_idx = std::upper_bound(positions[a[i]].begin(), positions[a[i]].end(), candidate_bound) - positions[a[i]].begin();
right_boundary[i] = positions[a[i]][prev_occurrence_idx - 1];
// Cộng thêm số cặp mới được tạo ra
total_pairs += (prev_occurrence_idx - occurrence_rank[i]);
}
}
// Cập nhật cây đoạn với vị trí xuất hiện kế tiếp
if (next_occurrence[i] <= n) {
update_segment_tree(1, next_occurrence[i], i);
}
}
printf("%lld\n", total_pairs);
return 0;
}
4. Tổng kết sau giải đấu
Thua quá thảm hại. (fuck €€£)