题解：P12845 [蓝桥杯 2025 国 A] 连锁反应【数据强度待检验】

· · 题解

P12845 [蓝桥杯 2025 国 A ] 连锁反应

题目分析

分析题目可知，爆炸是一种树形结构，我们要引爆的是跟节点，那现在要求的就是有多少棵树

问题转化

现在的问题就是计算一个节点所在的最大树并把它清除 然后从左到右遍历出所有树

思路

这里提供一个贪心算法

  1. 根节点为炸毁当前连通块已遍历节点的最右节点（因为我们从左往右遍历）
  2. 那怎么更新呢这个跟节点呢? 如果一个节点能炸毁当前根节点，那这个节点一定能炸毁连通块已遍历节点，因为根节点会继续引爆
  3. 如果一个节点不能炸毁当前根节点，那他一顶定炸不毁当前根节点（能炸毁且靠右的点会被更新为根节点，说明右边没有点能炸毁当前根节点），那自然炸不掉,不会更优

    解法

    那我们只需要维护右最大炸毁边界和最优根节点, O(n) 遍历即可，排序时间复杂度 O(nlog{n}) ，这个算法即便 l, r 达到 1e18 也是可以的，数据适配范围上优于直接使用 SCC 。

    代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct sg{
    int x,l,r;
};
bool cmp(sg a,sg b){
    return a.x < b.x;
}
bool cmp1(sg a,sg b){
    return a.l < b.l;
}
int sm[200005];
void solve(){
    int n; cin >> n;
    vector<sg> a(n);
    for (int i = 0; i < n; i++){
       int p,l,y;
       cin >> p >> l >> y;
       a[i] = {p,p-l,p+y}; 
    }
    sort(a.begin(),a.end(),cmp);
    queue<sg> q;
    for (int i = 0; i < n; i++){
       q.push(a[i]); 
    }
    int ans = 0,x=-1e18;
    sort(a.begin(),a.end(),cmp1);
    queue<sg> q1;
    for (int i = 0; i < n; i++){
       q1.push(a[i]);
    }
    int r=-1e18;
    while(!q.empty()){
        if(q1.front().l > x){
            x=q.front().x;
            q.pop();
            ans++;
        }
        while(!q1.empty() && q1.front().l <= x){
            r=max(r,q1.front().r);
            x=max(x,q1.front().x);
            q1.pop();
        }
        while(!q.empty() && q.front().x <= r){
            if(q.front().l <= x&& q.front(). x){
                x=max(x,q.front().x);
            }
            r=max(r,q.front().r);
            q.pop();
        }
    }
    cout << ans << endl;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}