-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathP5594.cpp
154 lines (110 loc) · 4.34 KB
/
P5594.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
int N, M, K; // N个人,M天能打比赛,总共有K天
scanf("%d %d %d", &N, &M, &K);
// 这里比赛天数和模拟题都从1开始编号
int matches[K + 1][K + 1]; // 至多有K天的比赛,每天可能至多有K套模拟题
memset(matches, 0, sizeof(matches));
// 读入N个人的数据
for (int i = 0; i < N; i++)
{
for (int no = 1; no <= M; no++)
{
int day;
scanf("%d", &day); // 第i位参赛者在第day天做第no套模拟题
if (!matches[day][no]) // 第day天还没有人做第no套模拟题,需要多准备一套
matches[day][0]++; // 0号下标元素用来储存第day天要用多少套模拟题
matches[day][no]++;
}
}
// 输出从第1天道第K天需要准备的模拟题套数
for (int i = 1; i <= K; i++)
{
if (i != 1)
printf(" "); // 不输出多余空格
printf("%d", matches[i][0]);
}
return 0;
}
/*
本题的重点在于统计【每天】需要用到【多少套不同的模拟题】。
一共有N位参赛者,第n位参赛者在第day天会做第no套模拟题(no=1,2,3,...,K)
很容易能发现,咱们可以用一个二维数组matches来记录:
* 【某天】的【某套模拟题】是否有人使用
* 【某天】共有【多少套不同的模拟题】
这个题解中,我将【某天】作为二维数组matches的第一维下标,而将【某套模拟题】作为二维数组的第二维下标。
* 其中【某天】和【某套模拟题】都是从1开始编号的
二维数组第二维的【0号下标元素】全部用来统计【某天】共有【多少套不同的模拟题】。
迭代过程中,只要【某一套模拟题是首次有人做】(matches[day][no]==0),那么就将这一天的【模拟题用量】加一(matches[day][0]++)。
- SomeBottle 2023.2.21
*/
/*
# 【XR-4】模拟赛
## 题目描述
X 校正在进行 CSP 前的校内集训。
一共有 $n$ 名 OIer 参与这次集训,教练为他们精心准备了 $m$ 套模拟赛题。
然而,每名 OIer 都有各自的时间安排,巧合的是,他们在接下来的 $k$ 天中都恰好有 $m$ 天有空打模拟赛。
为了方便管理,教练规定一个人必须按顺序打完 $m$ 套模拟赛题。
比如,小 X 在接下来的第 $2,3,5$ 天有空打模拟赛,那么他就必须在第 $2$ 天打第 $1$ 套模拟赛题,第 $3$ 天打第 $2$ 套模拟赛题,第 $5$ 天打第 $3$ 套模拟赛题。
教练需要为每一个人的每一次模拟赛做准备,为了减小工作量,如果在某一天有多个人打同一套模拟赛题,那么教练只需要在这一天准备一场使用这一套题的模拟赛即可。
你作为机房大佬,教练想请你帮他计算一下,他每天需要准备多少场模拟赛。
## 输入格式
第一行三个整数 $n,m,k$。
接下来 $n$ 行,每行 $m$ 个整数,第 $i$ 行第 $j$ 列的整数 $a_{i,j}$ 表示第 $i$ 个人在接下来的 $k$ 天中第 $j$ 个有空的日子为第 $a_{i,j}$ 天。
## 输出格式
一行 $k$ 个整数,第 $i$ 个整数表示接下来的第 $i$ 天教练需要准备的模拟赛场数。
## 样例 #1
### 样例输入 #1
```
1 3 5
2 3 5
```
### 样例输出 #1
```
0 1 1 0 1
```
## 样例 #2
### 样例输入 #2
```
6 3 7
2 3 4
2 5 7
3 5 7
1 3 5
5 6 7
1 2 3
```
### 样例输出 #2
```
1 2 3 1 3 1 1
```
## 样例 #3
### 样例输入 #3
```
10 10 20
2 3 4 8 9 11 12 16 17 18
2 3 6 10 12 13 14 15 19 20
1 3 7 10 11 13 14 15 17 19
1 2 4 6 7 9 15 17 19 20
2 3 5 6 9 11 14 16 19 20
1 2 3 8 9 10 11 12 15 19
1 4 6 7 9 12 13 17 18 19
1 7 8 9 10 11 13 15 18 20
1 5 6 7 8 9 13 16 18 19
4 5 7 10 11 13 14 17 18 20
```
### 样例输出 #3
```
1 2 2 3 2 2 4 3 3 3 3 4 2 1 3 1 2 2 2 1
```
## 提示
**本题采用捆绑测试。**
- Subtask 1(13 points):$n = m = k = 1$。
- Subtask 2(24 points):$n = 1$。
- Subtask 3(24 points):$m = 1$。
- Subtask 4(39 points):无特殊限制。
对于 $100\%$ 的数据,$1 \le n,m,k \le 10^3$,$m \le k$,$1 \le a_{i,1} < a_{i,2} < \cdots < a_{i,m} \le k$。
*/