mtmatt

One

0%

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

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

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

用到了 set 和 iterator

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;
struct data{
    int x,i;
};
data dt[200000];
bool cmp(data a,data b){
    return a.i<b.i;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;int L;
    cin>>n>>L;
    for(int i=0;i<n;i++){
        cin>>dt[i].x;
        cin>>dt[i].i;
    }
    sort(dt,dt+n,cmp);
    set<int> s;
    s.insert(0);
    s.insert(L);
    long long sum=0;
    set<int>::iterator ptrE=s.begin();
    set<int>::iterator ptrB=s.end();
    for(int i=0;i<n;i++){
        s.insert(dt[i].x);
        ptrE=s.lower_bound(dt[i].x);
        ptrE--;
        ptrB=ptrE;
        ptrE++;ptrE++;
        sum+= (*ptrE)-(*ptrB); 
    }
    cout<<sum;
    return 0;
}
閱讀全文 »