A175519.[CSP-J 2026] 纸牌游戏(文件读写)
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:1024MB
题目描述
题目描述
小 Z 正在玩一种单人纸牌游戏。
他有一叠特制的纸牌,共有 n 张,从上到下的点数依次为 a1,a2,…,an。每张牌的点数都是 1 到 m 之间的整数,且每种点数都出现至少一次。
小 Z 将进行 n 局相互独立的游戏。每局开始前,他会将所有牌按原顺序放回牌堆,并清空桌面。在第 i(1≤i≤n)局中,他跳过前 i−1 张牌,依次打出第 i 张到第 n 张牌,这些牌的点数依次为 ai,ai+1,…,an。
桌面上的牌始终从左到右排成一行。打出一张点数为 k 的牌时:
- 若桌面上没有点数为 k 的牌,就将这张牌放在最右端;
- 否则,收走桌面上点数为 k 的牌及其右侧的所有牌,再把这张牌放在最右端。被收走的牌在本局中不再使用。
由上述规则可知,任意时刻桌面上同一种点数的牌至多只有一张。
最后一张牌打出后,本局游戏结束。
例如,若桌面上从左到右的牌的点数依次为 1,4,2,则打出一张点数为 3 的牌后,桌面上从左到右的牌的点数依次为 1,4,2,3。接着打出一张点数为 4 的牌时,桌面上原来点数为 4 的牌及其右侧的所有牌(点数依次为 4,2,3)被收走,再把新打出的 4 放在最右端,此时桌面上从左到右的牌的点数依次为 1,4。
你需要帮助小 Z 依次求出,对于每个 i=1,2,…,m,在所有 n 局游戏中,有多少局结束时桌面上留有点数为 i 的牌。
输入格式
从文件 card.in 中读入数据。
输入的第一行包含两个正整数 n,m,分别表示牌的数量和点数种类数。
输入的第二行包含 n 个正整数 a1,a2,…,an,依次表示小 Z 的牌从上到下的点数。
输出格式
输出到文件 card.out 中。
输出一行 m 个非负整数,其中第 i(1≤i≤m)个整数表示在所有 n 局游戏中,有多少局结束时桌面上留有点数为 i 的牌。
输入输出样例
输入#1
4 3 1 2 1 3
输出#1
3 1 4
输入#2
10 3 3 1 2 1 3 2 3 1 2 1
输出#2
10 3 3
说明/提示
说明/提示
样例 1 解释
对于第 1 局游戏,小 Z 依次打出点数为 1,2,1,3 的牌:
- 打出第 1 张牌(点数为 1)后,桌面上只有一张点数为 1 的牌;
- 打出第 2 张牌(点数为 2)后,桌面上从左到右的牌的点数依次为 1,2;
- 打出第 3 张牌(点数为 1)后,先收走桌面上点数为 1,2 的两张牌,再放上新打出的 1,桌面上只有一张点数为 1 的牌;
- 打出第 4 张牌(点数为 3)后,桌面上从左到右的牌的点数依次为 1,3。
因此第 1 局游戏结束时,桌面上从左到右的牌的点数依次为 1,3。
对于第 2 局游戏,小 Z 依次打出点数为 2,1,3 的牌,结束时桌面上从左到右的牌的点数依次为 2,1,3。
对于第 3 局游戏,小 Z 依次打出点数为 1,3 的牌,结束时桌面上从左到右的牌的点数依次为 1,3。
对于第 4 局游戏,小 Z 仅打出一张点数为 3 的牌,结束时桌面上只有一张点数为 3 的牌。
因此,在全部 4 局游戏中:
- 有 3 局游戏结束时,桌面上留有点数为 1 的牌,即第 1,2,3 局;
- 有 1 局游戏结束时,桌面上留有点数为 2 的牌,即第 2 局;
- 有 4 局游戏结束时,桌面上留有点数为 3 的牌,即全部 4 局。
样例 3
见题目目录下的 card/3.in 与 card/3.ans。
该样例满足测试点 4∼6 的约束条件。
样例 4
见题目目录下的 card/4.in 与 card/4.ans。
该样例满足测试点 7∼9 的约束条件。
样例 5
见题目目录下的 card/5.in 与 card/5.ans。
该样例满足测试点 15∼17 的约束条件。
样例 6
见题目目录下的 card/6.in 与 card/6.ans。
该样例满足测试点 21,22 的约束条件。
数据范围
对于所有测试数据,均有:
- 2≤n≤5×105,1≤m≤3×105;
- 对于所有 i(1≤i≤n),均有 1≤ai≤m;
- 每种点数都出现至少一次,即对于所有 i(1≤i≤m),均存在 j(1≤j≤n)满足 aj=i。
| 测试点编号 | n≤ | m≤ | 特殊性质 |
|---|---|---|---|
| 1∼3 | 5 | 2 | 无 |
| 4∼6 | 500 | 200 | 无 |
| 7∼9 | 5000 | 3000 | A |
| 10∼12 | 5000 | 3000 | 无 |
| 13,14 | 2×105 | 2 | 无 |
| 15∼17 | 2×105 | 3000 | B |
| 18,19 | 2×105 | 3000 | 无 |
| 20 | 2×105 | 105 | A |
| 21,22 | 2×105 | 105 | 无 |
| 23∼25 | 5×105 | 3×105 | 无 |
特殊性质 A:a1≤a2≤⋯≤an。
特殊性质 B:至多存在 4999 个 i(1≤i≤n−1)满足 ai=ai+1。
附件下载:card.zip
输入解题思路,AI测评打分。不知道怎么写?