2025寒假专场5

· · 题解

501最年轻开始

模拟

502近似值

模拟

503病毒感染

求连通性，可以dfs, bfs, 并查集

504 蛋糕

枚举每一个草莓，利用二分确定是在哪个块当中！

假设草莓的位置是(x,y)，那么草莓一定会出现在第一个比x大的平行x轴的切线 以及第一个比y大的平行y轴的切线 的方格内。

利用map对每个草莓进行统计，然后再找出那个方格的数量最少喝最多就可以。

特殊情况：最后统计的方格的数量有cnt个方格存在草莓，若cnt < (A+1) * (B + 1)则，说明最小值为0.

#include<bits/stdc++.h>
using namespace std;
const int mxv = 2e5 + 9;
#define int long long
int w, h, n;
pair<int, int> p[mxv];
int a[mxv],b[mxv],cnta,cntb;
map<pair<int,int>, int> mp;
void solve(){
    cin >> w >> h >> n;
    for(int i = 1;i <= n; i++) cin >> p[i].first >> p[i].second;// 草莓位置 
    cin >> cnta;
    for(int i = 1; i <= cnta; i++) cin >> a[i];  
    cin >> cntb;
    for(int i = 1; i <= cntb; i++) cin >> b[i];

    a[++cnta] = w; b[++cntb] = h;

    sort(a + 1, a + 1 + cnta);
    sort(b + 1, b + 1 + cntb);

    for(int i = 1; i <= n; i++){
        int x = p[i].first, y = p[i].second;
        int xx = lower_bound(a + 1, a + 1 + cnta, x) - a;
        int yy = lower_bound(b + 1, b + 1 + cntb, y) - b;
        mp[{xx, yy}]++;
    }

    int min1 = 1e18, max1 = -1e18, cnt = 0;
    for(auto t: mp){
        int y = t.second;
        min1 = min(min1, y);
        max1 = max(max1, y);
        cnt++;
    }
    if(cnt < cnta * cntb) min1 = 0;
    cout << min1 << " " << max1 << "\n";
    return;
}
signed main(){
    int t=1;
    while(t--) solve();
    return 0;
}

505好图

并查集

每次添加都是独立的，求解的问题是单独的。 每天添加一条边，只要检查看看，这两个集合是否是可以相通的即可。 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int n, m, k, q; int fa[N]; map< pair<int, int>, int > mp; int find(int x){ if(x != fa[x]) return fa[x] = find(fa[x]); return x; } void merge(int u, int v){ u = find(u), v = find(v); if(u != v) fa[u] = v; } void solve(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) fa[i] = i; for(int u, v, i = 1; i <= m; i++){ scanf("%d%d", &u, &v); if(u == v) continue; merge(u, v); } scanf("%d", &k); for(int x, y, i = 1; i <= k; i++){ scanf("%d%d", &x, &y); int xx = find(x), yy = find(y); mp[{xx, yy}] = -1; } scanf("%d", &q); while(q--){ int x, y; scanf("%d%d", &x, &y); int xx = find(x), yy = find(y); if(mp[{xx, yy}] != -1 && mp[{yy, xx}] != -1) puts("Yes"); else puts("No"); } } int main(){ solve(); return 0; } ```