题解：AT_abc017_4 [ABC017D] サプリメント

· · 题解

AT_abc017_4 [ABC017D] サプリメント 题解

题目大意

给定长度为 n\,(1\le n\le 10^5) 的数组，要从位置 1 跳若干次到位置 n + 1。每次至少跳一格，而且每次跳的区间（包含起终点）不能有重复数字。求方案数。（请理解此段，否则后面可能比较难懂）

思路

这种只往一个方向跳，求方案数的题 90\% 都是 dp。 令 endd_i 为区间 [i,j] 满足没有重复数字的 j 的最大值，dp_i 为从 i 跳到 n + 1 的方案数。

则：

dp[i] = \sum_{j = i + 1}^{endd_i+1}dp_j

这个东西使用前缀和很好维护，那么我们的问题就是如何求 endd_i。

欸，我会，线段树！

我们其实可以直接用双指针 O(n) 维护，具体地，我么先预处理表示 a_i 上一次出现的下标 lastt_i，然后开始双指针：

  1. 将 r 往后移
  2. 当当前的 lastt_r\ge l 时， 将 endd_l 到 endd_{lastt_r} 都赋值为 r - 1，将 l 赋值为 lastt_r + 1

Code

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 100010, modd = 1e9 + 7; // 不要忘记取模！

int n, m, a[maxn];
int dp[maxn], endd[maxn];
int las[maxn], lastt[maxn]; // las[i] 表示 i 上次出现的位置，laastt[i] 表示 a[i] 上次出现的位置
int l, r; // 双指针
int sum[maxn]; // 前缀和

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], lastt[i] = las[a[i]], las[a[i]] = i; // 求 lastt
    l = r = 1;
    while (1) {
        r++;
        if (lastt[t] >= l) { // 如果当前有重复
            while (1) {
                endd[l] = r - 1;
                l++;
                if (l == lastt[r] + 1) break;
            }
        }
        if (r == n) break;
    }
    while (1) {
        endd[l++] = n;
        if (l == n + 1) break;
    } // 别忘了把后面无重复的设为 n
    dp[n] = 1;
    dp[n + 1] = 1;
    sum[n + 1] = 1;
    sum[n + 2] = 0;
    sum[n] = dp[n] + 1;
    for (int i = n - 1; i > 0; i--) {
        dp[i] = (sum[i + 1] - sum[endd[i] + 2]) % modd;
        sum[i] = (sum[i + 1] + dp[i]) % modd;
    } // dp 转移
    cout << (dp[1] + modd) % modd << '\n';

    return 0;
}