确实太颓了，在 csp 前教练给的题单里的题，快退役了才做/ll

思路

显然切除的一定是一个区间。其次若对于一列达到了他可行的最小的切除高度，那么切得更多一定合法，于是考虑求出这个值。

仔细观察发现，第

i

列至少要把第

\min(h_{i - 1},h_i,h_{i + 1})

行及以上切掉（若

i - 1,i + 1

列都要切）。令这个值为

a_i

。

枚举区间右端点

r

，所有合法区间的答案为：

\sum_{l < r}{((\min(h_l,h_{l + 1}) - 1) \times (\min(h_r,h_{r - 1}) - 1) \times \prod_{l < i < r}{(a_i - 1)}})

考虑对

a_i - 1

做前缀积：

s_i = \prod_{j \leq i}{(a_i - 1)}

。得：

\sum_{l < r}(\min(h_l,h_{l + 1} - 1) \times (\min(h_r,h_{r - 1}) - 1) \times \frac{s_{r - 1}}{s_{l}})\\ \Rightarrow \sum_{l < r}{(\frac{\min(h_l,h_{l + 1}) - 1}{s_l}) \times (\min(h_r,h_{r - 1}) - 1) \times s_{r - 1}}

考虑对

\frac{\min(h_i,h_{i + 1}) - 1}{s_l}

做前缀和，记为

S_i

，得：

(\min(h_r,h_{r + 1}) - 1) \times s_{r - 1} \times S_{r - 1}

需要注意

h_i = 1

的情况，以及在上述情况的基础上加上

r

单独为一段的情况。

Code

CPP

#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) (((a) + (b)) % mod)
#define Mul(a,b) ((a) * (b) % mod)
#define chAdd(a,b) (a = Add(a,b))
#define chMul(a,b) (a = Mul(a,b))

using namespace std;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
int n,ans;
int arr[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int qmi(int a,int b){
    int res = 1;
    while (b){
        if (b & 1) chMul(res,a);
        chMul(a,a); b >>= 1;
    } return res;
}

signed main(){
    n = read();
    for (re int i = 1;i <= n;i++) arr[i] = read();
    for (re int i = 1,s = 1,sum = 0;i <= n;i++){
        int v1 = inf,v2 = inf;
        if (arr[i - 1] > 1) v1 = arr[i - 1];
        if (arr[i + 1] > 1) v2 = arr[i + 1];
        chAdd(ans,Add(arr[i] - 1,Mul(Mul(s,sum),min(arr[i],v1) - 1)));
        chMul(s,min({v1,arr[i],v2}) - 1);
        if (!s) s = 1,sum = 0;
        else chAdd(sum,Mul(qmi(s,mod - 2),min(arr[i],v2) - 1));
    } printf("%lld",ans);
    return 0;
}

[题解]CF659G Fence Divercity

文章操作

思路

Code

相关推荐

评论

[题解]CF659G Fence Divercity