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

我来写一篇大家都能看懂的，很好理解的算法。

这道题比赛时考虑的是可以用桶排的思想，但是比赛时想多了，按照横排去遍历了。 （太***了

经过我赛时的思考以及赛后的努力，我想出了 非常好理解 的方法。看到楼上的 dalao 们用的 STL 大法，我一个蒟蒻瑟瑟发抖~~

我们先来理解一下这道题目

观察数据特征+思路解析

• Subtask 1（13 points）：n = m = k = 1。

这是送分。。

//附上代码
cout<<"1";

不用解释吧 QWQ

• Subtask 2（24 points）：n = 1。

在这里我们思考一下，当 n = 1 时，意味着只有一个人参加模拟赛，那么直接输出一组数，使这个人有空的日数为 1 即可，其余为 0，这里运用到桶排的思想。

cin >> n >> m >> k;
memset(pp, 0, sizeof(pp));
for (int i = 0; i < n * m; i++) {
    cin >> f;
    pp[f]++;
}
for (int i = 1; i <=k; i++) {
        cout << pp[i]<<" ";
}

• Subtask 3（24 points）：m = 1。 继续向下看，m = 1 时，每个人只有一天做模拟题，那么从上到下遍历，去重，得到结果。

for (int i = 0; i < n * m; i++) {
    cin >> f;
    pp[f]++;
}
for (int i = 1; i <= k; i++) {
    if (pp[i] != 0) cout << "1 ";
    else cout << pp[i] << " ";
}

• Subtask 4（39 points）：无特殊限制。

那么正解也就出来了。我们可以结合前两种方案来得出最终的结果：

既然每一列代表的是同一套模拟题，那么我们是不是可以一列一列的来遍历数据？

这样我们就可以得到每套题在哪几天被做，为了解释的更清楚，我画个图来解释。（以样例 2 为例）

首先画出表格，上边代表的是 k 天，左边代表数据。以画 正 字模拟计数。

将每一列相同的数据存入一个桶中（桶排+去重）。

完成第一列的遍历。

再从第二列开始。

完成第二列的遍历。

完成遍历后输出数列 kk[] 存放的模拟赛场数。

代码解释

读入数据

cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

遍历每一列

for (int i = 0; i < m; i++) {

将每一列相同的数据存入一个桶中（桶排）

memset(b, 0, sizeof(b));
for (int j = 0; j < n; j++) {
    int k = a[j][i];
    b[k]++;
}

去重

for (int f = 0; f <= k; f++)
    if (b[f] != 0) b[f] = 1;

将结果存入kkk[ ]数组

for (int kk = 0; kk <= k; kk++) {
    kkk[kk] += b[kk];
}

按照顺序输出每一天需要准备的模拟赛场数

for (int i = 1; i <= k; i++)
    cout << kkk[i] << " ";

至此，这道 红题 就被完美地解决了，貌似解决了讨论版 Helenal 的问题，在这里 @Helenal 来解决问题。