专栏文章

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

xxh39
P12845题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip29vs2
此快照首次捕获于
2025/12/03 04:59
3 个月前
此快照最后确认于
2025/12/03 04:59
3 个月前
查看原文

一些说明

本题解是纯思维解法。只需要用到排序算法。（也用到了枚举和贪心，但我认为这是一种思路而非算法。也用到了类似双指针的思路）但可能有些难理解，我还是尽量讲详细些。有些啰嗦，概要已加粗，可以先阅读。
遇到不理解的可以往后看，有些正确性和解释会放在结论后面。
为了方便，本题解中 lil_i 表示原题目中的 pi−lip_i-l_i，rir_i 表示原题目中的 pi+rip_i+r_i。
暴力可以不看，但对正解的思路有帮助，还是建议阅读。如果没学过搜索就跳过那一段就好。
“直接引爆”指不考虑其它炸弹的再次爆炸，爆炸的炸弹一次即可炸到的区域或炸弹。“最终能引爆”指其它炸弹也可以爆炸的情况下能炸到的区域或炸弹。

O(n2)O(n^2) 暴力

显然的做法是建图、缩点、拓扑排序，然后树形 dp。但是太难打了与本题正解无关，故不多言。

贪心+搜索做法

首先先按 pip_i 从小到大把所有炸弹排序。接着，考虑炸弹 00。炸弹 00 最终肯定是要被引爆的。然则可否顺便多带几个炸弹呢？这里的多带几个炸弹的方法是，不直接引爆炸弹 00，而是用其它的炸弹间接使炸弹 00 爆炸。显然间接爆炸一定不劣于直接爆炸，因为原本能引爆的其他炸弹一定还能引爆。
那么就去找，引爆哪些炸弹可以最终引爆 00 呢？
这时可以搜索。如果 li>pjl_i>p_j 说明 ii 可以直接引爆 jj。于是可以找到那些直接引爆炸弹 00 的炸弹，再进一步搜索能直接引爆这些炸弹的炸弹，以此类推，最终找到所有能直接引爆 00 的炸弹。
那有这么多炸弹，到底要选哪一个呢？这时候就要用到贪心。选择右端点最远的。 设这个炸弹为 ii。

正确性解释

为什么这样是对的呢？这个炸弹引爆了 [p0,ri][p_0,r_i] 中所有的炸弹（原因见下行）。因此选择这个区间的炸弹一定不优，反正炸弹 ii 可以引爆它们。所以选取 rir_i 尽可能大，最终爆炸范围就向右延拓得最远。
这个正确性是建立在保证 li≤pi≤ril_i\leq p_i\leq r_i 的基础上的。（即原题目中说的 li,ri≥0l_i,r_i\geq 0。）这样才能保证爆炸范围是连通的。（注：连通指范围是一个闭区间，比如 [0,5][0,5]，而若该条件不满足，有可能会出现多个闭区间的情况，比如 [0,3]∪[7,11][0,3] \cup [7,11]。）
（连通性的证明：两个有交的闭区间的并一定是一个闭区间，如 [1,6]∪[5,8]=[1,8][1,6]\cup[5,8]=[1,8]，而若 aa 炸弹引爆了 bb 炸弹，即 la≤pb≤ral_a\leq p_b\leq r_a，则据 lb≤pb≤rbl_b\leq p_b\leq r_b，易得这两个区间肯定有公共元素 pbp_b。证明了两个的情况，则可以数学归纳法证明任意个数的情况。）
而向左延拓再多也没有意义，因为炸弹 00 左边已经没有炸弹了。这就是要选择最左边的炸弹 00 而不能随便选一个炸弹的原因。
然后再找到最左没爆的炸弹，重复上述操作。
算法不稳定，最坏会是 O(n2)O(n^2)。（考虑如果所有炸弹互不引爆对方（即答案为 nn 的情况），每次都会把剩余没引爆的炸弹检验一遍。）

O(n+max⁡{pi})O(n+\max\{p_i\}) 正解

优化的方向

前面暴力的时间浪费在搜索时，每个炸弹无论是否可以引爆都要被枚举一遍。现在看能不能尽量只枚举可以引爆炸弹 00 的炸弹。（以炸弹 00 为例，实际上是当前没引爆的最左边的炸弹。）这样保证每个炸弹只被检验一次，复杂度就降到 O(n)O(n) 了。于是想到利用单调性。
当然还要用到前文讲到的连通性，很重要的结论（下文称为范围不跨越）是：若炸弹 ii 不能被右边的炸弹 j  (j>i)j\;(j>i) 直接引爆，那它左边的炸弹 k  (k<i)k\;(k<i) 肯定也不行。 因为引爆若能炸到 pkp_k，则说明 lj≤pk≤pi≤rjl_j\leq p_k\leq p_i\leq r_j。所以也能炸到 pip_i。

做法

于是又是贪心，先找到所有能直接引爆 00 的最右边的炸弹。（注意是位置 pp 最大不是右端点最大）然后再找 能直接引爆这枚炸弹的 最右边的 炸弹，以此类推，直到没有右边的炸弹能直接引爆它。这枚炸弹就是能直接引爆炸弹 00 的最右炸弹。然后引爆它。
正确性：因为范围不跨越，如果右边的炸弹都不能直接引爆炸弹 ii，那么最终也不能引爆炸弹 00。因为它们都不可能直接引爆在炸弹 ii 左边的炸弹。所以只能在 炸弹 (i+1)(i+1) 到 (n−1)(n-1) 内部互相引爆了。

具体实现

可以对于每个 ii，设 bib_i 表示最右边能直接炸到它的炸弹。把 bib_i 预处理出来。（如果右边没有炸弹能炸到它，bi=ib_i=i。）这就直接倒序枚举。先枚举炸弹 n−1n-1，它能炸到哪些炸弹，由于 n−1n-1 是最右边的炸弹了，所以它能炸到 ii，则 bib_i 一定为 n−1n-1。然后 n−1n-1 炸不到的，就看 n−2n-2 能不能炸到。一直枚举到 00。
不能每枚举一个炸弹都把 nn 个炸弹全枚举一遍。这时用 单调性，如果一个炸弹 ii 不能被它右边的某个炸弹炸到，那它左边的炸弹肯定更不行了。于是枚举炸弹 ii 能炸到的范围时，弄一个指针 jj，每次从右往左枚举到 pj<lip_j<l_i（炸不到）则停止。在枚举 i−1i-1 时接着上次的 jj 枚举。这样每枚炸弹都只会被枚举一次。代码如下：
CPP
j=n-1;
for(i=n-1;i&&j>=0;i--){ //如果 i=0 就不用再循环了，因为数组初始值本来就是 0。
	for(;j>=0&&_[j].a>=_[i].l;j--){ //如果 i 号炸弹直接炸到 j 号炸弹。
		b[j]=i;
	}
}
接下来就是引爆的过程。枚举每枚炸弹，找到 rr 最大的炸弹。然后继续枚举在 rr 左边的炸弹，接着引爆，一直到所有能被引爆的炸弹都引爆完。 注意新引爆的炸弹也得更新 rr 的最大值。说不清楚，那就看代码吧：
CPP
maxr=0;
for(i=0;i<n;sum++){ //每次循环时，炸弹 i 都是没被引燃的最左炸弹。sum++ 表示主动引燃了一枚炸弹。
	for(j=i;b[j]>j;j=b[j]); //不断向右炸找最远能炸到 i 的。
	maxr=max(maxr,_[j].r); //_[j].r 没有被枚举。故预判之。
	for(;i<j;i++){ //这是之前引爆的炸弹。
		maxr=max(maxr,_[i].r);
	}
	for(;i<n&&_[i].a<=maxr;i++){ //枚举能被引燃的炸弹，maxr 表示最右炸到的范围。
		maxr=max(maxr,_[i].r); //新引爆的炸弹，也要更新最右能炸到的范围。
	}
}
cout<<sum;
由于每枚炸弹只会被引爆一次，所以就算把所有炸弹枚举了总复杂度也是 O(n)O(n)。
时间复杂度：后面利用单调性，每枚炸弹最多被访问 22 次，复杂度为 O(n)O(n)，所以整体取决于排序算法的选择。桶排为 O(n+max⁡{pi})O(n+\max\{p_i\})。但我懒，STL中的sort或归并、堆排等方式就是 O(n×log⁡2(n))O(n\times \log_2(n))。
还是放一下完整的代码吧。我用这个代码弄到了截至目前的最优解。（为了最优解还得手写桶排。。。）
CPP
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &a){
	a=0;
	char c=getchar();
	for(;c<48&&c;c=getchar()){}
	for(;c>47&&c<58;c=getchar()){
		a=(a<<3)+(a<<1)+c-48;
	}
} 
struct xyq{
	int l,a,r;
}t[200005],_[200005];
struct rule{
	bool operator()(const xyq &s1,const xyq &s2){
		return s1.a<s2.a;
	}
};
int zyl[200005],b[200005]; //zyl：最右直接向左炸到 i 号炸弹的。也就是题解中的 b[i]。
int main(){
	int n,i,j,sum=0,maxr=0,maxa=0,ykb;
	cin>>n;
	for(i=0;i<n;i++){
		read(t[i].a);
		read(t[i].l);
		read(t[i].r);
		b[t[i].a+1]++;
		maxa=max(maxa,t[i].a);
		t[i].l=t[i].a-t[i].l; 
		t[i].r=t[i].a+t[i].r; 
	}
	if(maxa>(n<<4)){ //这是排序过程，大概判断一下用 sort 还是桶排快。
		for(i=0;i<n;i++){
			_[i]=t[i];
		}
		sort(_,_+n,rule());
	}else{
		for(i=2;i<=maxa+1;i++){
			b[i]+=b[i-1];
		}
		for(i=0;i<n;i++){
			_[b[t[i].a]++]=t[i];
		}
	}
	j=n-1;
	for(i=n-1;i&&j>=0;i--){ //如果 i=0 就不用再循环了，因为初始值本来就是 0。
		for(;j>=0&&_[j].a>=_[i].l;j--){ //如果 i 号炸弹直接炸到 j 号炸弹。
			zyl[j]=i;
		}
	}
	for(i=0;i<n;sum++){ //枚举第 sum 次引爆。此时 i 为最左边的炸弹。
		for(j=i;zyl[j]>j;j=zyl[j]); //不断向右炸找最远能炸到 i 的。
		maxr=max(maxr,_[j].r); //_[j].r 没有被枚举。故预判之。
		for(;i<j;i++){
			maxr=max(maxr,_[i].r);
		}
		for(;i<n&&_[i].a<=maxr;i++){ //枚举能被引燃的炸弹，maxr 表示最右炸到的范围。
			maxr=max(maxr,_[i].r); //更新最右能炸到的范围。
		}
	}
	cout<<sum;
	return 0;
}

题外话

唉，AFO 已经快四年了。高考完了来回忆一下 OI 时光，真是感慨万千。题解都是线段树，我肯定不会了，没想到还另辟蹊径，想到了纯结论的线性解法。（所以难度是不是可以降蓝了。）
这是我做这题时的一些心路历程。也提醒大家一个错解。

一个错解

一开始我想到的思路是排序后对每个炸弹先分别求出向左和右能炸到的最远炸弹编号 zlizl_i 和 zrizr_i。然后从左往右，贪心选取 rr 最大的最终能引爆当前最左炸弹的炸弹。
对于这个最远距离，我是用递推的方法求解的：以向左为例，从左往右依次确定。每枚炸弹能向左炸到的最左炸弹 zlizl_i 就是在 [li,pi][l_i,p_i]（直接炸到的所有炸弹）的 zlzl 最小值。倍增查询最小值即可。
这个漏考虑了一个问题：可以先引爆右边的某个范围更大的炸弹。一开始我以为这样的方式肯定不优，所以可以不考虑。但是对于这组数据：
CPP
4
0 0 0
1 0 2
2 2 0
3 0 0
处理出来的数据：
iizlizl_izrizr_i
000000
1111（实际为 00）33
220022（实际为 33）
333333
于是输出了错误答案 22。因为计算 zl1zl_1 时认为引爆 11 不优于引爆 22。所以没考虑向右引爆 22。而计算 zr2zr_2 时也如此。出现了两个最优解互不优于对方而都被排除的情况。
不知道这个问题可不可以被修复。但我目前没想到可以证明正确的方法。
其实我的思路和这篇题解有相似之处。这篇也错误输出了 22，验证了这个做法的错误。但这篇题解能过，我的只有 95 分。还好被卡了，不然我还以为这个做法是对的。

逐渐想到的正解

几乎做了一个下午，居然是错的。我当然不甘心，看能不能弥补这个漏洞。于是就想到了能不能不求 zlzl 和 zrzr，直接开始贪心。
于是我就想，哪些炸弹能最终引爆炸弹 00 呢？最终的不好求，先求直接引爆 00 的，然后再向右？这样不就结束了吗？
但是正要写代码时，又发现了严重的问题。在引爆关系是一条链时，这样的复杂度会降到 O(n2)O(n^2)。
怎么找 rr 最大的呢？要是是按 rr 来排序的就好了，这样就可以用单调指针的方式找到。但是贪心又得按 pp 排序。
冥思无果，我都关了电脑，打算改日再想了。但就在我躺在飘窗上时不断想，之所以会 O(n2)O(n^2)，是因为找了很多根本不需要找（不优）的炸弹，能不能避免呢？突然灵机一动，想到可不可以先找 aa 最大的。于是赶紧起来在草稿纸上画了一番，一下就解决了。
aa 越大更容易被更右边的引爆，而且 [p0,ai][p_0,a_i] 的区域肯定全部直接引爆。
但是如果右边有能引爆它的好说，直接顺序推过去就好了，反正这堆虽然是多枚举的，但也只枚举了一次。不影响复杂度。但如果右边没有，那复杂度可能又降到了 O(n2)O(n^2)。
看能不能知道右边还有没有。一番尝试后想到的一个很简单的方法，预处理出来最右边的。
而预处理如果是从左往右，要区间赋值，那又要线段树。于是就从右往左就好了。
开始又错了一次，因为只找了一次 aa 最大的，忘记了还可以继续往右搜索最终能引爆炸弹 00 的。
接着修改了一些代码细节错误，终于 AC 了。比之前的错解反而更好写。独立做出了紫题，还是挺开心的，虽然只是偶尔重拾旧好。
证明了一下正确性，就有了这篇题解。如果有疏漏也欢迎指出。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...