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

Anye
Anye
发布于 2019-10-23 / 2 阅读
0
0

【百题千解】题解 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为例)

KtdcCV.png

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

Ktdy40.png

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

KtdrEn.png

完成第一列的遍历。

KtdsNq.png

再从第二列开始。

KtdBHs.png

完成第二列的遍历。

Ktdg3T.png

完成遍历后输出数列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来解决问题。


评论