Bài toán đầu tiên là một bài toán đơn giản về kiểm tra ma trận.
Mục tiêu là kiểm tra xem tất cả các phần tử của ma trận có nằm trên đường chéo chính hoặc dưới nó hay không. Nếu đúng, ta sẽ nhân tất cả các phần tử trên đường chéo chính với nhau.
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
bool kiemTraDuongCheo(ll n, vector<vector<ll>> &mat) {
for (ll i = 0; i < n; ++i) {
for (ll j = 0; j < i; ++j) {
if (mat[i][j] != 0) return false;
}
}
return true;
}
bool kiemTraDuoiDuongCheo(ll n, vector<vector<ll>> &mat) {
for (ll i = 0; i < n; ++i) {
for (ll j = i + 1; j < n; ++j) {
if (mat[i][j] != 0) return false;
}
}
return true;
}
int main() {
ll n;
cin >> n;
vector<vector<ll>> mat(n, vector<ll>(n));
for (ll i = 0; i < n; ++i) {
for (ll j = 0; j < n; ++j) {
cin >> mat[i][j];
}
}
ll ketQua = 1;
if (kiemTraDuongCheo(n, mat) || kiemTraDuoiDuongCheo(n, mat)) {
for (ll i = 0; i < n; ++i) {
ketQua = (ketQua * mat[i][i]) % MOD;
}
cout << ketQua;
} else {
cout << "Arknights!";
}
return 0;
}Bài toán tiếp theo liên quan đến việc tối ưu hóa việc tiêu diệt các đoạn trên trục số.
Nếu độ dài của đoạn lớn hơn hoặc bằng T, chúng ta luôn có thể tiêu diệt nó. Đối với các đoạn ngắn hơn, chúng ta sẽ ánh xạ chúng vào khoảng từ 1 đến T và tìm cách tiêu diệt hiệu quả nhất.
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n, t;
cin >> n >> t;
vector<pair<ll, pair<ll, ll>>> doan(n);
ll tong = 0, daXoa = 0;
for (auto &x : doan) {
cin >> x.first >> x.second.first >> x.second.second;
tong += x.second.second;
if (x.second.first - x.first + 1 >= t) {
daXoa += x.second.second;
} else {
ll viTriBatDau = x.first % t;
if (viTriBatDau == 0) viTriBatDau = t;
ll viTriKetThuc = min(2 * t, x.second.first - x.first + viTriBatDau);
doan.push_back({viTriBatDau, {viTriKetThuc, x.second.second}});
}
}
vector<ll> suLy(2 * t + 1, 0);
for (auto &x : doan) {
suLy[x.first] += x.second.second;
suLy[x.second.first + 1] -= x.second.second;
}
for (ll i = 1; i <= 2 * t; ++i) {
suLy[i] += suLy[i - 1];
}
ll ketQua = 0;
for (ll i = 1; i <= t; ++i) {
ketQua = max(ketQua, suLy[i] + suLy[i + t]);
}
ketQua += daXoa;
ketQua = tong - ketQua;
cout << ketQua;
return 0;
}Bài toán sau đây yêu cầu tìm khoảng con có độ dài cố định sao cho tổng hiệu giữa giá trị lớn nhất và nhỏ nhất là lớn nhất.
Chúng ta sử dụng cấu trúc dữ liệu hàng đợi đơn điệu để giải quyết bài toán này.
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n, k;
cin >> n >> k;
vector<ll> mang(n);
for (ll &x : mang) cin >> x;
deque<ll> hangDoiLon, hangDoiNho;
ll ketQua = LLONG_MIN;
auto themVaoHangDoiLon = [&](ll viTri) {
while (!hangDoiLon.empty() && mang[viTri] >= mang[hangDoiLon.back()]) hangDoiLon.pop_back();
hangDoiLon.push_back(viTri);
};
auto themVaoHangDoiNho = [&](ll viTri) {
while (!hangDoiNho.empty() && mang[viTri] <= mang[hangDoiNho.back()]) hangDoiNho.pop_back();
hangDoiNho.push_back(viTri);
};
for (ll i = 0; i < k; ++i) {
themVaoHangDoiLon(i);
themVaoHangDoiNho(i);
}
for (ll i = k; i < n; ++i) {
if (hangDoiLon.front() <= i - k) hangDoiLon.pop_front();
if (hangDoiNho.front() <= i - k) hangDoiNho.pop_front();
themVaoHangDoiLon(i);
themVaoHangDoiNho(i);
ketQua = max(ketQua, mang[hangDoiLon.front()] - mang[hangDoiNho.front()]);
}
cout << ketQua;
return 0;
}Bài toán cuối cùng liên quan đến việc tìm chi phí tối thiểu để phân bổ các phần thưởng.
Chúng ta sử dụng kỹ thuật chia để trị (binary search) để tìm ra chi phí tối đa mà mỗi phần thưởng có thể được phân bổ, sau đó tính toán tổng chi phí.
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll kiemTra(ll chiPhi, const vector<ll> &phanThuong, ll soLuongCanPhanBo) {
ll dem = 0;
for (ll giaTri : phanThuong) {
dem += chiPhi / giaTri;
}
return dem >= soLuongCanPhanBo;
}
int main() {
ll n, L;
cin >> n >> L;
vector<ll> phanThuong(n);
for (ll &x : phanThuong) cin >> x;
sort(phanThuong.begin(), phanThuong.end());
ll trai = 0, phai = 1e18, giua;
while (trai < phai) {
giua = (trai + phai) / 2;
if (kiemTra(giua, phanThuong, L)) phai = giua;
else trai = giua + 1;
}
ll tongChiPhi = 0;
for (ll giaTri : phanThuong) {
ll soPhanBo = trai / giaTri;
tongChiPhi += giaTri * soPhanBo * (soPhanBo + 1) / 2;
}
ll soPhanBoThua = 0;
for (ll giaTri : phanThuong) {
soPhanBoThua += trai / giaTri;
}
soPhanBoThua -= L;
tongChiPhi -= soPhanBoThua * trai;
cout << tongChiPhi;
return 0;
}