Solutions of k-th occurence

Select solution language

vdgminh Created at 2 likes

# C++ Ta sử dụng một map có key là int và value là vector<int> # Code: ``` /*code by: vdgm*/ #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); map<int, vector<int>> mp; int n, q; cin >> n >> q; for(int i = 1; i <= n; i++){ int x; cin >> x; mp[x].push_back(i); } while(q--){ int x, y; cin >> x >> y; cout << mp[x][y - 1] << '\n'; } return 0; } ``` # Giải thích code: + Chạy vòng lặp for từ 1 tới N, nhập giá trị vào biến X, ta đẩy chỉ số của X vào trong mp. + Giờ chỉ việc chạy vòng while từ 1 -> Q và nhập x và y rồi trả ra kết quả là mp[x][y - 1] (y - 1 là vì index của value trong vector) + Complexity: **O((N + Q) * log(k))**

vdgminh Created at 2 likes

# lài giởi ###### Sống trên đời, chỉ có làm thì mới có ăn nên toi không khuyến khích bạn chép code vì AC mà không hiểu thì cũng vứt *** ## C++ *** ### Ý tưởng - Ta dùng một map để lưu các phần tử $A_i$ trong mảng $A$ và vị trí của từng các phần tử. * ví dụ như mảng $A$ có các phần tử "1; 2; 3; 4; 3; 2; 1", trong map $mp$ của chúng ta sẽ như thế này: $mp_1$ = {1, 7}; $mp_2$ = {2, 6}; $mp_3$ = {3, 5} và $mp_4$ = {4}* - Trong mỗi truy vấn, ta chỉ việc trả ra số $x$ thứ $k$ nằm ở đâu là xong! *** ### Code: ```cpp #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); map<int, vector<int>> mp; // int để lưu index, vector để lưu các vị trí của index int n, q; cin >> n >> q; for(int i = 1; i <= n; i++){ int x; cin >> x; mp[x].push_back(i); } while(q--){ int x, k; cin >> x >> k; cout << mp[x][k - 1] << '\n'; // k - 1 vì ta sử dụng base-0 } return 0; } ``` *** # NHẤN MẠNH LẠI, KHÔNG NÊN CHÉP CODE