mtmatt.Page

commonPage

0%

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

題目連結：e525: 106 彰雲嘉區複賽 - Q5 回文日期問題

窮舉法

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
71
72
73
74
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int dom[15]={0,31,28,31,30,31,30,31,31,30,31,30,31,0,0};
int pro[700],nt,ct=0;

void check(int y){
    if(y%400==0 || (y%4==0 && y%100!=0)){
        dom[2]=29;
    }else dom[2]=28;
}

void isv(int a){
    string s;
    int b=a;
    while(a>0){
        s+=char(a%10+'0');
        a/=10;
    }
    for(int i=0;i<=s.size()/2;i++){
        if(s[i]!=s[s.size()-1-i]){
            return;
        }
    }
    pro[nt++]=b;
    return;
}

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

    int n;
    cin>>n;
    while(n--){
        int y;
        nt=ct=0;
        cin>>y;
        check(y);
        for(int i=1;i<=12;i++){
            int tmp=i;
            for(int j=1;j<=dom[i];j++){
                if(i<10){
                    if(j<10){
                        isv(y*100+i*10+j);
                        isv(y*1000+i*10+j);
                        isv(y*1000+i*100+j);
                        isv(y*10000+i*100+j);
                    }else{
                        isv(y*1000+i*100+j);
                        isv(y*10000+i*100+j);
                    }
                }else{
                    if(j<10){
                        isv(y*1000+i*10+j);
                        isv(y*10000+i*100+j);
                    }else{
                        isv(y*10000+i*100+j);
                    }
                }
            }
            i=tmp;
        }
        cout<<nt<<" ";
        sort(pro,pro+nt);
        for(int i=0;i<nt;i++){
            cout<<pro[i]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}
閱讀全文 »

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

題目連結：e521: 106 彰雲嘉區複賽 - Q1 三角形

簡單的三角形判別

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

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

    int n;
    cin>>n;
    while(n--){
        int d[3];
        for(int i=0;i<3;i++) cin>>d[i];
        sort(d,d+3);
        if(d[0]+d[1]<=d[2]){
            cout<<0<<"\n";
        }else{
            cout<<1<<" ";
            if(d[0]==d[1] || d[1]==d[2]) cout<<1;
            else cout<<0;
            cout<<"\n";
        }
    }
    return 0;
}
閱讀全文 »

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

題目連結：e522: 106 彰雲嘉區複賽 - Q2 跑長編碼與資料壓縮

字串基本應用

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

string num[10]={"000","001","010","011","100","101","110","111"};

string print(int sum,char bit){
    string re(1,bit);
    re+=num[sum];
    re+=" ";
    return re;
}

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

    int iptNum=0;
    cin>>iptNum;

    string bit,out;
    getline(cin,bit);

    while(iptNum--){
        out="";
        getline(cin,bit);
        int j,sum=1;
        long long rate=0;
        for(j=1;j<bit.size();j++){
            if(bit[j]!='0' && bit[j]!='1'){
                cout<<"-1\n";
                j++;
                break;
            }

            if(bit[j-1]==bit[j] && sum<7){
                sum++;
            }else{
                out+=print(sum,bit[j-1]);
                rate+=4;
                sum=1;
            }
        }
        out+=print(sum,bit[j-1]);
        rate+=4;
        rate*=1000;
        rate/=bit.size();
        rate=(rate+5)/10;

        if(bit[j-1]=='0' || bit[j-1]=='1'){
            cout<<out<<rate<<"\n";
        }
    }
    return 0;
}
閱讀全文 »

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

題目連結：e523: 106 彰雲嘉區複賽 - Q3 費波南希數列

用到最簡單DP和二分搜(都可以不用)

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

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

    int n,f[200];
    cin>>n;

    f[0]=-1;f[1]=1;f[2]=1;
    for(int i=3;i<100;i++){
        f[i]=f[i-1]+f[i-2];
        if(f[i]<0) f[i]=0x3f3f3f3f;
    }

    while(n--){
        int a;
        cin>>a;
        int it=lower_bound(f,f+100,a)-f;
        if(f[it]==a){
            cout<<it;
        }else{
            cout<<-1;
        }
        cout<<"\n";
    }
    return 0;
}
閱讀全文 »

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

題目連結：e524: 106 彰雲嘉區複賽 - Q4 變位字判斷

用map很方便(如果是C++11更方便)

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
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<cstdlib>
using namespace std;

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

    string a,b;
    int n;
    cin>>n;
    getline(cin,a);
    while(n--){
        getline(cin,a);
        getline(cin,b);
        map<char,int> ma,mb;

        for(int i=0;i<a.size();i++){
            char c=a[i];
            if(islower(c)){
                ma[c]++;
            }else if(isupper(c)){
                ma[tolower(c)]++;
            }
        }

        for(int i=0;i<b.size();i++){
            char c=b[i];
            if(islower(c)){
                mb[c]++;
            }else if(isupper(c)){
                mb[tolower(c)]++;
            }
        }

        bool isv=true;
        map<char,int>::iterator ta=ma.begin(),tb=mb.begin();
        for(ta=ma.begin();ta!=ma.end() && tb!=mb.end();ta++){
            pair<char,int> pa=(*ta),pb=(*tb);
            if(pa!=pb){
                isv=false;
            }
            tb++;
        }
        if(ma.size()!=mb.size()) isv=false;
        cout<<isv<<"\n";
    }
    return 0;
}
閱讀全文 »

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

題目連結：Sprout Online Judge No. 393

這題用 Bellman-Ford 必定 TLE

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
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int dr[4]{1,0,-1,0},dc[4]{0,1,0,-1};

int dt[2005][2005];
string mp[2005];
bitset<2005> v[2005];

struct position{
    int r,c;
    bool operator==(position a){
        return r==a.r && c==a.c;
    }
};
bool operator<(position a,position b){
    return dt[a.r][a.c]>dt[b.r][b.c];
}

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

    int n,m,ans=INF;
    cin>>n>>m;

    for(int i=0;i<n;i++) for(int j=0;j<m;j++) dt[i][j]=INF;

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

    position ps,pe;
    cin>>ps.r>>ps.c;ps.r--;ps.c--;
    cin>>pe.r>>pe.c;pe.r--;pe.c--;
    dt[ps.r][ps.c]=0;

    priority_queue<position> bfs;
    bfs.push(ps);

    int ct;
    position now,next,mnPos;
    while(!bfs.empty()){
        now=bfs.top();
        bfs.pop();
        v[now.r][now.c]=1;
        for(int i=0;i<4;i++){
            next.r=now.r+dr[i];
            next.c=now.c+dc[i];
            if(next.r>=0 && next.c>=0 && next.r<n && next.c<m){
                ct=dt[now.r][now.c];
                if(mp[next.r][next.c]=='.')
                    ct++;
                if(pe==next)
                    ans=min(ans,ct);
                if(!v[next.r][next.c]){
                    v[next.r][next.c]=1;
                    dt[next.r][next.c]=ct;
                    bfs.push(next);
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}
閱讀全文 »

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

題目連結：Merge Sort: Counting Inversions | HackerRank

這就是反序數對了(Merge Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<long> dt;

long msort(long l,long r){
    if(l>=r-1) return 0;
    long mid=(l+r)/2,j=mid;
    long sum=msort(l,mid)+msort(mid,r);
    long tmp[r-l],k=0;
    for(long i=l;i<mid;i++){
        while(j<r && dt[j]<dt[i]){
            tmp[k++]=dt[j++];
        }
        tmp[k++]=dt[i];
        sum+=j-mid;
    }
    while(j<r){
        tmp[k++]=dt[j++];
    }
    j=0;
    for(long i=l;i<r;i++){
        dt[i]=tmp[j];
        j++;
    }
    return sum;
}
閱讀全文 »

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

題目連結：Fraudulent Activity Notifications | HackerRank

我只想到用 Counting Sort (O(n*exp[i]_range))。

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
int activityNotifications(vector<int> e, int d) {
    int ct=0;
    vector<int> m(205,0);
    for(int i=0;i<d;i++){
        m[e[i]]++;
    }
    for(int i=d;i<e.size();i++){
        int k=0,p=-1;
        for(int j=0;j<201;j++){
            k+=m[j];
            if(d&1){
                if(k>=d/2+1){
                    if(e[i]>=j*2) ct++;
                    break;
                }
            }else{
                if(k==d/2){
                    p=j;
                }else if(k>d/2){
                    if(p==-1){
                        if(e[i]>=j*2) ct++;
                    }else{
                        if(e[i]>=j+p) ct++;
                    }
                    break;
                }
            }
        }
        m[e[i]]++;
        m[e[i-d]]--;
    }
    return ct;
}
閱讀全文 »

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

題目來源：106東區學科能力競賽

gcd轉lcm

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

int dayInM[12]={31,28,31,30,31,30,31,31,30,31,30,31};

void check(int y){
    if((y%4==0 && y%100!=0) || y%400==0){
        dayInM[1]=29;
    }else{
        dayInM[1]=28;    
    }
    return;
}

int gcd(int a,int b){
    if(a%b==0){
        return b;
    }else{
        return gcd(b,a%b);
    }
}

int main(){
    int n;
    scanf("%d",&n);

    int dt[500];
    for(int i=0;i<n;i++){
        scanf("%d",dt+i);
    }

    int y,m,d;
    scanf("%d/%d/%d",&y,&m,&d);
    for(int i=0;i<n-1;i++){
        int d=gcd(dt[i],dt[i+1]);
        int min=d*dt[i]/d*dt[i+1]/d;
        dt[i+1]=min;
    }

    d+=dt[n-1];

    check(y);
    while(d>dayInM[m-1]){
        d-=dayInM[m-1];
        m++;
        if(m>12){
            m=1;
            y++;
        }
        check(y);
    }
    printf("%4d/%02d/%02d",y,m,d);
    return 0;
}
閱讀全文 »