专栏文章

CF2117C 酷分割

AAndy1101
CF2117C题解参与者 1已保存评论 0

文章操作

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

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

题目传送门

思路

从题目中不难看出，bjb_j 需要包含 b1∼bj−1b_1 \sim b_{j-1} 所出现过的所有数。我们可以建两个 set，一个记录一个段的数 ss，另外一个记录之前的所有数 sallsall，当两个 set 的长度一样说明成功找到了一个段，那么此时数量 +1+1，并且清空 ss。
最后还要再特判一下，当数量为 00 时，说明无法分割，只有一大段（即原数组），此时答案为 11。

AC Code：

CPP
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N]; 
void solve()
{
	set<int> s,sall;
	int n;
	cin >>n;
	int cnt=0;
	for(int i=1;i<=n;i++) cin >>a[i];
	for(int i=1;i<=n;i++)
	{
		s.insert(a[i]);
		sall.insert(a[i]);
		if(s.size()==sall.size())
		{
			cnt++;
			s.clear();
		}
	}
	if(!cnt) cout <<cnt<<'\n';
	else cout <<cnt<<'\n';
}
int main()
{
	int t;
	cin >>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

评论

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

正在加载评论...