C++ 最短路徑問題 Dijkstra應用

題目連結:Sprout Online Judge No. 393

這題用 Bellman-Ford 必定 TLE

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

HackerRank Sorting 5.Counting Inversions

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

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

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

HackerRank Sorting 4.Fraudulent Activity Notifications

題目連結:Fraudulent Activity Notifications | HackerRank

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

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

HackerRank Sorting 1.Bubble Sort

題目連結:Sorting: Bubble Sort | HackerRank

這題雖然有更好的算法(merge sort+反序數對),但用氣泡就可以了

void countSwaps(vector<int> a) {
    int ct=0;
    for(int i=0;i<a.size();i++){
        for (int j=0;j<a.size()-1;j++){
            if (a[j]>a[j+1]){
                ct++;
                swap(a[j],a[j+1]);
            }
        }
    }
    cout<<"Array is sorted in "<<ct<<" swaps."<<"\n";
    cout<<"First Element: "<<a[0]<<"\n";
    cout<<"Last Element: "<<a[a.size()-1];
    return;
}

HackerRank Set And Map 4.Frequency Queries

題目連結:Frequency Queries | HackerRank

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

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

HackerRank Set And Map 3.Sherlock and Anagrams

題目連結:Sherlock and Anagrams | HackerRank

對於每個左右端窮舉即可,不過別做成O(N4logN)就好

int sherlockAndAnagrams(string s) {
    int ct=0,len=s.size();
    for(int i=0;i<len;i++){
        for(int j=i;j<len;j++){
            multiset<char> st,tt;
            for(int k=i;k<=j;k++){
                st.insert(s[k]);
                tt.insert(s[k]);
            }

            for(int k=i+1;k<len-(j-i);k++){
                tt.insert(s[k+(j-i)]);
                auto it=tt.find(s[k-1]);
                if(it!=tt.end()) tt.erase(it);
                if(tt==st) ct++;
            }
        }
    }
    return ct;
}