我来写一篇大家都能看懂的,很好理解的算法。
这道题比赛时考虑的是可以用桶排的思想,但是比赛时想多了,按照横排去遍历了。 _ (太。。。了 _
经过我赛时的思考以及赛后的努力,我想出了非常好理解的方法。~~看到楼上的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来解决问题。