C++ 基礎題 洛谷 P3613 【深基15. 例2】寄包櫃

題目連結:【深基15.例2】寄包柜 – 洛谷

map and pair ( stl ) 的搜尋應用。

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

int main(){
    ios::sync_with_stdio(false);cin.tie(0);

    map<pair<int,int>,int> mp;
    int n,q;
    cin>>n>>q;

    for(int i=0;i<q;i++){
        int a;
        cin>>a;

        if(a==1){
            int x,y,st;
            cin>>x>>y>>st;
            mp[{x,y}]=st;
        }else{
            int x,y;
            cin>>x>>y;
            cout<<mp[{x,y}]<<"\n";
        }
    }
    return 0;
}

C++ 基礎題 TIOJ 1911 . 雲端列印

用 priority_queue 與 unordered_map 。

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

int main(){
    ios::sync_with_stdio(false);cin.tie(0);

    priority_queue<int> mx;
    priority_queue<int,vector<int>,greater<int>> mn;
    unordered_map<int,int> s;

    int t;
    while(cin>>t){
        if(t==0) break;

        if(t==-1){
            while(!mn.empty() && !s[mn.top()]){
                mn.pop();
            }
            if(!mn.empty()){    
                cout<<mn.top()<<' ';
                s[mn.top()]--;
                mn.pop();
            }
        }else if(t==-2){
            while(!mx.empty() && !s[mx.top()]){
                mx.pop();
            }
            if(!mx.empty()){
                cout<<mx.top()<<' ';
                s[mx.top()]--;
                mx.pop();
            }
        }else{
            s[t]++;
            mx.push(t);
            mn.push(t);
        }
    }
    return 0;
}

C++ 基礎題 單調對列

單調對列模板,因為題目的關係所以用 1 開始。

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

int idx[5000100],nm[5000100];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    stack<int> st;
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>nm[i];
        while(!st.empty() && nm[st.top()]<nm[i]){
            idx[st.top()]=i;
            st.pop();
        }

        st.push(i);
    }

    while(!st.empty()){
        idx[st.top()]=0;
        st.pop();
    }

    for(int i=1;i<=n;i++){
        cout<<idx[i]<<" ";
    }
    return 0;
}

C++ 基礎題 : 後序式求值

關於 stack 的應用 ( 經典題 )

#include<bits/stdc++.h>

using namespace std;

int main(){
    string c;
    while(getline(cin,c)){
        stack<int> st;
        for(int i=0;i<c.size();i++){
            if(isdigit(c[i])){
                st.push(c[i]-'0');
            }else{
                int a=st.top();
                st.pop();
                int b=st.top();
                st.pop();
                if(c[i]=='+'){
                    st.push(b+a);
                }else if(c[i]=='-'){
                    st.push(b-a);
                }else if(c[i]=='*'){
                    st.push(b*a);
                }else if(c[i]=='/'){
                    st.push(b/a);
                }else if(c[i]=='%'){
                    st.push(b%a);
                }
            }
        }
        cout<<st.top()<<"\n";
    }
    return 0;
}