• 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'

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();
}