Xây dựng mã Gray từ số nguyên
Mã Gray là một hệ thống mã hóa nhị phân mà hai giá trị liên tiếp chỉ khác nhau một bit. Để chuyển đổi một số nguyên $k$ sang mã Gray tương ứng, chúng ta sử dụng công thức dựa trên phép toán bitwise: $G(k) = k \oplus \lfloor \frac{k}{2} \rfloor$. Trong bài toán yêu cầu in ra mã Gray $n$ bit của số thứ $k$, ta có thể thực hiện kiểm tra từng bit từ cao đến thấp.
#include <iostream>
using namespace std;
void generate_gray_code() {
int n;
unsigned long long k;
if (!(cin >> n >> k)) return;
for (int i = n - 1; i >= 0; --i) {
// Áp dụng công thức: (k ^ (k >> 1)) để tìm bit thứ i
unsigned long long gray_val = k ^ (k >> 1);
cout << ((gray_val >> i) & 1);
}
cout << endl;
}
Tính toán dãy ngoặc hợp lệ trên cấu trúc cây
Bài toán yêu cầu đếm số lượng dãy ngoặc đúng trên đường đi từ gốc đến từng nút của cây. Đây là một biến thể của bài toán dãy ngoặc trên mảng phẳng nhưng được mở rộng lên cấu trúc cây bằng cách sử dụng DFS kết hợp với ngăn xếp (stack).
Để giải quyết, chúng ta duy trì một stack lưu trữ vị trí của các dấu ngoặc mở '(' chưa được ghép đôi. Khi gặp dấu ngoặc đóng ')', nếu stack không rỗng, chúng ta đã tìm thấy một cặp ngoặc hợp lệ. Số lượng dãy ngoặc kết thúc tại nút hiện tại sẽ bằng số lượng dãy ngoặc kết thúc tại nút cha của nút mở tương ứng cộng thêm 1. Lưu ý quan trọng là phải khôi phục trạng thái của stack sau khi thực hiện DFS xong một nhánh để không ảnh hưởng đến các nhánh khác.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 500005;
vector<int> adj[MAXN];
int parent[MAXN], bracket_stack[MAXN], top = 0;
long long count_at_node[MAXN], total_path[MAXN];
char s[MAXN];
void dfs_brackets(int u) {
int last_pos = 0;
if (s[u] == ')') {
if (top > 0) {
last_pos = bracket_stack[top--];
count_at_node[u] = count_at_node[parent[last_pos]] + 1;
}
} else {
bracket_stack[++top] = u;
}
total_path[u] = total_path[parent[u]] + count_at_node[u];
for (int v : adj[u]) {
dfs_brackets(v);
}
// Khôi phục trạng thái stack (Backtracking)
if (last_pos) {
bracket_stack[++top] = last_pos;
} else if (top > 0 && s[u] == '(') {
--top;
}
}
Tối ưu hóa tổ hợp với nguyên lý bù trừ
Trong bài toán lựa chọn món ăn với các điều kiện ràng buộc phức tạp (như mỗi loại nguyên liệu không được chiếm quá nửa tổng số món), phương pháp hiệu quả nhất là sử dụng nguyên lý bù trừ: Tổng số cách chọn thỏa mãn điều kiện cơ bản trừ đi số cách chọn không hợp lệ.
Trường hợp không hợp lệ xảy ra khi có duy nhất một loại nguyên liệu xuất hiện nhiều hơn $\lfloor k/2 \rfloor$ lần (với $k$ là tổng số món đã chọn). Để tối ưu hóa, thay vì duy trì hai trạng thái độc lập cho số lượng món của nguyên liệu đang xét và số lượng món của các nguyên liệu khác, ta có thể sử dụng hiệu số giữa chúng. Điều này giúp giảm độ phức tạp của quy hoạch động từ $O(n^3 m)$ xuống $O(n^2 m)$.
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
long long a[105][2005], row_sum[105];
long long f[105][205]; // DP với hiệu số được offset thêm n đơn vị
void solve_emiya() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
row_sum[i] = (row_sum[i] + a[i][j]) % MOD;
}
}
// Tính tổng tất cả các phương án thỏa mãn điều kiện mỗi dòng chọn tối đa 1 món
vector<long long> g(n + 1, 0);
g[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i; j >= 1; --j) {
g[j] = (g[j] + g[j - 1] * row_sum[i]) % MOD;
}
}
long long total_ways = 0;
for (int j = 1; j <= n; ++j) total_ways = (total_ways + g[j]) % MOD;
long long invalid_ways = 0;
for (int col = 1; col <= m; ++col) {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= 2 * n; ++j) f[i][j] = 0;
}
f[0][n] = 1; // Offset n để tránh chỉ số âm
for (int i = 1; i <= n; ++i) {
for (int j = n - i; j <= n + i; ++j) {
f[i][j] = f[i - 1][j]; // Không chọn dòng i
f[i][j] = (f[i][j] + f[i - 1][j - 1] * a[i][col]) % MOD; // Chọn cột đang xét
f[i][j] = (f[i][j] + f[i - 1][j + 1] * (row_sum[i] - a[i][col] + MOD)) % MOD; // Chọn cột khác
}
}
for (int j = 1; j <= n; ++j) {
invalid_ways = (invalid_ways + f[n][n + j]) % MOD;
}
}
cout << (total_ways - invalid_ways + MOD) % MOD << endl;
}
Phân hoạch tối ưu và hàng đợi đơn điệu
Để tối thiểu hóa tổng bình phương của các đoạn phân hoạch, ta cần một chiến lược chia sao cho đoạn cuối cùng có tổng nhỏ nhất có thể. Tính chất này cho phép chúng ta áp dụng quy hoạch động tối ưu. Điều kiện để chuyển trạng thái từ vị trí $j$ sang $i$ là tổng đoạn hiện tại $(s_i - s_j)$ phải lớn hơn hoặc bằng tổng đoạn trước đó $(s_j - s_{g_j})$.
Điều kiện này tương đương với: $2s_j - s_{g_j} \leq s_i$. Vì các giá trị của $s$ tăng dần, ta có thể duy trì một hàng đợi đơn điệu để tìm giá trị $j$ lớn nhất thỏa mãn điều kiện trên trong thời gian $O(n)$. Đối với các bài toán có kết quả cực lớn, việc sử dụng kiểu dữ liệu __int128 là cần thiết.
#include <iostream>
using namespace std;
const int MAXN = 40000005;
int q[MAXN], pre[MAXN];
long long s[MAXN];
void optimize_partition(int n) {
int head = 1, tail = 1;
q[tail] = 0;
for (int i = 1; i <= n; ++i) {
// Loại bỏ các điểm không còn tối ưu trong hàng đợi
while (head < tail && (2 * s[q[head + 1]] - s[pre[q[head + 1]]]) <= s[i]) {
head++;
}
pre[i] = q[head];
// Duy trì tính đơn điệu của hàng đợi
while (head <= tail && (2 * s[q[tail]] - s[pre[q[tail]]]) >= (2 * s[i] - s[pre[i]])) {
tail--;
}
q[++tail] = i;
}
// Tính toán kết quả cuối cùng bằng __int128
unsigned __int128 result = 0;
int curr = n;
while (curr > 0) {
unsigned __int128 segment_sum = s[curr] - s[pre[curr]];
result += segment_sum * segment_sum;
curr = pre[curr];
}
// Logic in result...
}