• 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ể đạt được số lần duyệt là í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ẽ đi đếm số lượng thành phần liên thông mạnh và đó cũng chính là số lần duyệt ít nhất cần tìm.

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

#define el cout << '\n'

int n, m, vis[1001];
vector<int> ke[1001];
stack<int> st;

void dfs(int u, int x){
    vis[u] = 1;
    for(int &v : ke[u]) if(!vis[v]) dfs(v, x);
    if(x == 0) st.push(u);
}

void Longg(){
    cin >> n >> m;
    while(m--){
        int u, v; cin >> u >> v;
        ke[u].push_back(v);
    }
    for(int i=1; i<=n; i++) if(!vis[i]){
        dfs(i, 0);
    }
    for(int i=1; i<=n; i++) vis[i] = 0;
    int res = 0;
    while(!st.empty()){
        int u = st.top(); st.pop();
        if(vis[u]) continue;
        dfs(u, 1);
        ++res;
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int o = 1; //cin >> o;
    while(o--) 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();
}