---
title: 'LiemChinh Contests Editorial'
disqus: MrTee & Teen2326
---

LiemChinh Contests Editorial
===

## LiemChinh #01

### TÌM Y
Bài này khá đơn giản, chỉ cần kiểm tra xem $n$ có chia hết cho $x$ và thương $\dfrac{n}{x}>0$ hay không.

### TRÒN CHỤC
Gọi $f(x)$ là số số chia hết cho $10$ trong khoảng $[1, x]$
Ta có $f(x) =$ $\left\lfloor\dfrac{x}{10}\right\rfloor$
Khi ấy bài kết quả của bài toán chính là $f(r-1)-f(l)$

### TỒNG MAX MIN
Bài có thể có nhiều cách làm. Chúng ta có thể làm theo cách duyệt qua dãy một lần để tìm min và max. Sau đó duyệt thêm một lần nữa để cộng tổng các giá trị bằng min và các giá trị bằng max

ĐPT: $O(n)$

### CẶP SỐ
Cặp số $(a_i, a_j)$ thỏa mãn đề bài có dạng:
$\dfrac{(a_i+a_j)}{2} = k \Rightarrow a_i+a_j = 2k$
Vậy ta cần tìm các cặp giá trị $(a_i, a_j)$ có tổng bằng $2k$. Đây là một bài toán quen thuộc.

### PA120
Ta có thể nhận xét rằng, 1 phục vụ có thể phục vụ hết tất cả các khách đến ở các thời điểm khác nhau. Từ đó có thể thấy rằng, kết quả của bài toán là số người đến cùng thời điểm nhiều nhất. Như vậy chúng ta có thể đếm tần số xuất hiện của các giá trị trong dãy h sử dụng một mảng $m[int(1e5)+7]$, kết quả bài toán là giá trị $m_i$ $max$

ĐPT: $O(n)$

## LiemChinh #02

### liemchinh
Bài này về thuật toán thì không có gì khó, nhưng nhiều bạn bị lừa ở chỗ: Phép toán `a/b` trong `C++` không phải lúc nào cũng bằng $\left\lfloor\dfrac{a}{b}\right\rfloor$, trường hợp dễ thấy nhất là phép chia số âm.

### mxmod
Ta có : $a$ $mod$ $i$ $=a-\left\lfloor\dfrac{a}{i}\right\rfloor \times i$

Ta chia 2 TH như sau :

+ $i \leq \left\lfloor\sqrt{a}\right\rfloor$ $\Rightarrow$ for trâu
+ $i>\left\lfloor\sqrt{a}\right\rfloor$ $\Rightarrow$ $\left\lfloor\dfrac{a}{i}\right\rfloor<\left\lfloor\sqrt{a}\right\rfloor$
Đặt $\left\lfloor\dfrac{a}{i}\right\rfloor=t$. Với mỗi giá trị $t$, để $a$ $\bmod$ $i$ max ta cần tìm $i$ min
Dễ thấy đáp án là $p=\left\lfloor\dfrac{a}{t+1}\right\rfloor+1$, và ta cần đảm bảo $l \leq p \leq r$.

ĐPT : $O(\sqrt a)$

### maxwseq
Xét trọng số ban đầu của dãy là $W = \displaystyle\sum_{i=1}^N A_i \times i$.

Khi xét đến phần tử thứ $i$ thì sẽ có hai lựa chọn:
**Lựa chọn 1:** Đưa phần tử $A_i$ lên đầu. Khi đó, những điều sau xảy ra:
- Phần tử $A_i$ chuyển về đầu nên $W$ sẽ mất đi giá trị là $A_i \times (i - 1)$.
- Các phần tử có vị trí từ $1$ đến $i - 1$ đều dịch lên $1$ chỉ số nên $W$ được tăng thêm giá trị là $\displaystyle\sum_{x=1}^{i-1} A_x$.
- Các phần tử có vị trí từ $i + 1$ đến $N$ không bị ảnh hưởng.

**Lựa chọn 2:** Đưa phần tử $A_i$ xuống cuối. Khi đó, những điều sau xảy ra:
- Phần tử $A_i$ chuyển về cuối nên $W$ sẽ được tăng thêm giá trị là $A_i \times (N - i)$.
- Các phần tử có vị trí từ $i + 1$ đến $r$ đều dịch xuống $1$ chỉ số nên $W$ sẽ mất đi giá trị là$\displaystyle\sum_{x=i+1}^{N} A_x$.
- Các phần tử có vị trí từ $1$ đến $i - 1$ không bị ảnh hưởng.

Những sự thay đổi trên hoàn toàn có thể tính được sử dụng prefix sum.

ĐPT: $O(n)$.

## LiemChinh #03

### PA059
Nhận thấy:
- Ước chung lớn nhất của n số bằng ước chung lớn nhất của n-1 số ban đầu và số thứ n.
Ta còn có thể tận dụng hàm `__gcd(x, y)` có sẵn trong thư viện giúp code gọn hơn.

### PA059
Cách làm:
- Tạo một vector chứa các chữ số là các số tự trong đáp án.
- Khi $n\neq0$, push vào vector phần tử $n%2$ rồi lấy $n = n / 2$.
- lặp lại đến khi $n=0$.
*Chú ý: khi in đáp án ta phải in từ dưới vector lên đầu.*

### PA508
Ta có thể chia hình tứ giác ra thành hai hình tam giác rồi tính diện tích hai tam giác nhỏ hơn rồi cộng lại.
-> Bài toán trở về việc tính diện tích tam giác biết tọa độ ba đỉnh của chúng.
Ta có thể thực hiện việc này bằng cách tính độ dài ba cạnh bằng công thức: d = $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$, rồi tính diện tích tam giác bằng công thức hê-rông.
*Chú ý: Ta đến để mọi số trong bài là long double để giảm thiểu sai số khi tính toán.*
Cách làm trên tuy đúng với việc tính diện tích tứ giác, nhưng lại không đúng khi đa giác có quá nhiều đỉnh. Đơn giản là vì cách làm này có quá nhiều việc cộng trừ số thực dẫn đến sai số. Vậy nên một cách làm khác tổng quát hơn là việc sử dụng công thức buộc dây giày. Bạn đọc có thể tỉm hiểu thêm.

### Khôi phục dãy
Ta có thể biến các phần tử $B_i$ từ trung binh cộng của các số từ 1 đến $i$ thành tổng các số từ 1 đến $i$ bằng cách nhân bản thân chúng với $i$.
Dễ thấy: $A_i = (A_1 + A_2 + ... + A_i) - (A_1 + A_2 + ... + A_{i-1}) = B_i - B_{i-1}$.

### Chọn tranh
Bài này là một bài dp cơ bản. Để giải bài toán, ta có thể tạo 3 mảng: $cur1[i], cur2[i], cur3[i]$ lần lượt là số cách chọn tranh $P$, số cách chọn tranh $A_x = P, A_y = Q$ sao cho $x<y$ và số cách chọn tranh $A_x = P, A_y = Q, A_z = R$ sao cho $x<y<z$ khi xét đến tranh thứ i.
Ta có công thức:
- cur3[i+1] += cur2[i] nếu $A_i=R$.
- cur2[i+1] += cur1[i] nếu $A_i=Q$.
- cur1[i+1] ++ nếu $A_i=P$.
Nhận thấy: ta có thể giảm bộ nhớ sử dụng bằng việc thay các mảng $cur1[i], cur2[i], cur3[i]$ bằng ba số tự nhiên $cur1, cur2, cur3$.
::: spoiler Code mẫu của lamlamlam

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,p,q,r,cur1=0,cur2=0,cur3=0;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    cin >> p >> q >> r;
    for(int i=0; i<n; i++){
        if(a[i]==r) cur3+=cur2;
        if(a[i]==q) cur2+=cur1;
        if(a[i]==p) cur1++;
    }
    cout << cur3;
}

:::

### Free Factorize
Để giải bài toán này, trước hết ta sẽ phân tích số n thành dạng $p_1^{a_1}* p_2^{a_2} *...* p_n^{a_n}$ với $p_1, p_2,..., p_n$ là các số nguyên tố.
Dễ thấy: các số $square-free$ cần tìm của chúng ta có dạng $p_{x_1}*p_{x_2}*...p_{x_n}$. Nên bằng phương pháp tham lam, ta có thể tìm số $square-free$ lớn nhất rồi hạ các lũy thừa $a_{x_1}, a_{x_2},...$ xuống 1 đơn vị cho đến khi tất cả bằng 0.
::: spoiler Code mẫu của lamlamlam

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int>> a;
void phan_tich(int n)
{
    for(int i=2; i<=sqrt(n); i++){
        if(n%i==0){
            int cnt=0;
            while(n%i==0){
                cnt++;
                n/=i;
            }
            a.push_back({i,cnt});
            phan_tich(n);
            return;
        }
    }
    if(n!=1) a.push_back({n,1});
}
bool rong(){
    for(int i=0; i<a.size(); i++){
        if(a[i].second!=0) return false;
    }
    return true;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    phan_tich(n);
    while(!rong()){
        int ans = 1;
        for(int i=0; i<a.size(); i++){
            if(a[i].second!=0){
                ans*=a[i].first;
                a[i].second --;
            }
        }
        cout << ans << '\n';
    }
}

:::

> Logic sẽ đưa chúng ta từ điểm A đến điểm B. Còn trí tưởng tượng và maithuy giúp ta bay đến mọi nơi.
~ Albert Einstein ft. Ivan Tèo ~

### xayhangrao
- Đầu tiên, ta sort lại mảng a giảm dần
- Ta nhận xét chỉ có 2 phương án chọn sau là tối ưu nhất
- + Chọn $k - 1$ miếng gỗ có $a$ lớn nhất có thể làm hàng rào và miếng gỗ còn lại là miếng gỗ có $b$ lớn nhất có thể làm cửa, độ đẹp của phương án này sẽ là $psA_{k - 1} + maxB_k$ (với $psA_i$ là $a_1 + a_2 + ... + a_i$ và $maxB_i$ là $max(b_i, b_{i + 1}, ..., b_n)$)
- + Chọn hết $k$ miếng gõ đầu để làm cửa và hàng rào, một trong những miếng gỗ này là cửa, độ đẹp của phương án này là $psA_k + b_g - a_g$ với $g (g \leq k)$ là miếng gỗ được chọn để làm hàng rào, phương án tối ưu là chọn $b_g - a_g$ lớn nhất.

::: spoiler Code mẫu fryingduc

/**
 *	author: fryingduc
 *	created:22.09.2023 15:05:46
**/
/* #pragma GCC optimize("Ofast,unroll-loops") */
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

#define int long long

const int maxn = 1e5+5;
int n, q, e[maxn];
pair<int, int> a[maxn];

namespace sub1{
    void solve(){
        int sum = 0;
        for(int i = 1; i <= n; ++i){
            sum += a[i].first;
        }
        int ans = 0;
        for(int i = 1; i <= n; ++i){
            ans = max(ans, sum - a[i].first + a[i].second);
        }
        cout << ans << " ";
    }
}
namespace sub2{
    void solve(){
        vector<int> best(n + 1);
        for(int i = 1; i <= n; ++i){
            best[1] = max(best[1], a[i].second);
            vector<int> v;
            for(int j = 1; j <= n; ++j){
                if(i == j) continue;
                v.push_back(a[j].first);
            }
            sort(v.begin(), v.end(), greater<int>());
            /* debug(i, v); */
            int cnt = 1, cur = a[i].second;
            for(int j = 0; j < v.size(); ++j){
                ++cnt;
                cur += v[j];
                best[cnt] = max(best[cnt], cur);
            }
        }
        /* debug(best); */
        for(int i = 1; i <= q; ++i){
            cout << best[e[i]] << ' ';
        }
    }
}
namespace sub3{
    void solve(){
        sort(a + 1, a + n + 1, greater<pair<int, int>>());
        priority_queue<pair<int, int>> pq;
        priority_queue<int> p;
        for(int i = 1; i <= n; ++i){
            pq.push({a[i].second, i});
        }
        vector<int> best(n + 1);
        int sum = 0;
        best[1] = pq.top().first;
        for(int i = 1; i <= n; ++i){
            sum += a[i].first;
            p.push(a[i].second - a[i].first);
            while(!pq.empty() and pq.top().second <= i){
                pq.pop();
            }
            if(pq.size()){
                best[i + 1] = max(best[i + 1], sum + pq.top().first);
            }
            best[i] = max(best[i], sum + p.top());
        }
        for(int i = 1; i <= q; ++i){
            cout << best[e[i]] << ' ';
        }
    }
}
void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].first;
    }
    for(int i = 1; i <= n; ++i){
        cin >> a[i].second;
    }
    for(int i = 1; i <= q; ++i){
        cin >> e[i];
    }
    if(q == 1 and e[1] == n){
        sub1::solve();
        return;
    }
    if(n <= 1000){
        sub2::solve();
        return;
    }
    sub3::solve();
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    /* freopen("xayhangrao.inp", "r", stdin); */
    /* freopen("xayhangrao.out", "w", stdout); */
    int test = 1;
    /* cin >> test; */
    for(int i = 1; i <= test; i++){
        /* cout << "Case " << "#" << i << ": "; */
        solve();
    }

    return 0;
}

:::
::: spoiler Code mẫu khanh_np

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define se second

using namespace std;

const int N=1e5+5;
int n,q;
ll a[N], b[N], ps[N], smx[N], f[N];
pii p[N];

bool cmp(pii a, pii b){
	return a.fi>b.fi || (a.fi==b.fi && a.se>b.se);
}
void pre(){
	sort(p+1, p+n+1, cmp);
	for (int i=1; i<=n; ++i)
		ps[i]=ps[i-1]+p[i].fi;
	for (int i=n; i>=1; --i)
		smx[i]=max(smx[i+1], p[i].se);
	f[1]=p[1].se;
	for (int i=2; i<=n; ++i)
		f[i]=max(f[i-1]+p[i].fi, ps[i-1]+p[i].se);
}
int main()
{
    freopen("xayhangrao.inp", "r", stdin);
	freopen("xayhangrao.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin>>n>>q;
	for (int i=1; i<=n; ++i)
		cin>>a[i];
	for (int i=1; i<=n; ++i){
		cin>>b[i];
		p[i]={a[i],b[i]};
	}
	pre();
	while(q--){
		int k;
		cin>>k;
		cout<<max(f[k], ps[k-1]+smx[k])<<" ";
	}
	return 0;
}

:::



### bài toán thú vị
- Sort lại 3 mảng $a$, $b$, $c$
- Với mỗi $y$, ta tìm hai vị trí $x$ và $z$ lớn nhất thoả mãn $a_x, c_z \leq b_y$ gọi $pF_i = f_1 + ... + f_i$, với từng $y$, sau khi tìm được $x, z$ ta sẽ cộng vào kết quả: $$ pA_x * pC_z + b_y (b_y * x * z + pA_x * z + pC_z * x) $$

::: spoiler Code mẫu

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

#define int long long

const int maxn = 1e5+5;
const int mod = 1e9+7;
int n, m, k, a[maxn], b[maxn], c[maxn];
int psa[maxn], psb[maxn], psc[maxn];

void solve(){
cin >> n >> m >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
for(int i = 1; i <= m; ++i){
cin >> b[i];
}
for(int i = 1; i <= k; ++i){
cin >> c[i];
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
sort(c + 1, c + k + 1);
int ans = 0;
for(int i = 1; i <= n; ++i){
psa[i] = (psa[i - 1] + a[i]) % mod;
}
for(int i = 1; i <= m; ++i){
psb[i] = (psb[i - 1] + b[i]) % mod;
}
for(int i = 1; i <= k; ++i){
psc[i] = (psc[i - 1] + c[i]) % mod;
}
for(int i = 1; i <= m; ++i){
int l = upper_bound(a + 1, a + n + 1, b[i]) - a - 1;
int r = upper_bound(c + 1, c + k + 1, b[i]) - c - 1;
ans = (ans + (l * r % mod) * (b[i] * b[i] % mod) % mod) % mod;
ans = (ans + b[i] * (psa[l] * r % mod + psc[r] * l % mod) % mod) % mod;
ans = (ans + psc[r] * psa[l] % mod) % mod;
}
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);

int test = 1;
// cin >> test;
for(int i = 1; i <= test; i++){
// cout << "Case " << "#" << i << ": ";
solve();
}

return 0;
}

:::


### Số yêu thích

Trước tiên xét tác động khi chọn số $x$ để đưa $L$ về $R$:

- $L < R$: Ta thấy nếu $L < x \leq R$ ta có thể biến $L$ thành $x$ sau đó chạy lên $R$. Ta có thể giảm cost ban đầu từ $R - L$ thành $R - x + 1$.
- $L > R$: Thay vì chạy $L$ đến $m$ xong quay về $1$, ta nhận xét nếu tăng $R$ lên $m$ đơn vị, bài toán trở về các đánh giá trên một đoạn thẳng. 

Từ đó ta có thể phát biểu lại bài toán dưới dạng các đoạn thẳng (Interval) trên trục $Ox$.

Với thao tác tăng số $l$ lên $r$ $(l < r)$ cần $r - l$ thao tác, ta có thể coi đó là một đoạn thẳng có chỉ số $[l + 1, r]$ trên trục $Ox$, khi đó độ dài của đoạn vẫn giữ nguyên là $r - l$.

Khi chọn một số $x \ (x \leq m)$, ta thấy có thể tối ưu đáp án nếu $x$ nằm trong $[l, r]$ bất kì, và đồng thời $x + m$ cũng được chọn. Như vậy ta duyệt qua từng $x$ và kiểm tra với $x$ và $x + m$ có thể tối ưu bao nhiêu đoạn, đến đây có thể sử dụng đánh dấu 2 đầu.

**Nhận xét**: Việc kiểm tra $x$ và $x + m$ là độc lập, tức một đoạn nếu chứa $x$ sẽ không chứa $x + m$ và ngược lại, do nếu $a[i] = a[i - 1]$ thì kết quả bằng $0$, vậy nên các đoạn ta xét chỉ có độ dài tối đa $m - 1$.

**Cài đặt**: Chuẩn bị 2 mảng hiệu $cnt$ và $tot$, với $cnt$ lưu tổng của các đầu mút $L$, và $tot$ lưu số đoạn phủ. Duyệt qua từng vị trí $x$, và tính xem nếu chọn $x$ sẽ được lợi bao nhiêu và lấy min của tất cả các $x$.


::: spoiler Code mẫu

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

#define int long long

const int inf = 1e18;
const int maxn = 1e5+5;
int n, m, a[maxn], cnt[maxn * 2], tot[maxn * 2];

int calc(int x){
return tot[x] * x - cnt[x];
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
int mx = a[1];
int sum = 0;
for(int i = 2; i <= n; ++i){
mx = max(mx, a[i]);
if(a[i] == a[i - 1]) continue;
int L = 0, R = 0;
if(a[i] < a[i - 1]){
L = a[i - 1] + 1, R = a[i] + m;
}
else{
L = a[i - 1] + 1, R = a[i];
}
sum += (R - L + 1);
tot[L]++, tot[R + 1]--;
cnt[L] += L, cnt[R + 1] -= L;
}
for(int i = 1; i <= m * 2; ++i){
tot[i] += tot[i - 1];
cnt[i] += cnt[i - 1];
}
int ans = inf;
for(int i = 1; i <= mx; ++i){
int dak = calc(i) + calc(i + m);
ans = min(ans, sum - dak);
}
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);

int test = 1;
// cin >> test;
for(int i = 1; i <= test; i++){
// cout << "Case " << "#" << i << ": ";
solve();
}

return 0;
}

:::

## LiemChinh #04

><span style="color:orange">*"The best way to get a project done faster is to start sooner"* - Jim Highsmith</span>

### Diện tích tam giác
Diện tích tam giác bên trong có thể tính bằng 1/4 của diện tích hình vuông bên trong, ta có công thức:
$S =$ $\dfrac{(u^2+v^2)}{4}$
Chú ý sử dụng $long$ $double$ vì các số $u$, $v$ lớn.

### Đếm kí tự
Tạo một mảng ```d[int('z')+1]```, sử dụng mảng này ta có thể đếm số lần xuất hiện của các kí tự trong xâu. Từ đây ta có thể giải được bài toán một cách dễ dàng.

ĐPT: $O(n)$

### Tổng đơn lẻ
Ta có thể tạo một $map$ để đếm số lần xuất hiện của các số trong dãy, sau đó duyệt qua map và cộng vào tổng các số xuất hiện 1 lần.

ĐPT: $O(nlogn)$

### Xuất hiện
Ta có thể sort lại dãy $b$. Sau đó duyệt qua dãy a. Với mỗi số $a_i$ được duyệt qua, sử dụng tìm kiếm nhị phân để tìm số đó trong dãy $b$.

ĐPT: $O(nlogn)$

### [Xâu đẹp](https://hnoj.edu.vn/problem/beastr)
- Kết quả: số lượng kí tự xuất hiện lẻ lần chia 2.
- Đếm số lần xuất hiện của các kí tự: có thể sắp xếp lại rồi đếm hoặc dùng mảng/map để đếm.
- Vì có nhiều truy vấn nên cần đếm trước khi thực hiện các truy vấn:
    - Gọi $d[i][c]=k$ là xét từ vị trí $0$ đến vị trí $i$, có $k$ kí tự $c$.
    - Tính trước mảng này.
    - Trả lời các truy vấn bằng tổng cộng dồn: đoạn từ $l$ đển $r$ có bao nhiêu kí tự $c$ xuất hiện lẻ lần $(c = 'a'..'z')$
    
### 💌 (bản dễ)
Với giới hạn $k = 2,$ $m <= 20$, bài này có thể sử dụng sinh nhị phân sinh ra các khả năng của xâu s. Tuy nhiên nếu lưu $2^{20}$ xâu để sort thì sẽ bị MLE. Vì vậy, chúng ta sẽ sort lại các xâu $t_i$ , sau đó sinh như bình thường, các xâu sẽ sắp xếp tăng dần theo thứ tự từ điển.

::: spoiler Code mẫu của Hoàng Minh Quân

#include<bits/stdc++.h>
#define int long long

using namespace std;

int n,m,k,x;
string s;
string t[40];
int cnt;
vector<int> q;

void xinh(int i){
for(int j=0;j<k;j++){
s[q[i-1]] = t[i][j];
if(i==m){
cnt++;
if(cnt==x){
cout << s;
exit(0);
}
}
else xinh(i+1);
}
}

signed main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin >> n >> m >> k >> x;
cin >> s;
for(int i=0;i<s.size();i++) if(s[i]=='?') q.push_back(i);
for(int i=1;i<=m;i++) cin >> t[i], sort(t[i].begin(),t[i].begin()+t[i].size());
xinh(1);
}

:::

### [Trung bình cộng](https://hnoj.edu.vn/problem/tbc)
- Ta có: 
$(a_1+a_2+...+a_n)/n \ge k$
$(a_1+a_2+...+a_n) \ge k \times n$
$(a_1-k)+(a_2-k)+...+(a_n-k) \ge 0$
- Vậy để tìm đoạn con dài nhất có trung bình cộng lớn hơn hoặc bằng $k$ tức là:
    - Trừ mỗi phần tử của mảng $a$ đi $k$;
    - Bài toàn trở thành: Tìm đoạn con dài nhất có tổng lớn hơn hoặc bằng $0$. 
    - Để giải quyết bài này có thể làm hai cách:
        - Tổng cộng dồn, nếu tổng nhỏ hơn $0$ thì cắt bỏ (cho tổng lại về $0$), luôn cập nhật dộ dài dãy liên tiếp;
        - Tổng cộng dồn. Lưu thêm "min dồn". Tại vị trí $i$ đang tính tổng cộng dồn, tìm vị trí $j$ trước đó sao cho tổng dồn từ đầu đến $j$ là nhỏ nhất (min dồn).

### [Tính tổng độ mạnh](https://hnoj.edu.vn/problem/cwp)
Đọc đoạn code sau và lấy test để bài ra để nghĩ (tác giả lười viết hướng dẫn quá)
::: spoiler Code

void solve(){
mp.clear();
int ans = 0;
for (int i = 1; i <= n; i++){
dp[i] = dp[i-1] + mp[a[i]];
ans += dp[i];
mp[a[i]] += i;
}
cout << ans << "\n";
}

:::

### [Trung bình siêu đắc](https://hnoj.edu.vn/problem/average)
- **Subtask 1:**
    - Kiếm tra toàn bộ đoạn con. Độ phức tạp $O(n^2)$

    Trước hết ta có nhận xét, với một dãy $B$ bất kì có độ dài $m$, nếu trung bình các phần tử của $B$ lớn hơn $d$ thì $\sum{B_i} - m*d \ge 0$ .

- **Subtask 2 + 3:**

    **Ý tưởng:** Tìm kiếm nhị phân và cách tính giống bài [Trung bình cộng](https://hackmd.io/nQY4Oec3RiCK7FIBK6TGfw?both#Trung-b%C3%ACnh-c%E1%BB%99ng) 
    Với một giá trị $d$ bất kì để kiểm tra xem có tồn tại dãy ta làm như sau:
    + Gọi $p_i = \sum_{j=1}^{i} A_j - i * d$ và $g_i = min(p_1, p_2, ..., p_i)$.
    + Nếu tồn tại vị trí $j \in \{k, n\}$ sao cho $p_j - g_{j - k} \ge 0$ thì thỏa mãn.

    Với **Subtask 2** ta tìm kiếm nhị phân trên tập số nguyên như bình thường, với **Subtask 3** thì cần tìm kiếm nhị phân trên tập số thực nên cần chú ý sai số. Độ phức tạp $O(nlogn)$
    
### 💌 (bản khó)
- Subtask 1: 
Với $x=1$ hay ta cần tìm xâu có thứ tự từ điển thấp nhất, ta chỉ cần điền vào mỗi dấu $?$ thứ $i$ kí tự có thứ tự từ điển thấp nhất trong xâu $k_i$
ĐPT: $O(m.k)$

- Subtask 2+3:

Subtask 2 củ bài này với giới hạn $m <= 10^5$ thì chúng ta cùng không dùng cách ở bản dễ được.
Từ gợi ý từ bản dễ, chúng ta có thể nhận ra vị trí thứ tự sắp xếp của các khả năng của xâu s có liên quan tới các số ở hệ cơ số k. Để có thể hiểu rõ hơn ta có thể xét ví dụ ở test mẫu:

10 3 2 4
d?uch?mq?a
ai
ie
ui

Đầu tiên ta sort lại các xâu $t_i$ như ở bản dễ và đánh số các số và đánh các chỉ số tăng dần từ $0$ đến $k-1$ cho các kí tự trong xâu k và chỉ số:

ai
01
ei
01
iu
01

Với $m$ dấu $?$, ta có không quá $k^m$ khả năng của xâu $s$. Với mỗi khả năng của s, ta gọi xâu $d$ có độ dài $m$ với $d_{i}$ lưu một số trong khoảng $[0; k)$ là chỉ số của kí tự được chọn trong xâu $t_i$ đã được sort. Các khả năng của xâu s sắp xếp theo thứ tự tăng dần và xâu $d$ tương ứng: 
1. dauchemqia - 000
2. dauchemqua - 001
4. dauchimqia - 010
5. dauchimqua - 011
6. diuchemqia - 100
7. diuchemqua - 101
8. diuchimqia - 110
9. diuchimqua - 111

Có thể nhận xét rằng, với 1 khả năng thứ $x$ của xâu s khi sắp xếp theo thứ tự từ điển thì xâu $d$ tương ứng chính là số $x-1$ ở dạng cơ số k.
Từ nhận xét này, ta có thể biến đổi x về cơ số k, giả sử ta biểu diễn số đó bằng xâu $d$, khi đó dấu $?$ thứ $i$ sẽ được thay bằng kí tự có chỉ số $d_i$ trong xâu $t_i$.
Để có thể chuyển $x-1$ về dạng cơ số k, ta sẽ chia x cho k để lấy số dư cho đến khi x bằng 0. sau đó đảo ngược dãy số dư ta tìm được.
:::spoiler Ví dụ chuyển số x sang cơ số k

string convertBase(int x, int k) {
string ans = "";
while(x > 0){
int m = x%k;
ans+=char(m+48);
x/=k;
}
reverse(ans.begin(), ans.end());
return ans;
}

:::
:::spoiler Code mẫu của Lê Ngọc Minh

//Author: 25812M_MingLe

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+7;
int n, m, k, x;
string s;
char d[N][27];

signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m>>k>>x;
cin>>s;
vector<int> b;
for(int i = 0; i < s.size(); i++){
if(s[i] == '?') b.push_back(i);
}
for(int i = 1; i <= m; i++){
cin>>d[i];
sort(d[i], d[i]+k);
}
x--;
vector<int> v;
while(x > 0){
v.push_back(x%k);
x/=k;
}
while(v.size() < m) v.push_back(0);
reverse(v.begin(), v.end());
for(int i = 0; i < v.size(); i++){
//cout<<d[i]<<" "<<v[i]<<endl;
s[b[i]] = d[i+1][v[i]];
}
cout<<s;
}

:::


## LiemChinh #05
### 1. [Chia kẹo](https://hnoj.edu.vn/problem/candy_1) 
<span style="color:red">*Editor: Vũ Mạnh Hùng*</span>

Đây là 1 bài mở đầu contest nên tương đối đơn giản , chỉ cần sử dụng 1 chút toán học (lớp mình chắc mọi người đều giỏi toán) liên quan đến số chẵn và số lẻ . Ta có thể thấy An và Bình đều muốn nhận số kẹo là số chẵn nên tổng số kẹo phải là số chẵn ( và lớn hơn hoặc bằng 4 nhé chứ bằng 2 không chia được đâu) .Ngoài ra đề bài còn yêu cầu chia sao cho số kẹo của mỗi người chênh nhau là ít nhất . Có thể thấy nếu tổng số kẹo là 1 số chia hết cho 4 thì số kẹo của mỗi bạn An và Bình là nửa tống số kẹo . Nếu tổng số kẹo của mẹ là 1 số chia 4 dư 2 thì khi chia 2 chúng ta được 2 số lẻ bằng nhau , do đó để được 2 số chẵn thì chỉ cần -1 và +1 vào số kẹo của An và Bình . 
:::spoiler Code mẫu

#include <bits/stdc++.h>
#define int long long
using namespace std ;
signed main () {
freopen ("candy.inp" ,"r" , stdin) ;
freopen ("candy.out" ,"w" , stdout) ;
int n ;
cin >> n ;
if (n%4 == 0 ) {
cout << n/2 << " " << n/2 ;
}
else if (n%4 == 2 && n > 4 ) {
cout << n/2 - 1 << " " << n/2 + 1 ;
}
else if (n%4 == 1 ) {
cout << -1 ;
}
else if (n%4 == 3 ) {
cout << -1 ;
}
else if (n < 4 ) {
cout << -1 ;
}
return 0 ;
}

:::

### 2. [Đếm cặp XY](https://hnoj.edu.vn/problem/cpxy)

<span style="color:red">*Editor: Nguyễn Công Duy*</span>

Từ đề bài,ta sẽ xử lý 4 trường hợp  :
+ Th1 $a < d$
Khi đó,đoạn $[a,b]$ sẽ lớn hơn hẳn đoạn $[c,d]$ nên kết quả là 0.
+ Th2 $b < c$
Khi này,toàn bộ đoạn $[a,b]$ sẽ nhỏ hơn hẳn đoạn $[c,d]$ nên mọi cặp $x,y$ đều thỏa mãn,do đó kết quả là $(b - a + 1) * (d - c + 1)$
+ Th3 $a <=c <=b$
Ta thấy mọi số trong đoạn $[a,c-1]$ đều nhỏ hơn các số trong đoạn $[c,d]$ nên số cặp có thể chọn sẽ là $(c - a) * k$.
Còn với các số còn lại,ta lấy $h = min(b,d)$ để xác định số còn lại để xét bằng việc tính $n = h-c+1$. Khi đó ,số cặp có thể chọn từ các số này sẽ là $(2*d-h-c)*n/2$.
+ Th4 $c <= a <= d$
Ta xử lý tương tự nửa sau của trường hợp 3.
:::spoiler Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a > d) {
cout << 0;
}
else if (b < c) {
cout << (b - a + 1) * (d - c + 1);
}
else if (a <= c) {
int k = d - c + 1;
int o= (c - a) * k;
int h = min(b, d);
int n = h - c + 1;
int o1 = (d - h + d - c) * n / 2;
cout << o1 + o;
}
else {
int h = min(b, d);
int n = h - a + 1;
int res= (d - h + d - a) * n / 2;
cout << res;
}
return 0;
}

:::

### 3. [Ký sinh đô thị](https://hnoj.edu.vn/problem/kysinhdothi)

<span style="color:red">*Editor: Lê Vĩnh Khoa*</span>

Cách làm giống hệt bài Số đơn lẻ trong LC2 (tính số phần tử phân biệt trong dãy), có thể dùng unordered_set để nhanh hơn. Unordered_set sẽ chỉ nhận các giá trị mà trước đó chưa được nhập vào (nếu nhập giá trị đã có sẵn trước đó thì sẽ tự động xóa), và tự động sort theo thứ tự giảm dần.
:::spoiler Code mẫu

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n; unordered_set<int> st;
signed main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
while (n--) {
int k; cin >> k;
st.insert(k);
}
cout << st.size();
return 0;
}

:::

### 5. [Đếm đoạn](https://hnoj.edu.vn/problem/sstring)

<span style="color:red">*Editor: Trần Đức Minh*</span>

Vì mỗi đoạn chỉ có cần 1 phần tử riêng biệt để được coi là 2 đoạn con khác nhau nên ta sẽ cố gắng tìm đoạn con chung dài nhất có thể của 2 đoạn này và  dịch lên một phần tử lên để thu về 2 đoạn con theo đề bài.
+Để thu được điều này,đầu tiên ta tìm vị trí số ‘$1$’ đầu tiên và cuối cùng của xâu,gọi chúng là $q1,q2$ và tìm khoảng cách của chúng đến đầu/cuối xâu,rồi gọi t là min của chúng. Từ đó,ta thấy đoạn $[q1-t,q2+t-1]$  và $[q1-t+1,q2+t]$ sẽ có cùng số phần tử ‘$1$’ do đoạn $[q1-t+1,q2+t-1]$ giống nhau và vị trí $q1-t$ và $q2+t$ sẽ đều là các phần tử ‘$0$’.
+Làm tương tự với vị trí của số ‘$0$’,ta thu về $e1,e2$ và $h$.Mục đích là để xử lý trường hợp phần tử ‘$1$’ ở ngay đầu/cuối.
Nếu $h$/$t$ bằng với độ dài của xâu,tức xâu đó chỉ chứa toàn ‘$0$’/’$1$’,ta dễ thấy độ dài đoạn con đáp ứng yêu câu đề bài.
Trong trường hợp còn lại, ta so sánh độ dài của 2 đoạn chung đã thu được ở trên và chọn lấy đoạn có trường hợp dài hơn.
:::spoiler Code mẫu

#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <climits>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <math.h>
#include <iomanip>
#include <string>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
const int MN = 1e5 + 5;

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin >> s;
int l, r;
int cnt1=0, cnt2=0;
int l1, r1;
int t1 = 0, t2 = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1') {
l = i + 1;
break;
}
cnt1++;
}
for (int i = 0; i < s.size(); i++) {
if (s[i] == '0') {
l1 = i + 1;
break;
}
t1++;
}
for (int i = s.size()-1; i >= 0; i--) {
if (s[i] == '1') {
r = i + 1;
break;
}
cnt2++;
}
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] == '0') {
r1 = i + 1;
break;
}
t2++;
}
if (cnt1 == s.size() || t1 == s.size()) {
cout << 1 << " " << s.size()-1 << " " << 2 << " " << s.size();
}
else {
int cnt = min(cnt1, cnt2);
int t = min(t1, t2);
int k = r+2*cnt-l;
int h = r1+2*t-l1;
if (k > h) {
cout << l - cnt << " " << r + cnt - 1 << " " << l - cnt + 1 << " " << r + cnt;
}
else {
cout << l1 - t << " " << r1 + t - 1 << " " << l1 - t + 1 << " " << r1 + t;
}
}
return 0;
}

:::

### 7. [Kiểm tra](https://hnoj.edu.vn/problem/ktra)
<span style="color:red">*Editor: Phạm Nguyễn Đăng Huy*</span>

**Subtask 1:**
Ta duyệt tất cả các cách gọi có thể. Độ phức tạp $O(T!)$ với $T = c_1 + c_2 + \dots c_K$.

**Subtask 2, 3:**

Ta sử dụng quy hoạch động: 
- Gọi $f(x)$ là đáp số của bài toán nếu chỉ xét các màu từ $1$ đến $x$.
- Ban đầu ta có $f(1) = 1$.
- Chuyển vị: Xét màu thứ $x$. Ta chỉ cần gọi một bạn mặc áo có màu $x$ cuối cùng, còn các bạn mặc áo có màu $x$ còn lại có thể được gọi lên tùy ý. Vậy số cách để thêm màu $x$ vào sẽ là $\displaystyle \binom{c_1 + c_2 + \dots c_x - 1}{c_{x} - 1}$ (trừ $1$ vì ta phải xếp một bạn vào cuối cùng). Ta có công thức chuyển vị:
$f(x) = f(x - 1) \times \binom{c_1 + c_2 + \dots c_x}{c_{x} - 1}$

    Nếu sử dụng cách tính hệ số nhị thức bằng quy hoạch động, các bạn sẽ giải quyết được subtask 2. Để giải quyết subtask 3 thì phải dùng **nghịch đảo modulo**.

    Cách tính hệ số nhị thức: [VNOI Wiki](https://vnoi.info/wiki/translate/he/Number-Theory-5.md#h%E1%BB%87-s%E1%BB%91-nh%E1%BB%8B-th%E1%BB%A9c-binomial-coefficients)
    Về nghịch đảo modulo: [VNOI Wiki](https://vnoi.info/wiki/algo/math/modular-inverse.md)

Độ phức tạp: $O(n * log(mod - 2)))$

(Vì bộ test mình tạo khá yếu nên một số submission tính hệ số nhị thức trong $O(n)$ vẫn AC ._.)

:::spoiler Code mẫu (kh0i):

#include "bits/stdc++.h"
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 3;
const ll mod = 1e9 + 7;

ll fact[N], invfact[N];

ll binpow(ll a, ll b){
if(b == 0)
return 1;
ll res = binpow(a, b >> 1);
res = (res * res) % mod;
if(b & 1)
return (res * a) % mod;
return res;
}

void precalc(){
fact[0] = 1;
for(ll i = 1; i < N; ++i)
fact[i] = (fact[i - 1] * i) % mod;
invfact[N - 1] = binpow(fact[N - 1], mod - 2);
for(ll i = N - 2; i >= 0; --i)
invfact[i] = (invfact[i + 1] * (i + 1)) % mod;
}

ll nCk(ll n, ll k){
if(k > n)
return 0;
return (((fact[n] * invfact[k]) % mod) * invfact[n - k]) % mod;
}

void solve(){

int k;
ll x, res = 1, total = 0;

cin >> k;
for(int i = 1; i <= k; ++i){
cin >> x;
res = (res * nCk(total + x - 1, x - 1)) % mod;
total += x;
}
cout << res << '\n';
}

int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
precalc();
int test = 1;
cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
return 0;
}

:::

### 8. [Bể xăng](https://hnoj.edu.vn/problem/fuel)
<span style="color:red">*Editor: Hoàng Minh Quân*</span>

Ý tưởng của bài này là tính xem cần lượng xăng là bao nhiểu để xăng tràn qua một cột bất kì từ 2 phía trái phải. Sau đó với mỗi k nhập vào ta sẽ dùng tìm kiếm nhị phân để tỉm xem số cột đã bị tràn qua ở cả 2 phía.
* Để tính lượng xăng này ta chỉ cần tìm được cột xăng gần nhất mà cao hơn cột đang xét (ví dụ ta sẽ xét với xăng đổ từ bên trái). Xét cột thứ $i$ ở vị trí $v_i$ và chiều cao $h_i$ có cột gần nhất cao hơn nó là $k$ ($v_k < v_i$ và $h_k >= h_i$)
* Để tìm cột xăng gần nhất cao hơn cột đang xét ta sẽ sử dụng stack. Ý tưởng là đút các phần tử vào stack theo thứ tự và khi xét đến $h_i$ cao hơn chiều cao của vị trị ở trên cùng thì sẽ pop phần tử đó ra. (Lưu ý: nếu muốn tìm phần tử gần nhất ở bên trái cần đảo ngược mảng ban đầu của đề bài).
:::spoiler Code tìm phần tử gần nhất có giá trị lớn hơn

void next_greater_element_right_side(){
stack<int> s;
s.push(0);
for (int i = 1; i <= n; i++) {
if(s.empty()){
s.push(i);
continue;
}
while(!s.empty() and h[s.top()] < h[i]) {
nge_right[s.top()] = i;
s.pop();
}
s.push(i);
}
while (s.empty() == false) {
nge_right[s.top()] = n + 1;
s.pop();
}
}

:::


* Sau khi tìm được $k$ thấy rằng lượng xăng để tràn qua cột $i$ sẽ bằng lượng xăng tràn qua cột $k$ cộng với diện tích hình chữ nhật có chiều rộng $h_i$ và chiều dài $v_i - v_k - 1$ trừ đi chiều cao các cột nằm giữa $i$ và $k$.
* Gọi lượng xăng để tràn qua cột thứ $i$ khi đổ từ trái sang là $L_i$ với $L_0 = 0$ và $pf_i$ là mảng tổng cộng dồn
* Ta sẽ có công thức: $l[i] = l[k] + h[i] * (v[i] - v[k] - 1) - pf[i-1] + pf[k];$

:::spoiler Code mẫu

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int mq = 1e5 + 6;
int n, m;
int pf[mq], sf[mq];
vector<int> va, vb;
pair<int, int> a[mq];
pair<int, int> b[mq];
int mxa[mq], mxb[mq];
int l[mq], r[mq];

void ange(){
stack<int> s;
s.push(0);
for (int i = 1; i <= n; i++) {
if (s.empty()) {
s.push(i);
continue;
}
while(!s.empty() and a[s.top()].second < a[i].second) {
mxb[s.top()] = i;
s.pop();
}
s.push(i);
}
while (s.empty() == false) {
mxb[s.top()] = n + 1;
s.pop();
}
}

void bnge(){
stack<int> s;
s.push(0);
for (int i = 1; i <= n; i++) {
if (s.empty()) {
s.push(i);
continue;
}
while(!s.empty() and b[s.top()].second < b[i].second) {
mxa[s.top()] = i;
s.pop();
}
s.push(i);
}
while(s.empty() == false){
mxa[s.top()] = n + 1;
s.pop();
}
}

signed main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin >> n >> m;
a[0].second = 1e8;
b[0].second = 1e8;
b[n+1].second = 1e8;
a[n+1].second = 1e8;
a[0].first = 0;
b[0].first = 0;
for(int i=1;i<=n;i++){
cin >> a[i].first;
b[n-i+1].first = m - a[i].first;
}
for(int i=1;i<=n;i++){
cin >> a[i].second;
b[n-i+1].second = a[i].second;
pf[i] = pf[i-1] + a[i].second;
}
for(int i=1;i<=n;i++) sf[i] = sf[i-1] + b[i].second;
ange();
bnge();
l[0] = 1;
for(int i=1;i<=n;i++){
int k = n - mxa[n-i+1] + 1;
l[i] = l[k] + a[i].second * (a[i].first - a[k].first - 1) - pf[i-1] + pf[k];
// cout << l[i] << ' ';
}
// cout << endl;
r[0] = 1;
for(int i=1;i<=n;i++){
int k = n - mxb[n-i+1] + 1;
r[i] = r[k] + b[i].second * (b[i].first - b[k].first - 1) - sf[i-1] + sf[k];
// cout << r[i] << ' ';
}
int q;
cin >> q;
while(q--){
int k;
cin >> k;
int x = upper_bound(r+1,r+n+1,k) - r - 1;
int y = upper_bound(l+1,l+n+1,k) - l - 1;
// cout << x << ' ' << y << ' ';
int ans = x + y;
ans = min(ans, n);
cout << ans << '\n';
}
}

:::
### 9. [Tổng đoạn](https://hnoj.edu.vn/problem/sumseq)
<span style="color:red">*Editor: Phạm Nam Khánh*</span>

Xét dãy tổng tiền tố $s_1, s_2, ..., s_n$. Ta rút ra nhận xét sau:
1. Với đoạn con có phần tử cuối cùng là $i$:
- Tổng các phần tử của đoạn con có độ dài $l$ là: $s_i - s_l$;
- Tổng các phần tử của đoạn con có độ dài $l+1$ là: $s_i - s_{l+1}$;
- $...$
- Tổng các phần tử của đoạn con có độ dài $r$ là: $s_i - s_r$.
$\Rightarrow$ Điều đó có nghĩa là với đoạn con kết thúc tại $i$, chúng ta cần tìm giá trị nhỏ nhất của đoạn $s_r, s_{r-1}, ..., s_l$ để tạo ra tổng lớn nhất có thể.

2. Đoạn chúng ta cần xét luôn tịnh tiến với độ dài không đổi là $r-l+1$.

Như vậy, chúng ta có thể đưa bài toán này về một bài toán sliding window tìm min trên đoạn tịnh tiến. Có ít nhất hai cách để giải quyết bài toán:
1. Sử dụng `multiset`. Ý tưởng là khi xét đến $s_i$, ta sẽ lấy phần đầu tiên trong `multiset` rồi cập nhật kết quả. Sau đó, ta sẽ loại bỏ phần tử $s_{i-r}$ (vì khi xét đến $s_{i+1}$ thì $s_{i-r}$ không còn sử dụng được nữa) và đẩy phần tử $s_i$ vào.
2. Sử dụng `deque`. Tham khảo cách làm ở [đây](https://vnoi.info/wiki/algo/data-structures/deque-min-max.md#b%C3%A0i-to%C3%A1n-1).
3. Ai thích trâu bò thì có thể dùng cấu trúc dữ liệu segment tree hoặc sparse table, tuy nhiên mình sẽ không đề cập đến cách làm này ở đây. 

### 10. [Tạo hình vuông](https://hnoj.edu.vn/problem/makesqr)
<span style="color:red">*Editor: Đỗ Phúc An Nguyên*</span>

Để ý thấy, sau một thao tác chia hình chữ nhật thì ta sẽ được một bài toán mới với hình chữ nhật nhỏ hơn. Vì vậy, bài này có thể sử dụng quy hoạch động để giải.
* Gọi $f(i, j)$ là số thao tác nhỏ nhất để chia hình chữ nhật $i*j$ thành các hình vuông. Từ đó mình có thể lập một mảng 2 chiều $dp[i][j]$, với dữ liệu cơ sở là: $f(k, k) = 0,$ $f(1, k) = k - 1,$ $f(k, 1) = k - 1$.
* Với hình chữ nhật $i*j$ (phần tử $dp[i][j]$), mình sẽ chia thành 2 hình chữ nhật nhỏ hơn, theo chiều rộng và chiều dài theo từng đơn vị và tính số thao tác nhỏ nhất để chia 2 hình nhỏ đấy thành các hình vuông, và cứ như vậy để hoàn thành mảng $dp$. Khi đó, $dp[n][m]$ sẽ là kết quả cho 2 số $n, m$.
* Công thức: $dp[a][b] = min(dp[a][b], dp[a][i] + dp[a][b-i] + 1);$ $dp[a][b] = min(dp[a][b], dp[j][b] + dp[a-j][b] + 1);$ với $i$ trong khoảng $[1, b-1]$ và $j$ trong khoảng $[1, a-1]$.
:::spoiler Code mẫu

//Author: AlephNull0826

#include<bits/stdc++.h>
#define vi vector<int>
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fu(i, a, b) for(int i = a; i < b; i++)
#define fub(i, a, b) for(int i = a; i <= b; i++)
#define pii pair<int, int>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
const int inf = 1061109567;
int n, m, dp[501][501];
int solve(int a, int b){
if(a > b) swap(a, b);
if(dp[a][b] != inf) return dp[a][b];
if(a == b) return dp[a][b] = 0;
if(a == 1 || b == 1)return dp[a][b] = (a == 1 ? b - 1 : a - 1);
fu(i, 1, a)dp[a][b] = min(dp[a][b], solve(i, b) + solve(a-i, b) + 1);
fu(i, 1, b)dp[a][b] = min(dp[a][b], solve(a, i) + solve(a, b-i) + 1);
return dp[a][b];
}

int main(){
memset(dp, 63, sizeof(dp));
cin >> n >> m;
cout << solve(n, m);
}

:::


## Liem chính 06
### 4.Đoán xâu
<span style="color:red">*Editor: Đỗ Minh Khôi*</span>
Bài này sinh hết tất cả các xâu ra từ 1 đến n.
* Tạo một hàm gọi là quay lui, hàm này sẽ làm nhiệm vụ sinh hết xâu 
* Cho một biến dem bên ngoài để đếm số xâu đã sinh, 1 biến check để biết là đã sinh đủ xâu hay chưa
* For từ 65 đến 'Z' là đủ các kí tự của bảng chữ cái, với mỗi kí tự ta lại đệ quy để sinh ra chữ cái tiếp theo
* Khi nào độ dài >=K thì sẽ return, dem++
* dem == n thì ta return và check = true để hàm ngừng sinh
* Tạo một mảng là visited[], vào mỗi lần đệ quy sẽ chuyển ôn của kí tự được chọn là false, chạy đệ quy xong sẽ chỉnh thành true để tiếp tục chạy tiếp
:::spoiler Code mẫu

#include <bits/stdc++.h>
#define int long long

using namespace std;

void printArray(int a[], int n){
for (int i = 0; i < n; i++){
cout << a[i] << " ";
}
}

const int mn = 1e5 + 5;
char a[mn];
int b[mn];
bool visited[mn];
int n,z,idx,m;

int gcd(int a, int b){
if (b == 0) return a;
else return gcd(b, a % b);
}

int fb(int a){
if (a == 0 or a == 1) return 1;
return fb(a - 1) + fb(a - 2);
}

int luythua(int n){
if (n == 1) return 1;
return luythua(n - 1) * n;
}

bool check = false;
int dem=0;
void quaylui(int m,int idx){
if (check) return;
if (idx == z){
dem++;
if (dem == n){
for (int i = 0; i < z; i++){
cout << a[i];
}
check = true;
}
return;
}
for (int i = 65; i <= 90; i++){
if (visited[i] == false){
visited[i] = true;
a[idx] = i;
quaylui(m,idx + 1);
visited[i] = false;
}
}
}

signed main(){
cin.tie(0)->sync_with_stdio(0);
freopen("guess.inp","r",stdin);
freopen("guess.out","w",stdout);
cin >> n >> z;
quaylui(0,0);

return 0;
}

:::

### 7.Cộng trừ
Ta sẽ tính kết quả của phép tính khi chưa xóa ký tự nào. Sau đó thử xóa từng phẩn tử trong xâu để xem kết quả bị thay đổi thế nào.
* Ta sẽ tạo một mảng để tách các số và ký tự cộng trừ.
*  Chuyển các số từ dạng string sang int bằng hàm
*  Ta thấy nếu xóa một ký từ cộng hoặc trừ bất kì thì số đằng sau dấu này sẽ được xét theo dấu ở đằng trước nữa. Còn số ở trước dấu bị xóa sẽ được xét lên gấp 10 mũ độ dài của số đằng sau
*  Nếu xóa một chữ số bất kì ở một số nào đó thì ta có thể trừ ở đáp án được tính ban đầu số đó và cộng lại số mới đã bị xóa 1 chữ số (trừ và cộng là tùy theo dấu ở trước số)
::: spoiler Code mẫu

#include <bits/stdc++.h>
#define int long long

using namespace std;

int stn(string s){
int n = 0;
for(int i=0;i<s.size();i++ ){
int k = s[i];
n += k - '0';
n *= 10;
}
return n / 10;
}

int poww(int n, int k){
int tich = 1;
while(k--) tich *= n;
return tich;
}

signed main(){
cin.tie(nullptr)->sync_with_stdio(0);
string s;
cin >> s;
vector<string> v;
string tmp = "";
v.push_back("+");
for(int i=0;i<s.size();i++){
if(s[i]!='+' and s[i]!='-'){
tmp += s[i];
}
if(s[i]=='+'){
v.push_back(tmp);
v.push_back("+");
tmp = "";
}
if(s[i]=='-'){
v.push_back(tmp);
v.push_back("-");
tmp = "";
}
}
v.push_back(tmp);
vector<int> a;
for(int i=0;i<v.size();i++){
if(v[i]=="+"){
a.push_back(1);
continue;
}
if(v[i]=="-"){
a.push_back(-1);
continue;
}
a.push_back(stn(v[i]));
}
int ans = 0;

for(int i=1;i<a.size();i+=2) ans += a[i-1] * a[i];
int p = ans;
for(int i=2;i<a.size();i+=2){
int cur = p;
cur -= a[i] * a[i+1];
cur += a[i-2] * a[i+1];
cur -= a[i-2] * a[i-1];
cur += a[i-2] * a[i-1] * poww(10,v[i+1].size());
ans = max(cur, ans);
}
for(int i=1;i<a.size();i+=2){
for(int j=0;j<v[i].size();j++){
int cur = p;
cur -= a[i] * a[i-1];
string tmp = v[i];
tmp.erase(tmp.begin()+j);
int k = stn(tmp);
// cout << k << " ";
cur += k * a[i-1];
ans = max(ans, cur);
}
}
cout << ans;
}

:::
Ở đây mình sẽ để dấu '+' mang giá trị 1 còn dấu '-' mang giá trị -1 khi đó ta có thể thực hiện các phép cộng trừ dễ dàng hơn bằng cách nhân số với giá trị của dấu.