专栏文章

题解 P13509 [OOI 2024] Almost Certainly

ccjh20090318
P13509题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@minp3o3a
此快照首次捕获于
2025/12/02 06:02
3 个月前
此快照最后确认于
2025/12/02 06:02
3 个月前
查看原文
提供一个考场思路。

分析

子任务 11：N≤100N \le 100

两个多重集完全等价时，需要的操作次数即为 ∑i=1nai−bi\sum\limits_{i=1}^n a_i - b_i。
几乎等价的条件允许了 aa 中有一个元素不进行操作，即存在一对 ai,bja_i,b_j 不同，去掉后剩下的序列有解，即一一对应的 a≥ba \ge b。答案为满足条件的 ai−bja_i - b_j 最大值。
对于每个前缀序列排序后询问，枚举 ai,bja_i,b_j，O(n)O(n) 判断剩下的是否可行，总体时间复杂度 O(n4)O(n^4)。

子任务 22：N≤500N \le 500

同样的对于每个前缀序列排序后询问。
j=ij=i 时必定有解，且 j>ij > i 时答案一定没有 j=ij=i 时优秀，所以只考虑 j≤ij \le i。
选择对于位置在 jj 之前的和位置在 ii 之后的都是没有影响的，只需要考虑这两段序列的大小关系，即 ∀x∈[j,i),ax≥bx+1\forall x \in [j,i), a_x \ge b_{x+1}。
固定 ii 的同时依次从右向左扫描 jj 判断条件的同时计算最大值，时间复杂度 O(n2)O(n^2)。总体时间复杂度 O(n3)O(n^3)。

子任务 33：N≤3000N \le 3000

同样的对于每个前缀序列排序后询问。
为了让 ai−bja_i - b_j 尽可能大，i−ji-j 也要尽可能的大。
所以找到每一个满足 ax≥bx+1a_x \ge b_{x+1} 的极长区间，所有极长区间答案的最大值一定是最大的，O(n)O(n) 扫一遍即可。
总体时间复杂度 O(n2log⁡n)O(n^2 \log n) 或 O(n2)O(n^2)，取决于排序方式。

子任务 44：ai<bi+1a_i < b_{i+1}

根据限制得到 bi≤ai<bi+1≤ai+1b_i \le a_i < b_{i+1} \le a_{i+1}，保证前缀序列有序，无需再排序。
极长区间即为 [1,i)[1,i)，最大值为 ai−b1a_i - b_1，时间复杂度 O(n)O(n)。

子任务 55：ai≤ai+1,bi≤bi+1a_i \le a_{i+1}, b_i \le b_{i+1}

保证前缀序列有序，无需再排序。
但该子任务并没有保证极长区间。
只需要维护和当前 ii 相连的极长区间端点 bb 值，新添加的 aa 和端点相减更新答案，时间复杂度 O(n)O(n)。
综合以上可以获得 8080 分。
CPP
//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
typedef long long LL;
int n;
int a[MAXN],b[MAXN];
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	LL ans=0;//完全等价的代价。
	int ret=0,la,lb=1;//分别表示
	for(int i=1;i<=n;i++){
		ans+=a[i]-b[i];
		if(i>1&&a[i]>=a[i-1]&&b[i]>=b[i-1]){//已经有序则无需排序。
			a[i-1]<b[i]&&(lb=max(lb,i));//不满足条件，更新极长区间起点。
			ret=max(ret,a[i]-b[lb]);
		}
		else{
			inplace_merge(a+1,a+i,a+i+1),inplace_merge(b+1,b+i,b+i+1);//懒得手写排序，所以直接归并。
			la=lb=ret=0;
			for(int j=i;j>0;--j)
				(j>=i||a[j]<b[j+1])&&(la=a[j]),ret=max(ret,la-b[j]),a[j-1]<b[j]&&(lb=max(lb,j));
		}
		printf("%lld ",ans-ret);
	}
	putchar('\n');
}
int main(){
	int T;scanf("%d",&T);
	while(T--) solve(); 
	return 0;
}

子任务 66：无特殊限制。

考试时败在了最后 2020 分。
考虑将每个极长区间表示为 [b,a][b,a] 的区间。
如果两个区间有交集，则可以合并为同一个区间。
证明是容易的，如果区间 [b1,a1][b_1,a_1] 和 [b2,a2][b_2,a_2] 有交必然有 a1≥b2a_1 \ge b_2 或 a2≥b1a_2 \ge b_1，即边界满足条件可以进行合并。
如果区间被已有区间完全包含，就不必合并，也不必加入，因为不会产生更大的答案。
所求为所有区间的长度最大值。
于是直接用 std::set 维护区间，时间复杂度 O(nlog⁡n)O(n \log n)。

代码

CPP
//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int n;
int a[MAXN],b[MAXN];
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	LL ans=0;
	int ret=0;
	set<PII> S;
	for(int i=1;i<=n;i++){
		ans+=a[i]-b[i];
		PII c(b[i],a[i]);
		bool fl=1;
		while(!S.empty()){
			auto it=S.lower_bound(c);
			if(it!=S.end()&&it->first==c.first&&it->second>=c.second){fl=0;break;}//区间被完全包含，合并后不产生贡献，退出。
			if(it!=S.begin()&&prev(it)->second>=c.second&&prev(it)->first<=c.first){fl=0;break;}
			if(it!=S.end()&&it->first<=c.second)
				c.second=max(c.second,it->second),S.erase(it);//向右侧合并。
			else if(it!=S.begin()&&(--it)->second>=c.first)
				c.first=min(c.first,it->first),S.erase(it);//向左侧合并。
			else break;//没有区间有交集了，退出。
		}
		if(fl) S.insert(c),ret=max(ret,c.second-c.first);
		printf("%lld ",ans-ret);
	}
	putchar('\n');
}
int main(){
	int T;scanf("%d",&T);
	while(T--) solve(); 
	return 0;
}

评论

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

正在加载评论...