JZTXT

ABC304

发布时间 2023-06-04 09:20:27作者: V_Melville

T1：First Player

模拟

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<string> s(n);
    vector<int> a(n);
    rep(i, n) cin >> s[i] >> a[i];
    
    int si = 0;
    rep(i, n) if (a[i] < a[si]) si = i;
    
    rep(i, n) {
        int ni = (si+i)%n;
        cout << s[ni] << '\n';
    }
    
    return 0;
}

T2：Subscribers

模拟

代码实现 
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    string s = to_string(n);
    for (int i = 3; i < s.size(); ++i) {
        s[i] = '0';
    }
    
    cout << s << '\n';
    
    return 0;
}

T3：Virus

可以将满足欧几里得距离不超过 \(d\) 的两点进行连边，在点 \(1\) 所在的连通分量内的点都会被感染

可以用 dfs/bfs/并查集 实现

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n, d;
    cin >> n >> d;
    
    vector<int> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];
    
    auto near = [&](int a, int b) {
        int dx = x[a]-x[b];
        int dy = y[a]-y[b];
        return dx*dx+dy*dy <= d*d;
    };
    
    queue<int> q;
    vector<bool> ans(n);
    ans[0] = true; q.push(0);
    while (q.size()) {
        int v = q.front(); q.pop();
        rep(u, n) {
            if (near(v, u)) {
                if (ans[u]) continue;
                ans[u] = true;
                q.push(u);
            }
        }
    }
    
    rep(i, n) {
        puts(ans[i] ? "Yes" : "No");
    }
    
    return 0;
}

T4：A Piece of Cake

先用两次 std::lower_bound() 来确定每个草莓位于哪块区域
再用 std::map<pair<int, int>, int> 来统计每块区域中草莓的个数
然后遍历一遍 map，找到 \(m\) 和 \(M\)

注意：当 map 的大小 \(< (A+1)(B+1)\) 时，\(m = 0\)

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    int w, h, n;
    cin >> w >> h >> n;
    
    vector<int> p(n), q(n);
    rep(i, n) cin >> p[i] >> q[i];
    
    int A;
    cin >> A;
    vector<int> a(A);
    rep(i, A) cin >> a[i];
    int B;
    cin >> B;
    vector<int> b(B);
    rep(i, B) cin >> b[i];
    
    map<P, int> mp;
    rep(i, n) {
        int x = lower_bound(a.begin(), a.end(), p[i])-a.begin();
        int y = lower_bound(b.begin(), b.end(), q[i])-b.begin();
        mp[P(x, y)]++;
    }
    
    int m = n, M = 0;
    for (auto e : mp) {
        m = min(m, e.second);
        M = max(M, e.second);
    }
    if (mp.size() < (ll)(A+1)*(B+1)) m = 0;
    
    cout << m << ' ' << M << '\n';
    
    return 0;
}