『模拟赛』暑假集训CSP提高模拟19

日常挂分：T2 \(\color{purple} RE\) -60pts

单看T2 T3怕不是学长失恋了（逃

T1 数字三角形

简单贪心。

能往左放就往左放，不行再往下挂。

正确性：

1. 无论怎么填，一定不会出现某个连通块向右填的情况。

   比如你现在填到第 \(i\) 个数。右边的数要么填满了格子，要么还有剩余。因为格子数是 \(n + (n-1) + \space ··· \space + (n-i+1)\)，这正好对应了排列 \(p\) 中前 \(i\) 大的数。因此格子剩余最少的情况（剩0个）就是 \({p_i=n-i+1}\)，即 \(p\) 为降序排列。否则一定会有剩余。故一定没有连通块向右填的。

2. 由上得,每个连通块只会向左或向下拐，而每个块都不会影响下一个块。虽然怪多少次未知，但一定会尽可能填满之前留下的空隙。所以最后每个块都可以连续生成，也就是说本题恒有解。

int n,a[N],strike[N][N];

signed main(){
	n=rd;
	for(int i=1;i<=n;i++){
		a[i]=rd;
		strike[i][i]=a[i];
	}
	
	int cnt;
	for(int i=1;i<=n;i++){
		cnt=a[i]-1;
		int x=i,y=i,num=a[i];
		while(cnt){
			if(strike[x][y-1]==0 && y-1>0){
				strike[x][y-1]=num;
				--cnt;
				--y;
			}else if(strike[x+1][y]==0 && x+1<=n){
				strike[x+1][y]=num;
				--cnt;
				++x;
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			printf("%lld ",strike[i][j]);
		}
		putchar('\n');
	}
	return Elaina;
}

T2 那一天她离我而去

T3 哪一天她能重回我身边

T4 单调区间

赛后调的BF过了？ 样例似乎有点水。

int n,a[N],k1[N],k2[N];
int ans;

bool check(int l,int r){
	int pos1=r,pos2=r;
	for(int i=r-1;i>=l;i--){
		if(a[i]>a[pos1]) pos1=i;
		if(a[i]<a[pos2]) pos2=i;
		if(pos1!=i&&pos2!=i) return 0;
	}
	return 1;
}

signed main(){
	n=rd;
	for(int i=1;i<=n;i++) a[i]=rd;
	
	int i=1,j=1,lst=1;
	while(1){
		int l=lst,r=n;
		while(l<=r){
			int mid=(l+r)>>1;
			if(check(i,mid)){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		j=r;
		int mx=0,mn=inf;
		for(int k=i;k<=j;++k){
			if(a[k]<a[r])mx=max(mx,a[k]);
			if(a[k]>a[r])mn=min(mn,a[k]);
		}
		if(!mx)mx=a[r];
		if(mn==inf)mn=a[r];
		++j;
		while(j<=n){
			if(a[j]>mn&&a[j]<mx)break;
			mx=max(a[j],mx);
			mn=min(a[j],mn);
			++j;
		}
		--j;
		lst=r;
		if(j==n){
			ans+=(j-i+2)*(j-i+1)/2;
			return cout<<ans,0;
		}
		ans+=j-i+1;
		++i;
	}
	return Elaina;
}