zd的小窝
0%

SP13707题解

发表于 更新于

题目大意

有 $n$ 次操作，对于每次操作，在 $m$ 处插入一个点，并求此时所有连续线段的数量。

题目大意

模拟。

对于每一个点，只会有三种情况：

  • 仅有一段有已插入的点，此时不会对线段数量造成影响。

  • 两端都有已插入的点，此时会将两条线段并为一条。

  • 两端都没有已插入的点，此时会增加一条线段。

代码

用 . 表示要插入的点，* 表示该点没有插入过，用 _ 表示该点被插入过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
bool f[20005];//维护线段
int main(){
	int n,cnt=0;//计数器
	cin>>n;
	for(int i=1;i<=n;i++) {
		int e;
		cin>>e;
		f[e]=1;
 		if(!f[e-1]&&!f[e+1]) cnt++;//如果出现*.*这种情况，就会多出一条
 		else if(f[e-1]&&f[e+1]) cnt--;//如果出现_._这种情况，会将两条线段并成一条
	 	cout<<cnt;
	 	puts("");//puts自动换行
 	}
 	puts("Justice");//puts自动换行
	return 0;
}