mtmatt

One

0%

發表於 分類於
文章字數： 1.1k 所需閱讀時間 ≈ 2 分鐘

用 priority_queue 與 unordered_map 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}
閱讀全文 »

發表於 分類於
文章字數： 670 所需閱讀時間 ≈ 1 分鐘

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}
閱讀全文 »

發表於 分類於
文章字數： 1k 所需閱讀時間 ≈ 2 分鐘

關於 stack 的應用 ( 經典題 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}
閱讀全文 »

發表於 分類於
文章字數： 424 所需閱讀時間 ≈ 1 分鐘
  1. 先安裝 iBus。
    1
    2
    sudo apt-get update
    sudo apt-get install ibus ibus-table
  2. 解壓縮行易官網上的圖像檔與表格檔，並且放到它們該去的位置。
    1
    2
    3
    4
    5
    tar xvf boshiamy-ibus-1-8-x.tar.gz
    cd boshiamy-ibus-1-8-x
    sudo mv *.png /usr/share/ibus-table/icons/
    sudo mv *.db /usr/share/ibus-table/tables/
    ibus restart
  3. 我是在 en-us 的環境下，先跑一趟 Preferences → Language Support 去確認 Keyboard Input method system 設定為 iBus。
  4. 再從 iBus Preferences 裡面的 Input Method 頁籤新增輸入法：Chinese - boshiamy-t。
  5. 順利的話，就可服用嘸蝦米。

發表於 分類於
文章字數： 1.2k 所需閱讀時間 ≈ 2 分鐘

用到了 Bellman-Ford Shortist Path Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;
#define INF 1e9

struct edge{
    int from,to,cost;
};

int d[505],c[505],n,m;
edge a[10050];

void shortistPath(){
    while(1){
        bool update=false;
        for(int i=0;i<2*m;i++){
            if(d[a[i].from]!=INF && 
              d[a[i].to]>d[a[i].from]+a[i].cost+c[a[i].to]){
                d[a[i].to]=d[a[i].from]+a[i].cost+c[a[i].to];
                update=true;
            }
        }
        if(!update) break;
    }
}

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

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        d[i]=INF;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].from>>a[i].to>>a[i].cost;
        a[m+i].from=a[i].to;
        a[m+i].to=a[i].from;
        a[m+i].cost=a[i].cost;
    }
    d[1]=0;
    shortistPath();
    if(d[n]!=INF){
        cout<<d[n];
    }else{
        cout<<"-1";
    }
    return 0;
}
閱讀全文 »

發表於 分類於 ，
文章字數： 1k 所需閱讀時間 ≈ 2 分鐘

關於樹狀圖的應用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

int w[2000010]={0},st[10010],child[2000010][2],n,m;

int dfs(int a){
    if(a>=n) return w[a];
    w[a]=dfs(child[a][0])+dfs(child[a][1]);
    return w[a];
}

int findBox(int stw,int a){
    if(a>=n){
        return a;
    }
    if(w[child[a][0]]<=w[child[a][1]]){
        w[child[a][0]]+=stw;
        return findBox(stw,child[a][0]);
    }
    w[child[a][1]]+=stw;
    return findBox(stw,child[a][1]);
}

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

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

    for(int i=0;i<m;i++) cin>>st[i];

    for(int i=1;i<n;i++){
        int p,s,t;cin>>p>>s>>t;
        child[p][0]=s;child[p][1]=t;
    }
    int root=1;
    w[1]=dfs(root);
    for(int i=0;i<m;i++){
        cout<<findBox(st[i],root)<<" ";
    } 

    return 0;
}
閱讀全文 »

發表於 分類於 ，
文章字數： 978 所需閱讀時間 ≈ 2 分鐘

樹狀圖的結構以及 DFS ( 深度優先搜索 ) ，另外用了 height[] 來儲存高度以降低複雜度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<(b);i++)

long long n;
vector<long long> child[100010];
long long p[100010],height[100010];

void dfs(long long a){
    height[a]=0;
    for(long long v:child[a]){
        dfs(v);
        height[a]=max(height[a],height[v]+1);
    }
    return;
}

int main(){
    cin>>n;
    For(i,1,n+1){
        long long chN;cin>>chN;
        For(j,0,chN){
            long long ch;cin>>ch;
            child[i].push_back(ch);
            p[ch]=i;
        }
    }
    int root;
    for(root=1;root<=n;root++){
        if(p[root]==0) break;
    }
    dfs(root);
    long long total=0;
    for(int i=1;i<=n;i++) total+=height[i];
    cout<<root<<"\n";
    cout<<total<<"\n";
    return 0;
}
閱讀全文 »

發表於 分類於
文章字數： 299 所需閱讀時間 ≈ 1 分鐘

直接附上範例

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    for(int i=0;i<1e6;i++){
        cout<<i;
    }
}
閱讀全文 »

發表於 分類於 ，
文章字數： 914 所需閱讀時間 ≈ 2 分鐘

計算前綴和以及二分搜，以下為程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);

    int n,m;cin>>n>>m;

    int q,pSum[200010];
    cin>>pSum[0];
    for(int i=1;i<n;i++){
        cin>>pSum[i];
        pSum[i]=pSum[i]+pSum[i-1];
    }
    int pos=0;
    for(int i=0;i<m;i++){
        cin>>q;
        if(pos!=0){
            if(q>(pSum[n-1]-pSum[pos-1])){
                q-=(pSum[n-1]-pSum[pos-1]);
                q%=pSum[n-1];
                pos=lower_bound(pSum,pSum+n,q)-pSum+1;
            }else{
                pos=lower_bound(pSum,pSum+n,q+pSum[pos-1])-pSum+1;
            }
        }else{
            q%=pSum[n-1];
            pos=lower_bound(pSum,pSum+n,q)-pSum+1;
        }
        pos%=n;
    }
    cout<<pos;
    return 0;
}
閱讀全文 »

發表於 分類於 ，
文章字數： 1.5k 所需閱讀時間 ≈ 3 分鐘

有意點點類似 BFS ，不過一次只會有一個分支，以下是程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<deque>

#define MAX 1000000
using namespace std;

struct step{
    long long x,y;
};

int main(){
    int n,m,min=MAX+1;
    cin>>n>>m;
    long long sum=0;
    step best;
    int mp[110][110]={MAX};

    for(int i=0;i<110;i++){
        for(int j=0;j<110;j++){
            mp[i][j]=MAX;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            if(min>mp[i][j]){
                min=mp[i][j];
                best.x=j;best.y=i;sum=min;
            } 
        }
    }

    deque<step> st;
    st.push_front(best);
    const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

    while(!st.empty()){
        step now=st.back();
        st.pop_back();

        min=MAX;

        mp[now.y][now.x]=MAX;
        for(int i=0;i<4;i++){
            step next;
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];
            if(mp[next.y][next.x]<min){
                min=mp[next.y][next.x];
                best.x=next.x;best.y=next.y;
            } 
        }
        if(min==MAX){
            continue;
        }else{
            sum+=mp[best.y][best.x];
            st.push_front(best);
        }

    }
    cout<<sum;
    return 0;
}
閱讀全文 »