mtmatt.Page

commonPage

0%

發表於 分類於
文章字數： 1.5k 所需閱讀時間 ≈ 3 分鐘 
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
#include<bits/stdc++.h>
using namespace std;

set<int> g[100010];
int ind[100010];
int n,m;

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

    int t;
    cin>>t;
    while(t--){
        ans="";ct=0;
        for(int i=0;i<100010;i++){
            g[i].clear();
            ind[i]=0;
            v[i]=0;
        }

        cin>>n>>m;
        for(int i=0;i<m;i++){
            int to,from;
            cin>>from>>to;
            g[from].insert(to);
        }

        for(int i=0;i<n;i++) 
            for(auto a:g[i])
                ind[a]++;
        vector<int> ans;
        priority_queue<int,vector<int>,greater<int>> topo;
        for(int i=0;i<n;i++){
            if(ind[i]==0){
                topo.push(i);
            }
        }

        while(!topo.empty()){
            int now=topo.top();
            topo.pop();
            ans.push_back(now);
            for(auto next:g[now]){
                if(--ind[next] ==0){
                    topo.push(next);
                }
            }
        }

        if(ans.size()==n){
            cout<<ans[0];
            for(int i=1;i<ans.size();i++) cout<<" "<<ans[i];
            cout<<"\n";
        }else{
            cout<<"QAQ\n";
        }
    }
    return 0;
}
閱讀全文 »

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

題目連結：Sprout Online Judge No. 44

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
#include<bits/stdc++.h>
using namespace std;

const int dr[4]{1,0,-1,0},dc[4]{0,-1,0,1};
struct step{
    int r,c,ct;
};

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

    int n;
    while(cin>>n && n!=0){
        vector<string> m;
        for(int i=0;i<n;i++){
            string l;
            cin>>l;
            m.push_back(l);
        }

        step start;
        for(int i=0;i<n;i++){
            for(int j=0;j<m[i].size();j++){
                if(m[i][j]=='K'){
                    m[i][j]='#';
                    start.r=i;
                    start.c=j;
                    start.ct=0;
                    break;
                }
            }
        }

        queue<step> bfs;
        bfs.push(start);
        bool isfind=false;
        int ans=1000000000;

        while(!bfs.empty()){
            step sNow=bfs.front();
            bfs.pop();
            for(int i=0;i<4;i++){
                step sNext={sNow.r+dr[i],sNow.c+dc[i],sNow.ct+1};
                if(m[sNext.r][sNext.c]=='.'){
                    m[sNext.r][sNext.c]='#';
                    bfs.push(sNext);
                }else if(m[sNext.r][sNext.c]=='@'){
                    isfind=true;
                    m[sNext.r][sNext.c]='#';
                    ans=min(sNext.ct,ans);
                }
            }
        }

        if(isfind){
            cout<<ans<<"\n";
        }else{
            cout<<"= =\n";
        }
    }
    return 0;
}
閱讀全文 »

發表於 分類於
文章字數： 767 所需閱讀時間 ≈ 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
32
#include<bits/stdc++.h>
using namespace std;

bitset<2500> tree;

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

    int iptNum;
    cin>>iptNum;
    while(iptNum--){
        int d,n;
        tree.set();
        cin>>d>>n;

        int pos;
        for(int i=0;i<n;i++){
            pos=1;
            for(int j=1;j<d;j++){
                if(tree[pos]){
                    tree[pos]=false;
                    pos*=2;
                }else{
                    tree[pos]=true;
                    pos=pos*2+1;
                }
            }
        }
        cout<<pos<<"\n";
    }
    return 0;
}
閱讀全文 »

發表於 分類於
文章字數： 749 所需閱讀時間 ≈ 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
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;

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

    int dt[1000];
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>dt[i];

    }
    stable_sort(dt,dt+n,[](int a,int b){
        int ctA=0,ctB=0;

        while(a>=1){
            if(a%2==1){
                ctA++;
            }
            a/=2;
        }
        while(b>=1){
            if(b%2==1){
                ctB++;
            }
            b/=2;
        }
        return ctA<ctB;
    });

    for(int i=0;i<n;i++){
        cout<<dt[i]<<" ";
    }
    return 0;
}
閱讀全文 »

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

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

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

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
#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;
}
閱讀全文 »

發表於 分類於
文章字數： 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;
}
閱讀全文 »

發表於 分類於
文章字數： 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;
}
閱讀全文 »