专栏文章

题解 CF2157C Meximum Array 2

ccjh20090318
CF2157C题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min19zkq
此快照首次捕获于
2025/12/01 18:55
3 个月前
此快照最后确认于
2025/12/01 18:55
3 个月前
查看原文
疑似校内选手最早通过 C。

分析

每个元素会有以下四种情况的限制：

既有 min⁡\min 限制也有 mex⁡\operatorname{mex} 限制

前者需要大于等于 kk，后者需要不等于 kk，直接填 k+1k+1 即可。

仅有 min⁡\min 限制

为了保证最小值能取到 kk，避免受 mex⁡\operatorname{mex} 限制的影响，填 kk 即可。

仅有 mex⁡\operatorname{mex} 限制

0∼k−10 \sim k-1 每个数必须至少出现一次，对于这些位置周期性填入即可。

两个限制都没有

想填什么填什么，对于这些位置没有任何限制。
在保证有解的情况下以上策略可以满足所有性质。
单次时间复杂度 O(qn)O(qn)，精细实现可以用差分做到 O(q+n)O(q+n) 但显然没有必要。

代码

CPP
//the code is from chenjh
#include<cstdio>
using namespace std;
int n,k,q;
bool a[105],b[105];
void solve(){
	scanf("%d%d%d",&n,&k,&q);
	for(int i=1;i<=n;i++) a[i]=b[i]=0;
	for(int c,l,r;q--;){
		scanf("%d%d%d",&c,&l,&r);
		if(c==1) for(;l<=r;l++) a[l]=1;// min 限制位置。
		else if(c==2) for(;l<=r;l++) b[l]=1;// mex 限制位置。
	}
	int x=0;
	for(int i=1;i<=n;i++)
		if(a[i]) printf("%d ",k+b[i]);
		else printf("%d ",b[i]?x:k+1),x=(x+b[i])%k;// 周期性填入。
	putchar('\n');
}
int main(){
	int T;scanf("%d",&T);
	while(T--) solve(); 
	return 0;
}

评论

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

正在加载评论...