B3731 题解

思路

首先初始化

R_i

，再令

A_i=R_i\bmod10

，表示每个瓦片的高度。

正序遍历

A_i

，用

L_{\max,i}

表示前

i

个瓦片的最大值，则

L_{\max,i}\gets\max(L_{\max,i-1},A_i)

。同理初始化

R_{\max,i}

，表示第

i

个及以后的瓦片的最大值。

最后遍历一遍，统计积水之和，即

\sum\min(L_{\max,i},R_{\max,i})-A_i

。

AC CODE

CPP

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=105;
int a[N],r[N],l_max[N],r_max[N];
int main(){
	int n=read();r[1]=read();
	a[1]=r[1]%10;
	for(int i=2;i<=n;++i){
		r[i]=(r[i-1]*6807+2831)%201701;
		a[i]=r[i]%10;
	}
	l_max[1]=a[1];
	for(int i=2;i<=n;++i)
		l_max[i]=max(l_max[i-1],a[i]);
	r_max[n]=a[n];
	for(int i=n-1;i>=1;--i)
		r_max[i]=max(r_max[i+1],a[i]);
	int res=0;
	for(int i=1;i<=n;++i)
		res+=min(l_max[i],r_max[i])-a[i];
	printf("%d\n",res);
	return 0;
}

文章操作

思路

相关推荐

评论

B3731 题解