锐客网

  1. 首页 > it技术 > >

Codeforces|【Codeforces Round #531 (Div. 3) E. Monotonic Renumeration】思维题

codeforces思维题

E. Monotonic Renumeration 题意
给你一个数组a，构造一个数组b,构造规则是:
b 1 = 0 b_1=0 b1?=0
对 于 每 一 对 1 < = i , j < = n , 如 果 a i = a j , 那 么 b i = b j 对于每一对1< =i,j< =n,如果a_i=a_j,那么b_i=b_j 对于每一对1<=i,j<=n,如果ai?=aj?,那么bi?=bj?
对 于 每 一 个 i ∈ [ 1 , n ? 1 ] , b i = b i + 1 或 者 b i + 1 = b i + 1 对于每一个i\in \left[ 1,n-1 \right] ,b_i=b_{i+1}或者b_i+1=b_{i+1} 对于每一个i∈[1,n?1],bi?=bi+1?或者bi?+1=bi+1?
做法
【Codeforces|【Codeforces Round #531 (Div. 3) E. Monotonic Renumeration】思维题】很显然如果两个数相等，那么他们中间这一段肯定都相等。
所以对于每个数我们可以得到一段线段，左端点是这个数第一次出现的地方，
右端点是这个数最后一次出现的地方，问题就转化为经典的线段覆盖问题，求一下最后有多少个不连续的段，答案就是 2 n u m ? 1 2^{num-1} 2num?1
由于这道题左端点一定是按照访问顺序的，所以我们可以动态的维护一个到上一段位置的最右端点下标right，如果right>=i我们更新right,否则说明出现不连续的段，答案*2之后再更新right.
代码

#include #include #include #include using namespace std; typedef long long ll; const int maxn = 2e5+5; const int Mod=998244353; map mp; int a[maxn]; int main() { int n; scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); for(int i=1; i<=n; i++) mp[a[i]]=i; int right=1; ll ans=1; for(int i=1; i<=n; i++) { if(right>=i) right=max(right,mp[a[i]]); else { ans=ans*2LL%Mod; right=max(right,mp[a[i]]); } } printf("%lld\n",ans); return 0; }

    推荐阅读


    上一篇：牛客|牛客练习赛3

    下一篇：Banner轮播图的使用方法