mtmatt.Page

commonPage

0%

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

題目連結：Frequency Queries | HackerRank

最後我是用兩個map，一個存數字，另一個存數量變化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> freqQuery(vector<vector<int>> q) {
    vector<int> ans;
    map<int,int> m,ct;
    for(auto a:q){
        if(a[0]==1){
            ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
            m[a[1]]++;
            ct[m[a[1]]]++;
        }else if(a[0]==2){
            ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
            m[a[1]]=max(m[a[1]]-1,0);
            ct[m[a[1]]]++;
        }else{
            ans.push_back(bool(ct[a[1]]));
        }
    }
    return ans;
}
閱讀全文 »

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

題目連結：c299. 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
#include<bits/stdc++.h>
using namespace std;

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

    int n;
    cin>>n;
    int dt[105];
    for(int i=0;i<n;i++){
        cin>>dt[i];
    }
    sort(dt,dt+n);

    bool ans=true;
    cout<<dt[0]<<" "<<dt[n-1];
    for(int i=1;i<n;i++){
        if(dt[i]!=dt[i-1]+1) ans=false;
    }
    if(ans){
        cout<<" yes";
    }else{
        cout<<" no";
    }

    return 0;
}
閱讀全文 »

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

題目連結：c459. 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
#include<bits/stdc++.h>
using namespace std;

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

    int base[15][10];
    for(int i=0;i<12;i++){
        base[i][0]=1;
        for(int j=1;j<10;j++){
            base[i][j]=base[i][j-1]*i;
        }
    }

    string N;
    int b,n=0,sum=0;
    cin>>b>>N;
    for(int i=0;i<N.size();i++){
        n*=b;
        n+=N[i]-'0';
        sum+=base[(N[i]-'0')][N.size()];
    }
    string ans=(n==sum)?"YES":"NO";
    cout<<ans<<"\n";
    return 0;
}
閱讀全文 »

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

並查集，適用於高速判斷AB是否再同一組，以及合併兩組。

包含路徑壓縮與啟發式合併。

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;

class dsu{
    private:
        vector<int> p;
        vector<long long> rank;
    public:
        void init(int n){
            for(int i=0;i<=n;i++){
                p.push_back(i);
                rank.push_back(1);
            }
        }

        int find(int a){
            if(a==p[a]) return a;
            return p[a]=find(p[a]);
        }

        bool same(int a,int b){
            return find(a)==find(b);
        }

        bool uni(int a,int b){
            if(!same(a,b)){
                int rA=rank[find(a)],rB=rank[find(b)];
                if(rA>rB){
                    p[find(b)]=p[find(a)];
                }else if(rA==rB){
                    p[find(b)]=p[find(a)];
                    rank[p[find(a)]]++;
                }else{
                    p[find(a)]=p[find(b)];
                }
            }
        }
};
閱讀全文 »

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

前提是n*W不能太大。

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;
typedef long long ll;

ll dp[105][100010],v[105],w[105];

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

    int n,W;
    cin>>n>>W;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=W;j++){
            if(w[i]>j) dp[i][j]=dp[i-1][j];
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    cout<<dp[n][W];
    return 0; 
}
閱讀全文 »

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

參考資料：動態規劃】 多米諾骨牌 （ssl 1632/luogu 1282） - IT閱讀

O(q2)以內的解，有點像01背包。

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

int q,d;
short dp[1005][12010];

int main(){
    cin>>q;
    int up,dw;
    for(int i=0;i<1050;i++){
        for(int j=0;j<12010;j++) dp[i][j]=INF;
    }

    const int mx=6*q;
    dp[0][mx]=0;
    for(int i=1;i<=q;i++){
        cin>>up>>dw;
        d=up-dw;
        for(int j=mx-i*6;j<=mx+i*6;j++){
            dp[i][j]=min(dp[i-1][j-d],dp[i-1][j+d]+1);
        }
    }

    int k=mx;
    while(dp[q][k]==INF) k++;
    cout<<dp[q][k]<<"\n"<<k-mx;
    return 0;
}
閱讀全文 »