Bài A: Lọc Ký Tự 2
Yêu cầu: Cho chuỗi ký tự đầu vào, in ra chuỗi chỉ chứa các ký tự số 2
Giải pháp:
Xem mã nguồn
#include <iostream>
#include <string>
using namespace std;
int main() {
string str;
cin >> str;
string result;
for(char c : str) {
if(c == '2') result += c;
}
cout << result;
return 0;
}
Bài B: Sắp Xếp Chuỗi
Yêu cầu: Sắp xếp n chuỗi theo thứ tự độ dài tăng dần, nếu bằng độ dài thì theo thứ tự từ điển, sau đó nối chúng lại
Xem mã nguồn
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compareStrings(const string& a, const string& b) {
if(a.length() == b.length()) return a < b;
return a.length() < b.length();
}
int main() {
int n;
cin >> n;
vector<string> list(n);
for(int i=0; iBài C: Sửa Lỗi WA
Yêu cầu: Thay thế tất cả các chuỗi "WA" thành "AC" trong chuỗi đầu vào, bắt đầu từ vị trí trái nhất
Xem mã nguồn
#include <iostream>
#include <string>
using namespace std;
int main() {
string str;
cin >> str;
for(int pos=0; pos < (int)str.length()-1; ) {
if(str[pos] == 'W' && str[pos+1] == 'A') {
str[pos] = 'A';
str[pos+1] = 'C';
pos = max(pos-1, 0);
} else {
pos++;
}
}
cout << str;
return 0;
}
Bài D: Kiểm Tra Dấu Ngoặc
Yêu cầu: Kiểm tra xem chuỗi dấu ngoặc có hợp lệ không
Xem mã nguồn
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
string brackets;
cin >> brackets;
stack<char> st;
for(char c : brackets) {
if(!st.empty()) {
char top = st.top();
if((top == '(' && c == ')') ||
(top == '[' && c == ']') ||
(top == '<' && c == '>')) {
st.pop();
} else {
st.push(c);
}
} else {
st.push(c);
}
}
cout << (st.empty() ? "Hợp lệ" : "Không hợp lệ");
return 0;
}
Bài E: Đường Đi Đối Xứng
Yêu cầu: Tìm độ dài đường đi ngắn nhất tạo thành chuỗi đối xứng trong đồ thị có hướng
Xem mã nguồn
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int main() {
int n;
cin >> n;
char graph[105][105];
for(int i=0; i<n; i++) {
cin >> graph[i];
}
int dist[105][105];
memset(dist, -1, sizeof(dist));
queue<pair<int,int>> q;
for(int i=0; i<n; i++) {
dist[i][i] = 0;
q.push({i, i});
for(int j=0; j<n; j++) {
if(i != j && graph[i][j] != '-') {
dist[i][j] = 1;
q.push({i, j});
}
}
}
while(!q.empty()) {
auto [u, v] = q.front(); q.pop();
for(int i=0; i<n; i++) {
if(graph[i][u] == '-') continue;
for(int j=0; j<n; j++) {
if(graph[v][j] == '-' || graph[i][u] != graph[v][j]) continue;
if(dist[i][j] == -1 || dist[i][j] > dist[u][v] + 2) {
dist[i][j] = dist[u][v] + 2;
q.push({i, j});
}
}
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cout << dist[i][j] << " ";
}
cout << endl;
}
return 0;
}
Bài F: Cây Hữu Cơ
Yêu cầu: Tìm cây con lớn nhất thỏa mãn điều kiện độ cao nút
Xem mã nguồn
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int result = -1;
vector<int> adj[200010];
bool visited[200010];
int dp[200010][2]; // dp[node][type]
void dfs(int node) {
visited[node] = true;
vector<int> candidates;
for(int neighbor : adj[node]) {
if(!visited[neighbor] && adj[neighbor].size() >= 4) {
dfs(neighbor);
candidates.push_back(dp[neighbor][1]);
}
}
sort(candidates.rbegin(), candidates.rend());
dp[node][1] = 1;
for(int i=0; i<min(3LL, (long long)candidates.size()); i++) {
dp[node][1] += candidates[i];
}
dp[node][0] = dp[node][1];
if(candidates.size() > 3) {
dp[node][0] += candidates[3];
}
result = max(result, dp[node][0]);
}
int main() {
int n;
cin >> n;
for(int i=0; i<n-1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
if(n < 5) {
cout << -1 << endl;
return 0;
}
for(int i=0; i<n; i++) {
if(!visited[i] && adj[i].size() >= 4) {
dfs(i);
}
}
cout << 3 * result + 2 << endl;
return 0;
}