CSP 2021-09-2 非零段划分

先附上队友的题解,u1s1队友不会是因为给我讲题多了逻辑这么清晰了吧
因为本人较菜,看到这题就想起了亚特兰蒂斯?
说白了这题思路就是一个裸的扫描线,可以从上往下扫描根据峰值来更新区间个数(详见队友博客或队内dalao给我对拍的代码,咳咳

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
const int N=5e5+10,mod=1e9+7;

void add(int &a,LL b){a=(a+b)%mod;return ;}
PII a[N];
bool dis[N]; 

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].first),a[i].second=i;
	sort(a+1,a+n+1);
	int ma=0,cnt=0;
	for(int i=n;i>=0;i--) 
	{
		int x=a[i].first,y=a[i].second;
		if(x!=a[i+1].first)ma=max(ma,cnt);
		
		if(dis[y-1]&&dis[y+1])cnt--;
		else if(!dis[y-1]&&!dis[y+1])cnt++;
		dis[y]=1;
	}
	printf("%d",ma);
	return 0;
}

附上队友博客

他们的思路太好理解了,我就不加赘述了

下面是我的思路:
首先把输入数据预处理成折线图,从下往上扫描,用map来统计每个值对res 的贡献,首先个数是1单独处理,p[0] == 0 ->0, p[0] != 0->1;
否则遍历预处理所有单调(non-decreasing or non-increasing) 折线,如果是单调递减则左端点贡献-1(区间出线,右端点贡献 1,区间被线分割。
注意此思路p[0] 和 p[n-1]贡献值为 1时不需要加入贡献,因为端点处不会发生区间分割。
然后丢进map自动排序遍历取最值即为答案。res 初始值为1,即默认扫描线起点在y = 0, 只有一个区间。

//#include <bits/stdc++.h>
#include <iostream>
#include <map>

#define In inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;
using namespace std;

In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ' ';
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(las == '-')	ans = -ans;
	return ans;
}

const int N = 6e5;
int p[N], n, cnt;

void run_case(){
	n = read(), cnt = 1;
	rep(i, 0, n-1)	p[i] = read();
	if(n == 1)	printf("%d\n", p[0] == 0 ? 0 :  1);
	else{
		map<int, int> m;
		int j = 1, op = 1;// op = 1 表示向上,0表示向下 
		while(p[0] == p[j] && j < n) j ++;
		if(j == n){//说明为一条水平线
			printf("%d\n", p[0] ? 1 : 0);
			return ;
		}
		if(p[j] < p[0]) m[p[0]] --, op ^= 1;//non-increasing
		while(j < n)
			if(op){
				while(p[j] >= p[j-1] && j < n) j ++;
				if(j == n) break;
				m[p[j-1]] --;
				op ^= 1;
			}
			else{
				while(p[j] <= p[j-1] && j < n) j ++;
				if(j == n) break;
				m[p[j-1]] ++;
				op ^= 1;
			}
		if(op) m[p[n-1]] --;//p[n-1]为右上端点,贡献-1;
		int res = cnt;
		for(auto x : m){
			cnt += x.second;
			res = max(res, cnt);
		}
		printf("%d\n", res);
	}
}

int main()
{
//	freopen("C:\\Users\\MARX HE\\Desktop\\input.txt","r",stdin);
//	freopen("C:\\Users\\MARX HE\\Desktop\\output.txt","w",stdout);
	int _ = 1;
//    int _ = read();
    while(_ --){
		run_case();
    }
}

CSP 2021-09-2 非零段划分

上一篇:并发模型分析


下一篇:CSP-S济南