Đây là lần đầu tiên kỳ thi CSP-J và CSP-S được tổ chức song song, cho phép học sinh tham gia cả hai vòng trong cùng một năm.
Bài 1: Trích xuất và sắp xếp chữ số
Nhiệm vụ yêu cầu đọc một chuỗi ký tự, trích xuất tất cả ký tự số (‘0’–‘9’), sau đó in ra theo thứ tự giảm dần. Không cần xử lý số có nhiều chữ số — chỉ xét từng ký tự riêng lẻ.
Bài 2: Xác định vị trí ghế theo thứ hạng
Cho ma trận ghế kích thước n × m được lưu dưới dạng mảng một chiều, với phần tử đầu tiên là điểm số của thí sinh R. Cần xác định hàng và cột thực tế của R sau khi sắp xếp toàn bộ điểm theo thứ tự giảm dần — với quy tắc: hàng chẵn thì đánh số cột từ phải sang trái.
Bài 3: Phân đoạn mảng để đạt XOR bằng k
Cho mảng số nguyên và giá trị k, cần chia mảng thành nhiều đoạn liên tiếp sao cho XOR của mỗi đoạn bằng k. Mục tiêu là tối đa hóa số đoạn. Giải pháp sử dụng kỹ thuật greedy kết hợp bảng băm động (hash table) để theo dõi các giá trị XOR tiền tố đã gặp.
Bài 4: Đếm đa giác hợp lệ từ thanh gỗ
Cho n thanh gỗ có độ dài nguyên dương, đếm số cách chọn ba hoặc nhiều thanh để tạo thành đa giác đơn (tổng độ dài n−1 cạnh lớn hơn cạnh còn lại). Sau khi sắp xếp tăng dần, sử dụng quy hoạch động với trạng thái f[i][s] là số cách chọn tập con từ i phần tử đầu có tổng bằng s, đồng thời giới hạn tổng không vượt quá giá trị lớn nhất trong mảng để đảm bảo độ phức tạp O(n²).
Nhiệm vụ yêu cầu đọc một chuỗi ký tự, trích xuất tất cả ký tự số (‘0’–‘9’), sau đó in ra theo thứ tự giảm dần. Không cần xử lý số có nhiều chữ số — chỉ xét từng ký tự riêng lẻ.
Giải pháp C++ hiệu quả
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
int main() {
std::ifstream fin("number.in");
std::ofstream fout("number.out");
std::string input;
fin >> input;
std::vector<int> digits;
for (char c : input) {
if (c >= '0' && c <= '9') {
digits.push_back(c - '0');
}
}
std::sort(digits.begin(), digits.end(), std::greater<int>());
for (int d : digits) {
fout << d;
}
return 0;
}Cho ma trận ghế kích thước n × m được lưu dưới dạng mảng một chiều, với phần tử đầu tiên là điểm số của thí sinh R. Cần xác định hàng và cột thực tế của R sau khi sắp xếp toàn bộ điểm theo thứ tự giảm dần — với quy tắc: hàng chẵn thì đánh số cột từ phải sang trái.
Cài đặt không dùng đệ quy, dễ bảo trì
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
int main() {
std::ifstream fin("seat.in");
std::ofstream fout("seat.out");
int n, m;
fin >> n >> m;
int total = n * m;
std::vector<int> scores(total + 1);
for (int i = 1; i <= total; ++i) {
fin >> scores[i];
}
int rScore = scores[1];
std::vector<int> sorted = scores;
std::sort(sorted.begin() + 1, sorted.end(), std::greater<int>());
int rank = 1;
while (rank <= total && sorted[rank] != rScore) ++rank;
int row = (rank - 1) / n + 1;
int col = (rank - 1) % n + 1;
if (row % 2 == 0) {
col = n - col + 1;
}
fout << row << " " << col;
return 0;
}Cho mảng số nguyên và giá trị k, cần chia mảng thành nhiều đoạn liên tiếp sao cho XOR của mỗi đoạn bằng k. Mục tiêu là tối đa hóa số đoạn. Giải pháp sử dụng kỹ thuật greedy kết hợp bảng băm động (hash table) để theo dõi các giá trị XOR tiền tố đã gặp.
Phiên bản tối ưu hóa bộ nhớ và thời gian
#include <iostream>
#include <vector>
#include <unordered_set>
#include <fstream>
int main() {
std::ifstream fin("xor.in");
std::ofstream fout("xor.out");
int n, k;
fin >> n >> k;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) fin >> a[i];
int segments = 0;
int i = 1;
while (i <= n) {
std::unordered_set<int> seen;
int prefix = 0;
bool found = false;
for (int j = i; j <= n; ++j) {
prefix ^= a[j];
if (seen.count(prefix ^ k)) {
segments++;
i = j + 1;
found = true;
break;
}
seen.insert(prefix);
}
if (!found) break;
}
fout << segments;
return 0;
}Cho n thanh gỗ có độ dài nguyên dương, đếm số cách chọn ba hoặc nhiều thanh để tạo thành đa giác đơn (tổng độ dài n−1 cạnh lớn hơn cạnh còn lại). Sau khi sắp xếp tăng dần, sử dụng quy hoạch động với trạng thái f[i][s] là số cách chọn tập con từ i phần tử đầu có tổng bằng s, đồng thời giới hạn tổng không vượt quá giá trị lớn nhất trong mảng để đảm bảo độ phức tạp O(n²).
Cải tiến rõ ràng về cấu trúc và tính đúng đắn
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
const int MOD = 998244353;
int main() {
std::ifstream fin("polygon.in");
std::ofstream fout("polygon.out");
int n;
fin >> n;
std::vector<long long> a(n + 1);
long long maxVal = 0;
for (int i = 1; i <= n; ++i) {
fin >> a[i];
maxVal = std::max(maxVal, a[i]);
}
std::sort(a.begin() + 1, a.end());
// dp[s] = số cách đạt tổng s
std::vector<long long> dp(maxVal + 1, 0);
dp[0] = 1;
long long result = 0;
for (int i = 1; i <= n; ++i) {
// Cập nhật kết quả: với mỗi tổng s hiện tại, nếu s > a[i],
// thì có thể thêm a[i] làm cạnh lớn nhất
for (int s = maxVal; s >= a[i]; --s) {
if (s > a[i]) {
result = (result + dp[s - a[i]] * (i - 1)) % MOD;
}
}
// Cập nhật dp ngược để tránh dùng lại cùng một phần tử
for (int s = maxVal; s >= a[i]; --s) {
dp[s] = (dp[s] + dp[s - a[i]]) % MOD;
}
}
fout << result;
return 0;
}