B3731 题解

getchar_unlocked · 2025-03-16 21:52:33 · 题解

题目传送门

思路

首先初始化 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

#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;
}