模拟
2026-11-08 11:18:51
发布于:湖北
64阅读
0回复
0点赞
parent[i] = last[a[i]] + 1;
它的意思是:
找到当前位置的点数最后出现的位置,然后指向它后面的一个位置。
例如:
- 第 1 个位置,点数是 1,last[1]=3,所以 parent[1]=4。
- 第 2 个位置,点数是 2,last[2]=2,所以 parent[2]=3。
- 第 3 个位置,点数是 1,last[1]=3,所以 parent[3]=4。
- 第 4 个位置,点数是 3,last[3]=4,所以 parent[4]=5。



#include <iostream>
using namespace std;
const int N = 500005;
const int M = 300005;
int n, m;
int a[N];
// last[i]:点数 i 最后一次出现的位置
int last[M];
// parent[i]:位置 i 指向的位置
int parent[N];
// sz[i]:以位置 i 为根的子树大小
int sz[N];
// ans[i]:最终留下点数 i 的游戏数量
int ans[M];
int main() {
cin >> n >> m;
// 读入牌的点数,并记录每种点数最后出现的位置
for (int i = 1; i <= n; i++) {
cin >> a[i];
last[a[i]] = i;
}
// 建立每个位置的指向关系
for (int i = 1; i <= n; i++) {
parent[i] = last[a[i]] + 1;
sz[i] = 1;
}
// 从小到大计算子树大小
for (int i = 1; i <= n; i++) {
sz[parent[i]] += sz[i];
}
// 统计每种点数的答案
for (int i = 1; i <= n; i++) {
ans[a[i]] += sz[i];
}
// 输出答案
for (int i = 1; i <= m; i++) {
cout << ans[i] << " ";
}
return 0;
}
这里空空如也



有帮助,赞一个