题解 CF466D

传送门

思维题。

首先可以设 \(a'_i=h-a_i\) 为每个数离 \(h\) 差的操作次数，而我们想通过若干次左右端点不重合的区间 \(-1\) 来使 \(a'_i=0\) 。考虑区间 \(-1\) 所带来的影响，设这段区间为 \([l,r]\) ，实质上为将差分数组 \(d\) 中的 \(d_l\) 减一，\(d_{r+1}\) 加一。而最终所有元素值相等则等价于将差分数组转为全 \(0\) ，故下面只考虑差分数组上的操作。

再看左右端点不重合的条件，这说明了一个值和原来相比，只有 \(+1,-1\) 或不变三种。所以如果差分数组中某个值的绝对值大于 \(1\) ，显然无解。最后做区间端点匹配即可，具体地：

  • 差分值为 \(1\) 则放进左端点中
  • 为 \(0\) 可以不操作，或者同时为左右端点
  • 为 \(-1\) 则是右端点，与前面有的任意左端点匹配。

时间复杂度： \(O(n)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+5,mod=1e9+7;
int n,h,a[N],d[N],num;
ll ans=1;
int main(){
    n=read(),h=read();
    rep(i,1,n)a[i]=h-read();
    rep(i,1,n+1){
        d[i]=a[i]-a[i-1];
        if(abs(d[i])>1)return puts("0"),0;
    }
    rep(i,1,n+1){
        if(d[i]==1)++num;
        if(d[i]==0){
            ans=ans*(num+1)%mod;
        }
        if(d[i]==-1){
            ans=ans*num%mod;--num;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Comments