题解：CF2069C Beautiful Sequence

题意

定义一个“美丽”的序列为：除第

1

个数，每个数左边都有至少

1

个比它小，除最后一个数，每个数右边都有至少

1

个比它大。给定一个只由

\{1,2,3\}

组成的数组，求有多少个“美丽”的子序列。

题解

我们看到只会有

\{1,2,3\}

出现，想到从这里入手。因为在数组里不会有比

1

更小的数，所以

1

只会是子序列的左端点。同理可得

3

只会是子序列的右端点。而它们俩中间夹的

2

会和它们组成一个合法子序列。如果一对

1

和

3

中间夹了

k

个

2

，那么合法的子串数量就是

2^k - 1

。现在我们就有

O(n^2)

做法：循环每个

1

，对于每个

1

循环找到它后面的每个

3

并统计

1

和这个

3

之间夹了多少个

2

，然后统计答案。

我们还得想如何把它变成

O(n)

或者

O(n \log n)

的做法。我们掏一个样例：1 2 3 2 1 3 2 2 3。对于每个

1

，我们把它对于答案的贡献写出来。

\begin{aligned} \text{第一个 1} \quad & 2^1 + 2^2 + 2^4 - 3 \\ \text{第二个 1} \quad & 2^0 + 2^2 - 2 \\ \end{aligned}

现在我们需要人类智慧。我们发现后面减的数就是这个

1

后面

3

的个数。再把后面减掉的数先扔掉，发现就是一堆

2^k

相加。结合样例分析：每个

3

会使贡献的项数增加

1

，每个

2

会使贡献乘

2

。那么我们从后往前循环，记录

cnt

表示出现了多少个

3

，

now

表示现在如果出现一个

1

需要计算答案，它贡献的

2^k

部分是多少。那么我们按照如下过程模拟：

遇到 $3$ 就 $cnt \leftarrow cnt + 1，now \leftarrow now + 2^0$ 。
遇到 $1$ 就把答案增加 $now - cnt$ 。
遇到 $2$ 就 $now \leftarrow now \times 2$ 。

这样我们就成功的搞出了一个

O(n)

的人类智慧解法。

代码

CPP

#include<bits/extc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n;
void solve()
{
    cin >> n;
    vector<int>a(n + 5);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int cnt = 0,ans = 0,now = 0;
    for (int i = n; i >= 1; i--)
    {//从后往前循环，模拟即可
        if (a[i] == 3)
        {
            cnt++;
            now++;
        }
        else if (a[i] == 1)
            ans = (ans + now - cnt + mod) % mod;
        else
            now = (now << 1) % mod;
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

题解：CF2069C Beautiful Sequence

文章操作

题意

题解

代码

相关推荐

评论

题解：CF2069C Beautiful Sequence