Bài A - Kiểm tra độ dài chuỗi
Hãy kiểm tra xem độ dài của chuỗi có phải là bội số của \(5\) hay không.
Xem mã nguồn
#include
using namespace std;
int main(){
string chuoi;
cin >> chuoi;
int doDai = chuoi.length();
cout << (doDai % 5 == 0 ? "Yes" : "No");
return 0;
}
Bài B - Thay đổi nhân sự
Tính toán số lượng nhân viên thay đổi giữa hai thời điểm trong mỗi phòng ban.
Xem mã nguồn
#include
using namespace std;
int main(){
int soPhong, soThayDoi;
cin >> soPhong >> soThayDoi;
vector<int> truocDo(105, 0), sauDo(105, 0);
for(int i=0; i> phongTruoc >> phongSau;
truocDo[phongTruoc]++;
sauDo[phongSau]++;
}
for(int i=1; i<=soThayDoi; ++i)
cout << (sauDo[i] - truocDo[i]) << '\n';
return 0;
}
Bài C - Quản lý cây con
Sử dụng cấu trúc dữ liệu heap tối thiểu để lưu trữ các giá trị và loại bỏ những phần tử nhỏ hơn hoặc bằng một ngưỡng nhất định.
Xem mã nguồn
#include
using namespace std;
int main(){
int soLenh;
cin >> soLenh;
priority_queue heap;
while(soLenh--){
int loai, giaTri;
cin >> loai >> giaTri;
if(loai == 1){
heap.push(giaTri);
}
else{
while(!heap.empty() && heap.top() <= giaTri){
heap.pop();
}
}
cout << heap.size() << '\n';
}
return 0;
}
Bài D - Số nguyên đặc biệt
Đếm số lượng số nguyên đặc biệt có thể tạo thành từ phép cộng lũy thừa của \(2\).
Xem mã nguồn
#include
using namespace std;
long long noiLienKet(long long x, long long y){
long long t = y;
while(t){
x *= 10;
t /= 10;
}
return x + y;
}
void timKiemSau(long long x, vector<long long>& danhSach, set<long long>& tapHop){
if(x <= 1e9){
if(x != 0 && tapHop.find(x) == tapHop.end()){
danhSach.push_back(x);
tapHop.insert(x);
}
}
else return;
for(int i=0; i<30; ++i){
timKiemSau(noiLienKet(x, pow(2, i)), danhSach, tapHop);
}
}
int main(){
int thuTu;
cin >> thuTu;
vector<long long> luuyThua;
for(int i=0; pow(2, i) <= 1e9; ++i){
luuyThua.push_back(pow(2, i));
}
vector<long long> cacSo;
set<long long> daXet;
timKiemSau(0, cacSo, daXet);
sort(cacSo.begin(), cacSo.end());
cout << cacSo[thuTu-1];
return 0;
}
Bài E - Khoảng cách trên cây
Kiểm tra xem ma trận khoảng cách đã cho có biểu diễn được bởi một cây hợp lệ hay không.
Xem mã nguồn
#include
using namespace std;
const int MAXN = 3005;
struct Canh {
int u, v;
long long w;
};
bool cmp(Canh a, Canh b) { return a.w < b.w; }
int cha[MAXN];
vector> ke[MAXN];
long long kc[MAXN], stt[MAXN][15], sau[MAXN];
int timCha(int x){
if(x == cha[x]) return x;
return cha[x] = timCha(cha[x]);
}
void dfs(int u, int p){
sau[u] = sau[p] + 1;
stt[u][0] = p;
for(int j=1; j<14; ++j){
stt[u][j] = stt[stt[u][j-1]][j-1];
}
for(auto &[v, w] : ke[u]){
if(v == p) continue;
kc[v] = kc[u] + w;
dfs(v, u);
}
}
int lca(int u, int v){
if(sau[u] < sau[v]) swap(u, v);
for(int j=13; j>=0; --j){
if(sau[stt[u][j]] >= sau[v])
u = stt[u][j];
}
if(u == v) return u;
for(int j=13; j>=0; --j){
if(stt[u][j] != stt[v][j]){
u = stt[u][j];
v = stt[v][j];
}
}
return stt[u][0];
}
int main(){
int n;
cin >> n;
vector<Canh> danhSachCanh;
for(int i=1; i<=n; ++i){
cha[i] = i;
for(int j=i+1; j<=n; ++j){
long long tmp;
cin >> tmp;
danhSachCanh.push_back({i, j, tmp});
}
}
sort(danhSachCanh.begin(), danhSachCanh.end(), cmp);
for(auto &c : danhSachCanh){
int u = c.u, v = c.v;
if(timCha(u) != timCha(v)){
cha[timCha(u)] = timCha(v);
ke[u].push_back({v, c.w});
ke[v].push_back({u, c.w});
}
}
dfs(1, 0);
bool hopLe = true;
for(int i=1; i<=n && hopLe; ++i){
for(int j=i+1; j<=n && hopLe; ++j){
if(kc[i] + kc[j] - 2 * kc[lca(i, j)] != danhSachCanh[(i-1)*n+j-1].w){
hopLe = false;
}
}
}
cout << (hopLe ? "Yes" : "No");
return 0;
}