补题Codeforces 1102E. Monotonic Renumeration

这个题还是不太懂，下面附上的是大佬的题解(https://zhanghuimeng.github.io/post/codeforces-1102e-monotonic-renumeration/)

E. Monotonic Renumeration

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

You are given an array a consisting of n integers. Let’s denote monotonic renumeration of array a as an array b consisting of n integers such that all of the following conditions are met:

b1=0;

for every pair of indices i and j such that 1≤i,j≤n, if ai=aj, then bi=bj (note that if ai≠aj, it is still possible that bi=bj);

for every index i∈[1,n−1] either bi=bi+1 or bi+1=bi+1.

For example, if a=[1,2,1,2,3], then two possible monotonic renumerations of a are b=[0,0,0,0,0] and b=[0,0,0,0,1].

Your task is to calculate the number of different monotonic renumerations of a. The answer may be large, so print it modulo 998244353.

Input

The first line contains one integer n (2≤n≤2⋅105) — the number of elements in a.

The second line contains n integers a1,a2,…,an (1≤ai≤109).

Output

Print one integer — the number of different monotonic renumerations of a, taken modulo 998244353.

Examples

inputCopy

5

1 2 1 2 3

outputCopy

2

inputCopy

2

100 1

outputCopy

2

inputCopy

4

1 3 3 7

outputCopy

4

题意

给定一个长度为n的数组a，要求为a生成一个对应的数组b，满足：

b[0] = 0

对于任意0 <= i < j <= n，如果满足a[i] == a[j]，必有b[i] == b[j]（不过a[i] != a[j]时也可能有b[i] == b[j]）

任取0 <= i < n - 1，必有b[i] = b[i+1]或b[i] + 1 = b[i+1]

问共有多少种可能的b。

分析

显然b[i]是一个递增序列，因此可以自然推出，若a[i] == a[j]，则必有b[i] == b[i+1] == … = b[j]，也就是说，对于a中任意位置两个相等的元素，它们在b中对应的是一整段相等的元素。显然这种元素相等是可能会发生重叠的，因此一个自然的想法就是，把重复的元素建模成线段，然后合并发生overlap的线段以得到相等元素的最长长度。

我的做法是，从后向前遍历a，如果发现当前元素和后面的元素重复了，则取index最靠后的元素，组成一条线段，插入到栈中与其他元素合并；否则把它自己的index作为一条线段插入到栈中。最后栈中留下的就是几条互不相交（且并组成了整个区间）的线段。

对于（除了第一条之外）每条线段，我们可以选择让它的值和前一条相等，也可以选择让它的值是前一条+1。每种选择都会导致生成一种新的b。于是结果是2^{线段数-1}。

例子：对于a = {1, 2, 1, 2, 3}，1对应的线段是[0, 2]，2对应的线段是[1, 3]，3对应的线段是[4, 4]；合并之后得到两条线段，[0, 3]和[1, 4]；只有两种b，分别是{0, 0, 0, 0, 0}和{0, 0, 0, 0, 1}。

#include <iostream>

#include <vector>

#include <map>

using namespace std;

int a[200005];

int n;

typedef long long int LL;

const LL P = 998244353;

LL pow2(LL x) {

    LL pow = 2, ans = 1;

    while (x > 0) {

        if (x & 1)

            ans = (ans * pow) % P;

        pow = (pow * pow) % P;

        x >>= 1;

    }

    return ans;

}

int main() {

    map<int, int> indMap;

    vector<pair<int, int>> s;

    cin >> n;

    for (int i = 0; i < n; i++) {

        cin >> a[i];

        if (indMap.find(a[i]) == indMap.end()) {

            indMap[a[i]] = i;

        }

    }

    for (int i = n - 1; i >= 0; i--) {

        pair<int, int> interval;

        if (indMap.find(a[i]) != indMap.end() && indMap[a[i]] < i) {

            interval = make_pair(indMap[a[i]], i);

        }

        else {

            interval = make_pair(i, i);

        }

        if (!s.empty() && s.back().first <= interval.first && s.back().second >= interval.second)

            continue;

        if (!s.empty() && interval.second >= s.back().first) {

            interval.second = s.back().second;

            s.pop_back();

            s.push_back(interval);

        }

        if (s.empty() || interval.second < s.back().first)

            s.push_back(interval);

    }

    int cnt = 0;

    if (!s.empty() && s.front().second < n - 1) cnt++;

    if (!s.empty() && s.back().first > 0) cnt++;

    for (int i = 0; i < s.size(); i++) {

        cnt++;

        // 本条线段和前一条线段之间的间隔

        if (i > 0 && s[i - 1].second < s[i].first - 1)

            cnt++;

    }

    cout << pow2(cnt - 1) << endl;

    return 0;

}

巴特西

补题Codeforces 1102E. Monotonic Renumeration

最新文章

热门文章