Educational Codeforces Round 89 (Rated for Div. 2)E

题：https://codeforces.com/contest/1366/problem/E

题意：划分a数组为m组，让每一组的最小值刚好为b数组，求划分方案数

分析1：关键是b数组是严格递增的！我们先看最小值，因为b递增，所以我们假想在a中找b数组的值的基准一定是每个bi 在a数组中最后出现的值，如果不这样就肯定没有合法方案。

　　　对于一个位置的最小值，它周围数要满足如下图：

　　　红色的位置就是bi数组的某一个值，那么我们对a数组的基准值做这样的构图，如果这些图案能够覆盖a数组，那么就有合法方案。

　　　接着方案的计数就是对于相邻基准值范围的交集部分的乘积，ans=∏C¹_{（交集长度）}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int M=2e5+5;
const int mod=998244353;
int a[M],b[M];
map<int,ll >pos;
ll l[M],r[M];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&b[i]);
    int top=0;
    for(int i=1;i<=n;i++){
        l[i]=i;
        while(l[i]-1>=1&&a[l[i]-1]>=a[i]){
            l[i]=l[l[i]-1];
        }
    }
    for (int i=n;i>=1;i--){
        r[i]=i;
        while(r[i]+1<=n&&a[r[i]+1]>=a[i]){
            r[i]=r[r[i]+1];
        }
    }
    for(int i=n;i>=1;i--){
        if(pos[a[i]]==0)
            pos[a[i]]=i;
    }

    int nowl=1;
    int tot=0;
    ///判断能否覆盖
    pos[b[m+1]]=n+1;
    for(int i=1;i<=m;i++){
        if(l[pos[b[i]]]<=nowl)
            nowl=min(1ll*n,min(1ll*pos[b[i+1]],r[pos[b[i]]]));
        else
            break;
    }
    if(nowl!=n)
        return printf("0"),0;

    int ans=1;
    ///让r[]代表的位置定位在每个梯度之间，l[]已经满足,所以不用操作
    ///r[pos[b[1]]]=min(r[pos[b[1]]],pos[b[2]]-1);
    for(int i=1;i<=m;i++){
        r[pos[b[i]]]=min(r[pos[b[i]]],pos[b[i+1]]-1);
    }

    for(int i=2;i<=m;i++){
        int R=r[pos[b[i-1]]],L=l[pos[b[i]]];
        ///cout<<L<<"!!"<<R<<endl;
        if(L!=pos[b[i-1]])
            L--;
        ans=(1ll*ans*(R-L+1))%mod;

    }
    printf("%d",ans);
    return 0;
}
/*
6 3
12 10 20 20 25 30
10 20 30
*/

View Code

分析2：还有一种方法是预处理后缀最小值，若有合法情况的前提为suf[1]==b[1]，反之直接输出0；

　　　　若存在前提条件，则我们可以计算b在a数组中出现的次数，这个出现次数就是交集长度，因为他们出现位置肯定是连续的。

　　　　若出现b在a中未出现也是可以的，因为我们是直接乘，所以会直接乘0，保证了答案合法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int M=2e5+5;
const int mod=998244353;
int a[M],b[M];
map<int,ll >pos;
int suf[M];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&b[i]);
    suf[n]=a[n];
    for(int i=n-1;i>=1;i--){
        suf[i]=min(a[i],suf[i+1]);
    }
    if(suf[1]!=b[1])
        return printf("0"),0;
    for(int i=1;i<=n;i++)
        pos[suf[i]]++;
    ll ans=1;
    for(int i=2;i<=m;i++)
        ans=(ans*pos[b[i]])%mod;
    printf("%d",ans);
    return 0;
}

View Code