Bài A - Kiểm tra chuỗi ABC
Cho chuỗi 3 ký tự, xác định xem chuỗi đó có chứa đủ 3 ký tự A, B, C hay không.
Giải pháp: Đếm tần suất xuất hiện từng ký tự bằng mảng đếm.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
sort(s.begin(), s.end());
cout << (s == "ABC" ? "Yes" : "No");
return 0;
}
Bài B - Tính ô an toàn trên bàn cờ
Trên bàn cờ 8×8, các ô '#' sẽ tấn công toàn bộ hàng và cột chứa nó. Đếm số ô không bị tấn công.
Giải pháp: Sử dụng 2 mảng boolean để đánh dấu hàng/cột bị tấn công.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<bool> row(8), col(8);
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 8; ++j) {
char c;
cin >> c;
if (c == '#') {
row[i] = col[j] = true;
}
}
}
int count = 0;
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 8; ++j) {
if (!row[i] && !col[j]) ++count;
}
}
cout << count;
return 0;
}
C - Đếm ô an toàn với nước đi mã
Trên lưới n×n, các quân mã tấn công theo nước đi chữ L. Đếm số ô không bị tấn công.
Giải pháp: Sử dụng set để lưu trữ các ô bị tấn công.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
int dx[8] = {2,1,-1,-2,-2,-1,1,2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};
int main() {
int n, m;
cin >> n >> m;
set<pair<int,int>> attacked;
while (m--) {
int x, y;
cin >> x >> y;
attacked.insert({x,y});
for (int i = 0; i < 8; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
attacked.insert({nx, ny});
}
}
}
cout << n * n - attacked.size();
return 0;
}
D - Đếm khoảng con hợp lệ
Tìm số cặp (l, r) sao cho không chứa bất kỳ đoạn [L_i, R_i] nào hoàn toàn.
Giải pháp: Sử dụng mảng tiền xử lý để lưu giá trị l tối đa.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> dp(m + 2, 1);
while (n--) {
int l, r;
cin >> l >> r;
dp[r] = max(dp[r], l + 1);
}
for (int i = 1; i <= m; ++i) {
dp[i] = max(dp[i], dp[i - 1]);
}
long long res = 0;
for (int r = 1; r <= m; ++r) {
res += r - dp[r] + 1;
}
cout << res;
return 0;
}
E - Lặp lại hoán vị K lần
Áp dụng phép biến đổi hoán vị K lần: P_i = P[P_i].
Giải pháp: Phân tích chu trình để tối ưu tính toán.