Codeforces Round #531 (Div. 3) E. Monotonic Renumeration(思维+差分数组)
Codeforces Round #531 (Div. 3) E. Monotonic Renumeration(思维+差分数组)
Ch_Zaqdt
发布于 2019-01-11 13:14:54
发布于 2019-01-11 13:14:54
题目链接：http://codeforces.com/contest/1102/problem/E
题意是给了n个数的a数组，要构造b数组，b数组需要满足以下三个要求，b[1] = 0，如果a[i] = a[j]，那么b[i] = b[j](a中相等的数，在b中对应的位置的数也相等)，b[i] = b[i+1]或者b[i] + 1 = b[i+1]，求出可以构造出多少种b数组。
首先我们要知道假如a[1] = 15，a[20] = 15，因为b[1] = 0，所以b[20] = 0，又因为b数组是一个递增的数列，所以在b数组中从1到20就一定都是0，所以我们就只需要去找区间，因为b[i+1]要么等于b[i]要么等于b[i]+1，所以如果我们找到了一个区间的左端点与之前的所有区间都没有交集，那么此时的方案数是乘以2的，所以这道题就是找有多少个独立的区间，每一个独立的区间的方案数就是2。我的方法是用差分数组来实现区间覆盖，对于每一个数用map来做标记。
AC代码：
#include <bits/stdc++.h>
#define maxn 200005
#define ll long long
const int mod = 998244353;
using namespace std;
int n;
ll pre[maxn];
int main()
{
map<ll,int> ma;
scanf("%d",&n);
for(int i=1;i<=n;i++){
ll xx;
scanf("%lld",&xx);
if(ma[xx] == 0) ma[xx] = i;
else pre[ma[xx] + 1] ++, pre[i + 1] --;
}
ll ans = 1;
for(int i=2;i<=n;i++){
pre[i] += pre[i-1];
if(pre[i] == 0) ans = (ans * 2 + mod) % mod;
}
printf("%lld\n", ans);
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年01月10日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读