APCS 2021 9/5

mtmattAPCS, APCS實作題Leave a Comment on APCS 2021 9/5

1. 對聯

  • A : 2, 4字平仄不同 && 2, 6平仄相同
  • B : 第一句最後一字仄，第二句則是平
  • C : 第一二句2, 4, 6 字分別平仄不同

input : 七言對聯 0->平, 1->仄

1
0 0 0 0 1 1 1
1 1 1 1 0 0 0

ouput : 違反ABC哪些個規則就輸出相對應的英文字母(ABC)，若沒違反則輸出 "None"

A

2. 炸彈魔王

遊戲採回合制，回合開始時若魔王位於炸彈上則所有在同一格的魔王會連同炸彈一起消失，所有未消失的魔王會先在腳下放一顆炸彈，再依據方向向量(s, t)移動。移動到邊界外的魔王視為消失。
求所有魔王消失時還有未爆彈的地點數。

n,m,r,c <= 100, k<500, |s,t|<=10

input : 第一行 n, m, k 分別表示地圖長寬以及魔王數，接下來有 k 行每一行都有r, c, s, t 分別表示魔王初始位置座標，以及移動向量。

3 3 2
1 2 0 -1
2 1 1 -2

output:

5

3. 幸運號碼

給一個陣列，依據以下步驟尋找答案。

  1. 找到區間最小值
  2. 依據最小值分為左右兩邊詢問
  3. 選擇區間和較小的一邊作為下個搜索區間
    n<=300000

input : 

6
3 2 1 5 4 7

output:

7

4. 美食

有 n 攤美食和 k 個人，每個人必須吃連續區段的攤位，且菜色不得重複。求最大可以被吃到的攤位數。

n<=1000000, k<=20, nk<=5000000, a[i]<100000

其他限制
50% k=1
100% none

input :

5 1
1 2 3 1 2

output:

3

C++資料結構：Binary Search Tree

mtmatt, C++學習心得Leave a Comment on C++資料結構：Binary Search Tree

Binary Search Tree (二元搜尋樹)，是用來存放多筆資料，並快速搜尋的資料結構。大概的原則就是，大的放右邊，小的放左邊。

新增，刪除一個值都只要O(log(N))

以下為實作範例

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

template<class T>
class bst{
    private:
        struct node{
            T val;
            node* l,r;

            node(){
                l=r=nullptr;
            }
            node(T v){
                l=r=nullptr;
                val=v;
            }
        };

        bool find(node *n,T v){
            if(n->val==v){
                return true;
            }else if(n->val > v && n->r!=nullptr){
                find(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                find(n->l,v);
            }else{
                return false;
            }
        }

        void insert(node *&n,T v){
            if(n==nullptr){
                node nd=new node(v);
                n=&nd;
            }else if(n->val > v && n->r!=nullptr){
                insert(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                insert(n->l,v);
            }
        }

        void DeleteNode(node *&n){
            if(n->l==nullptr && n->r==nullptr){
                delete n;
                n=nullptr;
            }else{
                node *left,*right;
                if(n->l==nullptr){
                    right=n->r;
                    n->val=right->val;
                    n->l=right->l;
                    n->r=right->r;
                    delete right;
                }else if(n->r==nullptr){
                    left=n->l;
                    n->val=left->val;
                    n->l=left->l;
                    n->r=left->r;
                    delete left;
                }else{
                    right=n;
                    left=n->l;
                    while(left->r!=nullptr){
                        right=left;
                        left=left->l;
                    }
                    n->val=left->val;
                    if(right!=n)
                        right->r=left->l;
                    else
                        right->l=left->l;
                    delete left;
                }
            } 
        }

        void erase(node *n,T v){
            if(n->val==v){
                DeleteNode(n);
            }else if(n->val > v && n->r!=nullptr){
                erase(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                erase(n->l,v);
            }
        }

        void DeleteTree(node *n){
            if(n->l!=nullptr)
                DeleteTree(n->l);
            if(n->r!=nullptr)
                DeleteTree(n->r);
            delete n;
        }
    public:
        bst(){
            root=nullptr;
            sz=0;
        }

        ~bst(){
            if(root!=nullptr)
                DeleteTree(root);
        }

        bool find(T v){
            if(root!=nullptr)
                return find(root,v);
        }

        void insert(T v){
            if(root==nullptr){
                node n=new node(v);
                root=&n;
            }else{
                insert(root,v);
            }
            sz++;
        }

        void erase(T v){
            if(root==nullptr) return;
            erase(root,v);
            sz--;
        }

        int size(){
            return sz;
        }
    private:
        node *root;
        int sz;
};



相同的，C++都幫你做好了，就是所謂的Set & Map。

以下為使用範例

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

int main(){
    vector<int> v(100);
    for(int i=0;i<100;++i){
        v[i]=i;
    }
    random_shuffle(v.begin(),v.end());

    set<int> s;
    for(auto a:v){
        s.insert(a);
    }

    random_shuffle(v.begin(),v.end());

    for(auto a:v){
        cout<<*s.lower_bound(a)<<" ";
        cout<<*s.upper_bound(a)<<"\n";
    }
    s.erase(10);
    cout<<*s.lower_bound(10);
}



我相信許多人跟我一樣，一開始不知道這些東西要用在哪？

以下我找了幾個範例

1. 在O(Nlog(26))以內找出是否有一個字母在兩個字串中均能被找到(出處：HackerRank)

string twoStrings(string s1, string s2) {
    set<char> s;
    for(auto a:s1){
        s.insert(a);
    }
    for(auto a:s2){
        if(s.count(a)){
            return "YES";
        }
    }
    return "NO";
}

2. 以O(N3log(N))找出一個字串中無序變形子串對的數目(出處：HackerRank) 最重要的，就是其刪除快速的特性

int sherlockAndAnagrams(string s) {
    int ct=0,len=s.size();
    for(int i=0;i<len;i++){
        for(int j=i;j<len;j++){
            multiset<char> st,tt;
            for(int k=i;k<=j;k++){
                st.insert(s[k]);
                tt.insert(s[k]);
            }

            for(int k=i+1;k<len-(j-i);k++){
                tt.insert(s[k+(j-i)]);
                auto it=tt.find(s[k-1]);
                if(it!=tt.end()) tt.erase(it);
                if(tt==st) ct++;
            }
        }
    }
    return ct;
}

3. 最後一個是Map的應用範例，Map是以first做排序依據，second存放對應資料。最常見的就是數字與出現頻率，以下甚至還有用來存頻率的頻率的用法。(出處：HackerRank) m 放<數字 , 頻率>，ct 放<頻率 , 頻率的頻率>

vector<int> freqQuery(vector<vector<int>> q) {
    vector<int> ans;
    map<int,int> m,ct;
    for(auto a:q){
        if(a[0]==1){
            ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
            m[a[1]]++;
            ct[m[a[1]]]++;
        }else if(a[0]==2){
            ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
            m[a[1]]=max(m[a[1]]-1,0);
            ct[m[a[1]]]++;
        }else{
            ans.push_back(bool(ct[a[1]]));
        }
    }
    return ans;
}

下一篇心得會補 pointer (指標) 的部分，在此之前可以先Google搜尋(C++指標)。

C++資料結構：Stack & Queue

mtmatt, C++學習心得Leave a Comment on C++資料結構：Stack & Queue

Stack，又稱作堆疊，顧名思義就是從上面(也可以說前面)放入與取出的資料結構。 Queue，稱為佇列，是從前面放後面取出的資料結構。

實作程式碼如下

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

template<class T>
class Stack{
    private:
        int t=-1;
        vector<T> dt;
    public:
        T top(){
            if(t!=-1){
                return dt[t];
            }else{
                cout<<"Stack is empty.\n";
            }
        }

        void pop(){
            if(t!=-1){
                t--;
                dt.pop_back();
            }else{
                cout<<"Stack is empty.\n";
            }
        }

        void push(T p){
            t++;
            dt.push_back(p);
        }
};

template<class T>
class Queue{
    private:
        deque<T> dt;
    public:
        T front(){
            if(!dt.empty()){
                return dt.front();
            }else{
                cout<<"Queue is empty.\n";
            }
        }

        void pop(){
            if(!dt.empty()){
                dt.pop_front();
            }else{
                cout<<"Queue is empty.\n";
            }
        }

        void push(T p){
            dt.push_back(p);
        }
};

C++已經幫你將這兩個資料結構實做好了，以下示範例程式碼

#include<iostream>
#include<stack>
#include<queue>
#include<deque>

using namespace std;

int main(){
    stack<int> st;
    for(int i=0;i<10;++i){
        st.push(i);
    }
    cout<<st.size()<<"\n";
    while(!st.empty()){
        cout<<st.top()<<" ";
        st.pop();
    }
    cout<<"\n\n";

    queue<int> q;
    for(int i=0;i<10;++i){
        q.push(i);
    }
    cout<<q.size()<<"\n";
    while(!q.empty()){
        cout<<q.front()<<" "<<q.back()<<"\n";
        q.pop();
    }
    cout<<"\n";
}

光聽這兩個介紹以及大部分的分享，相信你還是不知道這兩個東西要用在哪裡。以下會有幾個應用的範例，都是用 STL 。

1.在 O(N) 的複雜度下做單調對列 Ex : 洛谷

題目敘述：
對於每個元素，從後面找出第一個比他大的元素的位置

這題就是要透過 stack 保持裡面所存位置對應的元素的單調遞減性。實際做法就是，遇到比他大的就丟掉，反正已經確認現在這個元素已經比他大了，後面也不會用到。否則他就還沒遇到還沒遇到比他大的。

以下為程式碼

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

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

    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;++i) cin>>v[i];

    vector<int> ans(n,0);
    stack<int,vector<int>> st;
    for(int i=0;i<n;++i){
        while(!st.empty() && v[st.top()]<v[i]){
            ans[st.top()]=i+1;
            st.pop();
        }
        st.push(i);
    }

    for(int a:ans)
        cout<<a<<" ";
}

2.以 O(N) 在滑動窗口中找最大以及最小值 Ex : 洛谷

題目敘述：
在所有長度為k的窗口中找到最大以及最小值

這題要用deque(double-ended-queue)，也就是雙向佇列，是一個從前後方都可以加入以及刪除值的queue。用以維持內部元素既在範圍以內，又保持單調遞增或遞減。

以下為程式碼

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

int nm[1000010]={0},rmax[1000010],rmin[1000010];

int main(){
    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>nm[i];

    deque<int> mx,mn;

    for(int i=0;i<k;i++){
        while(!mx.empty() && nm[mx.front()]<nm[i])
            mx.pop_front();
        mx.push_front(i);

        while(!mn.empty() && nm[mn.front()]>nm[i])
            mn.pop_front();
        mn.push_front(i);
    }

    rmax[0]=mx.back();
    rmin[0]=mn.back();

    for(int i=1,j=k;j<n;i++){

        while(!mx.empty() && mx.back()<i)
            mx.pop_back();
        while(!mn.empty() && mn.back()<i)
            mn.pop_back();

        while(!mx.empty() && nm[mx.front()]<nm[j])
            mx.pop_front();
        mx.push_front(j);
        while(!mn.empty() && nm[mn.front()]>nm[j])
            mn.pop_front();
        mn.push_front(j);

        rmax[i]=mx.back();
        rmin[i]=mn.back();

        j++;
    }

    for(int i=0;i<n-k+1;i++)
        cout<<nm[rmin[i]]<<" ";
    cout<<"\n";
    for(int i=0;i<n-k+1;i++)
        cout<<nm[rmax[i]]<<" ";
    return 0;
}

未完待續~~