ZigZagK的博客
[思维]Codeforces1442B【Identify the Operations】题解
2020年11月3日 20:35
查看标签

题目概述

CF1442B

解题报告

定义一个新数组 $A_i$ 表示 $b_i$ 在 $\{a_n\}$ 中的下标,然后将 $\{a_n\}$ 递增排序,问题转化为在 $\{a_n\}$ 中选出 $A$ 数组。显然这两个问题等价。

经过观察,我们可以发现一个性质:在处理 $A_i$ 时(前面已经处理好了并且可行),如果 $A_i>1$ ,则 $1\sim A_i-1$ 中必定存在一个元素没有被删去,如果 $A_i<n$ ,则 $A_i+1\sim n$ 中必定存在一个元素没有被删去。

如果 $A_i>1$ 时,$1\sim A_i-1$ 中的元素全被删去了,说明 $1\sim A_i-1$ 的位置全部在 $A_i$ 之前被添加到了 $A$ 中,但是如果不删掉 $A_i$ 或者提前处理 $A_i$ ,这是不可能做到的,因此必定无解。$A_i+1\sim n$ 同理。

也就是说处理到 $A_i$ 的时候,左右两边一定有相邻的元素存在,除非 $A_i=1$ 或 $A_i=n$ 。

但是需要注意,如果处理 $A_i$ 的时候 $A_i-1$ 或者 $A_i+1$ 还没被处理,那么就不能取左边或者右边。

所以对于每个 $A_i$ 求出可取相邻元素的个数乘起来就是方案数。

示例程序

#include<cstdio>
using namespace std;
const int maxn=200000,MOD=998244353;

int te,n,m,ID[maxn+5],a[maxn+5],vis[maxn+5],ans;

int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&m);ans=1;
        for (int i=1,x;i<=n;i++) scanf("%d",&x),ID[x]=i,vis[i]=false;
        for (int i=1;i<=m;i++) scanf("%d",&a[i]),a[i]=ID[a[i]],vis[a[i]]=true;
        for (int i=1;i<=m;i++){
            int now=0;
            if (a[i]>1 && !vis[a[i]-1]) now++;
            if (a[i]<n && !vis[a[i]+1]) now++;
            ans=ans*now%MOD;vis[a[i]]=false;
        }
        printf("%d\n",ans);
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!