题解
2026-11-08 18:17:32
发布于:新疆
16阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
/*
* [CSP-J 2026] 纸牌游戏 (card)
*
* 核心:
* 1) last[k] = 点数 k 最后出现的位置;
* 2) 第 i 局等价于「保留 a[i],跳到 last[a[i]] + 1 继续」(因为
* 打出最后一次出现的 a[i] 会把桌面清成只剩 a[i]);
* 3) cnt[p] 表示有多少局会经停在位置 p,cnt[i] 初值 1(自己起局);
* 4) cnt[ last[a[i]]+1 ] += cnt[i],即把局数传递给跳转目标;
* 5) 答案 ans[a[i]] += cnt[i]。
* 复杂度 O(n+m)。
*/
const int MAXN = 500005;
int n, m;
int a[MAXN];
int lst[MAXN]; // 点数 -> 最后出现位置(下标 1..m)
long long cnt[MAXN]; // 位置 -> 经过该位置的局数
long long ans[MAXN]; // 答案
int main() {
freopen("card.in", "r", stdin);
freopen("card.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
lst[a[i]] = i; // 最终记录为最后出现位置
}
// cnt[i] 初值 1:位置 i 本身作为某局起点必然经过自己
for (int i = 1; i <= n; ++i) cnt[i] = 1;
// 正序传递:父亲位置 last[a[i]]+1 一定大于 i
for (int i = 1; i <= n; ++i) {
int nxt = lst[a[i]] + 1;
if (nxt <= n) cnt[nxt] += cnt[i];
ans[a[i]] += cnt[i]; // 位置 i 对应的点数 a[i] 获得这 cnt[i] 局
}
for (int i = 1; i <= m; ++i) cout << ans[i] << ' ';
cout << '\n';
return 0;
}
这里空空如也







有帮助,赞一个