2025寒假专场6

· · 题解

补水站

入门模拟

字母距离

入门模拟

饼干位置

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

睡觉时间

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

#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();

#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大的数在第一个集合，若超过了，则移动到第二个集合中，若少了，则从第二个集合中移过来。

#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;
}