A - Số Fibonacci
Đề bài
Cho một dãy số nguyên có độ dài 5, biết trước \(a_1, a_2, a_4, a_5\). Hãy điền một giá trị \(a_3\) sao cho số lượng chỉ số \(i\) thỏa mãn \(a_{i+2}=a_{i+1}+a_i\) là lớn nhất.
Giải pháp
Chỉ có 3 trường hợp có thể xảy ra cho \(a_3\).
Mã nguồn
Nhấn để xem mã
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve() {
vector<int> v(5);
for (int i = 0; i < 5; i++) {
if (i == 2) continue;
cin >> v[i];
}
int option1 = v[0] + v[1];
int option2 = v[4] - v[3];
int option3 = v[3] - v[1];
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
v[2] = option1;
if (v[2] == v[1] + v[0]) cnt1++;
if (v[3] == v[2] + v[1]) cnt1++;
if (v[4] == v[3] + v[2]) cnt1++;
v[2] = option2;
if (v[2] == v[1] + v[0]) cnt2++;
if (v[3] == v[2] + v[1]) cnt2++;
if (v[4] == v[3] + v[2]) cnt2++;
v[2] = option3;
if (v[2] == v[1] + v[0]) cnt3++;
if (v[3] == v[2] + v[1]) cnt3++;
if (v[4] == v[3] + v[2]) cnt3++;
cout << max({cnt1, cnt2, cnt3}) << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
B - Trò Chơi Bài Của Nông Dân John
Đề bài
Có \(n\) con bò được đánh số từ 1 đến \(n\), mỗi con có \(m\) lá bài. Tổng cộng có \(n \times m\) lá bài được đánh số từ 0 đến \(n \times m - 1\). Hãy xây dựng một dãy \(p\) (thứ tự các con bò) sao cho các lá bài được đánh ra theo thứ tự tăng dần.
Giải pháp
Nếu \(m = 1\), dãy \(p\) luôn tồn tại (chỉ cần sắp xếp theo thứ tự lá bài tăng dần). Trong trường hợp khác, có ít nhất \(2n\) lá bài. Ta ghi lại mỗi lá bài thuộc về con bò nào, sau đó duyệt các lá bài theo thứ tự tăng dần và đẩy số hiệu con bò vào mảng kết quả \(ans\) cho đến khi mảng có kích thước \(2n\). Kiểm tra xem nửa đầu và nửa sau của mảng có giống nhau không; nếu giống thì đó là đáp án, nếu không thì vô nghiệm.
Mã nguồn
Nhấn để xem mã
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve() {
int n, m;
cin >> n >> m;
set<pii> cards;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
int x;
cin >> x;
cards.insert({x, i});
}
}
if (m == 1) {
for (auto& p : cards) cout << p.second << " ";
cout << endl;
return;
}
vector<int> ans;
for (auto& p : cards) {
ans.push_back(p.second);
if (ans.size() == 2 * n) break;
}
for (int i = 0; i < n; i++) {
if (ans[i] != ans[i + n]) {
cout << -1 << endl;
return;
}
}
for (int i = 0; i < n; i++) cout << ans[i] << " ";
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
C - Trò Chơi Của Các Nhà Toán Học
Đề bài
Ban đầu có \(n\) số và điểm số là 0. Trò chơi có \(\frac{n}{2}\) lượt. Mỗi lượt, Alice xóa một số \(a\), sau đó Bob xóa một số \(b\). Nếu \(a + b = k\), điểm tăng thêm 1. Alice muốn điểm số nhỏ nhất, Bob muốn điểm số lớn nhất. Cả hai đều chơi tối ưu. Hãy tìm điểm số cuối cùng.
Giải pháp
Kết quả cuối cùng chính là điểm số tối đa mà Bob có thể đạt được, bởi vì dù Alice chọn số nào, Bob vẫn luôn có thể chọn được số để tạo thành tổng \(k\) nếu còn cặp phù hợp.
Mã nguồn
Nhấn để xem mã
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve() {
int n, k, ans = 0;
cin >> n >> k;
map<int, int> freq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
freq[x]++;
}
for (auto& [val, cnt] : freq) {
int target = k - val;
auto it = freq.find(target);
if (it == freq.end()) continue;
if (it->first == val) {
ans += cnt / 2;
cnt = cnt % 2;
} else {
int pairs = min(cnt, it->second);
ans += pairs;
cnt -= pairs;
it->second -= pairs;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
D - Sắp Xếp Bằng Phép Trừ Tối Thiểu
Đề bài
Cho dãy số nguyên dương \(a\). Có thể thực hiện thao tác sau không giới hạn lần: chọn \(a_i\) và \(a_{i+1}\) rồi trừ cả hai đi \(min(a_i, a_{i+1})\). Hãy xác định xem có thể làm cho dãy không giảm bằng các thao tác này hay không.
Giải pháp
Vì mục tiêu là dãy không giảm, các số ở đầu càng nhỏ càng tốt. Do đó, ta thực hiện thao tác bất cứ khi nào có thể. Nếu kết quả cuối cùng là dãy không giảm thì có lời giải, ngược lại là vô nghiệm.
Mã nguồn
Nhấn để xem mã
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n - 1; i++) {
if (a[i] <= a[i + 1]) {
int minVal = min(a[i], a[i + 1]);
a[i] -= minVal;
a[i + 1] -= minVal;
}
}
cout << (is_sorted(a.begin(), a.end()) ? "Yes" : "No") << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
E - Đồ Thị Hợp Thành
Đề bài
Cho hai đồ thị vô hướng đơn \(F\) và \(G\), \(F\) có \(m_1\) cạnh, \(G\) có \(m_2\) cạnh. Có thể thực hiện hai thao tác trên \(F\): xóa cạnh và thêm cạnh. Yêu cầu làm cho \(F\) có cùng tính liên thông với \(G\). Tìm số thao tác tối thiểu.
Giải pháp
Các cạnh của \(F\) nối hai đỉnh thuộc các thành phần liên thông khác nhau của \(G\) chắc chắn phải bị xóa. Số cạnh cần thêm chính là hiệu số thành phần liên thông giữa hai đồ thị.
Mã nguồn (tham khảo từ jiangly)
Nhấn để xem mã
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 5e5 + 5;
struct DSU {
vector<int> parent, size;
DSU() {}
DSU(int n) { init(n); }
void init(int n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
size.assign(n, 1);
}
int find(int x) {
while (x != parent[x]) {
x = parent[x] = parent[parent[x]];
}
return x;
}
bool sameSet(int x, int y) { return find(x) == find(y); }
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
size[x] += size[y];
parent[y] = x;
return true;
}
int getSize(int x) { return size[find(x)]; }
};
void solve() {
int n, m1, m2;
cin >> n >> m1 >> m2;
vector<pii> edgesF(m1);
DSU dsuF(n), dsuG(n);
for (int i = 0; i < m1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
edgesF[i] = {u, v};
}
int compF = n, compG = n;
for (int i = 0; i < m2; i++) {
int u, v;
cin >> u >> v;
u--; v--;
if (dsuG.unite(u, v)) compG--;
}
int deletions = 0;
for (auto& [u, v] : edgesF) {
if (!dsuG.sameSet(u, v)) {
deletions++;
} else {
if (dsuF.unite(u, v)) compF--;
}
}
int additions = compF - compG;
cout << deletions + additions << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
Liên kết cuộc thi: https://mirror.codeforces.com/contest/2060