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

int n, m, k;
char a[1001][1001];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

void dfs(int i, int j, int &cnt){
    a[i][j] = '.';
    ++cnt;
    for(int id=0; id<4; id++){
        int ni = i + dx[id];
        int nj = j + dy[id];
        if(1 <= ni and ni <= n and 1 <= nj and nj <= m and a[ni][nj] == '#'){
            dfs(ni, nj, cnt);
        }
    }
}

void solve(){
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[i][j] = '.';
        }
    }
    for(int i=1; i<=k; i++){
        int x, y; cin >> x >> y;
        a[x][y] = '#';
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j] == '#'){
                int cnt = 0;
                dfs(i, j, cnt);
                res = max(res, cnt);
            }
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

int n, ok[101][101], vis[101];
vector<int> a[101];

void dfs(int &u){
    vis[u] = 1;
    for(int &v : a[u]){
        if(!vis[v] and ok[u][v]) dfs(v);
    }
}

int check(int i, int j){
    for(int u=1; u<=n; u++) vis[u] = 0;
    ok[i][j] = 0;
    int res = 0;
    for(int u=1; u<=n; u++){
        if(!vis[u]){
            dfs(u);
            ++res;
        }
    }
    ok[i][j] = 1;
    return res;
}

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> ok[i][j];
            if(ok[i][j]) a[i].push_back(j);
        }
    }
    int tplt = 0;
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            dfs(i);
            ++tplt;
        }
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(ok[i][j] and check(i, j) > tplt){
                ++res;
            }
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005

int n, m, d[mxn], sz[mxn];
 
int get(int u){
    if(u == d[u]) return u;
    return d[u] = get(d[u]);
}
 
void uni(int x, int y){
    x = get(x); y = get(y);
    if(x == y) return;
    if(x > y) swap(x, y);
    d[y] = x;
    sz[x] += sz[y];
}
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        d[i] = i;
        sz[i] = 1;
    }
    while(m--){
        int x, y; cin >> x >> y;
        uni(x, y);
    }
    int mx = 0;
    for(int i=2; i<=n; i++){
        int x = get(i);
        if(x > 1){
            mx = max(mx, sz[x]);
        }
    }
    cout << sz[1] + mx;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 

int n, m, s, t;
vector<int> a[105];
bool vis[105];
 
void dfs(int u){
    vis[u] = 1;
    for(int &v : a[u]){
        if(!vis[v]) dfs(v);
    }
}
 
void solve(){
    cin >> n >> m >> s >> t;
    while(m--){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        memset(vis, 0, sizeof vis);
        vis[i] = 1;
        dfs(s);
        if(!vis[t]) ++res;
    }
    cout << res << el;
    for(int i=1; i<=n; i++) a[i].clear();
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;
const int mxn = 1e3 + 7;

int n, m;
vector<int> a[mxn];
bool del[mxn], vis[mxn];

void dfs(int u){
    vis[u] = 1;
    for(int &v : a[u]){
        if(!vis[v]) dfs(v);
    }
}

void solve(){
    cin >> n >> m;
    while(m--){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
    }
    for(int i=1; i<=n; i++){
        for(int &j : a[i]){
            del[j] = 1;
        }
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        if(!del[i]){
            dfs(i);
            ++res;
        }
    }
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            dfs(i);
            ++res;
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();        
}

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

#define el '\n'
#define mxn 100005

int n, m, a[mxn], p[mxn], c[mxn];

int get(int u){
    if(u == p[u]) return u;
    return p[u] = get(p[u]);
}

void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        p[i] = i;
        c[i] = a[i];
    }
    while(m--){
        int x, y; cin >> x >> y;
        x = get(x); y = get(y);
        if(c[x] < c[y]) p[y] = x;
        else p[x] = y;
    }
    long long res = 0;
    for(int i=1; i<=n; i++){
        int u = get(i);
        res += c[u];
        c[u] = 0;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

const int mxn = 1e5 + 7;

int n, k, m; // các biến đề cho
int f[mxn]; // f[i]: thời gian tối thiểu người thứ i đến được lối thoát
vector<int> a[mxn]; // danh sách kề
bool ex[mxn]; // ex[i] = 1 -> lối thoát, ex[i] = 0 -> phòng bình thường

void bfs(int s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int &v : a[u]){
            // phòng v không phải lối thoát và
            // cách đi này tốn ít thời gian hơn các cách trước
            if(!ex[v] and f[u] + 1 < f[v]){
                f[v] = f[u] + 1;
                q.push(v);
            }
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    cin >> n >> k;
    // ban đầu gán giá trị lớn cho thời gian
    for(int i=1; i<=n; i++) f[i] = 1e8;
    while(k--){
        int room; cin >> room;
        ex[room] = 1; // room là lối thoát
        f[room] = 0; // không tốn thời gian di chuyển
    }
    cin >> m;
    while(m--){
        // thiết kế danh sách kề
        int x, y; cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    // BFS đa luồng -> xuất phát từ các lối thoát
    // đi đến các phòng khác để tìm thời gian tối thiểu
    for(int i=1; i<=n; i++) if(ex[i]) bfs(i);
    // in ra kết quả
    for(int i=1; i<=n; i++) cout << f[i] << ' ';
}

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

#define el '\n'
#define mxn 10004

int p[mxn];
int get(int u){
    if(u == p[u]) return u;
    return p[u] = get(p[u]);
}

void solve(){
    int n, q; cin >> n >> q;
    for(int i=1; i<=n; i++) p[i] = i;
    while(q--){
        int x, y, z; cin >> x >> y >> z;
        if(z == 1){
            x = get(x); y = get(y);
            if(x > y) swap(x, y);
            p[y] = x;
        }else{
            cout << (get(x) == get(y) ? "Yes\n" : "No\n");
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}  

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

#define el '\n'
#define mxn 100005

int n, q, a[mxn], p[mxn];
map<int, int> f[mxn];

int get(int u){
    if(u == p[u]) return u;
    return p[u] = get(p[u]);
}

void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        p[i] = i;
        ++f[i][a[i]];
    }
    while(q--){
        int t, x, y; cin >> t >> x >> y;
        if(t == 1){
            x = get(x); y = get(y);
            if(x == y) continue;
            if(x > y) swap(x, y);
            p[y] = x;
            for(auto &[i, j] : f[y]){
                f[x][i] += j;
            }
        }else{
            x = get(x);
            cout << f[x][y] << el;
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define pe pair<int, int>
int n, m, k, p[2][200005];
map<pe, int> mp;

int get(int u, int p[]){
    if(u == p[u]) return u;
    return p[u] = get(p[u], p);
}

void solve(){
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        p[0][i] = p[1][i] = i;
    }
    for(int i=0; i<m; i++){
        int x, y; cin >> x >> y;
        x = get(x, p[0]); 
        y = get(y, p[0]);
        if(x > y) swap(x, y);
        p[0][y] = x;
    }
    for(int i=0; i<k; i++){
        int x, y; cin >> x >> y;
        x = get(x, p[1]);
        y = get(y, p[1]);
        if(x > y) swap(x, y);
        p[1][y] = x;
    }
    for(int i=1; i<=n; i++){
        ++mp[{get(i, p[0]), get(i, p[1])}];
    }
    for(int i=1; i<=n; i++){
        cout << mp[{p[0][i], p[1][i]}] << ' ';
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define pe pair<ld, ld>
#define fi first
#define se second
#define el '\n'
#define ld long double

struct canh{
    int u, v;
    ld w;
};
 
int n, m, p[1005];
vector<canh> v;
 
int get(int u){
    if(u == p[u]) return u;
    return p[u] = get(p[u]);
}
 
ld dis(pe a, pe b){
    return sqrtl((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}
 
bool cmp(canh a, canh b){
    return a.w < b.w;
}
 
void solve(){
    cin >> n >> m;
    pe a[n+5];
    for(int i=1; i<=n; i++){
        p[i] = i;
    }
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    for(int i=1; i<=m; i++){
        int x, y; cin >> x >> y;
        x = get(x); y = get(y);
        if(x == y) continue;
        p[y] = x;
    }
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            v.push_back({i, j, dis(a[i], a[j])});
        }
    }
    sort(v.begin(), v.end(), cmp);
    ld mst = 0;
    int sz = 0;
    for(int i=0; i<v.size() and sz < n - 1; i++){
        canh c = v[i];
        int x = get(c.u), y = get(c.v);
        if(x == y) continue;
        p[y] = x;
        mst += c.w;
        ++sz;
    }
    cout << fixed << setprecision(2) << mst;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define pe pair<int, int>
#define fi first
#define se second
#define el '\n'
#define mxn 100005
#define int long long

int n, m, s, t, dp[mxn];
vector<pe> a[mxn];

void dijkstra(){
    for(int i=1; i<=n; i++) dp[i] = 1e16;
    dp[s] = 0;
    priority_queue<pe, vector<pe>, greater<pe>> q;
    q.push({dp[s], s});
    while(!q.empty()){
        auto top = q.top(); q.pop();
        int u = top.se;
        int kc = top.fi;
        if(kc > dp[u]) continue;
        for(auto &i : a[u]){
            int v = i.fi;
            int w = i.se;
            if(dp[u] + w < dp[v]){
                dp[v] = dp[u] + w;
                q.push({dp[v], v});
            }
        }
    }
    cout << dp[t];
}

void solve(){
    cin >> n >> m >> s >> t;
    while(m--){
        int x, y, w; cin >> x >> y >> w;
        a[x].push_back({y, w});
        a[y].push_back({x, w});
    }
    dijkstra();
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005

int n, sz[mxn];
vector<int> a[mxn];

void dfs(int u, int p = 0){
    sz[u] = 1;
    for(int &v : a[u]){
        if(v != p){
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}

void solve(){
    cin >> n;
    for(int i=1; i<n; i++){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1);
    for(int i=1; i<=n; i++) cout << sz[i] << ' ';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005

int n, d[mxn];
vector<int> a[mxn];

void dfs(int u, int p = 0){
    for(int &v : a[u]){
        if(v != p){
            d[v] = d[u] + 1;
            dfs(v, u);
        }
    }
}

void solve(){
    int k;
    cin >> n >> k;
    for(int i=1; i<n; i++){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1);
    sort(d+1, d+n+1, greater<int>());
    long long res = 0;
    for(int i=1; i<=k; i++) res += d[i];
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005

int n, res, dp[mxn];
vector<int> a[mxn];
string s;

void dfs(int u, int p = 0){
    if(s[u] == 'W') ++dp[u];
    else --dp[u];
    for(int &v : a[u]){
        if(v != p){
            dfs(v, u);
            dp[u] += dp[v];
        }
    }
    if(dp[u] == 0) ++res;
}

void solve(){
    cin >> n;
    for(int i=2; i<=n; i++){
        int p; cin >> p;
        a[p].push_back(i);
        a[i].push_back(p);
    }
    cin >> s; s = " " + s;
    res = 0;
    dfs(1);
    cout << res << el;
    for(int i=1; i<=n; i++){
        dp[i] = 0;
        a[i].clear();
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 303

int n, m, q, d[mxn][mxn];
 
void solve(){
    cin >> n >> m >> q;
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            d[i][j] = d[j][i] = 1e9;
        }
    }
    while(m--){
        int x, y, w; cin >> x >> y >> w;
        d[x][y] = w;
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
            }
        }
    }
    while(q--){
        int x, y; cin >> x >> y;
        if(d[x][y] != 1e9) cout << d[x][y] << el;
        else cout << "-1\n";
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Vì các toán hạng có thể có nhiều chữ số, hoặc là số âm nên ta sẽ coi mỗi toán tử/toán hạng là một xâu ký tự. Như vậy, ta sẽ nhập vào một mảng gồm $$$n$$$ xâu ký tự, rồi xử lý giống như bài ở trên Code PTIT.

• Ở đây, để kiểm tra một xâu đang duyệt đến có là "số" hay không thì ta chỉ cần kiểm tra ký tự cuối cùng của nó có là chữ số hay không ?

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

#define el '\n'
#define int long long

void solve(){
    int n; cin >> n;
    vector<string> v(n);
    for(auto &i : v) cin >> i;
    stack<int> st;
    for(int i=n-1; i>=0; i--){
        if(isdigit(v[i].back())){
            st.push(stoll(v[i]));
        }else{
            int x = st.top(); st.pop();
            int y = st.top(); st.pop();
            if(v[i] == "+"){
                st.push(x + y);
            }else if(v[i] == "*"){
                st.push(x * y);
            }else if(v[i] == "/"){
                st.push(x / y);
            }else st.push(x - y);
        }
    }
    cout << st.top() << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Vì các toán hạng có thể có nhiều chữ số, hoặc là số âm nên ta sẽ coi mỗi toán tử/toán hạng là một xâu ký tự. Như vậy, ta sẽ nhập vào một mảng gồm $$$n$$$ xâu ký tự, rồi xử lý giống như bài ở trên Code PTIT.

• Ở đây, để kiểm tra một xâu đang duyệt đến có là "số" hay không thì ta chỉ cần kiểm tra ký tự cuối cùng của nó có là chữ số hay không ?

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

#define el '\n'
#define int long long

void solve(){
    int n; cin >> n;
    vector<string> v(n);
    for(auto &i : v) cin >> i;
    stack<int> st;
    for(int i=0; i<v.size(); i++){
        if(isdigit(v[i].back())){
            st.push(stoll(v[i]));
        }else{
            int x = st.top(); st.pop();
            int y = st.top(); st.pop();
            if(v[i] == "+"){
                st.push(x + y);
            }else if(v[i] == "*"){
                st.push(x * y);
            }else if(v[i] == "/"){
                st.push(y / x);
            }else st.push(y - x);
        }
    }
    cout << st.top() << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Vì các toán hạng có thể có nhiều chữ số, hoặc là số âm nên ta sẽ coi mỗi toán tử/toán hạng là một xâu ký tự. Như vậy, ta sẽ nhập vào một mảng gồm $$$n$$$ xâu ký tự, rồi xử lý giống như bài ở trên Code PTIT.

• Ở đây, để kiểm tra một xâu đang duyệt đến có là "số" hay không thì ta chỉ cần kiểm tra ký tự cuối cùng của nó có là chữ số hay không ? Điều này sẽ giúp ta vừa kiểm tra được khi quyết định nhét nó vào stack cũng như là xác định biểu thức đã cho là tiền tố hay hậu tố.

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

#define el '\n'
#define int long long

void solve(){
	int n; cin >> n;
	string a[n+5];
	for(int i=1; i<=n; i++){
		cin >> a[i];
	}
	stack<int> st;
	if(isdigit(a[1].back())){
		for(int i=1; i<=n; i++){
			if(isdigit(a[i].back())){
				st.push(stoll(a[i]));
			}else{
				int x = st.top(); st.pop();
				int y = st.top(); st.pop();
				if(a[i] == "+"){
					st.push(x + y);
				}else if(a[i] == "-"){
					st.push(y - x);
				}else if(a[i] == "*"){
					st.push(x * y);
				}else{
					st.push(y / x);
				}
			}
		}
	}else{
		for(int i=n; i>=1; i--){
			if(isdigit(a[i].back())){
				st.push(stoll(a[i]));
			}else{
				int x = st.top(); st.pop();
				int y = st.top(); st.pop();
				if(a[i] == "+"){
					st.push(x + y);
				}else if(a[i] == "-"){
					st.push(x - y);
				}else if(a[i] == "*"){
					st.push(x * y);
				}else{
					st.push(x / y);
				}
			}
		}
	}
	cout << st.top() << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 1000006

int dp[mxn];
 
void solve(){
    int n, m; cin >> n >> m;
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        int x = q.front(); q.pop();
        if(x == m){
            cout << dp[x]; return;
        }
        if(x * 2 <= 1e6 and dp[x * 2] == 0){
            dp[x * 2] = dp[x] + 1;
            q.push(x * 2);
        }
        if(x - 1 >= 1 and dp[x - 1] == 0){
            dp[x - 1] = dp[x] + 1;
            q.push(x - 1);
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Xâu $$$s$$$ có thể có dấu cách nên ngoài các cách nhập xâu có dấu cách mà bạn có thể đã biết, thì mình có $$$1$$$ cách sau đây cũng khá đơn giản mà cũng có tác dụng tương tự getline(cin >> ws, s) thì ws ở đây mình nghĩ có nghĩa là whitespace, thì nó cũng giúp việc cin xong getline không bị lỗi. Tuy nhiên, nếu không có cin trước cái getline này, thì mình không khuyến khích các bạn sử dụng vì nó có thể gây lỗi.

• Ở bài toán này, ta sẽ sử dụng ngăn xếp để xử lý. Về cơ bản, phần thuật sẽ khá giống với bài kiểm tra dãy ngoặc đúng, chỉ khác ở chỗ khi gặp dấu ( ta sẽ in ra số thứ tự nó xuất hiện và đẩy số thứ tự đó vào stack (mục đích là để khi gặp dấu đóng ngoặc tương ứng, ta cũng sẽ in ra được số thứ tự này). Như vậy, khi gặp dấu ) thì ta chỉ cần in ra số ở đầu stack và pop nó ra.

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

#define el '\n'

void solve(){
    string a; getline(cin >> ws, a);
    int n = a.size();
    stack<int> st;
    int x = 1;
    for(int i=0; i<n; i++){
        if(a[i] == '('){
            cout << x << ' ';
            st.push(x);
            ++x;
        }else if(a[i] == ')'){
            cout << st.top() << ' ';
            st.pop();
        }
    }
    cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Ta sẽ sử dụng hàng đợi để sinh ra đủ $$$2 \times 10^5$$$ các số có tổng chữ số bằng $$$10$$$, lưu các phần tử trong hàng đợi theo cặp {số, tổng chữ số} để đỡ phải tính toán nhiều lần. Ta sẽ duyệt các chữ số $$$[0, 9]$$$ kiểm tra xem việc nối chữ số đó vào cuối đã làm tổng chữ số vượt quá $$$10$$$ hay chưa, nếu chưa vượt quá $$$10$$$ thì ta tiếp tục đưa nó vào hàng đợi. Với mỗi phần tử ở đầu hàng đợi mà có tổng chữ số là $$$10$$$, ta sẽ nhét chúng vào một cái vector/mảng để trả lời cho các truy vấn.

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

#define pe pair<int, int>
#define fi first
#define se second
#define el '\n'
#define int long long

vector<int> v;
void pre(){
    queue<pe> q;
    for(int i=1; i<=9; i++){
        q.push({i, i});
    }
    while(1){
        pe x = q.front(); q.pop();
        int n = x.fi, s = x.se;
        if(s == 10){
            v.push_back(n);
            if(v.size() == 2e5) return;
        }
        for(int i=0; i<=9; i++){
            if(s + i <= 10){
                q.push({n * 10 + i, s + i});
            }else break;
        }
    }
}
 
void solve(){
    int n; cin >> n;
    cout << v[n - 1] << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Ta sẽ xử lý bài toán này giống bài Giải mã xâu ký tự trên Code PTIT. Ý tưởng chính sẽ là phân tích hết các phân tử dạng nén ra thành nguyên tử, rồi sau đó cộng hết các giá trị đó và in ra kết quả.

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

#define el '\n'

int val(char c){
    // khối lượng nguyên tử
    if(c == 'C') return 12;
    if(c == 'O') return 16;
    return 1;
}
 
int it = 1;
void solve(){
    cout << "Test #" << it++ << ": ";
    string a; cin >> a;
    int n = a.size();
    stack<char> st;
    for(int i=0; i<n; i++){
        if(a[i] != ')'){
            // đang xét một phân tử có dạng nén
            // CH2O -> CHHO
            if(isdigit(a[i])){
                int times = a[i] - '0';
                for(int j=1; j<times; j++) st.push(st.top());
            }else st.push(a[i]);
        }else{
            // tính số lần nén, mặc định là 1
            int times = 1;
            if(i + 1 < n and isdigit(a[i + 1])) times = a[i + 1] - '0';
            // dịch thêm 1 chỉ số để bỏ qua "số lần lặp" vừa xét
            if(times > 1) ++i;
            // bắt đầu tìm công thức được lặp
            string s = "";
            while(!st.empty() and st.top() != '('){
                s += st.top();
                st.pop();
            }
            st.pop();
            // tạo ra công thức đầy đủ
            string str = "";
            while(times--) str += s;
            // rồi đưa lại vào ngăn xếp
            for(char &c : str) st.push(c);
        }
    }
    // tính toán kết quả
    int res = 0;
    while(!st.empty()){
        res += val(st.top());
        st.pop();
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Ta sẽ sử dụng hàng đợi để duyệt qua tất cả các số có thể gặp. Giống với thao tác đề bài cho, ta sẽ duyệt qua các cặp số có tích đúng bằng $$$n$$$, rồi tìm ra số mới và kiểm tra xem số đó đã được xét hay chưa ? Nếu chưa thì ta sẽ push nó vào hàng đợi rồi tiếp tục quá trình.

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

#define el '\n'
#define mxn 

void solve(){
    int n; cin >> n;
    map<int, int> mp; // đánh dấu các phần tử đã được xét
    queue<int> q;
    q.push(n); // bắt đầu quá trình
    while(!q.empty()){
        int x = q.front(); q.pop();
        int c = sqrtl(x);
        for(int u=1; u<=c; u++){
            // tìm các cặp số u, v
            if(x % u == 0){
                int v = x / u;
                int num = (u - 1) * (v + 1);
                if(!mp[num]){ // chưa xét
                    mp[num] = 1;
                    q.push(num);
                }
            }
        }
    }
    // in ra kết quả
    cout << mp.size() << el;
    for(auto &i : mp) cout << i.first << ' ';
    cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

int n, a[1000006];

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    stack<int> st;
    for(int i=1; i<=n; i++){
        if(st.empty()){
            st.push(a[i]);
        }else{
            if((st.top() + a[i]) % 2 == 0){
                st.pop();
            }else st.push(a[i]);
        }
    }
    cout << st.size();
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

int n;
map<string, int> mp;
int cal(string s){
    int res = 0;
    for(char &c : s){
        res = res * 10 + (c - '0');
        res %= n;
    }return res;
}
 
void solve(){
    cin >> n;
    queue<string> q;
    q.push("6"); mp["6"] = cal("6");
    q.push("8"); mp["8"] = cal("8");
    while(!q.empty()){
        string s = q.front(); q.pop();
        if(s.size() > 200) break;
        if(mp[s] == 0){
            cout << s; return;
        }
        string x = s + "6";
        if(mp[x] == 0){
            mp[x] = cal(x);
            q.push(x);
        }
        string y = "8" + s;
        if(mp[y] == 0){
            mp[y] = cal(y);
            q.push(y);
        }
    }
    cout << -1;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005

int n, q, a[mxn], dp[mxn];
stack<int> st;

void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    st.push(n);
    dp[n] = 0;
    for(int i=n-1; i>=1; i--){
        while(!st.empty() and a[st.top()] <= a[i]){
            st.pop();
        }
        if(!st.empty()){
            dp[i] = dp[st.top()] + 1;
        }else dp[i] = 0;
        st.push(i);
    }
    while(q--){
        int x; cin >> x;
        cout << dp[x] << el;
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

int n, m, a[1005][1005], l[1005][1005], r[1005][1005];
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
            if(a[i][j]){
                a[i][j] = a[i - 1][j] + 1;
            }
        }
    }
    for(int i=1; i<=n; i++){
        stack<int> st1;
        st1.push(1);
        l[i][1] = 0;
        for(int j=2; j<=m;j++){
            while(!st1.empty() && a[i][j] <= a[i][st1.top()]){
                st1.pop();
            }if(st1.empty()){
                l[i][j] = 0;
            }else l[i][j] = st1.top();
            st1.push(j);
        }
        stack<int> st2;
        st2.push(m);
        r[i][m] = m + 1;
        for(int j=m-1; j>=1; j--){
            while(!st2.empty() && a[i][j] <= a[i][st2.top()]){
                st2.pop();
            }if(st2.empty()){
                r[i][j] = m + 1;
            }else r[i][j] = st2.top();
            st2.push(j);
        }
    }
    int x = 0, y = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int left = l[i][j] + 1;
            int right = r[i][j] - 1;
            int len = right - left + 1;
            if(a[i][j] * len > x * y){
                x = min(a[i][j], len);
                y = max(a[i][j], len);
            }else if(a[i][j] * len == x * y and abs(a[i][j] - len) < y - x){
                x = min(a[i][j], len);
                y = max(a[i][j], len);
            }
        }
    }
    cout << x << ' ' << y << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Kiểu dữ liệu long long sẽ không lưu được số Fibonacci thứ $$$92$$$. Như vậy, chúng ta sẽ phải dùng unsigned long long.

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

#define el '\n'
#define int unsigned long long

int f[100];

void solve(){
    int n; cin >> n;
    cout << f[n] << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    f[0] = f[1] = 1;
    for(int i=2; i<=92; i++) f[i] = f[i - 1] + f[i - 2];

    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Với giới hạn lên tới $$$10^6$$$, việc duyệt qua từng số rồi tìm ước nguyên tố lớn nhất là không thể, vì ta sẽ mất $$$O(\sqrt n)$$$ để tìm ước, tức là xấp xỉ $$$10^3$$$ $$$\to$$$ tổng độ phức tạp sẽ là $$$O(10^9)$$$, vượt quá $$$1$$$ giây cho phép.

• Để có thể tối ưu được thời gian, ta sẽ cần sử dụng Sàng Biến Đổi ở đây. Đầu tiên, ta sẽ duyệt qua các số trong đoạn $$$[2, 10^6]$$$, với mỗi số $$$i$$$ đang xét tới, ta sẽ duyệt các bội của nó và cập nhật ước nguyên tố lớn nhất hiện tại chính là $$$i$$$. Tiếp theo, các truy vấn tính tổng tĩnh trong đoạn $$$[l, r]$$$ nào đó, ta sẽ phải nghĩ ngay đến Tổng cộng dồn để tiếp tục tối ưu thời gian, chứ không thể duyệt trâu các truy vấn được.

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

#define el '\n'
 
int d[1000005];
long long f[1000005];
void pre(){
    for(int i=2; i<=1e6; i++){
        if(d[i] == 0){
            for(int j=i; j<=1e6; j+=i){
                d[j] = i;
            }
        }
    }
    for(int i=2; i<=1e6; i++){
        f[i] = f[i - 1] + d[i];
    }
}
 
void solve(){
    int l, r; cin >> l >> r;
    cout << f[r] - f[l - 1] << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mod 1000000007
#define mxn 1000006

int n, dp[mxn];
 
void solve(){
    cin >> n;
    dp[0] = 1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=6; j++){
            if(i >= j){
                dp[i] = (dp[i] + dp[i - j]) % mod;
            }
        }
    }
    cout << dp[n];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Ta sẽ sử dụng quy hoạch động để giải quyết bài toán này, gần giống bài tìm dãy con tăng dài nhất nhưng thay số bằng ký tự. Gọi $$$dp_i$$$ là dãy con không giảm dài nhất kết thúc tại vị trí $$$i$$$.

• Cơ sở quy hoạch động sẽ là mọi dãy con độ dài $$$1$$$ đều thoả mãn, sau đó ta sẽ duyệt qua từng phần tử $$$j$$$ phía trước phần tử $$$i$$$ đang xét, nếu $$$a_j \le a_i$$$ thì ta sẽ cập nhật $$$dp_i = max(dp_i, dp_j + 1)$$$. Đáp số của bài toán sẽ là $$$max(dp_1, dp_2, ..., dp_n)$$$.

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

#define el '\n'

int dp[5005];
void solve(){
    int n; cin >> n;
    string a; cin >> a;
    a = "@" + a;
    int res = 1;
    for(int i=1; i<=n; i++){
        dp[i] = 1;
        for(int j=1; j<i; j++){
            if(a[i] >= a[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 5005

bool dx[mxn][mxn];
 
void solve(){
    string a; cin >> a;
    int n = a.size();
    a = "@" + a;
    for(int i=1; i<=n; i++) dx[i][i] = 1;
    for(int len=2; len<=n; len++){
        for(int i=1; i<=n-len+1; i++){
            int j = i + len - 1;
            if(a[i] == a[j]){
                if(len == 2) dx[i][j] = 1;
                else dx[i][j] = dx[i + 1][j - 1];
            }
        }
    }
    int q; cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        if(dx[l][r]) cout << "Yes\n";
        else cout << "No\n";
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, dp[1005][1005];
char a[1005][1005];

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> a[i][j];
        }
    }
    if(a[1][1] == '*') out(0);
    dp[1][1] = 1;
    for(int i=2; i<=n; i++){
        if(a[1][i] == '*') break;
        dp[1][i] = dp[1][i - 1];
    }
    for(int i=2; i<=n; i++){
        if(a[i][1] == '*') break;
        dp[i][1] = dp[i - 1][1];
    }
    for(int i=2; i<=n; i++){
        for(int j=2; j<=n; j++){
            if(a[i][j] == '.'){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                dp[i][j] %= mod;
            }
        }
    }
    cout << dp[n][n];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define ms(a, x) memset(a, x, sizeof(a))
#define all(x) begin(x), end(x)
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e4 + 7;

int dp[mxn];
// dp[i] : giá trị lớn nhất đạt được khi cái túi có khối lượng là i

signed main(){
    cin.tie(NULL) -> sync_with_stdio(false);

    int n, m; cin >> n >> m;
    int w[n+5], v[n+5];
    for(int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
    }
    for(int i=1; i<=n; i++){
        for(int j=m; j>=w[i]; j--){
            if(j - w[i] == 0 or dp[j - w[i]] > 0){
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
    }
    int res = -1;
    for(int i=1; i<=m; i++){
        res = max(res, dp[i]);
    }
    cout << res;
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, a[5005], dp[5005], tv[5005];

void solve(){
    cin >> n;
    dp[0] = 1;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    int mx = 1, id = 0;
    for(int i=1; i<=n; i++){
        dp[i] = 1;
        tv[i] = 0;
        for(int j=1; j<i; j++){
            if(a[i] > a[j]){
                if(dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    tv[i] = j;
                }
            }
        }
        if(dp[i] > mx){
            mx = dp[i];
            id = i;
        }
    }
    cout << mx << el;
    vector<int> v;
    while(id > 0){
        v.push_back(a[id]);
        id = tv[id];
    }
    reverse(all(v));
    for(int &i : v) cout << i << ' ';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

string a, b;
int n, m, dp[5005][5005];
 
void solve(){
    cin >> a >> b;
    n = a.size();
    m = b.size();
    a = " " + a; 
    b = " " + b;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
        }
    }
    string s = "";
    while(n and m){
        if(a[n] == b[m]){
            s += a[n];
            --n; --m;
        }else{
            if(dp[n - 1][m] > dp[n][m - 1]) --n;
            else --m;
        }
    }
    reverse(s.begin(), s.end());
    cout << s;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005

int f[mxn][5];
 
void solve(){
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        int a, b, c; cin >> a >> b >> c;
        f[i][1] = max(f[i-1][2], f[i-1][3]) + a;
        f[i][2] = max(f[i-1][1], f[i-1][3]) + b;
        f[i][3] = max(f[i-1][1], f[i-1][2]) + c;
    }
    cout << max({f[n][1], f[n][2], f[n][3]});
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 100005

int f[mxn][5];
 
void solve(){
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        int a, b, c; cin >> a >> b >> c;
        f[i][1] = max(f[i-1][2], f[i-1][3]) + a;
        f[i][2] = max(f[i-1][1], f[i-1][3]) + b;
        f[i][3] = max(f[i-1][1], f[i-1][2]) + c;
    }
    cout << max({f[n][1], f[n][2], f[n][3]});
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005
#define int long long

int n, a[mxn], dp[mxn][2];
 
void solve(){
    cin >> n;
    for(int i=1; i<n; i++) cin >> a[i];
    dp[1][0] = 1e16;
    dp[1][1] = a[1];
    for(int i=2; i<n; i++){
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i];
    }
    cout << dp[n - 1][1];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 3003

string a;
int q, dp[mxn][mxn];
bool dx[mxn][mxn];
 
void solve(){
    cin >> a >> q;
    int n = a.size();
    a = " " + a;
    for(int i=1; i<=n; i++){
        dx[i][i] = 1;
        dp[i][i] = 1;
    }
    for(int len=2; len<=n; len++){
        for(int i=1; i<=n-len+1; i++){
            int j = i + len - 1;
            if(a[i] == a[j]){
                if(len == 2) dx[i][j] = 1;
                else dx[i][j] = dx[i + 1][j - 1];
            }
            dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + dx[i][j];
        }
    }
    while(q--){
        int l, r; cin >> l >> r;
        cout << dp[l][r] << el;
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 3003

string a, b;
int n, m, mod = 1e9 + 7;
long long dp[mxn][mxn];
 
void solve(){
    cin >> a >> b;
    n = a.size(); m = b.size();
    a = " " + a; b = " " + b;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i] == b[j]){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1;
            }else dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            dp[i][j] = (dp[i][j] + mod) % mod;
        }
    }
    cout << dp[n][m];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, s, a[105], dp[mxn];

void solve(){
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    dp[0] = 1;
    for(int i=1; i<=s; i++){
        for(int j=1; j<=n; j++){
            if(i >= a[j]){
                dp[i] += dp[i - a[j]];
                dp[i] %= mod;
            }
        }
    }
    cout << dp[s];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, s, a[105], dp[mxn];

void solve(){
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    dp[0] = 1;
    for(int i=1; i<=n; i++){
        for(int j=a[i]; j<=s; j++){
            dp[j] += dp[j - a[i]];
            dp[j] %= mod;
        }
    }
    cout << dp[s];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, a[105], dp[100005];

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    dp[0] = 1;
    set<int> s;
    for(int i=1; i<=n; i++){
        for(int j=1e5; j>=a[i]; j--){
            if(dp[j - a[i]] > 0){
                dp[j] = 1;
                s.insert(j);
            }
        }
    }
    cout << len(s) << el;
    for(int i : s) cout << i << ' ';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 1000006

int n, a[mxn], dp[mxn];

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    int res = 1;
    for(int i=n; i>=1; i--){
        dp[a[i]] = 1;
        for(int j=a[i]*2; j<=n; j+=a[i]){
            dp[a[i]] = max(dp[a[i]], dp[j] + 1);
        }
        res = max(res, dp[a[i]]);
    }
    cout << res << el;
    for(int i=1; i<=n; i++) dp[i] = -n;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 1000006

int n, k, dp[mxn], mod = 20051608;
 
void solve(){
    cin >> n >> k;
    for(int i=0; i<=k+1; i++) dp[i] = i + 1;
    for(int i=k+2; i<=n; i++){
        dp[i] = dp[i - 1] + dp[i - k - 1];
        dp[i] %= mod;
    }
    cout << dp[n];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

int n, m, a[1005][1005], dp[1005][1005];
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
        }
    }
    int mx = 0, res = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j]){
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                if(dp[i][j] > mx){
                    mx = dp[i][j];
                    res = 1;
                }else if(dp[i][j] == mx) ++res;
            }
        }
    }
    cout << mx << ' ' << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 300005

int n, k, a[mxn], d[1005];

void solve(){
    cin >> n >> k;
    string s;
    for(int i=1; i<=n; i++){
        cin >> s;
        a[i] = s.size();
    }
    long long res = 0;
    for(int i=1; i<=n; i++){
        if(i > k + 1) --d[a[i - k - 1]];
        res += d[a[i]];
        ++d[a[i]];
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Truy vấn $$$t = 1$$$, bạn có thể sử dụng hàm binary_search trả về kiểu dữ liệu bool có sẵn trong thư viện.

Truy vấn $$$t = 2$$$, bạn có thể sử dụng hàm lower_bound trả về luôn vị trí cần tìm.

Truy vấn $$$t = 3$$$, bạn có thể sử dụng hàm upper_bound trả về vị trí ngay sau vị trí cần tìm.

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

#define el '\n'
#define mxn 100005

int n, q, a[mxn];
 
void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    while(q--){
        int t, x; cin >> t >> x;
        if(t == 1){
            bool ok = 0;
            int l = 0, r = n + 1;
            while(r - l > 1){
                int mid = l + r >> 1;
                if(a[mid] == x){
                    ok = 1; break;
                }
                if(a[mid] < x) l = mid;
                else r = mid;
            }
            cout << (ok ? "YES\n" : "-1\n");
        }else if(t == 2){
            int l = 0, r = n + 1;
            while(r - l > 1){
                int mid = l + r >> 1;
                if(a[mid] >= x) r = mid;
                else l = mid;
            }
            if(r <= n and a[r] == x) cout << r << el;
            else cout << "-1\n";
        }else{
            int l = 0, r = n + 1;
            while(r - l > 1){
                int mid = l + r >> 1;
                if(a[mid] <= x) l = mid;
                else r = mid;
            }
            if(l >= 1 and a[l] == x) cout << l << el;
            else cout << "-1\n";
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ duy trì $$$2$$$ con trỏ $$$i, j$$$ chạy từ đầu mảng $$$a$$$ và $$$b$$$, nếu $$$a_i \le b_j$$$ thì ta sẽ đưa phần tử $$$a_i$$$ vào cuối mảng $$$c$$$ và thêm ký tự a vào xâu truy vết, ngược lại thì ta sẽ đưa phần tử $$$b_j$$$ và thêm ký tự b.

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

#define el '\n'
#define mxn 1000005

int n, m, a[mxn], b[mxn];
vector<int> c;
 
void solve(){
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    cin >> m;
    for(int i=0; i<m; i++) cin >> b[i];
    string s = "";
    int i = 0, j = 0;
    while(i < n and j < m){
        if(a[i] <= b[j]){
            c.push_back(a[i++]);
            s.push_back('a');
        }else{
            c.push_back(b[j++]);
            s.push_back('b');
        }
    }
    while(i < n) c.push_back(a[i++]), s.push_back('a');
    while(j < m) c.push_back(b[j++]), s.push_back('b');
    for(int &i : c) cout << i << ' ';
    cout << el << s;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Với mỗi giá trị $$$b_i (1 \le i \le m)$$$, ta sẽ cần tìm vị trí $$$j$$$ cuối cùng trong mảng $$$a$$$ sao cho $$$a_j < b_i$$$, bởi vì như vậy, các số từ $$$1$$$ đến $$$j$$$ sẽ đều thoả mãn nhỏ hơn $$$b_i$$$. Tuy nhiên, ta có thể sẻ dụng hàm lower_bound có sẵn trong thư viện, trả về vị trí $$$j$$$ đầu tiên mà $$$a_j \geq b_i$$$, suy ra là nếu ta lùi về $$$1$$$ đơn vị thì ta cũng ra được vị trí cần tìm.

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

void solve(){
    int n, m; cin >> n >> m;
    int a[n+5], b[m+5];
    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<=m; i++){
        int l = 0, r = n + 1;
        while(r - l > 1){
            int mid = l + r >> 1;
            if(a[mid] < b[i]) l = mid;
            else r = mid;
        }
        cout << l << ' ';
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Xét từng vị trí $$$i$$$ trong mảng $$$a$$$ $$$(1 \le i \le n)$$$, ta sẽ cần đi tìm vị trí $$$j$$$ đầu tiên mà $$$a_i = b_j$$$ và một vị trí $$$k$$$ đầu tiên sao cho $$$a_i > b_k$$$. Như vậy, kết quả sẽ được tăng thêm một lượng bằng độ dài đoạn $$$[j, j + 1, ..., k - 1]$$$.

Tuy nhiên, ta hoàn toàn có thể áp dụng hàm có sẵn bằng việc tìm vị trí $$$j$$$ bằng lower_bound và vị trí $$$k$$$ bằng upper_bound.

Một cách xử lý khác nghe có vẻ đơn giản hơn đó chính là sử dụng $$$map$$$ để đếm số lượng các giá trị. Tuy nhiên, do độ phức tạp của $$$map$$$ có thêm một hằng số $$$c$$$ có giá trị nào đó mà không phải là độ phức tạo $$$O(log(n))$$$ của tìm kiếm nhị phân nên có thể sẽ bị TLE trong một vài trường hợp đặc biệt.

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

#define mxn 1000005

int n, m, a[mxn], b[mxn];
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    for(int i=1; i<=m; i++){
        cin >> b[i];
    }
    long long res = 0;
    for(int i=1; i<=m; i++){
        int l = lower_bound(a+1, a+n+1, b[i]) - a;
        int r = upper_bound(a+1, a+n+1, b[i]) - a;
        res += r - l;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ duyệt mọi vị trí bắt đầu, ta sẽ gọi là $$$i (1 \le i \le n)$$$, như vậy ta sẽ cần tìm vị trí $$$j$$$ cuối cùng sao cho $$$a_i + a_{i + 1} + ... + a_j \le s$$$. Ta có thể rút ra nhận xét ở đây là ta sẽ cần sử dụng mảng cộng dồn để tính tổng tĩnh một cách nhanh chóng và mảng cộng dồn cũng thoả mãn tính chất tăng dần (đồng biến) để ta có thể tìm kiếm nhị phân.

Cụ thể hơn, ta sẽ có biểu thức sau đây: $$$pre[j] - pre[i - 1] \le s \to pre[j] \le pre[i - 1] + s$$$. Như vậy, ta sẽ tìm vị trí $$$j$$$ đầu tiên có $$$pre[j] > pre[i - 1] + s$$$ bằng upper_bound rồi sau đó lùi về $$$1$$$ đơn vị.

Hoặc ta cũng có thể sử dụng $$$2$$$ con trỏ để giải quyết. Duy trì con trỏ $$$r$$$ duyệt qua mảng, con trỏ $$$l$$$ được tuỳ chỉnh theo trạng thái dãy con $$$[l, r]$$$ hiện tại và một tổng $$$sum$$$ lưu tổng các phần tử trong đoạn $$$[l, r]$$$. Ngay khi tổng $$$sum$$$ vượt quá $$$s$$$, ta sẽ dịch con trỏ $$$l$$$ lên dần dần, tổng $$$sum$$$ trừ dần đi các $$$a_l$$$ đã bỏ qua, rồi sau đó khi tổng trở về $$$\le s$$$ thì ta sẽ cập nhật kết quả.

Hướng giải quyết thì ta sẽ tư duy giống như bài $$$E$$$ ở phía trên, chỉ khác ở chỗ kết quả sẽ được cập nhật bằng độ dài đoạn $$$[i, i + 1, ..., j]$$$ do $$$j$$$ là vị trí cuối cùng thoả mãn, nên các vị trí đằng trước đương nhiên cũng thoả mãn.

Ta sẽ duyệt mọi vị trí bắt đầu, ta sẽ gọi là $$$i (1 \le i \le n)$$$, như vậy ta sẽ cần tìm vị trí $$$j$$$ đầu tiên sao cho $$$a_i + a_{i + 1} + ... + a_j \geq s$$$. Ta có thể rút ra nhận xét ở đây là ta sẽ cần sử dụng mảng cộng dồn để tính tổng tĩnh một cách nhanh chóng và mảng cộng dồn cũng thoả mãn tính chất tăng dần (đồng biến) để ta có thể tìm kiếm nhị phân.

Cụ thể hơn, ta sẽ có biểu thức sau đây: $$$pre[j] - pre[i - 1] \geq s \to pre[j] \geq pre[i - 1] + s$$$. Như vậy, ta sẽ tìm vị trí $$$j$$$ đó bằng lower_bound rồi sau đó cập nhật kết quả.

Hoặc ta cũng có thể sử dụng $$$2$$$ con trỏ để giải quyết. Duy trì con trỏ $$$r$$$ duyệt qua mảng, con trỏ $$$l$$$ được tuỳ chỉnh theo trạng thái dãy con $$$[l, r]$$$ hiện tại và một tổng $$$sum$$$ lưu tổng các phần tử trong đoạn $$$[l, r]$$$. Chừng nào ta còn có thể dịch cận $$$l$$$ lên thêm $$$1$$$ đơn vị, tức là $$$sum - a_l \geq s$$$ thì ta sẽ tiếp tục dịch để giảm độ dài đoạn con.

Hướng giải quyết thì ta sẽ tư duy giống như bài $$$G$$$ ở phía trên, chỉ khác ở chỗ kết quả sẽ được cập nhật bằng độ dài đoạn $$$[1, i - 1]$$$ do $$$[i, j]$$$ là đoạn ngắn nhất ta tìm được, vậy nên khi thêm các phần tử vào thì $$$sum$$$ vẫn $$$\geq s$$$.

Ta sẽ sử dụng $$$2$$$ con trỏ để giải quyết, con trỏ $$$r$$$ sẽ duyệt từ đầu đến cuối cùng với đó là tăng số lần xuất hiện của $$$a_r$$$ lên $$$1$$$ đơn vị, nếu số lần xuất hiện là $$$1$$$ thì đây là lần $$$a_r$$$ xuất hiện đầu tiên và như vậy ta sẽ phải tăng số lượng phần tử khác nhau lên $$$1$$$ đơn vị.

Ngay khi số lượng phần tử khác nhau vượt quá $$$k$$$ thì ta sẽ loại bỏ dần các phần tử $$$a_l$$$, giảm số lần xuất hiện nếu trở về $$$0$$$ thì giảm số phần tử khác nhau đi $$$1$$$ đơn vị. Cuối cùng, ta sẽ có đoạn $$$[l, r]$$$ thoả mãn yêu cầu đề bài để cập nhật kết quả.

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, k, a[mxn], d[mxn];

void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    int res = 0, cnt = 0, l = 1;
    for(int r=1; r<=n; r++){
        ++d[a[r]];
        if(d[a[r]] == 1) ++cnt;
        while(cnt > k){
            --d[a[l]];
            if(d[a[l]] == 0) --cnt;
            ++l;
        }
        res += r - l + 1;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta vẫn sẽ dùng $$$2$$$ con trỏ để giải quyết bài toán, tuy nhiên ở đây để lưu trạng thái đoạn con $$$[l, r]$$$ đang xét thì ta sẽ cần sử dụng đến multiset. Lí do chính là vì nó sẽ giúp chúng ta lấy ra được giá trị $$$min$$$ và $$$max$$$ một cách dễ dàng, rồi sau đó kiểm tra xem hiệu giữa chúng có thoả mãn hay không.

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e5 + 7;

int n, k, a[mxn];
multiset<int> ms;

void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    int res = 0, l = 1;
    for(int r=1; r<=n; r++){
        ms.insert(a[r]);
        while((*ms.rbegin()) - (*ms.begin()) > k){
            ms.erase(ms.find(a[l]));
            ++l;
        }
        res += r - l + 1;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define int long long
#define mxn 200005

int n, q, a[mxn], f[mxn];
 
void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1, greater<int>());
    for(int i=1; i<=n; i++){
        f[i] = f[i - 1] + a[i];
    }
    while(q--){
        int x; cin >> x;
        int l = 0, r = n + 1;
        while(r - l > 1){
            int mid = l + r >> 1;
            if(f[mid] >= x) r = mid;
            else l = mid;
        }
        cout << (r <= n ? r : -1) << ' ';
    }
    cout << '\n';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define int long long
#define mxn 200005

int n, m, a[mxn];
bool check(int x){
    int s = 0;
    for(int i=1; i<=n; i++){
        s += x / a[i];
        if(s >= m) return 1;
    }return 0;
}
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    int l = 0, r = 1e18;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << r;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define int long long

int a, b, n, c;
int gcd(int a, int b){
    while(b){
        a %= b; swap(a, b);
    }return a;
}
 
bool check(int x){
    return (x / a) + (x / b) - (x / c) >= n;
}
 
void solve(){
    cin >> a >> b >> n;
    c = a / gcd(a, b) * b;
    int l = min(a, b) - 1, r = 1e18 + 1;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << r << '\n';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define int long long

int odd(int l, int r){
    if(l % 2 == 0) ++l;
    if(r % 2 == 0) --r;
    return (r + l) * ((r - l) / 2 + 1) / 2;
}
 
int even(int l, int r){
    if(l % 2 == 1) ++l;
    if(r % 2 == 1) --r;
    return (r + l) * ((r - l) / 2 + 1) / 2;
}
 
void solve(){
    int n; cin >> n;
    int l = 0, r = n;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(odd(1, mid) > even(mid + 1, n)) r = mid;
        else l = mid;
    }
    cout << r << '\n';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define int long long
#define mxn 100005

int n, m, a[mxn];
bool check(int x){
    int cnt = 1, id = 1;
    for(int i=2; i<=n; i++){
        if(a[i] - a[id] >= x){
            ++cnt; if(cnt == m) return 1;
            id = i;
        }
    }return 0;
}
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    int l = 0, r = 1e9 + 1;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Chênh lệch tối đa có thể đạt được bằng cách chọn một nửa số lá bài có giá trị nhỏ nhất cho một người, và phần còn lại được chọn cho người kia.

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

void solve(){
    int n; cin >> n;
    int a[n];
    for(int &i : a) cin >> i;
    sort(a, a + n);
    int x = 0, y = 0;
    for(int i=0; i<n; i++){
        if(i < n / 2) x += a[i];
        else y += a[i];
    }
    cout << y - x;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ cần sắp xếp lại mảng các số này, tuy nhiên, nếu ta sắp xếp theo thứ tự giảm dần thì rất có thể sẽ gặp phải trường hợp

$$$a = [321, 32] \to 32132$$$ nhưng nó sẽ nhỏ hơn việc ta ghép ngược lại là $$$32321$$$.

Như vậy, ta sẽ cần sắp xếp theo tiêu chí số dứng trước nối với số đứng sau phải lớn hơn phép nối ngược lại.

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

void solve(){
    int n; cin >> n;
    string a[n];
    for(auto &i : a) cin >> i;
    sort(a, a + n, [](string a, string b){
        return a + b > b + a;
    });
    for(auto &i : a) cout << i;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta có nhận xét rằng khi độ chênh lệch là nhỏ nhất thì tức là tập hợp $$$k$$$ phần tử đó là các giá trị gần nhau nhất có thể.

Hay có thể hiểu là khi ta sắp xếp lại mảng $$$a$$$ thì tập hợp đó sẽ là $$$1$$$ trong những đoạn con độ dài $$$k$$$ của mảng.

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

#define el '\n'

void solve(){
    int n, k; cin >> n >> k;
    int a[n+1];
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    int res = 2e9;
    for(int i=1; i<=n-k+1; i++){
        res = min(res, a[i + k - 1] - a[i]);
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Đây thực chất là bài toán Nối dây mà các bạn làm ở trên Code PTIT.

Ta có thể tư duy theo hướng ghép lại $$$n$$$ thanh gỗ đó trở lại ban đầu, tức là ghép $$$2$$$ đoạn gỗ dài $$$u$$$ và $$$v$$$ thì sẽ tốn $$$u + v$$$ đơn vị tiền.

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

#define el '\n'
#define int long long 

void solve(){
    int n; cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i=1; i<=n; i++){
        int x; cin >> x;
        q.push(x);
    }
    int res = 0;
    while(q.size() > 1){
        int x = q.top(); q.pop();
        int y = q.top(); q.pop();
        q.push(x + y);
        res += x + y;
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Thao tác đề bài đã cho có thể giúp ta sắp xếp lại mảng theo cách tuỳ ý. Như vậy, ta cần sắp xếp sao cho các phần tử cách nhau $$$k$$$ đơn vị có giá trị chênh lệch nhau là nhỏ nhất.

Tuy nhiên, để việc chuyển suy nghĩ đó vào code trở nên đơn giản thì ta sẽ sắp xếp lại mảng:

Xét ví dụ $$$1$$$, ta có $$$a = [5, 2, 7, 1, 10, 3] \to a = [1, 2, 3, 5, 7, 10]$$$.

Sau đó, ta sẽ coi $$$1$$$ ở vị trí $$$1$$$, duyệt qua các số ngay phía sau và gán cho nó vị trí $$$1 + k$$$ tức là $$$2$$$ sẽ ở vị trí $$$1 + k$$$. Cứ như vậy thì số $$$3$$$ sẽ ở vị trí $$$1 + k \times 2$$$, tuy nhiên vị trí này đã vượt quá kích thước mảng nên ta sẽ phải coi nó như vị trí $$$2$$$ rồi lại gán tiếp các vị trí $$$2 + k, ...$$$

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

#define el '\n'
#define int long long 

void solve(){
    int n, k; cin >> n >> k;
    int a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    int res = 0, x = n / k;
    for(int i=1; i<=n; i+=x){
        for(int j=i; j<i+x-1; j++){
            res += a[j + 1] - a[j];
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Các giá trị có thể đạt được của biểu thức $$$x$$$ $$$\%$$$ $$$y$$$ là bao nhiêu ?

Đúng, các giá trị sẽ nằm trong đoạn $$$[0, y - 1]$$$. Như vậy để có thể tối đa hoá tập hợp kết quả thì ta sẽ cần làm gì với giá trị $$$y$$$ ?

Đúng, ta sẽ chỉ cần chọn $$$y$$$ là lớn nhất có thể, như vậy $$$y = max(a_1, a_2, ..., a_n)$$$. Vậy còn giá trị $$$x$$$ thì sao ?

Đúng, ta sẽ cần chọn giá trị $$$x$$$ là giá trị lớn thứ hai trong mảng vì khi đó đáp số bài toán sẽ chính là $$$x$$$. Ngoài ra, khi mảng chỉ gồm $$$1$$$ giá trị duy nhất, đương nhiên đáp số bài toán sẽ là $$$0$$$.

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

#define el '\n'

void solve(){
    int n; cin >> n;
    int a[n];
    for(int &i : a) cin >> i;
    sort(a, a + n);
    for(int i=n-1; i>0; i--){
        if(a[i] > a[i - 1]){
            cout << a[i - 1];
            return;
        }
    }
    cout << 0;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Giả dụ An sẽ làm hết $$$n \times 2$$$ công việc, vậy thì tổng thời gian giải quyết sẽ là $$$S = \sum\limits_{i = 1}^{n \times 2} a_i$$$. Như vậy, ta cần tham lam sang cho Bình $$$n$$$ công việc sao cho giảm được giá trị $$$S$$$ đi càng nhiều càng tốt.

Vì giá trị $$$S$$$ sẽ thay đổi theo hướng: đổi việc thứ $$$i$$$ từ An thành Bình $$$\to S = S - a_i + b_i = S - (a_i - b_i)$$$, nên ta sẽ cần tạo thêm một mảng lưu các giá trị $$$(a_i - b_i)$$$ và rồi chọn ra đúng $$$n$$$ giá trị lớn nhất.

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

#define pe pair<int, int>
#define fi first
#define se second
int n;
pe a[1000005];
 
void solve(){
    cin >> n; n *= 2;
    int x = 0;
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
        x += a[i].fi;
    }
    sort(a+1, a+n+1, [](pe a, pe b){
        if(a.fi - a.se == b.fi - b.se) return a.se < b.se;
        return a.fi - a.se > b.fi - b.se;
    });
    for(int i=1; i*2<=n; i++){
        x = x - a[i].fi + a[i].se;
    }
    cout << x;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta dễ dàng nhận thấy rằng tập con $$$b$$$ không thoả mãn điều kiện đề bài khi và chỉ khi tồn tại $$$2$$$ số $$$x$$$ và $$$y$$$ sao cho:

$$$(x + y)$$$ $$$\%$$$ $$$k = 0$$$ $$$\to$$$ $$$((x$$$ $$$\%$$$ $$$k) + (y$$$ $$$\%$$$ $$$k))$$$ $$$\%$$$ $$$k = 0$$$.

Ta có thể rút ra $$$2$$$ nhận xét là:

• Chia dư mọi phần tử mảng cho $$$k$$$ để dễ xử lý $$$\to$$$ từ giờ coi như các số đã được chia dư cho $$$k$$$.

• Nếu $$$x = i$$$ thì $$$y = k - i$$$, như vậy ta sẽ đếm số lần xuất hiện của các số trong đoạn $$$[0, k - 1]$$$ do khi chia dư thì các kết quả chỉ nằm trong đoạn đó.

Để tập con $$$b$$$ là lớn nhất thì với mỗi cặp $$$(i, k - i)$$$ ta sẽ cần chọn ra giá trị $$$max(cnt[i], cnt[k - i])$$$. Tuy nhiên, có $$$2$$$ giá trị đặc biệt mà ta cần chú ý đó chính là $$$0$$$ và $$$k / 2$$$ (nếu $$$k$$$ là số chẵn). Lí do là bởi vì ta sẽ chỉ có thể sử dụng tối đa $$$1$$$ số $$$0$$$ duy nhất để nhét vào $$$b$$$, cũng như là tối đa $$$1$$$ số $$$k / 2$$$ (nếu $$$k$$$ là số chẵn) để nhét vào $$$b$$$.

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

int cnt[1005];

void solve(){
    int n, k; cin >> n >> k;
    int a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
        ++cnt[a[i] % k];
    }
    int res = 0;
    if(cnt[0] > 0) res = 1;
    for(int i=1; i<=k/2; i++){
        if(i < k - i){
            res += max(cnt[i], cnt[k - i]);
        }else if(cnt[i] > 0) ++res;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ tách bài toán này thành $$$2$$$ bài toán con là tìm giá trị nhỏ nhất của tổng khoảng cách từ điểm $$$u$$$ đến $$$a_x$$$ và $$$v$$$ đến $$$a_y$$$.

Như vậy, ta sẽ cần biết thêm một nhận xét là trung vị của mảng sẽ là phần tử mà có tổng khoảng cách tới các phần tử trong mảng là nhỏ nhất. Dưới đây là $$$2$$$ ảnh minh hoạ:

Cụ thể hơn, khi ta dịch sang phải so với phần tử trung vị thì sẽ có $$$4$$$ phần tử tăng thêm $$$2$$$ đơn vị khoảng cách, còn chỉ có đúng $$$3$$$ phần tử giảm đi $$$2$$$ đơn vị khoảng cách. Chốt lại, ta sẽ có toạ độ điểm cần tìm là (trung vị của mảng các $$$a_x$$$, trung vị của mảng các $$$a_y$$$).

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

void solve(){
    int n; cin >> n;
    int a[n+5], b[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
    }
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    int res = 0, x = a[(n + 1) / 2], y = b[(n + 1) / 2];
    for(int i=1; i<=n; i++){
        res += abs(x - a[i]) + abs(y - b[i]);
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Với số phút $$$m$$$ có thể lên tới $$$10^9$$$, ta phải làm cách nào để xác định được hết rằng phút $$$i$$$ sẽ luyện kỹ năng nào ?

Đúng, ta không cần xét hết $$$m$$$ phút, cụ thể hơn là tối đa ta sẽ cần $$$n$$$ phút, lí do là bởi vì khi sử dụng hết lần đầu tiên của các kỹ năng thì ta sẽ chỉ luyện đúng duy nhất $$$1$$$ kỹ năng cung cấp nhiều sức mạnh nhất. Vậy thì chọn kỹ năng như nào cho phù hợp đây ?

Đúng, ta sẽ sử dụng hàng đợi ưu tiên để giải quyết bài toán này. Đầu tiên thì ta sẽ đưa vào các giá trị sức mạnh $$$e_i + s_i$$$ mà phép luyện kỹ năng có thể cung cấp, sau đó mỗi khi lấy phần tử ở đầu ra thì ta sẽ chỉ đưa lại giá trị $$$e_i$$$ vào thôi, do $$$s_i$$$ chỉ nhận được khi lần đầu luyện kỹ năng $$$i$$$ đó.

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

#define pe pair<int, int>
#define fi first
#define se second

void solve(){
    int n, m; cin >> n >> m;
    pe a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    priority_queue<pe> q;
    for(int i=1; i<=n; i++){
        q.push({a[i].fi + a[i].se, i});
    }
    int res = 0;
    for(int i=1; i<=min(n, m); i++){
        pe top = q.top(); q.pop();
        int sc = top.fi, id = top.se;
        res += sc;
        q.push({a[id].se, id});
    }
    if(m > n) res += (m - n) * q.top().fi;
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, ta chỉ cần kiểm tra xem số đầu tiên có phải số $$$m$$$ hay không, nếu đúng thì ta sẽ in ra hoán vị đó.

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

#define el '\n'

int n, m, p[15], used[15];
void ql(int id){
    for(int i=1; i<=n; i++){
        if(!used[i]){
            used[i] = 1;
            p[id] = i;
            if(id == n){
                for(int j=1; j<=n; j++) cout << p[j] << ' '; cout << el;
            }else if(p[1] == m) ql(id + 1);
            used[i] = 0;
        }
    }
}

void solve(){
    cin >> n >> m;
    ql(1);
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, nếu phần tử cuối cùng của hoán vị đúng là tên đề bài yêu cầu thì ta nhét hoán vị đó vào set để in ra theo thứ tự từ điển.

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

#define el '\n'

void solve(){
    int n; cin >> n;
    string a[n+1];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    string s; cin >> s;
    int p[n+1];
    for(int i=1; i<=n; i++) p[i] = i;
    set<string> se;
    do{
        if(a[p[n]] == s){
            string str = "";
            for(int i=1; i<=n; i++){
                str += a[p[i]] + " ";
            }
            se.insert(str);
        }
    }while(next_permutation(p+1, p+n+1));
    for(auto &i : se) cout << i << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, nếu số đầu tiên lớn hơn số cuối cùng thì ta sẽ in ra hoán vị đó.

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

#define el '\n'
 
void solve(){
    int n; cin >> n;
    vector<int> v;
    for(int i=1; i<=n; i++) v.push_back(i);
    do{
        if(v[0] > v[n - 1]){
            for(int &i : v) cout << i << ' '; cout << el;
        }
    }while(next_permutation(v.begin(), v.end()));
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Quay lui như bài tổ hợp chập $$$k$$$ của $$$n$$$, sau đó với mỗi trạng thái nối đủ $$$k$$$ số khác nhau, ta sẽ nhét trạng thái đó vào $$$set$$$ do không được in trùng và phải liệt kê theo thứ tự từ điển.

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

#define el '\n'

int n, k, x[20];
string a[20];
set<string> s;
 
void run(int id){
    for(int i=x[id-1]+1; i<=n-k+id; i++){
        x[id] = i;
        if(id == k){
            string tmp = "";
            for(int j=1; j<=k; j++) tmp += a[x[j]];
            s.insert(tmp);
        }else run(id + 1);
    }
}
 
void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    run(1);
    for(auto &i : s) cout << i << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Quay lui tạo ra các dãy con của mảng $$$a$$$, tức là chỉ số của phần tử đứng sau phải lớn hơn chỉ số của phần tử đứng trước. Ngoài ra, có thể thêm nhánh cận rằng nếu tổng hiện tại cộng thêm $$$a_i$$$ vẫn chưa vượt quá $$$s$$$ thì mới tiếp tục.

• Trường hợp $$$s = 0$$$, ta sẽ không được lấy dãy con rỗng, do đó cần xét kỹ ở trường hợp này.

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

#define el '\n'

int n, s, a[22], res;
 
void run(int pos, int sum){
    if(sum == s and pos > 1) ++res;
    for(int i=pos; i<=n; i++){
        if(sum + a[i] <= s){
            run(i + 1, sum + a[i]);
        }
    }
}
 
void solve(){
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    run(1, 0);
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Kiểm tra tổng tất cả phần tử tỏng mảng $$$sum$$$ có chia hết cho $$$k$$$ hay không ? Nếu không chia hết, thì đáp án bài toán là $$$-1$$$.

Ta sẽ đặt một biến là tổng cần có của mỗi dãy con được tạo ra, có giá trị là $$$sum / k$$$. Sau đó quay lui tạo ra các dãy con của $$$a$$$, mỗi khi lấy một phần tử nào đó thì đánh dấu, xét xong thì xoá dấu. Ngoài ra, sử dụng thêm một biến $$$id$$$ dùng để đánh dấu số thứ tự nhóm đang có.

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

#define el '\n'

int n, k, a[21], aim, f[21];
bool used[21];
 
bool run(int pos, int sum, int id){
    if(id > k) return 1;
    for(int i=pos; i<=n-k+id; i++){
        if(!used[i]){
            used[i] = 1;
            f[i] = id;
            sum += a[i];
            if(sum < aim){
                if(run(i + 1, sum, id)) return 1;
            }else if(sum == aim){
                if(run(1, 0, id + 1)) return 1;
            }
            used[i] = 0;
            sum -= a[i];
        }
    }return 0;
}
 
void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        aim += a[i];
    }
    if(aim % k){
        cout << -1;
        return;
    }
    aim /= k;
    if(run(1, 0, 1)){
        for(int i=1; i<=n; i++){
            cout << f[i] << ' ';
        }
    }else cout << "-1";
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Cách $$$1$$$: bạn có thể sử dụng stack hoặc string để xử lý, lặp tới chừng nào $$$n = 0$$$, đưa số dư vào biến rồi sau đó in ngược lại.

• Cách $$$2$$$: sử dụng đệ quy, trường hợp cơ sở sẽ là $$$n = 0$$$ thì ta sẽ không in gì, nếu $$$n \neq 0$$$ thì ta sẽ gọi tới hàm $$$n / 2$$$ rồi sau đó mới in ra số dư của $$$n$$$ chia cho $$$2$$$. Tuy nhiên, trường hợp $$$n = 0$$$ ngay từ đầu thì ta sẽ phải in ra $$$0$$$ luôn.

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

#define el '\n'

void run(int n){
    if(!n) return;
    run(n / 2);
    cout << n % 2;
}
 
void solve(){
    int n; cin >> n;
    if(!n) cout << 0;
    else run(n);
    cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Ta sẽ sinh ra các dãy ngoặc bất kỳ giống như sinh xâu nhị phân, rồi sau đó kiểm tra tính đúng và in ra kết quả.

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

#define el '\n'

bool check(string a){
    stack<char> st;
    for(char &c : a){
        if(c == '('){
            st.push(c);
        }else{
            if(st.empty()) return 0;
            st.pop();
        }
    }return st.empty();
}
 
void solve(){
    int n; cin >> n;
    n *= 2;
    queue<string> q;
    q.push("(");
    vector<string> v;
    while(!q.empty()){
        string s = q.front(); q.pop();
        if(s.size() == n and check(s)) v.push_back(s);
        if(s.size() < n){
            q.push(s + "(");
            q.push(s + ")");
        }
    }
    cout << v.size() << el;
    for(auto &i : v) cout << i << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Cách $$$1$$$: do giới hạn $$$n$$$ khá là bé, nên ta hoàn toàn có thể xét các vị trí $$$i$$$ trong đoạn $$$[1, j]$$$. Tuy nhiên, để có thể tính tổng một cách nhanh chóng thì ta sẽ cần sử dụng thêm mảng cộng dồn.

• Cách $$$2$$$: sử dụng chia để trị (tìm kiếm nhị phân), do $$$i$$$ càng gần $$$j$$$ thì tổng sẽ càng nhỏ nên ta sẽ sử dụng được thuật tìm kiếm này.

• Ta sẽ tính trước độ dài và số lượng kí tự a mà mỗi xâu $$$f_n$$$ đang quản lý.

• Với mỗi xâu $$$f_n$$$, ta sẽ phải xét đến $$$3$$$ vị trí như sau:

• Nếu $$$k$$$ đúng bằng độ dài xâu $$$f_n$$$ thì ta sẽ trả về luôn số lượng ký tự a trong xâu đó.

• Nếu $$$k$$$ lớn hơn độ dài xâu $$$f_{n - 1}$$$, tức là ta sẽ phải cộng toàn bộ số lượng ký tự a trong xâu $$$f_{n - 1}$$$ rồi ta lùi về xâu $$$f_{n - 2}$$$ rồi tính tiếp, nhưng chỉ số $$$k$$$ ta sẽ phải giảm đi $$$1$$$ lượng bằng độ dài xâu $$$f_{n - 1}$$$.

• Cuối cùng, $$$k$$$ nằm trong đoạn mà xâu $$$f_{n - 1}$$$ quản lý, thì ta chỉ việc lùi về xâu $$$f_{n - 1}$$$ và tính tiếp.

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

#define el '\n'

int len[50], f[50];
void pre(){
    len[0] = len[1] = 1;
    f[0] = 1; f[1] = 0;
    for(int i=2; i<=45; i++){
        len[i] = len[i - 1] + len[i - 2];
        f[i] = f[i - 1] + f[i - 2];
    }
}
 
int solve(int n, int k){
    if(k == len[n]) return f[n];
    if(k > len[n - 1]) return f[n - 1] + solve(n - 2, k - len[n - 1]);
    return solve(n - 1, k);
}
 
void solve(){
    int n, k; cin >> n >> k;
    cout << solve(n, k) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Đầu tiên, ta cần tạo một mảng lưu độ dài xâu: $$$len_i = |f_i|$$$. Với mỗi xâu $$$f_i$$$ = $$$f_{i - 1} + 1 + f_{i - 2}$$$ ta sẽ có $$$3$$$ vị trí $$$k$$$ cần phải xét đến như sau:

• $$$k$$$ nằm trong đoạn mà $$$f_{i - 1}$$$ quản lý, lúc đó ta chỉ cần tìm tiếp vị trí thứ $$$k$$$ ở xâu $$$f_{i - 1}$$$.

• $$$k$$$ nằm ngay sau đoạn mà $$$f_{i - 1}$$$ quản lý, tức là chỉ có thể là ký tự L hoặc V, lúc này ta dựa vào công thức đề để tìm đáp án.

• $$$k$$$ nằm trong đoạn mà $$$f_{i - 2}$$$ quản lý, lúc đó ta cần tìm tiếp ở xâu $$$f_{i - 2}$$$ nhưng ở vị trí nào ? Ta nhận thấy rằng ta phải giảm bớt $$$k$$$ xuống một lượng bằng nguyên đoạn đằng trước, tức là $$$k - len[i - 1] - 1$$$.

• Cuối cùng, khi xâu cần tìm ở vị trí $$$1$$$ hoặc $$$2$$$, ta sẽ giải quyết được bài toán.

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

#define el '\n'

int len[90];
void prepare(){
    len[1] = len[2] = 1;
    for(int i=3; i<=88; i++) len[i] = len[i - 1] + 1 + len[i - 2];
}
 
char kitu(int n, int k){
    if(n == 1) return 'L';
    if(n == 2) return 'V';
    if(k == len[n - 1] + 1){
        if(n % 2 == 1) return 'L';
        return 'V';
    }
    if(k <= len[n - 1]) return kitu(n - 1, k);
    return kitu(n - 2, k - len[n - 1] - 1);
}
 
void solve(){
    int n, k; cin >> n >> k;
    cout << kitu(n, k) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    prepare();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Để tính được $$$a^n$$$, ta sẽ cần đi tính trước giá trị $$$a^{n / 2}$$$ rồi sau đó bình phương lên, nếu $$$n$$$ là số lẻ thì ta nhân thêm $$$a$$$ vào. Như vậy, ta sẽ gọi hàm tính $$$a^{n / 2}$$$ đến khi gặp trường hợp cơ sở là $$$a^0 = 1$$$ và $$$a^1 = a$$$.

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

#define el '\n'
#define int long long
#define mod 1000000007

int mu(int a, int b){
    if(b == 0) return 1;
    if(b == 1) return a;
    int tmp = mu(a, b / 2);
    int res = (tmp * tmp) % mod;
    if(b % 2) res *= a;
    return res % mod;
}

void solve(){
    int a, b; cin >> a >> b;
    cout << mu(a, b) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Cách làm tương tự như bản $$$1$$$, tuy nhiên ta sẽ gặp phải một vấn đề như sau đó chính là thao tác nhân kể cả $$$2$$$ số sau khi đã được chia dư cho $$$c$$$ vẫn có thể gây ra tràn số $$$\to$$$ ta sẽ phải sử dụng chia để trị lần nữa để xử lý phép nhân này.

• Tư duy cũng giống với phép toán mũ, để tính được $$$a \times b$$$, ta sẽ cần tính trước $$$a \times (b / 2)$$$ và nếu $$$b$$$ là số lẻ thì ta cộng thêm $$$1$$$ số $$$a$$$ vào nữa. Trường hợp cơ sở sẽ là $$$a \times 0 = 0$$$ và $$$a \times 1 = a$$$.

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

#define el '\n'
#define int long long

int mul(int a, int b, int c){
    int res = 0;
    while(b){
        if(b & 1) res = (res + a) % c;
        b /= 2; a = (a + a) % c;
    }return res;
}
 
int cal(int a, int b, int c){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a, c);
        b /= 2; a = mul(a, a, c);
    }return res;
}

void solve(){
    int a, b, c; cin >> a >> b >> c;
    cout << cal(a, b, c) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Về cơ bản thì đây là bài toán xử lý $$$a^b$$$ chia dư cho 10^6$, tuy nhiên đề bài lại yêu cầu bạn phải in ra đủ $$$6$$$ chữ số cuối cùng trong đáp án. Như vậy nếu cứ mod liên tục để lấy đáp án thì ta sẽ gặp tình trạng $$$10^6$$$ chia dư cho $$$10^6$$$ cho ra kết quả là $$$0$$$ mặc dù $$$1000000$$$ có $$$7$$$ chữ số $$$\to$$$ ta phải in ra $$$000000$$$ mới chính xác.

• Dựa vào đó, ta sẽ cần kiểm tra trước khi mod cho $$$10^6$$$ thì số đó đã $$$\geq 10^6$$$ hay chưa, nếu rồi thì ta sẽ cần in ra số dư đó với việc chèn thêm các số $$$0$$$ vào đầu cho đủ $$$6$$$ chữ số.

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

#define el '\n'
#define int long long
#define mod 1000000

bool check;
int ltnp(int a, int b){
    int res = 1;
    while(b){
        if(a >= mod){
            a %= mod;
            check = 1;
        }
        if(b % 2){
            res *= a;
            if(res >= mod){
                res %= mod;
                check = 1;
            }
        }
        b /= 2;
        a *= a;
    }return res;
}
 
void solve(){
    int a, b; cin >> a >> b;
    int res = ltnp(a, b);
    if(check){
        string s = to_string(res);
        while(s.size() < 6) s = "0" + s;
        cout << s;
    }else cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Ta sẽ quay lui giống theo dãy con $$$a$$$ có $$$k$$$ phần tử có tổng bằng $$$c$$$, và với điều kiện đề bài thì các dãy được tạo ra không tăng, tức là $$$a_i \le a_{i - 1}$$$ với $$$2 \le i \le k$$$.

• Vì các khả năng có thể chia được kẹo là một mảng giảm dần, nên ta sẽ quay lui theo từng vị trí trong mảng, với các khả năng sẽ là $$$min(a_{i - 1}, x) \to 1$$$ với $$$x$$$ là số kẹo còn lại.

• Ta sẽ duy trì thêm một biến $$$opt$$$ để lưu giá trị nhỏ nhất của người được nhiều và ít kẹo nhất, cùng với đó là một mảng lưu trạng thái tối ưu. Chừng nào chúng ta chia được hết số kẹo, tức là số kẹo còn lại có thể đưa được hết cho người thứ $$$n$$$ thì ta sẽ cập nhật kết quả.

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

#define all(x) begin(x), end(x)
#define len(x) (int)x.size()
#define set(a, x) memset(a, x, sizeof(a))
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, c; // 2 biến đề cho
int cnt, opt; // cnt: số cách chia | opt: chênh lệch tối ưu
int cur[30], f[30]; // cur: trạng thái khi quay lui | f: phương án tối ưu

void run(int id, int c){ // xét vị trí id trong trạng thái với số kẹo còn lại là c
    // duyệt các khả năng
    for(int i=min(cur[id - 1], c); i>=1; i--){
        cur[id] = i;
        // trạng thái đã được tạo xong
        if(id == n){
            // kiểm tra trạng thái và cập nhật kết quả
            if(c == i){
                ++cnt;
                if(cur[1] - cur[n] < opt){
                    opt = cur[1] - cur[n];
                    for(int i=1; i<=n; i++) f[i] = cur[i];
                }
            }
        }else run(id + 1, c - i);
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n >> c;
    cur[0] = opt = oo;
    run(1, c);
    cout << cnt << el;
    for(int i=1; i<=n; i++) cout << f[i] << ' ';
}

• Ý tưởng của bài toán được xuất phát từ nhận xét rằng $$$ax^3 + bx - c$$$ là hàm đồng biến. Như vậy, việc áp dụng tìm kiếm nhị phân trên hàm này là hoàn toàn khả thi. Trường hợp $$$a = 1, c = 10^6$$$ sẽ cho ra kết quả $$$x$$$ có thể lên tới $$$10^2$$$, do đó ta cần chặt trên đoạn $$$[1, 100]$$$.

• Tuy nhiên, để làm việc với số thực một cách chính xác nhất, ta nên sử dụng kiểu dữ liệu double cùng với đó là một số $$$epsilon$$$ đủ nhỏ để coi như $$$2$$$ số có chênh lệch $$$< epsilon$$$ là bằng nhau.

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

#define el '\n'

double a, b, c;
double cal(double x){
    return a * x * x * x + b * x - c;
}
 
void solve(){
    cin >> a >> b >> c;
    double res = 0, l = 0, r = 100.0;
    while(r - l >= 1e-9){
        double mid = (l + r) / 2;
        if(cal(mid) <= 1e-9){
            res = mid;
            l = mid;
        }else r = mid;
    }
    cout << fixed << setprecision(4) << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Nếu $$$n$$$ là số lẻ thì: $$$a^0 + a^1 + a^2 + ... + a^n$$$

$$$= (a^0 + a^1 + ... + a^{(n - 1) / 2}) + a^{(n + 1) / 2} \times (a^0 + a^1 + ... + a^{(n - 1) / 2})$$$.

$$$= (a^0 + a^1 + ... + a^{(n - 1) / 2}) \times (a^{(n + 1) / 2} + 1)$$$.

Nếu $$$n$$$ là số chẵn thì: $$$a^0 + a^1 + a^2 + ... + a^n$$$

$$$= (a^0 + a^1 + ... + a^{n / 2 - 1}) + a^{n / 2} \times (a^0 + a^1 + ... + a^{n / 2 - 1}) + a^n$$$.

$$$= (a^0 + a^1 + ... + a^{n / 2 - 1}) \times (a^{n / 2} + 1) + a^n$$$.

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

#define int long long

int mu(int a, int b, int m){
    int res = 1;
    while(b){
        a %= m;
        if(b & 1) res = res * a % m;
        a *= a; b >>= 1;
    }return res;
}

int cal(int a, int n, int m){
    if(n == 0) return 1;
    if(n % 2){
        int tmp = cal(a, n / 2, m);
        return (tmp + mu(a, n / 2 + 1, m) * tmp) % m;
    }else{
        int tmp = cal(a, n / 2 - 1, m);
        return (tmp + mu(a, n / 2, m) * tmp + mu(a, n, m)) % m;
    }
}

void solve(){
    int a, n, m; cin >> a >> n >> m;
    cout << cal(a, n, m);
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, nếu phần tử cuối cùng của hoán vị đúng là tên đề bài yêu cầu thì ta nhét hoán vị đó vào set để in ra theo thứ tự từ điển.

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

#define el '\n'

void solve(){
    int n; cin >> n;
    string a[n+1];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    string s; cin >> s;
    int p[n+1];
    for(int i=1; i<=n; i++) p[i] = i;
    set<string> se;
    do{
        if(a[p[n]] == s){
            string str = "";
            for(int i=1; i<=n; i++){
                str += a[p[i]] + " ";
            }
            se.insert(str);
        }
    }while(next_permutation(p+1, p+n+1));
    for(auto &i : se) cout << i << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Ta sẽ tính trước độ dài và số lượng kí tự a mà mỗi xâu $$$f_n$$$ đang quản lý.

• Với mỗi xâu $$$f_n$$$, ta sẽ phải xét đến $$$3$$$ vị trí như sau:

• Nếu $$$k$$$ đúng bằng độ dài xâu $$$f_n$$$ thì ta sẽ trả về luôn số lượng ký tự a trong xâu đó.

• Nếu $$$k$$$ lớn hơn độ dài xâu $$$f_{n - 1}$$$, tức là ta sẽ phải cộng toàn bộ số lượng ký tự a trong xâu $$$f_{n - 1}$$$ rồi ta lùi về xâu $$$f_{n - 2}$$$ rồi tính tiếp, nhưng chỉ số $$$k$$$ ta sẽ phải giảm đi $$$1$$$ lượng bằng độ dài xâu $$$f_{n - 1}$$$.

• Cuối cùng, $$$k$$$ nằm trong đoạn mà xâu $$$f_{n - 1}$$$ quản lý, thì ta chỉ việc lùi về xâu $$$f_{n - 1}$$$ và tính tiếp.

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

#define el '\n'

int len[50], f[50];
void pre(){
    len[0] = len[1] = 1;
    f[0] = 1; f[1] = 0;
    for(int i=2; i<=45; i++){
        len[i] = len[i - 1] + len[i - 2];
        f[i] = f[i - 1] + f[i - 2];
    }
}
 
int solve(int n, int k){
    if(k == len[n]) return f[n];
    if(k > len[n - 1]) return f[n - 1] + solve(n - 2, k - len[n - 1]);
    return solve(n - 1, k);
}
 
void solve(){
    int n, k; cin >> n >> k;
    cout << solve(n, k) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Ta sẽ sử dụng hàng đợi để sinh ra đủ $$$2 \times 10^5$$$ các số có tổng chữ số bằng $$$10$$$, lưu các phần tử trong hàng đợi theo cặp {số, tổng chữ số} để đỡ phải tính toán nhiều lần. Ta sẽ duyệt các chữ số $$$[0, 9]$$$ kiểm tra xem việc nối chữ số đó vào cuối đã làm tổng chữ số vượt quá $$$10$$$ hay chưa, nếu chưa vượt quá $$$10$$$ thì ta tiếp tục đưa nó vào hàng đợi. Với mỗi phần tử ở đầu hàng đợi mà có tổng chữ số là $$$10$$$, ta sẽ nhét chúng vào một cái vector/mảng để trả lời cho các truy vấn.

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

#define pe pair<int, int>
#define fi first
#define se second
#define el '\n'
#define int long long

vector<int> v;
void pre(){
    queue<pe> q;
    for(int i=1; i<=9; i++){
        q.push({i, i});
    }
    while(1){
        pe x = q.front(); q.pop();
        int n = x.fi, s = x.se;
        if(s == 10){
            v.push_back(n);
            if(v.size() == 2e5) return;
        }
        for(int i=0; i<=9; i++){
            if(s + i <= 10){
                q.push({n * 10 + i, s + i});
            }else break;
        }
    }
}
 
void solve(){
    int n; cin >> n;
    cout << v[n - 1] << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Để có thể sử dụng số lần duyệt ít nhất, ta có thể tham lam bằng cách: xét đường đi là $$$1 \to 2 \to 3 \to 4 \to 5$$$, việc ta chọn xuất phát từ $$$2, 3, 4$$$ hoặc $$$5$$$ là hoàn toàn không tối ưu, vì như vậy không thể duyệt hết được cả con đường. Ngược lại, nếu ta duyệt từ $$$1$$$ thì ta sẽ chỉ cần đúng duy nhất $$$1$$$ lần chạy được hết cả con đường trên.

• Từ đây ta rút ra kết luận là những đỉnh "ở đầu đường đi" sẽ là thích hợp nhất để làm điểm xuất phát. Vậy đặc điểm của những đỉnh đó là gì ? Đó chính là sẽ không có đỉnh nào đến được nó, mà chỉ có nó đi ra các đỉnh khác thôi. Như vậy, với mỗi đỉnh từ $$$1$$$ đến $$$n$$$, ta sẽ duyệt danh cách kề của nó, đánh dấu hết những đỉnh này là không thích hợp. Sau đó, ta sẽ bắt đầu duyệt những đỉnh chưa được đánh dấu đi khắp đồ thị.

• Tuy nhiên, khi đồ thị xuất hiện chu trình thì ta sẽ lỡ đánh dấu mất cả chu trình đó (do đỉnh nào cũng có đỉnh khác đi đến được), vì vậy ta sẽ duyệt lại đồ thị $$$1$$$ lần nữa, xem đỉnh nào chưa được thăm thì ta sẽ bắt đầu duyệt từ đó.

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

int n, m;
vector<int> a[1005];
bool del[1005], vis[1005];
 
void dfs(int u){
    vis[u] = 1;
    for(int &v : a[u]){
        if(!vis[v]) dfs(v);
    }
}
 
void solve(){
    cin >> n >> m;
    while(m--){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
    }
    for(int i=1; i<=n; i++){
        for(int &j : a[i]){
            del[j] = 1;
        }
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        if(!del[i]){
            dfs(i);
            ++res;
        }
    }
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            dfs(i);
            ++res;
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Thao tác chèn: ta sẽ duyệt từ gốc, nếu giá trị cần chèn mà nhỏ hơn giá trị của node hiện tại thì ta sẽ cần chèn giá trị đó vào cây con bên trái của node, ngược lại thì ta sẽ chèn vào cây con bên phải.

• Thao tác xoá: ta sẽ duyệt từ gốc, nếu giá trị cần xoá mà nhỏ hơn giá trị của node hiện tại thì ta sẽ đi xuống cây con bên trái của node, ngược lại thì ta sẽ đi xuống cây con bên phải và ta sẽ dừng lại khi giá trị cần xoá đúng bằng giá trị node.

• Ta có $$$2$$$ phương án xoá node mà vẫn bảo toàn cấu trúc cây ban đầu, đó chính là tìm node nhỏ nhất của cây con bên phải hoặc tìm node lớn nhất của cây con bên trái, mục đích là để thay node đó lên chính vị trí của node cần xoá. Khi đó, node cần tìm sẽ vẫn đảm bảo rằng nó lớn hơn node bên trái của node bị xoá, và nhỏ hơn node bên phải của node bị xoá.

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

#define el '\n'

struct node{
    int val;
    node *l, *r;
    node(int x){
        val = x;
        l = r = 0;
    }
};
 
node *ins(node *root, int x){
    // đã tìm thấy node cần chèn
    if(!root) return new node(x);
    // giá trị cần chèn nhỏ hơn giá trị hiện tại
    // tức là cần chèn vào cây con bên trái
    if(x < root->val) root->l = ins(root->l, x);
    // ngược lại thì chèn vào cây con bên phải
    else root->r = ins(root->r, x);
    return root;
}
 
node *find(node *root){
    // tìm node nhỏ nhất
    while(root->l) root = root->l;
    return root;
}
 
node *del(node *root, int x){
    // nếu node cần xoá có giá trị nhỏ hơn giá trị node hiện tại
    // suy ra node cần xoá thuộc cây con bên trái của node hiện tại
    if(x < root->val) root->l = del(root->l, x);
    // tương tự với cây con bên phải
    else if(x > root->val) root->r = del(root->r, x);
    // đã tìm thấy node cần xoá
    else{
        // nếu node cần xoá không có cây con bên trái
        // thì ta chỉ cần "nối tiếp" cây con bên phải lên trên
        if(!root->l){
            node *tmp = root->r;
            delete root;
            return tmp;
        }
        // tương tự với cây con bên trái
        if(!root->r){
            node *tmp = root->l;
            delete root;
            return tmp;
        }
        // trường hợp có cả cây con bên trái và phải
        // ta sẽ chọn 1 trong 2 cách đều được
        // 1. tìm node nhỏ nhất của cây con bên phải
        // 2. tìm node lớn nhất của cây con bên trái
        // đây là phương án 1
        node *tmp = find(root->r);
        root->val = tmp->val;
        // sau khi cho node cần tìm thay thế lên node hiện tại
        // thì ta cần xoá bỏ cái node "cần tìm" đó
        root->r = del(root->r, tmp->val);
    }return root;
}
 
void pre(node *root){
    if(!root) return;
    cout << root->val << ' ';
    pre(root->l);
    pre(root->r);
}
 
void solve(){
    int q; cin >> q;
    node *root = nullptr;
    for(int i=1; i<=q; i++){
        cout << "Query #" << i << ": ";
        string s; cin >> s;
        int x; cin >> x;
        if(s == "ins") root = ins(root, x);
        else root = del(root, x);
        pre(root); cout << el;
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, nếu số đầu tiên lớn hơn số cuối cùng thì ta sẽ in ra hoán vị đó.

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

#define el '\n'
 
void solve(){
    int n; cin >> n;
    vector<int> v;
    for(int i=1; i<=n; i++) v.push_back(i);
    do{
        if(v[0] > v[n - 1]){
            for(int &i : v) cout << i << ' '; cout << el;
        }
    }while(next_permutation(v.begin(), v.end()));
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Với giới hạn lên tới $$$10^6$$$, việc duyệt qua từng số rồi tìm ước nguyên tố lớn nhất là không thể, vì ta sẽ mất $$$O(\sqrt n)$$$ để tìm ước, tức là xấp xỉ $$$10^3$$$ $$$\to$$$ tổng độ phức tạp sẽ là $$$O(10^9)$$$, vượt quá $$$1$$$ giây cho phép.

• Để có thể tối ưu được thời gian, ta sẽ cần sử dụng Sàng Biến Đổi ở đây. Đầu tiên, ta sẽ duyệt qua các số trong đoạn $$$[2, 10^6]$$$, với mỗi số $$$i$$$ đang xét tới, ta sẽ duyệt các bội của nó và cập nhật ước nguyên tố lớn nhất hiện tại chính là $$$i$$$. Tiếp theo, các truy vấn tính tổng tĩnh trong đoạn $$$[l, r]$$$ nào đó, ta sẽ phải nghĩ ngay đến Tổng cộng dồn để tiếp tục tối ưu thời gian, chứ không thể duyệt trâu các truy vấn được.

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

#define el '\n'
 
int d[1000005];
long long f[1000005];
void pre(){
    for(int i=2; i<=1e6; i++){
        if(d[i] == 0){
            for(int j=i; j<=1e6; j+=i){
                d[j] = i;
            }
        }
    }
    for(int i=2; i<=1e6; i++){
        f[i] = f[i - 1] + d[i];
    }
}
 
void solve(){
    int l, r; cin >> l >> r;
    cout << f[r] - f[l - 1] << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Xâu $$$s$$$ có thể có dấu cách nên ngoài các cách nhập xâu có dấu cách mà bạn có thể đã biết, thì mình có $$$1$$$ cách sau đây cũng khá đơn giản mà cũng có tác dụng tương tự getline(cin >> ws, s) thì ws ở đây mình nghĩ có nghĩa là whitespace, thì nó cũng giúp việc cin xong getline không bị lỗi. Tuy nhiên, nếu không có cin trước cái getline này, thì mình không khuyến khích các bạn sử dụng vì nó có thể gây lỗi.

• Ở bài toán này, ta sẽ sử dụng ngăn xếp để xử lý. Về cơ bản, phần thuật sẽ khá giống với bài kiểm tra dãy ngoặc đúng, chỉ khác ở chỗ khi gặp dấu ( ta sẽ in ra số thứ tự nó xuất hiện và đẩy số thứ tự đó vào stack (mục đích là để khi gặp dấu đóng ngoặc tương ứng, ta cũng sẽ in ra được số thứ tự này). Như vậy, khi gặp dấu ) thì ta chỉ cần in ra số ở đầu stack và pop nó ra.

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

#define el '\n'

void solve(){
    string a; getline(cin >> ws, a);
    int n = a.size();
    stack<int> st;
    int x = 1;
    for(int i=0; i<n; i++){
        if(a[i] == '('){
            cout << x << ' ';
            st.push(x);
            ++x;
        }else if(a[i] == ')'){
            cout << st.top() << ' ';
            st.pop();
        }
    }
    cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Ta có thể dễ dàng nhận ra rằng các điểm nghẽn, khi ta bỏ chúng ra khỏi đồ thị, thì việc đi từ $$$x \to y$$$ là hoàn toàn bất khả thi. Như vậy, ta sẽ duyệt qua các đỉnh từ $$$1 \to n$$$, ta sẽ đánh dấu vis[i] = 1 để khi chạy từ $$$x$$$ đến $$$y$$$ nó sẽ không đi qua được $$$i$$$ nữa. Nếu $$$x$$$ vẫn đến được $$$y$$$ thì chứng tỏ $$$i$$$ không phải điểm nghẽn, ngược lại thì $$$i$$$ là điểm nghẽn.

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

#define el '\n'

int n, m, s, t;
vector<int> a[101];
bool vis[101];
 
void dfs(int u){
    vis[u] = 1;
    for(int &v : a[u]){
        if(!vis[v]) dfs(v);
    }
}
 
void solve(){
    cin >> n >> m >> s >> t;
    while(m--){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        memset(vis, 0, sizeof vis);
        vis[i] = 1;
        dfs(s);
        if(!vis[t]) ++res;
    }
    cout << res << el;
    for(int i=1; i<=n; i++) a[i].clear();
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Sau khi nhập xâu $$$s$$$ vào thì ta nên lưu chúng thành vector cho dễ thao tác. Vì cây nhị phân được mô tả bởi xâu $$$s$$$, nên ta sẽ lưu các giá trị node như $$$1$$$ xâu. Về việc xây cây, ta sẽ sử dụng hàng đợi để giải quyết, duy trì thêm biến $$$i$$$ để xác định node cần chèn (bắt đầu từ $$$1$$$ do $$$0$$$ được lấy làm gốc).

• Xuất phát từ $$$a_0$$$ được lấy ra ở đầu hàng đợi, ta sẽ gán $$$a_i$$$ và $$$a_{i + 1}$$$ lần lượt là node con bên trái và phải của $$$a_0$$$. Sau đó kiểm tra $$$a_i$$$ và $$$a_{i + 1}$$$ xem nếu không phải node NULL (tức là $$$a_i$$$ khác N) thì ta mới push tiếp vào hàng đợi, bởi vì NULL sẽ không thể có node con.

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

#define el '\n'

struct node{
    string val;
    node *l, *r;
    node(string x){
        val = x;
        l = r = 0;
    }
};
 
void duyet(node *x){
    if(!x or x->val == "N") return;
    duyet(x->r);
    cout << x->val << ' ';
    duyet(x->l);
}
 
void solve(){
    string a; getline(cin >> ws, a);
    vector<string> v;
    stringstream ss(a);
    string tmp;
    while(ss >> tmp) v.push_back(tmp);
    queue<node*> q;
    node *root = new node(v[0]);
    q.push(root);
    int i = 1;
    while(!q.empty()){
        node *x = q.front(); q.pop();
        if(i == v.size()) break;
        x->l = new node(v[i]);
        if(v[i] != "N") q.push(x->l);
        ++i;
        if(i == v.size()) break;
        x->r = new node(v[i]);
        if(v[i] != "N") q.push(x->r);
        ++i;
    }
    duyet(root); cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, ta chỉ cần kiểm tra xem số đầu tiên có phải số $$$m$$$ hay không, nếu đúng thì ta sẽ in ra hoán vị đó.

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

#define el '\n'

int n, m, p[15], used[15];
void ql(int id){
    for(int i=1; i<=n; i++){
        if(!used[i]){
            used[i] = 1;
            p[id] = i;
            if(id == n){
                for(int j=1; j<=n; j++) cout << p[j] << ' '; cout << el;
            }else if(p[1] == m) ql(id + 1);
            used[i] = 0;
        }
    }
}

void solve(){
    cin >> n >> m;
    ql(1);
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Ta sẽ sử dụng quy hoạch động để giải quyết bài toán này, gần giống bài tìm dãy con tăng dài nhất nhưng thay số bằng ký tự. Gọi $$$dp_i$$$ là dãy con không giảm dài nhất kết thúc tại vị trí $$$i$$$.

• Cơ sở quy hoạch động sẽ là mọi dãy con độ dài $$$1$$$ đều thoả mãn, sau đó ta sẽ duyệt qua từng phần tử $$$j$$$ phía trước phần tử $$$i$$$ đang xét, nếu $$$a_j \le a_i$$$ thì ta sẽ cập nhật $$$dp_i = max(dp_i, dp_j + 1)$$$. Đáp số của bài toán sẽ là $$$max(dp_1, dp_2, ..., dp_n)$$$.

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

#define el '\n'

int dp[5005];
void solve(){
    int n; cin >> n;
    string a; cin >> a;
    a = "@" + a;
    int res = 1;
    for(int i=1; i<=n; i++){
        dp[i] = 1;
        for(int j=1; j<i; j++){
            if(a[i] >= a[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Vì các toán hạng có thể có nhiều chữ số, hoặc là số âm nên ta sẽ coi mỗi toán tử/toán hạng là một xâu ký tự. Như vậy, ta sẽ nhập vào một mảng gồm $$$n$$$ xâu ký tự, rồi xử lý giống như bài ở trên Code PTIT.

• Ở đây, để kiểm tra một xâu đang duyệt đến có là "số" hay không thì ta chỉ cần kiểm tra ký tự cuối cùng của nó có là chữ số hay không ?

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

#define el '\n'
#define int long long

void solve(){
    int n; cin >> n;
    vector<string> v(n);
    for(auto &i : v) cin >> i;
    stack<int> st;
    for(int i=n-1; i>=0; i--){
        if(isdigit(v[i].back())){
            st.push(stoll(v[i]));
        }else{
            int x = st.top(); st.pop();
            int y = st.top(); st.pop();
            if(v[i] == "+"){
                st.push(x + y);
            }else if(v[i] == "*"){
                st.push(x * y);
            }else if(v[i] == "/"){
                st.push(x / y);
            }else st.push(x - y);
        }
    }
    cout << st.top() << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Ta sẽ cần tối ưu $$$1$$$ thao tác thêm cạnh duy nhất, vậy phải làm như thế nào ? Việc thêm $$$1$$$ cạnh nối $$$2$$$ đỉnh đã thuộc cùng thành phần liên thông là thừa thãi, vì nó không làm thay đổi số đỉnh được đánh dấu khi duyệt từ $$$1$$$ $$$\to$$$ ta sẽ cần nối $$$2$$$ đỉnh không cùng thuộc thành phần liên thông, cụ thể là nối $$$1$$$ đỉnh thuộc thành phần liên thông chứa đỉnh $$$1$$$ với $$$1$$$ đỉnh khác thuộc thành phần liên thông khác.

• Để có thể đi từ đỉnh $$$1$$$ đến nhiều đỉnh khác nhất có thể, tức là ta cần nối thành phần liên thông nào đó không chứa $$$1$$$ và có kích thước là lớn nhất $$$\to$$$ ta sẽ duyệt qua đồ thị, tính toán kích thước của các thành phần liên thông, rồi chọn ra kích thước cần tìm đó.

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

#define el '\n'

int n, m, d[100005], sz[100005];
 
int get(int u){
    if(u == d[u]) return u;
    return d[u] = get(d[u]);
}
 
void uni(int x, int y){
    x = get(x); y = get(y);
    if(x == y) return;
    if(x > y) swap(x, y);
    d[y] = x;
    sz[x] += sz[y];
}
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        d[i] = i;
        sz[i] = 1;
    }
    while(m--){
        int x, y; cin >> x >> y;
        uni(x, y);
    }
    int mx = 0;
    for(int i=2; i<=n; i++){
        int x = get(i);
        if(x > 1){
            mx = max(mx, sz[x]);
        }
    }
    cout << sz[1] + mx;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Phần tử thứ $$$i$$$ trong mảng sẽ có node con bên trái nằm ở vị trí $$$i \times 2$$$ và có node con bên phải nằm ở vị trí $$$i \times 2 + 1$$$. Dựa vào điều này ta sẽ lưu các node vào một mảng $$$f$$$ với $$$f[i] \to l = f[i \times 2]$$$ và $$$f[i] \to r = f[i \times 2 + 1]$$$.

• Chú ý kích thước mảng $$$f$$$ có thể lên đến hơn $$$n \times 2$$$.

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

#define el '\n'

int n, a[100005];
struct node{
    int val;
    node *l, *r;
    node(int x){
        val = x;
        l = r = 0;
    }
};
 
node* f[200005];
 
void inOrder(node *root){
    if(!root) return;
    inOrder(root->l);
    cout << root->val << ' ';
    inOrder(root->r);
}
 
void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    f[1] = new node(a[1]);
    for(int i=2; i<=n; i++){
        if(i % 2 == 0){
            f[i] = new node(a[i]);
            f[i / 2]->l = f[i];
        }else{
            f[i] = new node(a[i]);
            f[(i - 1) / 2]->r = f[i];
        }
    }
    inOrder(f[1]);
    cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Cách làm giống với sinh xâu nhị phân có độ dài không quá $$$n$$$, điểm khác biệt ở đây là 0 ta sẽ coi là 6, còn 1 thì ta coi nó như là 8.
• Ta sẽ sử dụng hàng đợi để giải quyết, ban đầu cho 6 và 8 bắt đầu chạy. Với mỗi trạng thái ta lấy ra ở đầu hàng đợi, ta sẽ cần kiểm tra xem nếu nối thêm 6 hoặc 8 số vào cuối thì độ dài đã vượt quá $$$n$$$ hay chưa ? Nếu chưa thì ta mới có thể đưa trạng thái mới đó vào.

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

#define el '\n'
#define int long long

void solve(){
	int n; cin >> n;
	int mx = (int)pow(1ll * 10, n);
	vector<int> v;
	queue<int> q;
	q.push(6);
	q.push(8);
	while(!q.empty()){
		int x = q.front(); q.pop();
		v.push_back(x);
		if(x * 10 + 6 < mx){
			q.push(x * 10 + 6);
			q.push(x * 10 + 8);
		}
	}
	cout << v.size() << el;
	for(int &i : v) cout << i << ' ';
	cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Vì các toán hạng có thể có nhiều chữ số, hoặc là số âm nên ta sẽ coi mỗi toán tử/toán hạng là một xâu ký tự. Như vậy, ta sẽ nhập vào một mảng gồm $$$n$$$ xâu ký tự, rồi xử lý giống như bài ở trên Code PTIT.
• Ở đây, để kiểm tra một xâu đang duyệt đến có là "số" hay không thì ta chỉ cần kiểm tra ký tự cuối cùng của nó có là chữ số hay không ? Điều này sẽ giúp ta vừa kiểm tra được khi quyết định nhét nó vào stack cũng như là xác định biểu thức đã cho là tiền tố hay hậu tố.

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

#define el '\n'
#define int long long

void solve(){
	int n; cin >> n;
	string a[n+5];
	for(int i=1; i<=n; i++){
		cin >> a[i];
	}
	stack<int> st;
	if(isdigit(a[1].back())){
		for(int i=1; i<=n; i++){
			if(isdigit(a[i].back())){
				st.push(stoll(a[i]));
			}else{
				int x = st.top(); st.pop();
				int y = st.top(); st.pop();
				if(a[i] == "+"){
					st.push(x + y);
				}else if(a[i] == "-"){
					st.push(y - x);
				}else if(a[i] == "*"){
					st.push(x * y);
				}else{
					st.push(y / x);
				}
			}
		}
	}else{
		for(int i=n; i>=1; i--){
			if(isdigit(a[i].back())){
				st.push(stoll(a[i]));
			}else{
				int x = st.top(); st.pop();
				int y = st.top(); st.pop();
				if(a[i] == "+"){
					st.push(x + y);
				}else if(a[i] == "-"){
					st.push(x - y);
				}else if(a[i] == "*"){
					st.push(x * y);
				}else{
					st.push(x / y);
				}
			}
		}
	}
	cout << st.top() << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Đây là dạng bài BFS cơ bản về việc tìm đường đi giữa $$$2$$$ đỉnh trên đồ thị, ta sẽ duy trì các biến sau đây:
• Hàng đợi: lưu các đỉnh của đồ thị.
• Mảng par: lưu đỉnh liền kề trước của một đỉnh nào đó, phục vụ cho việc truy vết lại đường đi để xác định độ dài.
• Mảng vis: đánh dấu xem đỉnh nào đó đã được thăm hay chưa.
• Sau đó, ta sẽ bắt đầu chạy từ đỉnh $$$s$$$, đến khi nào gặp được đỉnh $$$t$$$ thì break. Sau đó, kiểm tra nếu vis[t] = 1 thì ta sẽ truy vết lại đường đi và in ra kết quả. Ngược lại, ta sẽ in ra -1.

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

#define el '\n'

int n, m, s, t, par[1001];
vector<int> a[1001];

void solve(){
    cin >> n >> m >> s >> t;
    while(m--){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    queue<int> q;
    q.push(s);
    par[s] = -1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        if(u == t) break;
        for(int &v : a[u]){
            if(par[v] == 0){
                par[v] = u;
                q.push(v);
            }
        }
    }
    if(par[t]){
        int res = 0;
        while(t != s){
            ++res;
            t = par[t];
        }
        cout << res << el;
    }else cout << "-1\n";
    for(int i=1; i<=n; i++){
        a[i].clear();
        par[i] = 0;
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Đây là một bài tập yêu cầu chúng ta phải nắm rõ về thao tác chèn trên cây nhị phân tìm kiếm (BST). Nếu bạn chưa rõ thì thao tác sẽ được chạy như sau:
• Ta gọi node đang xét đến là $$$x$$$, và giá trị $$$a_i$$$ đang cần chèn.
• Nếu $$$a_i < x \to val$$$, thì tức là $$$a_i$$$ cần thuộc cây con bên trái của $$$x$$$.
• Nếu $$$a_i > x \to val$$$, thì tức là $$$a_i$$$ cần thuộc cây con bên phải của $$$x$$$.
• Nếu $$$x$$$ là con trỏ NULL, tức là ta đã tìm thấy vị trí cần chèn, ta sẽ tạo cho $$$x$$$ là một node mới với giá trị chính là $$$a_i$$$.
• Sau khi chèn hết $$$n$$$ phần tử, ta sẽ duyệt theo phép Post Order để in ra kết quả.

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

#define el '\n'

struct node{
    int val;
    node *l, *r;
    node(int x){
        val = x;
        l = r = 0;
    }
};

node *ins(node *x, int v){
    if(x == nullptr) return new node(v);
    if(v < x->val) x->l = ins(x->l, v);
    else x->r = ins(x->r, v);
    return x;
}

void post(node *x){
    if(!x) return;
    post(x->l);
    post(x->r);
    cout << x->val << ' ';
}

int cnt = 1;
void solve(){
    cout << "Test #" << cnt++ << ": ";
    int n; cin >> n;
    int a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    node *x = nullptr;
    for(int i=1; i<=n; i++) x = ins(x, a[i]);
    post(x); cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}