2025寒假专场3

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

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

解法一：二分

对每个

a[i]

，二分查找

a[i]-d

和

a[i]+d

在

b[]

中的位置为

l

r

,则若

l == r

,说明无解，否则

ans = max(ans, a[i] + b[r - 1])

解法二：双指针

转自方嘉皓同学

CPP

#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

。

CPP

#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$ ，不设边权。

1 \sim M

表示元素的编号，

M+1 \sim M+M

表示集合的编号。

那么题目就转为元素

1

和元素

M

合并时，最少需要穿过几个集合。最后的答案还要再减去1即可。

设

dist[i]

表示从

1

开始到

i

合并后需要的最少集合数量，跑一边01最短路。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
const ll N = 4e5 + 10;
ll dist[N], w[N];
bool st[N];
vector<ll>g[N];
void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[1] = 0;
	priority_queue<pii, vector<pii>, greater<pii>>q;
	q.push({0, 1});
	while (q.size()) {
		auto u = q.top().second;
		q.pop();
		if (st[u]) {
			continue;
		}
		st[u] = 1;
		for (auto v : g[u]) {
			if (dist[v] > dist[u] + w[v]) {
				dist[v] = dist[u] + w[v];
				q.push({dist[v], v});
			}
		}
	}
}
int main() {

	ll n, m;
	cin >> n >> m;
	for (ll i = 1, k; i <= n; i++) {
		cin >> k;
		w[i + m] = 1;// 集合的点权 
		for (ll j = 1, x; j <= k; j++) {
			cin >> x;
			g[x].push_back(i + m); //元素与集合建边，双向边 
			g[i + m].push_back(x);
		}
	}
	dijkstra();
	if (dist[m] > 1e18) 
		cout << "-1\n";
	else 
		cout << dist[m] - 1 << "\n";
	
}

文章操作

相关推荐

评论

2025寒假专场3