LOADING

加载过慢请开启缓存 浏览器默认开启

codeforces804C

赛后补的题

题目描述:

给定一个长度为n的数组a,其中每个a[i]的范围在0~n-1 且每个数仅出现一次 ,其中b数组满足对a和b数组任意的任意区间1<=l<=r<=n,其中mex{a[l],a[l+1]…a[r]}==mex{b[l],b[l+1]…b[r]},mex是求该区间内未出现的最小非负整数,如mex{1,2,3}=0,mex{0,1,2,3}=4,输出满足的b数组的个数

题解:

我们可以用p来存每个数字在a数组里的位置,初始l=r=p[0],

然后遍历i从0~n-1,每次查看p[i]的位置是否在区间l到r内,

如果不在l到r内,更行区间,且说明这个位置的数放上去后是区间的边界,mex值在区间改变后也会发生改变,改位置就是固定的,ans不做处理

如果在l到r内,因为i之前的数组的位置都已经找过了,而l和r的位置也存的是i之前的数,那么在这个区间内,除了已经找过的数,其他任意位置是可以随意放的,这时候的任意位置个数就是r-l+1-i,(注意这里的i意思是已经确定了i个数,如果减去,就意味着还有这么些个位置没有放),所以ans*=(这些位置个数)

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=100050;
const ll MOD=1e9+7;
ll a[N];
map<ll,ll>p;
void solve()
{
    int n;cin>>n;
    p.clear();
    rep(i,1,n){
        cin>>a[i];
        p[a[i]]=i;   //记录每个数在数组a的位置
    }
    ll l=p[0],r=p[0],ans=1;   //初始化区间和答案
    rep(i,1,n-1){
        if(p[i]>l&&p[i]<r){
             ans*=1LL*(r-l+1-i);  //ans*(区间内未出现过数的位置)
             ans%=MOD;
        }
        l=min(l,p[i]);
        r=max(r,p[i]);
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    while(n--)solve();
    return 0;
}