Chuỗi bao trùm
Cho danh sách các chuỗi, xác định xem có tồn tại một chuỗi chứa tất cả các chuỗi còn lại như chuỗi con hay không. Nếu có, in ra chuỗi đó.
Giải pháp: Chuỗi dài nhất là ứng viên duy nhất. Duyệt qua từng chuỗi khác để kiểm tra xem nó có xuất hiện trong chuỗi dài nhất hay không bằng hàm tìm kiếm hoặc thuật toán KMP.
Xem mã dùng hàm find()
#include <bits/stdc++.h>
using namespace std;
void process() {
int n;
cin >> n;
vector<string> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
sort(arr.begin(), arr.end(), [](const string& x, const string& y) {
return x.size() > y.size();
});
string candidate = arr[0];
for (int i = 1; i < n; ++i) {
if (candidate.find(arr[i]) == string::npos) {
cout << "No\n";
return;
}
}
cout << candidate << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int cases;
cin >> cases;
while (cases--) {
process();
}
return 0;
}
Xem mã dùng KMP
#include <bits/stdc++.h>
using namespace std;
const int MAX_LEN = 1e6 + 5;
int failure[MAX_LEN];
void build_failure(string pattern) {
int len = pattern.length();
failure[0] = -1;
int i = 0, j = -1;
while (i < len) {
while (j >= 0 && pattern[i] != pattern[j]) j = failure[j];
i++; j++;
failure[i] = (j < len && pattern[i] == pattern[j]) ? failure[j] : j;
}
}
bool kmp_search(string needle, string haystack) {
build_failure(needle);
int n = haystack.length(), m = needle.length();
int i = 0, j = 0;
while (i < n) {
while (j >= 0 && haystack[i] != needle[j]) j = failure[j];
i++; j++;
if (j == m) return true;
}
return false;
}
void process() {
int n;
cin >> n;
vector<string> arr(n);
int longest_idx = 0;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
if (arr[i].length() > arr[longest_idx].length()) {
longest_idx = i;
}
}
string container = arr[longest_idx];
for (int i = 0; i < n; ++i) {
if (i == longest_idx) continue;
if (!kmp_search(arr[i], container)) {
cout << "No\n";
return;
}
}
cout << container << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int cases;
cin >> cases;
while (cases--) {
process();
}
return 0;
}
Tính tuổi theo 12 con giáp
Cho biết con giáp của hai người (người thứ nhất lớn tuổi hơn), tính khoảng cách tuổi nhỏ nhất giữa họ.
Giải pháp: Nếu cùng con giáp, chênh lệch là 12 năm. Ngược lại, tính hiệu chỉ số trong chu kỳ 12 con giáp, cộng thêm 12 rồi lấy modulo 12 để đảm bảo kết quả dương.
Xem mã
#include <bits/stdc++.h>
using namespace std;
string zodiacs[] = {"rat", "ox", "tiger", "rabbit", "dragon",
"snake", "horse", "sheep", "monkey",
"rooster", "dog", "pig"};
void process() {
string elder, younger;
cin >> elder >> younger;
if (elder == younger) {
cout << "12\n";
return;
}
int idx1 = -1, idx2 = -1;
for (int i = 0; i < 12; ++i) {
if (zodiacs[i] == elder) idx1 = i;
if (zodiacs[i] == younger) idx2 = i;
}
int diff = (idx2 - idx1 + 12) % 12;
cout << diff << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int cases;
cin >> cases;
while (cases--) {
process();
}
return 0;
}
Hiệu lập phương của hai số nguyên
Cho số nguyên tố \( p \), kiểm tra xem có tồn tại hai số nguyên dương \( a \) và \( b \) sao cho \( a^3 - b^3 = p \).
Giải pháp: Áp dụng hằng đẳng thức \( a^3 - b^3 = (a - b)(a^2 + ab + b^2) \). Vì \( p \) là số nguyên tố nên \( a - b = 1 \). Do đó, chỉ cần duyệt \( a \) từ 1 đến \( 10^6 \), đặt \( b = a - 1 \), và kiểm tra \( a^2 + ab + b^2 \) có bằng \( p \) hay không.
Xem mã
#include <bits/stdc++.h>
using namespace std;
void process() {
long long p;
cin >> p;
for (long long a = 2; a <= 1000000; ++a) {
long long b = a - 1;
long long value = a * a + a * b + b * b;
if (value == p) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int cases;
cin >> cases;
while (cases--) {
process();
}
return 0;
}