Try   HackMD

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

Slide 講義

link : https://slides.com/jasonliu424/cpp-stl/

有地方沒講清楚歡迎來問我 > <

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

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

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

延伸閱讀

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

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

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

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

vector

Zerojuege : f819 圖書館

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

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/

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

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

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

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

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

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

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

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

一些提示
  1. 考慮邊界條件
  2. 會用到 二分搜 跟 iterator
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

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/

嘗試用

O(nlog⁡k) 的時間複雜度來解

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

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

還有 pbds 跟 binary index tree 也可以解

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

如果想知道題怎麼用其他資料結構來解的話：
可以看 這邊

tags: 題解 資料結構 競程
Last changed by 
 
JasonLiu
https://github.com/jason810496/ https://www.linkedin.com/in/zhe-you-liu/ https://blog.zhu424.dev
0
1
485

Read more

NCKU CSIE PD1 Week15

👉English

Dec 12, 2023
NCKU CSIE PD1 Week15 English

If you already know what Generic Programming is,you can jump directly to Lab.

Dec 12, 2023
2023 SITCON 台南 HoC

都只有教到 for loop，差別在國小是用 Blocky (scratch) ， 國中以上是用 Python 來完成

Dec 10, 2023
基礎 Python 上課筆記

[]

Jul 13, 2023
Read more from JasonLiu
Published on HackMD