2025寒假专场6

补水站

入门模拟

字母距离

入门模拟

饼干位置

扫描整个图中的#，通过坐标最值可以找到矩形的边界，那么扫描矩形区域，出现.就是缺的地方了。

睡觉时间

一维区间询问，可以使用前缀和，考虑到给定的区间会把原来的睡眠时间分割开，使用二分找到第一个不小于区间端点的元素位置，修正分割量即可。

CPP

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;

const int N = 4e5 + 10;
const int MOD = 1e9 + 7;

int a[N], s[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + (a[i] - a[i - 1]) * (i & 1);
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        int idl = lower_bound(a + 1, a + n + 1, l) - a;
        int idr = lower_bound(a + 1, a + n + 1, r) - a;
        LL cnt = 0;
        if (idr & 1) 
            cnt += a[idr] - r;
        
        if (idl & 1) 
            cnt += l - a[idl - 1];
        
        cout << s[idr] - s[idl - 1] - cnt << endl;
    }
}

signed main() {

    int T = 1;
    while (T--) 
        solve();
	return 0;
}

守卫保护

从

k

个点进行扩展，假设从

u

点进行扩展，

u

点的耐力值为

h

,那么从

u

扩展到邻接点

v

时，

v

的耐力值为

h-1

, 只要耐力值不为

0

，就可以继续扩展。

可能有多个点能扩展到

v

点，那么对于

v

点来说，应选择最大的耐力值，这样能解决

v

接下来能尽可能多的扩展，且可以减少遍历的次数，降低时间复杂度。

利用优先队列代替普通队列进行

bfs()

;

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, k;
int h[N], p[N];
int vis[N], dis[N];
vector<int>g[N];
priority_queue< pair<int, int> > heap;

void bfs(){
	while(heap.size()){
		int step = heap.top().first, u = heap.top().second;
		heap.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		if(step == 0) continue; // 扩不出去
		for(auto v: g[u]){
			if(vis[v]) continue;
			heap.push({step - 1, v}); 
		}
	}
}
int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u); 
	}
	
	for(int i = 1; i <= k; i++){
		int h, p;
		scanf("%d%d", &p, &h);
		heap.push({h, p}); 
	}
	
	bfs();
	int ans = 0;
	for(int i = 1; i <= n; i++) 
		if(vis[i]) ans++;
	printf("%d\n", ans);
	for(int i = 1; i <= n; i++)
		if(vis[i]) printf("%d ", i);
	return 0;
}

函数计算1

能支持插入，自动排序，删除等操作的数据结构可以是

set

，但是本题有重复元素，所以可以使用

multiset

维护两个集合，第一个集合维护前K大数，第二个集合维护剩余的

N-K

。

对于输入的

x_i,y_i

,可以先判断

a_{x_i}

在那个集合中，再维护集合大小，保证前

K

大的数在第一个集合，若超过了，则移动到第二个集合中，若少了，则从第二个集合中移过来。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;

int n, k, q, a[N];
long long sum;
multiset<int>up, dn;

int main(){
	scanf("%d%d%d", &n, &k, &q);
	for(int i = 1; i <= k; i++)
		up.insert(0);
	for(int i = k + 1; i <= n; i++)
		dn.insert(0);
	
	while(q--){
		int x, y;
		scanf("%d%d", &x, &y);
		auto it = up.find(a[x]);//
		if(it != up.end()){
			up.erase(it);
			sum -= a[x];
		}
		else
			dn.erase(dn.find(a[x]));
		
		a[x] = y;
		if(up.size() && y >= (*up.begin())){
			up.insert(y);
			sum += y;
		}
		else
			dn.insert(y);
		
		while(up.size() < k){
			//auto it = (dn.end()--);  
			 auto it = prev(dn.end());
			up.insert(*it);
			sum += (*it);
			dn.erase(it);
		}
		
		while(up.size() > k){
			auto it = up.begin();
			sum -= (*it);
			dn.insert(*it); // 插入值
			up.erase(it); 
		}
		printf("%lld\n", sum);	
	}	
	
	
	return 0;
}

文章操作

相关推荐

评论

2025寒假专场6