AtCoder Beginner Contest 191 解題報告

題目鏈接：點這里~

比賽心得：遇到幾何不要慌，試試看暴力行不行=， =

A - Vanishing Pitch

題目大意

v表示小球速度， t s 表示一個時間區間， d表示球距離棒球手的距離

在小球勻速飛行，在[t,s]時間區間內會消失，問棒球手最后能不能擊中棒球

思路

求出小球飛到棒球手所花時間d/v，看是否在那個時間段就行

如果怕精度問題可以將時間區間變成距離區間[vt, vs]，然后看d是否在區間內就好

ac代碼

#include<bits/stdc++.h>
using namespace std;
#define io cin.tie(0);ios::sync_with_stdio(false);
#define debug(x) cout<<#x<<"="<<x<<endl
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define rs p<<1|1
#define ls p<<1
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline ll read(){
    ll p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+(c^48),c=getchar();}
    return f*p;
}
void solve(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    b *= a; c *= a;
    if(d >= b && d <= c) puts("No");
    else puts("Yes");
}
int main(){
    solve();
    return 0;
}

B - Remove It

題目大意

給你長度為n的序列，還有一個m，然后要你去掉序列中所有等于m的數，輸出剩下的數

思路

判斷留不留，直接用vector存

ac代碼

#include<bits/stdc++.h>
using namespace std;
#define io cin.tie(0);ios::sync_with_stdio(false);
#define debug(x) cout<<#x<<"="<<x<<endl
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define rs p<<1|1
#define ls p<<1
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline ll read(){
    ll p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+(c^48),c=getchar();}
    return f*p;
}

vector<int> ans;
void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        int x; cin >> x;
        if(x == m) continue;
        ans.push_back(x);
    }
    int f = 0;
    for(auto it : ans){
        if(f) cout << " "; f = 1;
        cout << it;
    }
}
int main(){
    solve();
    return 0;
}

D - Circle Lattice Points

題目大意

給你一個圓心坐標和半徑，問你該圓包含的整點是多少

思路

雖然是道不擅長的幾何題，但是無妨，直接暴力跑整點橫坐標，然后求出上下兩個縱坐標，然后對上下坐標之間的整點數求和即可，但是精度會損失，所以這里的應對方法是半徑R+1e-14

ac代碼

#include<bits/stdc++.h>
using namespace std;
#define io cin.tie(0);ios::sync_with_stdio(false);
#define debug(x) cout<<#x<<"="<<x<<endl
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define lb long double
#define rs p<<1|1
#define ls p<<1
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline ll read(){
    ll p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+(c^48),c=getchar();}
    return f*p;
}

void solve(){
    io;
    lb x, y, R;
    cin >> x >> y >> R;
    R += 1e-14;
    ll ans = 0;
    for(int i = ceil(x - R); i <= floor(x + R); i ++){ //左邊界向上取整，有邊界向下取整
        lb t, b;
        t = y + sqrt(R * R - (x - i) * (x - i));
        b = y - sqrt(R * R - (x - i) * (x - i));
        ans += floor(t) - ceil(b) + 1; //上邊界向下取整，下邊界向上取整
    }
    cout << ans << endl;
}

int main(){
    solve();
    return 0;
}

E - Come Back Quickly

題目大意

n個城市m條道路，每條路ai, bi, ci，表示ai到bi的單項路，需要花費ci分鐘走到，可能會有重邊和自環，問能否從第i個城市出發然后回到該城市形成一個環？可以輸出最短時間，否則-1

思路

時間給了3s，2000個點，直接考慮n個優先佇列優化的dijkstra，求出城市i到其他城市的最短路，一個for更新來回跑的最小值，最后看有沒有自環，如果有那么存自環的最短時間，然后跟之前更新的最小值當中取較小者，

ac代碼

#include<bits/stdc++.h>
using namespace std;
#define io cin.tie(0);ios::sync_with_stdio(false);
#define debug(x) cout<<#x<<"="<<x<<endl
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define rs p<<1|1
#define ls p<<1
const int maxn = 2005;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline ll read(){
    ll p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+(c^48),c=getchar();}
    return f*p;
}

int dis1[maxn][maxn], vis[maxn];
//dis1表示i到其他城市最短路，vis是自環的最小權值
struct node{
    int u, w;
    bool operator < (const node &a) const{
        return w > a.w;
    }
};
vector<node> v1[maxn]; 
void dij1(int st){
    dis1[st][st] = 0;
    queue<node> q;
    q.push({st, 0});
    while(q.size()){
        node t = q.front(); q.pop();
        int from = t.u;
        for(auto it : v1[from]){
            int to = it.u, w = it.w;
            if(dis1[st][from] + w < dis1[st][to]){
                dis1[st][to] = dis1[st][from] + w;
                q.push({to, dis1[st][to]});
            }
        }
    }
}
void solve(){
    int n, m;
    scanf("%d%d", &n, &m);
    fill(vis, vis + maxn, inf);
    for(int i = 1; i <= m; i ++){
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        if(x == y){
            vis[x] = min(vis[x], w);
            continue; //自環沒必要建圖，只需更新最小值
        }
        v1[x].push_back({y, w});
    }
    memset(dis1, inf, sizeof dis1);
    for(int i = 1; i <= n; i ++){
        dij1(i);
    }
    for(int i = 1; i <= n; i ++){
        int ans = inf;
        for(int j = 1; j <= n; j ++){
            if(i == j) continue;
            ans = min(ans, dis1[i][j] + dis1[j][i]);//一個往返的時間
        }
        ans = min(ans, vis[i]); //最后跟自環的比大小
        if(ans == inf) ans = -1;
        printf("%d\n", ans);
    }
}
int main(){
    solve();
    return 0;
}