2025寒假专场3

compaq · 2025-01-08 10:44:58 · 题解

301排序

n很小，直接全排列枚举，判断。

302礼物

对a[] 和b[]进行排序；

解法一： 二分

对每个a[i]， 二分查找a[i]-d 和a[i]+d在b[]中的位置为l, r,则若l == r,说明无解，否则ans = max(ans, a[i] + b[r - 1]).

解法二： 双指针

转自方嘉皓同学

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+17;
long long a[N],b[N];
int main(){
    int n,m;
    long long d;
    cin>>n>>m>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    int i=n,j=m;
    while(i>=1&&j>=1){
        if(abs(a[i]-b[j])>d){
            if(a[i]>b[j])i--;
            else j--;
        }
        else {
            cout<<a[i]+b[j];
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

303顶点数量

最初0条边，q次查询，最多有3e5条边。

依次2操作, 也只需要遍历一遍出边，就能解决。时间复杂度是够的。

为了方便维护删除操作，可以使用set。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, q, cnt[N]; // cnt[i]表示与i联通的点个数 

set<int>st[N];

int main(){
    scanf("%d%d", &n, &q);

    int ans = n;

    while(q--){
        int op, u, v;
        scanf("%d", &op);
        if(op == 1){
            scanf("%d%d", &u, &v);
            if(cnt[u] == 0 && cnt[v] == 0) ans -= 2;
            else if(cnt[u] == 0 || cnt[v] == 0) ans -= 1;
            cnt[u]++;
            cnt[v]++;
            st[u].insert(v);
            st[v].insert(u);
        }
        else{
            scanf("%d", &v);
            if(st[v].size() == 0){
                printf("%d\n", ans);
                continue;
            }
            for(auto x:st[v]){
                st[x].erase(v);
                cnt[x]--;
                if(cnt[x] == 0) ans++;
            }
            st[v].clear();
            cnt[v] = 0;
            ans++;
        }
        printf("%d\n", ans); 
    }
    return 0; 
}

/*
set 集合，支持插入，删除 ，自动排序， 自动去重 
set<int>se;
se.insert(t); 在se中插入整数t

se.erase(t); 在se中删除t

se.clear(); 清空se

for(auto v: se){ // 遍历se中的每个元素 

}

multiset<int>se;  支持元素重复 

*/ 

304合并集合

如果两个集合可以合并，我们就把这两个集合之间建立一条边权为1的无向边。

显然答案就是某一个包含 1 的集合作为源点到某一个包含 M的集合的最短路。

但是集合的个数达到2e5，无法直接建图。

但是A_i总和不超过5e5，可以通过将集合中的元素与集合连边，集合点权为 1，不设边权。