mtmatt.Page

commonPage

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;
    }
}

cout 1.362s 1e5 printf() 6.840s 1e5 cout 3.794s 1e6 printf() 44.907s 1e6

以上為我測試的結果，大家也可以試試看。

閱讀全文 »

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

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

題目連結：宜中資訊校隊練習1 - DFS, BFS & Next_Permutation - Virtual Judge

好像還是 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
#include<iostream>
#include<vector>
#include<string>
#include<deque>
using namespace std;

struct step{
    int x,y;
};

int main(){
    int n,m;
    while(cin>>m>>n){
        if(m==0) break;

        vector<string> mp;

        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            mp.push_back(s);
        }

        deque<step> bfs;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mp[i][j]=='@'){
                    step s;
                    s.y=i;s.x=j;
                    bfs.push_front(s);
                    mp[i][j]='#';
                }
            }
        }

        int ct=1;
        int dx[10]={0,1,0,-1},dy[10]={1,0,-1,0};
        while(!bfs.empty()){
            step now=bfs.back();
            bfs.pop_back();
            for(int i=0;i<4;i++){
                step next;
                next.y=now.y+dy[i];
                next.x=now.x+dx[i];
                if(next.y<0 || next.x<0 || next.y>=n || next.x>=m){
                    continue;
                }
                if(mp[next.y][next.x]=='.'){
                    mp[next.y][next.x]='#';
                    bfs.push_front(next);
                    ct++;
                }
            }
        }
        cout<<ct<<"\n";
    }
    return 0;
}
閱讀全文 »

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

題目連結：宜中資訊校隊練習1 - DFS, BFS & Next_Permutation - Virtual Judge

這個問題主要在訓練 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
65
66
67
68
69
70
#include<iostream>
#include<vector>
#include<string>
#include<deque>
using namespace std;

struct step{
    int x,y;
};

int main(){
    int n,m;
    vector<string> mp;
    bool used[110][110]={false};
    int dx[8]={-1,0,1,1,1,0,-1,-1},dy[8]={1,1,1,0,-1,-1,-1,0};

    cin>>n>>m;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        mp.push_back(s);
    }
    deque<step> bfs;
    int pos=0;
    int ct=0;

    while(1){
        step stNow;stNow.x=0;stNow.y=0;
        if(!bfs.empty()){
            stNow=bfs.front();
            bfs.pop_front();

            if(stNow.y==n-1 && stNow.x==m-1){
                break;
            }
            for(int i=0;i<8;i++){
                step next;
                next.x=stNow.x+dx[i];
                next.y=stNow.y+dy[i];
                if(next.x>=0 && next.y>=0 && next.x<m && 
                   next.y<n && mp[next.y][next.x]=='W' && 
                   !used[next.y][next.x]){
                      used[next.y][next.x]=true;
                      bfs.push_back(next);
                }
            }
        }else{
            bool isFind=false;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(mp[i][j]=='W' && used[i][j]==false){
                        used[i][j]==true;
                        step s;
                        s.y=i;s.x=j;
                        bfs.push_back(s);
                        isFind=true;
                        ct++;
                        break;
                    }
                }
                if(isFind) break;
            }
            if(!isFind){
                break;
            }
        }
    }
    cout<<ct;
    return 0;
}
閱讀全文 »

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

題目連結：c292. APCS2017-0304-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
#include<bits/stdc++.h>

int map[101][101];
bool visit[101][101]={false};

int main(){
    int n,r;
    std::cin>>n>>r;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            std::cin>>map[i][j];
        }
    }

    int row=n/2,col=n/2;
    for(int i=0;i<n*n;i++){
        visit[row][col]=true;
        std::cout<<map[row][col];

        switch(r){
            case 0:
//left
                col--;
                if(!visit[row-1][col]){
                    r++;
                }
                break;
            case 1:
//up
                row--;
                if(!visit[row][col+1]){
                    r++;
                }
                break;
            case 2:
//right
                col++;
                if(!visit[row+1][col]){
                    r++;
                }
                break;
            case 3:
//down
                row++;
                if(!visit[row][col-1]){
                    r=0;
                }
                break;
        }
    }
    return 0;
}
閱讀全文 »

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

經典的 LIS(最長遞增子序列)

但把 lower_bound() 改成 upper_bound() 就會過了。 (這點我也想了一下)

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<iostream>
#include<vector>
#include<algorithm>
using namespace std;

pair<int,int> pt[200005];

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

    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>pt[i].first>>pt[i].second;
    }
    sort(pt,pt+n);
    vector<int> v;
    for(int i=0;i<n;i++){
        auto a=upper_bound(v.begin(),v.end(),pt[i].second);
        if(a==v.end()) v.push_back(pt[i].second);
        else *a=pt[i].second;
    }
    cout<<v.size();
    return 0;
}
閱讀全文 »

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

題目連結：d050. Q_4_8 先到先服務 (* - JMJudge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

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

    ll n,m,worst;
    cin>>n>>m;
    priority_queue<ll> bars;
    for(int i=0;i<m;i++){
        bars.push(0);
    }
    for(int i=0;i<n;i++){
        ll total=bars.top();
        bars.pop();
        int ipt=0; cin>>ipt;
        total-=ipt;
        worst=max(-(total),worst);
        bars.push(total);
    }
    cout<<worst;
    return 0;
}
閱讀全文 »

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

題目連結：d041. Q_3_13 X差值範圍內的最大Y差值 - JMJudge

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
#include<iostream>
#include<algorithm>
#include<cmath> 
#include<deque>
#include<fstream>
using namespace std;

struct posion{
    int x,y;
};

bool cmp(posion a,posion b){
    return a.x<b.x;
}

posion seq[200010];

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

    int n,L;
    cin>>n>>L;
    for(int i=0;i<n;i++){
        cin>>seq[i].x;
    }
    for(int i=0;i<n;i++){
        cin>>seq[i].y;
    }
    sort(seq,seq+n,cmp);

    int best=0;
    deque<int> max,min;
    for(int i=0,j=0;i<n;i++){
        while(!max.empty() && seq[i].x-seq[max.back()].x>L)
            max.pop_back();
        while(!min.empty() && seq[i].x-seq[min.back()].x>L)
            min.pop_back();
        while(!max.empty() && seq[i].y>seq[max.back()].y)
            max.pop_front();
        while(!min.empty() && seq[i].y<seq[min.back()].y)
            min.pop_front();
        max.push_front(i);
        min.push_front(i);

        if(!max.empty() && !min.empty() && 
            abs(seq[max.back()].y-seq[min.back()].y)>best){
                best=abs(seq[max.back()].y-seq[min.back()].y);
            }
    }
    cout<<best;
    return 0;
}
閱讀全文 »