Hướng dẫn cho LQDOJ CUP 2022 - Round 2 - SCORING
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(20\%\) số điểm): \(k \leq 10\).
Tutorial
Duyệt qua từng cách chọn \(n\) màu trong \(k\) màu để tô cho các đỉnh. Sau đó thử từng cách tô \(n\) màu này cho \(n\) đỉnh và kiểm tra điều kiện xem có thỏa không.
Độ phức tạp: \(\displaystyle \mathcal{O}\left(\binom{k}{n} \cdot n! \cdot n \right)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
int n, k;
vector<int> adj[MAX_N];
int a[MAX_N];
int c[MAX_N];
vector<vector<int> > hold;
vector<int> cur;
void backtrack(int i, int l) {
if (i == n) {
hold.push_back(cur);
return;
}
for (int x = l + 1; x <= k; x++) {
cur.push_back(x);
backtrack(i + 1, x);
cur.pop_back();
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("SCORING.inp", "r", stdin);
freopen("SCORING.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int u = 1; u <= n; u++) {
cin >> a[u];
}
backtrack(0, 0);
int answer = 0;
for (auto x : hold) {
for (int i = 1; i <= n; i++) {
c[i] = x[i - 1];
}
do {
bool check = true;
for (int u = 1; u <= n; u++) {
for (auto v : adj[u]) {
if (a[u] > a[v]) {
check &= (c[u] > c[v]);
}
}
}
answer += check;
} while (next_permutation(c + 1, c + n + 1));
}
cout << answer << '\n';
return 0;
}
Subtask \(2\) (\(20\%\) số diểm): \(k \leq 10 ^ 2\).
Subtask \(3\) (\(20\%\) số điểm): \(k \leq 10 ^ 3\).
Subtask \(4\) (\(20\%\) số điểm): \(k = n\).
Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Nhận xét: Nếu đặt đỉnh \(r\) có \(a_r = 1\) làm gốc của cây thì các giá trị trên mọi đường đi từ \(r\) xuống lá đều tăng dần.
Chứng minh: Có thể chứng minh bằng quy nạp từ các nút lá đi lên.
Trước tiên, số cách chọn \(n\) màu trong \(k\) màu là \(\displaystyle \binom{k}{n}\).
Gọi \(sub_u\) là số đỉnh trong cây con gốc \(u\). Bắt đầu từ đỉnh \(u = r\), mình chỉ có thể chọn màu nhỏ nhất để gán cho đỉnh \(u\). Với mỗi đỉnh con trực tiếp \(v\) của \(u\), mình có thể chọn \(sub_v\) màu trong số các màu còn lại có thể chọn để gán cho các đỉnh trong cây con gốc \(v\) rồi sau đó xét đến đỉnh \(v\). Sau khi duyệt từ gốc xuống lá, tích tất cả số cách chọn sẽ là đáp án.
Độ phức tạp: Tùy vào cách cài đặt, trong đó, độ phức tạp chuẩn là \(\mathcal{O}(n)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
const int MOD = 1e9 + 7;
int n, k;
int fct[MAX_N], ifct[MAX_N];
vector<int> adj[MAX_N];
int sub[MAX_N];
int answer;
int inverse(int x) {
if (x <= 1) {
return 1;
}
return (MOD - MOD / x) * (long long)inverse(MOD % x) % MOD;
}
int choose(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return 0;
}
if (n < MAX_N) {
return fct[n] * (long long)ifct[n - k] % MOD * ifct[k] % MOD;
}
k = min(k, n - k);
int res = 1;
for (int i = 1; i <= k; i++) {
res = res * (long long)(n - k + i) % MOD * inverse(i) % MOD;
}
return res;
}
void dfs(int node, int parent) {
sub[node] = 1;
for (auto u : adj[node]) {
if (u != parent) {
dfs(u, node);
sub[node] += sub[u];
}
}
int rem = sub[node] - 1;
for (auto u : adj[node]) {
if (u != parent) {
answer = answer * (long long)choose(rem, sub[u]) % MOD;
rem -= sub[u];
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("SCORING.inp", "r", stdin);
freopen("SCORING.out", "w", stdout);
fct[0] = 1;
for (int i = 1; i < MAX_N; i++) {
fct[i] = fct[i - 1] * (long long)i % MOD;
}
ifct[MAX_N - 1] = inverse(fct[MAX_N - 1]);
for (int i = MAX_N - 2; i >= 0; i--) {
ifct[i] = ifct[i + 1] * (long long)(i + 1) % MOD;
}
cin >> n >> k;
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int root = -1;
for (int u = 1; u <= n; u++) {
int a;
cin >> a;
if (a == 1) {
root = u;
}
}
answer = choose(k, n);
dfs(root, 0);
cout << answer << '\n';
return 0;
}
Bình luận