专栏文章

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

pporse
AT_abc017_4题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqrc3v5
此快照首次捕获于
2025/12/04 09:28
3 个月前
此快照最后确认于
2025/12/04 09:28
3 个月前
查看原文

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

题目大意

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

思路

这种只往一个方向跳，求方案数的题 90%90\% 都是 dp。 令 enddiendd_i 为区间 [i,j][i,j] 满足没有重复数字的 jj 的最大值，dpidp_i 为从 ii 跳到 n+1n + 1 的方案数。
则：
dp[i]=∑j=i+1enddi+1dpjdp[i] = \sum_{j = i + 1}^{endd_i+1}dp_j
这个东西使用前缀和很好维护，那么我们的问题就是如何求 enddiendd_i。
欸，我会，线段树！
我们其实可以直接用双指针 O(n)O(n) 维护，具体地，我么先预处理表示 aia_i 上一次出现的下标 lasttilastt_i，然后开始双指针：
  1. 将 rr 往后移
  2. 当当前的 lasttr≥llastt_r\ge l 时， 将 enddlendd_l 到 enddlasttrendd_{lastt_r} 都赋值为 r−1r - 1，将 ll 赋值为 lasttr+1lastt_r + 1

Code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...