对于这道题,可以想想对于每个b[i],a[i]中可选的位置的区间在哪,这样只要找到区间,就能知道当前可以选那几个位置断开
b[1]的开头肯定是1号位,而我们发现如果对后缀求一下后缀的最小值,这样就天然满足题目条件,我们用一个map存一下答案,就能知道b[i]是最小值的区间是哪些
因为b是单调递增的数学因此可以从头枚举b[i]所在位置,用乘法原理进行计算。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; const int mod=998244353; int a[N]; int b[N]; int suffix[N]; map<int,int> cnt; int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; int i; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=m;i++) cin>>b[i]; suffix[n+1]=0x3f3f3f3f; for(i=n;i>=1;i--){ suffix[i]=min(suffix[i+1],a[i]); cnt[suffix[i]]++; } ll ans=1; if(suffix[1]!=b[1]){ cout<<0<<endl; } else{ for(i=2;i<=m;i++){ ans=ans*cnt[b[i]]%mod; } cout<<ans<<endl; } return 0; }
View Code
原文链接: https://www.cnblogs.com/ctyakwf/p/13358133.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/369230
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!