【CF1443F】Identify the Operations 题解

Qing-LKY 2020-11-05 原文

模拟简单计数桶

原题链接

题意简介

建议去原题看。这题意我表达不清楚。

大概就是给你一个 n 的排列，现在要求你进行 m 次操作。

每次操作，你会在现有的排列中删去一个数，然后选择其左边或右边的一个与之相邻的数加入 b 数组中。

然后将变成两截的数组重新连在一起，更新下标。

现在问有多少种操作方案，可以使 b 数组中恰好按顺序排列着它给定的那几个数字。

只要两个方案中任一轮删数的下标不同，就视为不同的方案。

思路分析

这道题显然是道水题。不明白为什么扔在 F。~~或许出题人是用脚编排题目~~。

其实这道题是同场 div1 的 B 题，之前写的 CF1443 D 则是 div1 的 A 题。

感觉E题更难一点。

由数字不会重复这一点上看，想要加入一个数字，就需要删去其中一个与之相邻的数字。

如果某个数字两端都是需要在其之后加入的数字，那么显然无解。

另外，在删数过后，后面的数字的下标会往前推一格。判断方案不同的依据就是被删除的下标的顺序。

如果某个数字原本另一边就有一个需要保留的数字，那么前面的所有操作都不可能改变这一点。

而如果数字的两边都可以删除，那么前面的操作依然不可能改变这一点。

每次操作实质上改变的有且只有下标和加入顺序都在它之后的数字的操作对应的 ti 。

在保证不会删掉还没加入 b 的需要的数字的前提下，记每个需要的数字可以删去的与之相邻的数的个数 c 。

不难发现答案应该是： \(\prod_{i=1}^m c_i\)

代码库

说起来这是我第一次在 memset 上吃瘪。

里头有一组数据 t=1e5 里头全是 n=2 m=1

然后我就 TLE 了。

这个故事告诉我们 t 比较大时 memset 不要乱用。

或者试一下 memset(p,0,(n+1)*sizeof(int)) 。

#include <cstdio>
#include <cstring>
typedef long long ll;
#define REG register
#define rep(i,a,b) for(REG int i=a;i<=b;i++)
const ll N=2e5+5,mod=998244353;
int n,m,A[N],B[N],p[N]; ll ans; bool vis[N]; 
int main(){
    REG int t; scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        //memset(p,0,sizeof(p));
        //memset(vis,0,sizeof(vis));
        rep(i,1,n) p[i]=vis[i]=0;
        rep(i,1,n) scanf("%d",A+i),p[A[i]]=i;
        rep(i,1,m) scanf("%d",B+i),vis[B[i]]=1;
        ans=1;
        rep(i,1,m){
            REG int pos=p[B[i]],c=0;
            if(pos-1>=1&&!vis[A[pos-1]]) c++;
            if(pos+1<=n&&!vis[A[pos+1]]) c++;
            ans=ans*c%mod; vis[B[i]]=0;
        }
        printf("%lld\n",ans);
    }
    return 0;
}