CF题解——Beautiful Sequence

算法竞赛相关
编程算法竞赛题解动态规划
本文最后更新于 9 个月前，文中所描述的信息可能已发生改变。

C. Beautiful Sequence 解题思路 ​

摘要与问题转化 ​

本题要求在一个仅包含数字 $ 1, 2, 3$ 的序列中，计算“完美子序列”的数量。一个完美子序列定义为形如 $ 1, 2, \dots, 2, 3$ 的序列，即以 $ 1$ 开头、以 $ 3$ 结尾，中间可以包含零个或多个 $ 2$。

由于序列的结构非常明确，我们不需要关注 22 的具体数量，只需要统计以 11 结尾的子序列数量、以 22 结尾的子序列数量以及以 33 结尾的（即完美）子序列数量。当遍历到当前的数字 xx 时，它可以通过衔接一个以 x−1x-1 结尾的子序列，从而形成新的以 xx 结尾的子序列。同时，如果 x=2x=2，它可以衔接任何一个已存在的以 22 结尾的子序列，从而生成新的以 22 结尾的子序列。

主体分析：动态规划策略 ​

1. 状态定义 ​

我们采用动态规划（Dynamic Programming, DP）来解决这个问题，其时间复杂度为 O(N)O(N)，可以满足 N≤2⋅105N \le 2 \cdot 10^5 的数据规模要求。

定义 dp[i]dp[i] 为：以数字 ii 结尾的合法子序列的数量。其中 i∈{1,2,3}i \in \{1, 2, 3\}。

  • dp[0]dp[0]：辅助状态，初始化为 11。它表示一个“空子序列”或“起始点”。当遇到 11 时，新的以 11 结尾的子序列数量可以从这个起始点计数 11 开始。

2. 状态转移方程 ​

我们遍历输入的序列，对于当前的数字 xx：

A. 特殊情况：数字 x=2x=2 的自我转移 ​

数字 22 具有特殊的性质，它可以接在任何一个已存在的以 22 结尾的子序列后面，形成一个新的以 22 结尾的子序列。

如果当前读入的数字 x=2x=2，则：

dp[2]←dp[2]+dp[2]dp[2] \leftarrow dp[2] + dp[2]

这个操作表示：对于已有的 dp[2]dp[2] 个以 22 结尾的子序列，新的 22 都可以接在它们后面，使得数量翻倍。由于 22 的自我衔接不依赖于 11 的转移，因此应先进行。

B. 核心递推：从 x−1x-1 转移到 xx

quot;">​

数字 xx 可以接在所有以 x−1x-1 结尾的子序列后面，形成新的以 xx 结尾的子序列。

dp[x]←dp[x]+dp[x−1]dp[x] \leftarrow dp[x] + dp[x-1]

  • 当 x=1x=1 时： dp[1]←dp[1]+dp[0]dp[1] \leftarrow dp[1] + dp[0]。所有以 11 结尾的子序列数量增加了 dp[0]=1dp[0]=1（新的 11 本身作为子序列）个。
  • 当 x=2x=2 时： dp[2]←dp[2]+dp[1]dp[2] \leftarrow dp[2] + dp[1]。以 22 结尾的子序列数量增加了所有以 11 结尾的子序列的数量。
  • 当 x=3x=3 时： dp[3]←dp[3]+dp[2]dp[3] \leftarrow dp[3] + dp[2]。以 33 结尾的完美子序列数量增加了所有以 22 结尾的子序列的数量。

3. 实现细节与模运算 ​

由于结果可能非常大，我们需要在每一步加法操作时对结果取模 MOD=998244353MOD = 998244353。

CPP 代码实现 ​

cpp
#include <bits/stdc++.h>

using namespace std;

// 定义模数
constexpr int MOD = 998244353;

// 安全的模加法函数
int add(int x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
    return x;
}

void solve() {

    int n;
    cin >> n;

    // dp[0]: 初始状态 (1)
    // dp[1]: 以 1 结尾的子序列数量
    // dp[2]: 以 2 结尾的子序列数量
    // dp[3]: 以 3 结尾的完美子序列数量 (最终结果)
    vector<int> dp(4, 0);
    dp[0] = 1; // 初始化起始计数

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

        // 步骤 A: 特殊转移 (仅当 x=2 时，实现 dp[2] = dp[2] * 2)
        if (x == 2) {
            dp[x] = add(dp[x], dp[x]);
        }

        // 步骤 B: 核心递推 (dp[x] += dp[x-1])
        // x=1 时: dp[1] += dp[0]
        // x=2 时: dp[2] += dp[1]
        // x=3 时: dp[3] += dp[2]
        dp[x] = add(dp[x], dp[x - 1]);
    }

    // dp[3] 即为完美子序列的总数
    cout << dp[3] << '\n';

}


int main() {

    // 优化 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

}
内网穿透简单教程
CF题解——Power of Points