Bài 1001: Nướng Thịt
Bài toán yêu cầu tính tổng giá trị lớn nhất từ các phần tử được chọn, với điều kiện không nhất thiết phải chọn tất cả. Đặc biệt cần xử lý trường hợp không chọn phần tử nào.
const int MAX_VAL = 1e9;
const int SIZE = 200010;
void solve() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
string color;
cin >> color;
vector<int> reds, blacks;
for (int i = 0; i < n; i++) {
if (color[i] == 'R') {
reds.push_back(arr[i]);
} else {
blacks.push_back(arr[i]);
}
}
sort(reds.rbegin(), reds.rend());
sort(blacks.rbegin(), blacks.rend());
long long total = 0;
int min_size = min(reds.size(), blacks.size());
for (int i = 0; i < min_size; i++) {
total += reds[i] + blacks[i];
}
if (reds.size() > blacks.size()) {
total += reds[blacks.size()];
}
cout << total << endl;
}Bài 1003: Mocha
Bài toán mô phỏng cần nhóm các phần tử có tổng giá trị bằng nhau, sau đó sử dụng mảng tiền tố để tính tổng giá trị nhanh.
const int MAX_N = 200000;
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
vector<int> group;
for (int i = 0; i < n; i++) {
group.push_back(a[i] + b[i]);
}
sort(group.begin(), group.end());
vector<long long> prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + group[i - 1];
}
long long max_sum = 0;
for (int i = 0; i < n; i++) {
int j = i + 1;
while (j < n && group[j] == group[i]) {
j++;
}
long long current = (j - i) * 1LL * group[i];
if (j <= n) {
current += prefix[j] - prefix[i];
}
max_sum = max(max_sum, current);
i = j - 1;
}
cout << max_sum << endl;
}Bài 1007: Songiang
Đây là bài toán tìm tổng giá trị lớn nhất bằng cách sắp xếp hai dãy theo thứ tự giảm dần và lấy xen kẽ. Lưu ý thứ tự người chơi (Mutsumi đi trước).
const int INF = 1e9;
void solve() {
int n;
cin >> n;
vector<int> values(n);
for (int i = 0; i < n; i++) {
cin >> values[i];
}
string colors;
cin >> colors;
vector<int> first, second;
for (int i = 0; i < n; i++) {
if (colors[i] == 'R') {
first.push_back(values[i]);
} else {
second.push_back(values[i]);
}
}
sort(first.rbegin(), first.rend());
sort(second.rbegin(), second.rend());
long long result = 0;
int i = 0;
while (i < first.size() && i < second.size()) {
result += first[i] + second[i];
i++;
}
if (first.size() > second.size()) {
result += first[i];
}
cout << result << endl;
}Bài 1008: Thiên Thần
Tổng giá trị S luôn bằng tổng của từng phần tử nhân với tổng các phần tử còn lại. Số cách thực hiện là tích của các tổ hợp C(n,2) từ n đến 2.
const long long MOD = 1e9 + 7;
long long mod_pow(long long base, long long exp) {
long long result = 1;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % MOD;
}
base = (base * base) % MOD;
exp >>= 1;
}
return result;
}
void solve() {
int n;
long long max_cost;
cin >> n >> max_cost;
long long total = 0;
for (int i = 1; i <= n; i++) {
total = (total + i * 1LL * (n - i)) % MOD;
}
long long result = 1;
for (int i = n; i >= 2; i--) {
result = (result * mod_pow(i, 2)) % MOD;
}
cout << result << endl;
}Bài 1002: Trốn Thoát
Sử dụng ST Table để xử lý truy vấn giá trị lớn nhất trong đoạn O(1), kết hợp với binary search để xác định độ dài đoạn tối thiểu.
const int MAX_N = 100000;
const int LOG_MAX = 17;
int st_table[MAX_N + 1][LOG_MAX + 1];
int log_table[MAX_N + 1];
void build_st(const vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; i++) {
st_table[i][0] = arr[i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
st_table[i][j] = max(st_table[i][j - 1], st_table[i + (1 << (j - 1))][j - 1]);
}
}
}
int query_max(int l, int r) {
int j = log_table[r - l + 1];
return max(st_table[l][j], st_table[r - (1 << j) + 1][j]);
}
void solve() {
int n;
long long max_cost;
cin >> n >> max_cost;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
log_table[1] = 0;
for (int i = 2; i <= n; i++) {
log_table[i] = log_table[i / 2] + 1;
}
build_st(arr);
vector<long long> diff(n);
for (int i = 1; i < n; i++) {
diff[i] = abs(arr[i] - arr[i - 1]);
}
vector<long long> prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + diff[i];
}
int low = 1, high = n;
while (low < high) {
int mid = (low + high) / 2;
long long min_cost = 1e18;
for (int i = 0; i + mid <= n; i++) {
int r = i + mid - 1;
int max_val = query_max(i, r);
long long left_cost = (i == 0 ? 0 : prefix[i] + abs(max_val - arr[i - 1]));
long long right_cost = (r == n - 1 ? 0 : prefix[n] - prefix[r + 1] + abs(max_val - arr[r + 1]));
min_cost = min(min_cost, left_cost + right_cost);
}
if (min_cost <= max_cost) {
high = mid;
} else {
low = mid + 1;
}
}
cout << low << endl;
}Bài 1009: Nút Bàn Phím
Áp dụng Dynamic Programming với trạng thái: dp[i][0] = chuỗi dài i kết thúc bằng phụ âm, dp[i][1] = chuỗi dài i kết thúc bằng nguyên âm.
const long long MOD = 1e9 + 7;
const int MAX_N = 1000000;
long long power5[MAX_N + 1];
long long inv_power5[MAX_N + 1];
long long mod_pow(long long base, long long exp) {
long long result = 1;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % MOD;
}
base = (base * base) % MOD;
exp >>= 1;
}
return result;
}
void precompute() {
power5[0] = 1;
for (int i = 1; i <= MAX_N; i++) {
power5[i] = (power5[i - 1] * 5) % MOD;
}
inv_power5[MAX_N] = mod_pow(power5[MAX_N], MOD - 2);
for (int i = MAX_N - 1; i >= 0; i--) {
inv_power5[i] = (inv_power5[i + 1] * 5) % MOD;
}
}
void solve() {
int n, max_vowels;
cin >> n >> max_vowels;
vector<long long> dp0(n + 1, 0), dp1(n + 1, 0);
vector<long long> prefix(n + 1, 0);
dp0[0] = 1;
prefix[0] = power5[n];
for (int i = 1; i <= n; i++) {
int start_index = max(0, i - max_vowels);
dp1[i] = (prefix[i - 1] - (start_index > 0 ? prefix[start_index - 1] : 0) + MOD) % MOD;
dp1[i] = (dp1[i] * inv_power5[n - i]) % MOD;
dp0[i] = (dp0[i - 1] + dp1[i - 1]) * 21 % MOD;
prefix[i] = (prefix[i - 1] + dp0[i] * power5[n - i]) % MOD;
}
long long result = 0;
for (int i = 0; i <= max_vowels; i++) {
result = (result + dp0[n - i] * power5[i]) % MOD;
}
cout << result << endl;
}
int main() {
precompute();
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}