Các bài tập ABC335
A. Chuyển đổi chuỗi
Đề bài
Cho một chuỗi ký tự \(S\) gồm các chữ cái thường và số.
\(S\) chắc chắn kết thúc bằng 2023.
Thay đổi ký tự cuối cùng của \(S\) thành 4, sau đó in chuỗi đã chỉnh sửa.
Giải pháp
Có hai cách tiếp cận:
- Thay thế ký tự cuối cùng bằng
4và in ra. - In \(n-1\) ký tự đầu tiên sau đó thêm
4.
Mã nguồn
#include <iostream>
#include <string>
using namespace std;
int main() {
string input;
cin >> input;
for (size_t i = 0; i < input.length() - 1; ++i) {
cout << input[i];
}
cout << "4\n";
return 0;
}
B - Số tam giác đều
Đề bài
Cho một số nguyên \(N\).
Hãy liệt kê tất cả các bộ ba số nguyên không âm \((x, y, z)\) sao cho \(x + y + z \leq N\) theo thứ tự từ điển tăng dần.
Giải pháp
Sử dụng ba vòng lặp lồng nhau để duyệt qua tất cả các giá trị có thể của \(x\), \(y\), và \(z\) và kiểm tra điều kiện.
Mã nguồn
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
for (int x = 0; x <= N; ++x) {
for (int y = 0; y <= N - x; ++y) {
for (int z = 0; z <= N - x - y; ++z) {
cout << x << " " << y << " " << z << "\n";
}
}
}
return 0;
}
C - Theo dõi Long
Đề bài
Trong trò chơi do Takahashi tạo ra, người chơi điều khiển một con rồng trên mặt phẳng tọa độ.
Rồng gồm \(N\) phần, đánh số từ \(1\) đến \(N\), trong đó phần \(1\) được gọi là đầu.
Ban đầu, phần \(i\) ở vị trí tọa độ \((i,0)\). Có \(Q\) truy vấn như sau.
1 C: Di chuyển đầu về phía \(C\) một đơn vị. Ở đây, \(C\) là "R", "L", "U" hoặc "D", tương ứng với các hướng dương \(x\), âm \(x\), dương \(y\) và âm \(y\). Mọi phần khác sẽ di chuyển theo phần phía trước nó. Điều này có nghĩa là phần \(i\) \((2\leq i \leq N)\) sẽ di chuyển đến vị trí của phần \(i-1\) trước khi di chuyển.2 p: Tìm vị trí của phần \(p\).
Giải pháp
Để duy trì một đoạn cố định độ dài, sử dụng hàng đợi kép để chèn vào đầu và xóa ở cuối. Truy vấn trực tiếp vào hàng đợi.
Mã nguồn
#include <iostream>
#include <deque>
using namespace std;
int main() {
int N, Q;
cin >> N >> Q;
deque<pair<int, int>> positions;
for (int i = 1; i <= N; ++i) {
positions.push_back({i, 0});
}
for (int i = 0; i < Q; ++i) {
int operation;
cin >> operation;
if (operation == 1) {
char direction;
cin >> direction;
pair<int, int> head = positions.front();
if (direction == 'R') {
positions.push_front({head.first + 1, head.second});
} else if (direction == 'L') {
positions.push_front({head.first - 1, head.second});
} else if (direction == 'U') {
positions.push_front({head.first, head.second + 1});
} else {
positions.push_front({head.first, head.second - 1});
}
positions.pop_back();
} else {
int part;
cin >> part;
cout << positions[part - 1].first << " " << positions[part - 1].second << "\n";
}
}
return 0;
}
D - Long và Takahashi
Đề bài
Mô tả bài toán
Có một lưới gồm \(N\) dòng và \(N\) cột, với \(N\) là số lẻ và tối đa là \(45\).
Hãy đặt Takahashi và một con rồng gồm \(N^2-1\) phần (đánh số từ \(1\) đến \(N^2-1\)) vào lưới sao cho:
- Takahashi nằm ở giữa lưới, tại ô \((\frac{N+1}{2},\frac{N+1}{2})\).
- Mỗi ô khác chứa một phần của rồng.
- Phần \(x\) \((2 \leq x \leq N^2-1\)) phải kề với phần \(x-1\). Hai ô \((i,j)\) và \((k,l)\) được coi là kề nếu \(|i-k|+|j-l|=1\).
In ra một cách sắp xếp thỏa mãn yêu cầu.
Giải pháp
Di chuyển theo chiều kim đồng hồ, bắt đầu từ phía phải xuống dưới, sang trái rồi lên trên.
Mã nguồn
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<vector<int>> grid(N, vector<int>(N, 0));
int dx[] = {0, 1, 0, -1}; // right, down, left, up
int dy[] = {1, 0, -1, 0};
int x = 0, y = 0, dir = 0;
for (int i = 1; i <= N * N - 1; ++i) {
grid[x][y] = i;
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[nx][ny] == 0) {
x = nx;
y = ny;
} else {
dir = (dir + 1) % 4;
x += dx[dir];
y += dy[dir];
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == N / 2 && j == N / 2) {
cout << "T ";
} else {
cout << grid[i][j] << " ";
}
}
cout << "\n";
}
return 0;
}
E - Đường đi Màu Đa Dạng Không Giảm
Đề bài
Có một đồ thị vô hướng liên thông với \(N\) đỉnh và \(M\) cạnh, trong đó mỗi cạnh \(i\) nối đỉnh \(U_i\) và \(V_i\). Mỗi đỉnh có một số nguyên ghi trên nó, đỉnh \(v\) ghi số nguyên \(A_v\).
Điểm số của một đường đi đơn giản từ đỉnh \(1\) đến đỉnh \(N\) xác định như sau:
- Nếu dãy số \(S\) gồm các số trên các đỉnh của đường đi không giảm thì điểm số của đường đi là số lượng các số khác nhau trong \(S\).
- Ngược lại, điểm số là \(0\).
Tìm đường đi đơn giản từ đỉnh \(1\) đến đỉnh \(N\) có điểm số cao nhất và in điểm số đó.
Giải pháp
Sử dụng kỹ thuật quy hoạch động (DP) kết hợp cấu trúc dữ liệu không gian (DSU) để giải quyết bài toán hiệu quả hơn so với việc liệt kê tất cả các đường đi.
Mã nguồn
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int weight, u, v;
};
bool compareEdges(const Edge& a, const Edge& b) {
return a.weight < b.weight;
}
int findSet(int x, vector<int>& parent) {
if (parent[x] != x) {
parent[x] = findSet(parent[x], parent);
}
return parent[x];
}
void unionSets(int x, int y, vector<int>& parent) {
int rootX = findSet(x, parent);
int rootY = findSet(y, parent);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
int main() {
int N, M;
cin >> N >> M;
vector<int> values(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> values[i];
}
vector<Edge> edges(M);
for (int i = 0; i < M; ++i) {
cin >> edges[i].u >> edges[i].v;
if (values[edges[i].u] > values[edges[i].v]) {
swap(edges[i].u, edges[i].v);
}
edges[i].weight = values[edges[i].u];
}
sort(edges.begin(), edges.end(), compareEdges);
vector<int> parent(N + 1);
vector<int> dp(N + 1, -1e9);
for (int i = 1; i <= N; ++i) {
parent[i] = i;
}
dp[findSet(1, parent)] = 1;
for (const auto& edge : edges) {
int uRoot = findSet(edge.u, parent);
int vRoot = findSet(edge.v, parent);
if (uRoot != vRoot) {
dp[vRoot] = max(dp[vRoot], dp[uRoot] + 1);
unionSets(uRoot, vRoot, parent);
}
}
int result = max(0, dp[findSet(N, parent)]);
cout << result << "\n";
return 0;
}