# 2023 南 11 校聯合寒訓 - STL容器題解

:::warning
**Slide 講義**

link : https://slides.com/jasonliu424/cpp-stl/
:::
:::info
**有地方沒講清楚歡迎來問我 > <**

Github ⚙️ https://github.com/jason810496

FB 🧬 https://www.facebook.com/JasonBigCow

IG 🐮 https://www.instagram.com/jason2004424/
:::

:::success
**延伸閱讀**

非常建議把 **CSES** 的 **Searching & Sorting** 都寫一遍

link : https://cses.fi/problemset/list/

裡面有很多**資料結構**( `STL` `pbds` `BIT` )與**排序、搜尋**搭配的經典技巧！

近幾次的 **APCS 第四題**都跟延伸閱讀的題單蠻相似的！
:::

## vector
### Zerojuege : f819 圖書館

link : https://zerojudge.tw/ShowProblem?problemid=f819

:::spoiler solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>

#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()
using namespace std;

signed main(){
    OAO
    int n;
    cin>>n;
    int ans=0;
    vector<int> over;
    int id,d;
    while(n--){
        cin>>id>>d;
        if( d>100 ){
            over.push_back(id);
            ans+=5*(d-100);
        }
    } 
    sort(all(over));

    for(const auto & i : over ){
        cout<<i<<' ';
    }
    cout<<(over.empty() ? "":"\n")<<ans<<"\n";
    return 0;
}

:::

### TOJ : 575

link : https://toj.tfcis.org/oj/pro/575/

:::info
**要注意輸出格式：** 行尾不要有空白
:::

:::spoiler solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>

#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()
using namespace std;

vector<int> vec[1000005];
signed main(){
    OAO
    int n,k;
    cin>>n>>k;

    while(k--){
        int a,b;
        cin>>a>>b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
		sort(vec[i].begin(),vec[i].end());
        if( vec[i].size() )cout << vec[i][0];
		for(int j = 1; j < vec[i].size(); j++){
			cout << ' ' << vec[i][j];
		}
		cout << '\n';
	}
    
    return 0;
}

:::

## pair

### Zerojuege : a915 二維點排序

link : https://zerojudge.tw/ShowProblem?problemid=a915

:::spoiler solution

用 `pair` 的話：連 `struct` , `compare function` 都不用寫！

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>

#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()
using namespace std;

typedef pair<int,int> pii;

signed main(){
    OAO
    int n;
    cin>>n;
    vector<pii> vec(n);
    for(auto & i :vec ){
        cin>>i.F>>i.S;
    }

    sort(all(vec));

    for(const auto & i : vec ){
        cout<<i.F<<' '<<i.S<<'\n';
    }
    return 0;
}

:::

## stack

### Zerojuege : b304 Parentheses Balance

link : https://zerojudge.tw/ShowProblem?problemid=b304

:::info
**輸入格式：** 要用 `getline` 讀
**其他：** 空字串也算正確
:::

:::spoiler solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<stack>
#include<string>

#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()
using namespace std;

signed main(){
    OAO
    int n;
    cin>>n;
    string str;
    getline(cin,str);
    while(n--){
        getline(cin,str);
        if(str.empty()){
            cout<<"Yes\n";
            continue;
        }
        else if( str.size()%2 ){
            cout<<"No\n";
            continue;
        }

        stack<char> stk;
        bool flag = true;
        
        for(int i=0;i<str.size() && flag ;i++){
            if( str[i] == '(' || str[i] == '[' ){
                stk.push(str[i]);
            }
            else if( str[i] == ')' ){
                if( stk.empty() || stk.size() && stk.top() != '(' ){
                    flag = false;
                    break;
                }
                else stk.pop();
            }
            else if( str[i] == ']' ){
                if( stk.empty() || stk.size() && stk.top() != '[' ){
                    flag = false;
                    break;
                }
                else stk.pop();
            }
        }

        cout<<(flag&&stk.empty() ? "Yes\n": "No\n" );
    }
    return 0;
}

:::

## deque

### Zerojuege : i400 字串解碼

link : https://zerojudge.tw/ShowProblem?problemid=i400

:::info
題目頗長，要仔細看，解碼要記得反著做
:::

:::spoiler solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<deque>

#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()
using namespace std;

signed main(){
    OAO
    int m , n;
    cin>>m>>n;
    vector<deque<int>> decode(m);
    deque<char> orig;
    string str;
    for(auto & i : decode ){
        cin>>str;
        for(char c : str){
            i.push_back( c-'0' );
        }
    }
    cin>>str;
    for(char c : str){
        orig.push_back( c );
    }

    int mid=n/2;
    for(int k=m-1;k>=0;k--){
        // decode part
        deque<char> after;
        for(int i=n-1;i>=0;i--){
            if(decode[k][i]){
                after.push_back( orig.back() );
                orig.pop_back();
            }
            else{
                after.push_front( orig.back() );
                orig.pop_back();
            }
        }
        orig = after;
        // swap front & back
        int cnt=0;
        for(int i=0;i<n;i++){
            cnt+=decode[k][i];
        }

        if( cnt%2 ){
            for(int i=0;i<mid;i++){
                swap(orig[i],orig[i+mid+(n%2)]);
            }
        }
    }

    for(const char & i : orig ){
        cout<<i;
    }
    cout<<'\n';
    return 0;
}

:::

## set

### CSES : Distinct Numbers

link : https://cses.fi/problemset/task/1621

:::spoiler solution

#include<iostream>
#include<utility>
#include<vector>
#include<set>
using namespace std;

#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()

signed main(){
    OAO 
    int n,x;
    set<int> Uset;
    cin>>n;
    while( n-- ){
        cin>>x;
        Uset.insert(x);
    }
    cout<<Uset.size()<<"\n";
    return 0;
}

:::

### Zerojuege : f607 切割費用

link : https://zerojudge.tw/ShowProblem?problemid=f607

:::info

:::spoiler 一些提示
1. 考慮邊界條件
2. 會用到 `二分搜` 跟 `iterator`

:::

:::spoiler solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>

#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()
using namespace std;

signed main(){
    OAO
    ll sum=0;
    int n,len,tmp,idx;
    cin>>n>>len;

    set<int> S{0,len};
    vector<int> vec(n);

    for(int i=0;i<n;i++){
        cin>>tmp>>idx;
        vec[idx-1]=tmp;
    }

    set<int>::iterator L,R;
    for(int i=0;i<n;i++){
        S.insert(vec[i]);

        L=S.lower_bound(vec[i]);
        L--;
        R=S.upper_bound(vec[i]);

        sum+=(*R-*L);
    }
    cout<<sum;

    return 0;
}

:::

## map

### CSES : Sum of Two Values

link : https://cses.fi/problemset/task/1640

:::spoiler solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>

#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()
using namespace std;

signed main(){
    OAO

    int n , k;
    cin>>n>>k;

    vi arr(n);
    map<int,int> MP;
    
    for(int &i: arr) cin>>i;

    bool flag = false;
    for(int i=0;i<n;i++ ){
        int target = k-arr[i];
        if( MP.find(target)!=MP.end() ){
            cout<<MP[ target ]+1<<" "<<i+1<<"\n";
            flag = true;
            break;
        }
        MP[ arr[i] ]=i;
    }
    if( !flag ) cout<<"IMPOSSIBLE\n";
    return 0;
}

:::

## priority_queue

### Leetcode : kth largest element in an array

link : https://leetcode.com/problems/kth-largest-element-in-an-array/

:::info
嘗試用 $O( n \log k )$ 的時間複雜度來解
:::

:::spoiler solution

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> pq;
        for(const int & i : nums ){
            pq.push(i);
            if(pq.size()>k) pq.pop();
        }
        return pq.top();
    }
};

:::

### CSES : Sliding Median

link : https://cses.fi/problemset/task/1076

:::info

這題預設用 `priority_queue` 解，不過也可以用 `multiset` ( 其實後者應該比較好想怎麼解XD )

還有 `pbds` 跟 `binary index tree` 也可以解
:::spoiler 一些提示（ 用 PQ 的話 ）
1. 中位數可以看成： 前半序列的最大值 or 後半序列的最小值
2. 所以可以開 maxHeap 跟 minHeap 來維護
3. PQ 只能刪除最大或最小值，但是有可能現在在 PQ 中的元素已經不在 window 當中了
4. 承 `3.` 所以需要另一個資料結構來紀錄「哪些元素已經不在 window 中 」這個狀態
5. 需要維護兩個 PQ 的平衡性
:::

:::spoiler solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<map>
 
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second 
#define PB push_back 
#define all(x) x.begin(),x.end()
using namespace std;
 
typedef pair<int,int> pii;
const int MAX_N = 2e5+5;
int arr[MAX_N];
signed main(){
    OAO
    int n,k;
    cin>>n>>k;
    map<int,int> Delete;
    priority_queue<int> Left;
    priority_queue<int,vector<int>,greater<int>> Right;
 
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    int mid=(k+1)/2;
    int x;
    for(int i=0;i<k;i++){
        Right.push(arr[i]);
    }
    for(int i=0;i<mid;i++){
        Left.push(Right.top());
        Right.pop();
    }
    cout<<Left.top()<<" ";
 
    for(int i=k;i<n;i++){
        int balance = 0;
        int old = arr[i-k];
        // delete old element from window 
        if( old<=Left.top() ){
            balance--;
            if( old==Left.top() ) Left.pop();
            else Delete[ old ]++;
        }
        else{
            balance++;
            if( old==Right.top() ) Right.pop();
            else Delete[ old ]++;
        }
        
        // insert cur into pq
        if( arr[i] <= Left.top() ){
            balance++;
            Left.push(arr[i]);
        }
        else{
            balance--;
            Right.push(arr[i]);
        }
        
        // balance two pq
        if(balance<0) {
            Left.push(Right.top());
            Right.pop();
        }
        if(balance>0) {
            Right.push(Left.top());
            Left.pop();
        }
 
        while( Right.size() && Delete[Right.top()]) {
            Delete[Right.top()]--;
            Right.pop();
        }
        while( Left.size() && Delete[Left.top()]) {
            Delete[Left.top()]--;
            Left.pop();
        }
        
        cout<<Left.top()<<' ';
    }
    return 0;
}

:::

:::success
如果想知道題怎麼用其他資料結構來解的話：
可以看 [這邊](https://usaco.guide/problems/cses-1076-sliding-median/solution)
:::

###### tags: `題解` `資料結構` `競程`