C++ 彰雲嘉區複賽106-1 三角形

簡單的三角形判別

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

出處:GreenJudge

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

這題用 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;
}

出處:資芽OJ

HackerRank Sorting 5.Counting Inversions

這就是反序數對了(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