题解 P5594 【【XR-4】模拟赛】

· · 题解

Update

Content

请前往原题查看。

数据范围：1\leqslant m\leqslant n,k\leqslant 10^3，1\leqslant a_{i,1}<a_{i,2}<\dots<a_{i,m}\leqslant k。

Solution

说实话，在这样的入门题中使用 \texttt{set}、\texttt{vector} 确实有点小题大做，而且这种题解一般对于刚学 OI 的萌新来说很不友好。其实没必要这么复杂，这道题目只要用一个二维 vis 数组即可。 那么这个 vis 数组契机从何而来呢？

我们注意到题目中的这段话：

教练需要为每一个人的每一次模拟赛做准备，为了减小工作量，如果在某一天有多个人打同一套模拟赛题，那么教练只需要在这一天准备一场使用这一套题的模拟赛即可。

如果你理解了这段话，这道题目就做完一大半了，剩下的就是代码实现的问题了。

这就是那个二维 vis 数组的作用所在。

设这个数组中的元素 vis_{i,j} 表示当 vis_{i,j}=1 的时候表示第 j 天已经准备了第 i 套模拟题，这样就可以保证只在第一次在第 j 天需要第 i 套模拟题的时候统计进去，而且接下来如果还碰到同一天打同一套题目的时候不会重复计算。

每个同学的空闲天也可以用二维数组 a 来保存，至于题目直接用 1,2,...,m 表示就可以了，不需要再开数组。

所以这道题目就写完了。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m, k, tot[1004], vis[1004][1004], a[1004][1004];

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(!vis[j][a[i][j]]) {
                vis[j][a[i][j]] = 1;
                tot[a[i][j]]++;
            }
        }
    }
    for(int i = 1; i <= k; ++i)
        printf("%d ", tot[i]);
    return 0;
}