Lời giải ngày 1 kì thi Học sinh giỏi Quốc gia năm 2021 môn tin học
---
**✏️Author: Nguyễn Ngọc Minh Kiên, Trần Đức Khải, Trần Bình Nguyên, Trần Hữu Đại, Nguyễn Nguyên Phúc
$\hspace{1.5cm}$gaugau**
[toc]
# Bài 1 Tặng quà
## Tóm tắt đề
Cho một dãy hoán vị $2n$ phần tử và số nguyên dương $d$. Cần tìm một dãy $2m$ phần tử có chỉ số $1 \le i_1 < i_2 < ... < i_m < ... < i_{2m} \le 2n$ sao cho $|c_{i_k} - c_{i_{m+k}}| \le d$
Hỏi: giá trị tối đa của $m$ là bao nhiêu?
**Subtasks:**
- $40\%$ test tương ứng $n \le 10$.
- $40\%$ test tương ứng $n \le 100$.
- $20\%$ test tương ứng $n \le 1000$
## Subtask 1
Subtask con nít cũng làm được :penguin:
Subtask này chỉ cần quay lui nhị phân $2m$ phần tử và kiểm tra điều kiện là được
**Độ phức tạp thời gian:** $O \left( 2^{2n} \times 2n \right)$.
## Subtask 2
>[!Note] Ý tưởng:
>Ta chia dãy hoán vị ra làm hai nửa
>Gọi $s$ là biên, ta có $c_1, c_2, ..., c_m$ thuộc nửa trái, $c_{m+1}, c_{m+2}, ..., c_{2m}$ thuộc nửa phải
Để dễ thao tác, ta sẽ cho nửa trái vào mảng $L$ có $s$ phần tử, nửa phải vào mảng $R$ có $2n - s$ phần tử
Từ đây, bài toán trở thành ==Tìm dãy các cặp giá trị $|L_i - R_j|$ dài nhất mà độ chênh lệch không vượt quá $d$==
Ta có thể áp dụng công thức **Quy hoạch động** giống dãy con chung dài nhất:
```cpp
if (abs(L[i] - R[j]) <= d)
dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
```
**Độ phức tạp thời gian:** $O \left( n^3 \right)$.
:::success
:::spoiler Code
```cpp=1
namespace sub1
{
bool checkSub12()
{
return n <= 100;
}
int dp[1009][1009], l[1009], r[1009];
void sub12()
{
int res = 0;
for(int s = 1; s <= 2 * n; s++)
{
int p = s, q = 2 * n - s;
// reset
for(int i = 0; i <= p; i++)
for(int j = 0; j <= q; j++)
dp[i][j] = 0;
// init
for(int i = 1; i <= s; i++)
l[i] = a[i]; // half left
for(int i = s + 1; i <= 2 * n; i++)
r[i - s] = a[i]; // half right
for(int i = 1; i <= p; i++)
{
for(int j = 1; j <= q; j++)
{
// dp LCS with special condition
if (abs(l[i] - r[j]) <= d)
dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
res = max(res, dp[p][q]);
}
cout<< res;
}
}
```
:::
## Subtask 3
>[!Note] Ý tưởng:
>Vẫn là chia dãy ra làm hai nửa bằng biến $s$, tuy nhiên ta duy trì thêm mảng $pos_x$ lưu vị trí của các giá trị phân biệt này trong mảng $A$ gốc mà các giá trị này thuộc nửa phải
>
>Nếu một giá trị thuộc nửa trái, ta không quan tâm đến nó
>
>Duyệt toàn bộ các giá trị $A_i$ thuộc nửa trái, ta sẽ tìm tất cả các giá trị hợp lệ với nó, tức là $A_i-d \le val \le A_i+d$ sao cho $pos_x > s$, tối đa duyệt $2 \times d$ giá trị với $d \le 5$
Sau khi đã có tập các $val$ hợp lệ của $A_i$, ta **sort giảm dần** và cho chúng vào một $vector$ $1D$ **$local$**, mục đích để tìm $LIS$ ở phía sau
làm vậy với $s$ giá trị nửa trái, nhận ra vector **$local$** chứa các block giá trị, với $block_i$ chứa các giá trị $val$ giảm dần của $A_i$ nửa trái
Cuối cùng, ta tìm $LIS$ trên $local$, vì ta biết rằng $i_1 < i_2 <... < i_m$ và $i_{m+1} < i_{m+2} < ... < i_{2m}$, ta đã cố định được nửa trái tăng dần rồi, việc còn lại là tìm ra nửa phải tăng dần. Một $block_i$ chỉ lấy một giá trị $val$ trong đó để ghép với $A_i$, do đó ta phải sort giảm dần để tránh ghép sai
Đáp án là số lượng cặp có thể ghép được, tương ứng với $LIS$ trên $vector \ local$
**Độ phức tạp thời gian:** $O \left( n^2 \times \log_2n \right)$.
:::success
:::spoiler Code
```cpp=1
namespace sub3
{
bool checkSub3()
{
return 1;
}
vector<int> local;
int b[maxn], cnt;
int calcLIS()
{
cnt = 0;
for(int i : local)
{
int j = lower_bound(b + 1, b + 1 + cnt, i) - b;
cnt = max(cnt, j);
b[j] = i;
}
return cnt;
}
int pos[maxn];
void sub3()
{
for(int i = 1; i <= 2 * n; i++) pos[a[i]] = i;
int res = 0;
for(int bound = 1; bound < 2 * n; bound++)
{
local.clear();
for(int i = 1; i <= bound; i++)
{
int l = max(1ll, a[i] - d), r = min(2 * n, a[i] + d);
vector<int> v;
for(int val = l; val <= r; val++)
if (pos[val] > bound) v.pb(pos[val]);
sort(v.begin(), v.end(), greater<int>());
for(int id : v) local.pb(id);
}
res = max(res, calcLIS());
}
cout<< res<< el;
}
}
```
:::
# Bài 2 Mạng truyền thông
## Tóm tắt đề
Cho một cái cây có $n$ đỉnh, yêu cầu đếm số cách chọn ra $k$ đỉnh sao cho số cạnh tối thiểu để các đỉnh được chọn liên thông nằm trong khoảng $[l, r]$.
**Giới hạn:** $n \leq 1000, k \leq 4$
## Tính toán trước
- Mình sẽ tính trước khoảng cách giữa $2$ đỉnh $i, j$ để tối ưu độ phức tạp và có thể chạy được subtask 3.
- Mình cũng sẽ tính thứ tự $DFS$ của các đỉnh để áp dụng trong subtask 1, 2, 3.
## Subtask 1, 2, 3
Ở các subtask này, $n \leq 100$ nên chúng ta có thể chạy trâu để chọn ra các bộ $k$ đỉnh và kiểm tra điều kiện.
Chúng ta sẽ áp dụng tính chất sau để tính số cạnh cần thiết tối thiểu:
- Với tập $x$ đỉnh được chọn ta, đầu tiên ta sẽ sắp xếp các đỉnh đó theo thứ tự $DFS$, thì số cạnh cần sẽ là $$\displaystyle \frac{dis[a_1][a_2] + dis[a_2][a_3] + ...+dis[a_n][a_1]}{2}$$ (Với mảng $a$ lưu các đỉnh sau khi được sắp xếp).
Vậy thì chúng ta đã có thể chọn các đỉnh và tính được số cạnh cần thiết, sau đó chỉ cần kiểm tra xem số lượng cạnh đó có thuộc đoạn $[l, r]$ hay không để tính được đáp án.
**Độ phức tạp:** $O(n^k) \leq O(10^8)$
:::spoiler Code mẫu
```cpp=
namespace subtask1 {
bool check() {
return n <= 100 && k == 2;
}
void main() {
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (dis[i][j] >= l && dis[i][j] <= r) ++ans;
}
}
cout << ans << "\n";
}
};
namespace subtask2 {
bool check() {
return n <= 100 && k == 3;
}
void main() {
tour(1);
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
for (int t = j + 1; t <= n; ++t) {
int d = (dis[nd[i]][nd[j]] + dis[nd[j]][nd[t]] + dis[nd[t]][nd[i]]) / 2;
if (d >= l && d <= r) ++ans;
}
}
}
cout << ans << "\n";
}
};
namespace subtask3 {
bool check() {
return n <= 100 && k == 4;
}
void main() {
tour(1);
int ans = 0;
l <<= 1; r <<= 1;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
for (int t = j + 1; t <= n; ++t) {
for (int kk = t + 1; kk <= n; ++kk) {
int d = dis[nd[i]][nd[j]] + dis[nd[j]][nd[t]] + dis[nd[t]][nd[kk]] + dis[nd[kk]][nd[i]];
if (d >= l && d <= r) ++ans;
}
}
}
}
cout << ans << "\n";
}
};
```
:::
## Subtask 4
Ở subtask này chúng ta cần rút ra một nhận xét là đối với mỗi bộ $3$ đỉnh bất kì, chúng ta luôn có thể chọn ra một đỉnh sao cho khi xoá đỉnh đó khỏi cây ban đầu thì $3$ đỉnh được chọn sẽ thuộc $3$ thành phần liên thông khác nhau (mình sẽ gọi nó là đỉnh quan trọng).
Vậy chúng ta sẽ cố định đỉnh quan trọng và làm quy hoạch động để chọn ra $3$ đỉnh trong các cây con khác nhau khi đỉnh quan trọng là gốc.
Gọi $dp_{i, \: j, \: k}$ đại diện cho số cách chọn khi tính đến cây con thứ $i$ mà số đỉnh đã được chọn là $j$ và tổng số cạnh cần thiết là $k$. Công thức quy hoạch động sẽ là:
$$
dp_{i, \: j, \: k} = dp_{i - 1, \: j, \: k} + \sum_{t = 1}^{k} dp_{i - 1, \: j - 1, \: k - t} \cdot cnt_{i, \: t}
$$
(Với $cnt_{i, \: t}$ là số đỉnh trong cây con thứ $i$ của đỉnh quan trọng đang xét mà có độ cao là $t$)
**Lưu ý:** Trong các đỉnh được chọn có thể có đỉnh quan trọng.
:::spoiler Code mẫu
Code mẫu này chỉ tạo chiều đầu tiên của mảng $dp$ có độ lớn là $2$ để tối ưu bộ nhớ vì ta chỉ quan tâm đến cây con hiện tại và trước đó.
```cpp=
namespace subtask4 {
long long dp[2][4][N], cnt[N][N];
int mx;
vector<int> depths;
void dfs(int s, int depth, int p, int cur) {
++cnt[cur][depth];
mx = max(mx, depth);
for (int z: v[s]) {
if (z == p) continue;
dfs(z, depth + 1, s, cur);
}
}
void main() {
long long ans = 0;
for (int u = 1; u <= n; ++u) {
depths.clear();
for (int i = 0; i < (int)v[u].size(); ++i) {
mx = 0;
dfs(v[u][i], 1, u, i + 1);
depths.push_back(mx);
}
memset(dp, 0, sizeof(dp));
dp[0][0][0] = dp[0][1][0] = 1;
int lim;
for (int i = 1; i <= (int)depths.size(); ++i) {
int cur = i & 1;
int pre = cur ^ 1;
memset(dp[cur], 0, sizeof(dp[cur]));
for (int j = 0; j <= 3; ++j) {
for (int kk = 0; kk <= r; ++kk) {
lim = min(depths[i - 1], kk);
dp[cur][j][kk] = dp[pre][j][kk];
if (j > 0) {
for (int t = 1; t <= lim; ++t) {
dp[cur][j][kk] += dp[pre][j - 1][kk - t] * cnt[i][t];
}
}
}
}
fill_n(cnt[i] + 1, depths[i - 1], 0);
}
int last = depths.size() & 1;
for (int i = l; i <= r; ++i) {
ans += dp[last][3][i];
}
}
cout << ans << "\n";
}
};
```
:::
# Bài 3 Phép toán OR
## Tóm tắt đề
Cho một mảng gồm $n$ phần tử, đếm số cách chọn dãy $i_1, i_2,... i_k$ sao cho $a_{i_1}\hspace{0.1cm} OR \hspace{0.3cm} a_{i_2}\hspace{0.3cm} OR\hspace{0.1cm}... OR\hspace{0.3cm} a_{i_k} = x (L\le x\le R, x|3)$ theo modulo $10^9+7$.
## Subtask 1
**$n\le20$ và $a_i\le200$**
Quay lui đơn giản mà bạn, chẳng lẽ bạn không biết quay lui. :penguin:
**Độ phức tạp:** $O(2^n)$
## Subtask 2
**$n\le200$ và $a_i\le200$**
Với độ phức tạp nhỏ như thế này, chúng ta có thể quy về một bài toán quy hoạch động đơn giản. Ta gọi trạng thái quy hoạch động của ta là $dp[i][k][value]$ với $i$ là ta đang xét tới phần tử thứ $i$, với các dãy gồm $k$ số, và giá trị or của dãy bằng $value$, từ đó ta có công thức quy hoạch động như sau:
$$dp[i][k][value] = dp[i-1][k][value] + \sum dp[i-1][k-1][x](\forall x,value =x|a_i)$$
Từ đó thì kết quả của chúng ta sẽ là: $\sum_{x=L}^{R} dp[n][k][x](\forall x\vdots3)$
**Độ phức tạp thời gian:** $O(n \times k \times max(a_i))$
>[!note] Lưu ý
> - Ta có thể chứng minh được rằng giá trị lớn nhất của or tất cả các phần trong A chỉ đạt max là $255 = 2^8-1$ để set mảng dp
> - Chúng ta có thể giảm chiều dp từ dp 3 chiều xuống còn 2 chiều $dp[k][x]$ với $k$ là chiều dài của dãy đang xét, $x$ là giá trị của dãy đó bởi vì chúng ta chỉ phụ thuộc vào giá trị $dp$ mà ta đã tính ở $i-1$
:::spoiler Code mẫu
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int maxval = 255;
int a[300];
int dp[300][300];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, L, R;
cin >> n >> k >> L >> R;
for (int i = 0; i < n; ++i) cin >> a[i];
dp[0][0] = 1;
for (int i = 0;i<n;i++) {
for (int j = k; j >= 1; --j) {
for (int x = 0; x <= maxval; ++x) {
if (dp[j-1][x]) {
int val = x | a[i];
dp[j][val] += dp[j-1][x];
dp[j][val] %= MOD;
}
}
}
}
long long ans = 0;
int upper = min(R, maxval);
for (int x = max(0, L); x <= upper; ++x) {
if (x % 3 == 0) {
ans += dp[k][x];
ans = ans%MOD;
}
}
cout << ans % MOD;
return 0;
}
```
:::
## Subtask 3
**$L = R$ và các số có dạng $2^k$**
Hiển nhiên $0≢L(mod$ $3)$ $\rightarrow ans=0$
Với subtask này ta có thể sử dụng **DP bitmask**, ta định nghĩa $cnt[mask]$ là số lượng $a[i]$ là một bit con của $mask$, ta định nghĩa $dp[mask]$ là số cách chọn sao cho tổng $OR$ của các số thuộc tập con của mask:
$$ {dp}[mask] = \binom{cnt[mask]}{k}$$
Để tính được $ans$, ta thực hiện biến đổi mobius trên $dp$ để tính $ans$:
$$ ans=\sum\limits_{S⊆L}(dp[S]\times (-1)^{|S|+|L|})$$
::: spoiler Code mẫu
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e6+5;
int a[N],n,fact[N],inv[N],l,r,k,cnt[N],dp[1<<20];
int add(int a,int b)
{
return (a+b)%mod;
}
int mul(int a,int b)
{
return (1LL*a*b)%mod;
}
int sub(int a,int b)
{
return ((a-b)%mod+mod)%mod;
}
int binpow(int a,int b)
{
if(!b) return 1;
int ans=binpow(a,b/2);
ans=mul(ans,ans);
if(b&1) return mul(ans,a);return ans;
}
int nCk(int n,int k)
{
if(k>n) return 0;
return mul(fact[n],mul(inv[k],inv[n-k]));
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
if(fopen("OR.inp","r"))
{
freopen("OR.inp","r",stdin);
freopen("OR.out","w",stdout);
}
cin >> n >> k >> l >> r;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
if(l%3)
{
cout << 0;
return 0;
}
fact[0]=1;
for(int i=1;i<=n;i++)
{
fact[i]=mul(fact[i-1],i);
}
inv[n]=binpow(fact[n],mod-2);
for(int i=n-1;i>=0;i--)
{
inv[i]=mul(inv[i+1],i+1);
}
for(int i=1;i<=n;i++)
{
cnt[__lg(a[i])]++;
}
for(int mask=0;mask<1<<20;mask++)
{
for(int i=0;i<20;i++)
{
if((mask>>i)&1)
{
dp[mask]+=cnt[i];
}
}
}
int base=__builtin_popcount(l);
int ans=0;
for(int i=0;i<=l;i++)
{
if((i&l)==i)
{
if(__builtin_popcount(i)%2!=base%2)
{
ans=sub(ans,nCk(dp[i],k));
}
else
{
ans=add(ans,nCk(dp[i],k));
}
}
}
cout << ans;
}
```
:::
## Subtask 4
**$L = R$**
Vì bây giờ các phần tử không chỉ có 1 bit mà có thể có nhiều bit. Nhận thấy rằng vỡi mỗi $cnt[MASK]=\sum\limits_{S⊆ MASK}(cnt[S])$ $\rightarrow$ Ta cải tiến bằng **DP SOS** để tính $cnt$. Còn lại làm tương tự subtask 3.
:::spoiler Code mẫu
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e6+5;
int a[N],n,fact[N],inv[N],l,r,k,cnt[1<<20];
int add(int a,int b)
{
return (a+b)%mod;
}
int mul(int a,int b)
{
return (1LL*a*b)%mod;
}
int sub(int a,int b)
{
return ((a-b)%mod+mod)%mod;
}
int binpow(int a,int b)
{
if(!b) return 1;
int ans=binpow(a,b/2);
ans=mul(ans,ans);
if(b&1) return mul(ans,a);return ans;
}
int nCk(int n,int k)
{
if(k>n) return 0;
return mul(fact[n],mul(inv[k],inv[n-k]));
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
if(fopen("OR.inp","r"))
{
freopen("OR.inp","r",stdin);
freopen("OR.ans","w",stdout);
}
cin >> n >> k >> l >> r;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
if(l%3)
{
cout << 0;
return 0;
}
fact[0]=1;
for(int i=1;i<=n;i++)
{
fact[i]=mul(fact[i-1],i);
}
inv[n]=binpow(fact[n],mod-2);
for(int i=n-1;i>=0;i--)
{
inv[i]=mul(inv[i+1],i+1);
}
for(int i=1;i<=n;i++)
{
cnt[a[i]]++;
}
for(int i=0;i<20;i++)
{
for(int mask=0;mask<1<<20;mask++)
{
if((mask>>i)&1) cnt[mask]+=cnt[(mask^(1<<i))];
}
}
int base=__builtin_popcount(l);
int ans=0;
for(int i=0;i<=l;i++)
{
if((i&l)==i)
{
if(base%2!=__builtin_popcount(i)%2)
{
ans=sub(ans,nCk(cnt[i],k));
}
else ans=add(ans,nCk(cnt[i],k));
}
}
cout << ans;
}
```
:::
## Subtask 5
**không có ràng buộc gì thêm**
Cải tiến từ subtask 4, bây giờ ta cần tính ans của nhiều số, vì thế việc duyệt qua mọi $i(L\leq i \leq R, i|3)$ không đủ đáp ứng vì thế ta cần tính trước các kết quả. Xét mỗi $mask$ ta biết rằng $dp[mask]$ là số cách chọn $k$ phần tử sao cho tổng $OR$ là con của $mask$, gọi $ways[smask]$ là số cách chọn $k$ phần tử sao cho tổng $OR = smask$. Vậy theo định nghĩa, $dp[mask]$ tương đương số cách chọn $k$ phần tử sao cho bằng đúng từng $smask$ riêng biệt, nói cách khác:
$$dp[mask]=\sum\limits_{smask⊆mask}ways[smask]$$
Vậy lúc này ta có thể truy hồi mảng $ways[]$ bằng kĩ thuật $DP$ $SOS$ ngược. Đáp án là
$$\sum\limits_{X=L}^R(ways[X]\times [X|3])$$
:::spoiler Code mẫu
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e6+5;
int a[N],n,fact[N],inv[N],l,r,k,cnt[1<<20],dp[1<<20];
int add(int a,int b)
{
return (a+b)%mod;
}
int mul(int a,int b)
{
return (1LL*a*b)%mod;
}
int sub(int a,int b)
{
return ((a-b)%mod+mod)%mod;
}
int binpow(int a,int b)
{
if(!b) return 1;
int ans=binpow(a,b/2);
ans=mul(ans,ans);
if(b&1) return mul(ans,a);return ans;
}
int nCk(int n,int k)
{
if(k>n) return 0;
return mul(fact[n],mul(inv[k],inv[n-k]));
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
if(fopen("OR.inp","r"))
{
freopen("OR.inp","r",stdin);
freopen("OR.out","w",stdout);
}
cin >> n >> k >> l >> r;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=n;i++)
{
dp[a[i]]++;
}
fact[0]=1;
for(int i=1;i<=n;i++)
{
fact[i]=mul(fact[i-1],i);
}
inv[n]=binpow(fact[n],mod-2);
for(int i=n-1;i>=0;i--)
{
inv[i]=mul(inv[i+1],i+1);
}
for(int i=0;i<20;i++)
{
for(int mask=0;mask<1<<20;mask++)
{
if((mask>>i)&1)
{
dp[mask]+=dp[mask^(1<<i)];
}
}
}
for(int i=0;i<1<<20;i++)
{
dp[i]=nCk(dp[i],k);
}
for(int i=19;i>=0;i--)
{
for(int mask=0;mask<(1<<20);mask++)
{
if((mask>>i)&1)
{
dp[mask]=sub(dp[mask],dp[mask^(1<<i)]);
}
}
}
while(l%3) l++;
int ans=0;
for(int i=l;i<=r;i+=3)
{
ans=add(ans,dp[i]);
}
cout << ans;
}
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
