题解：P10748 [SEERC2020] Mistake

_hxh · 2024-07-17 15:21:18 · 题解

分析

题意还是非常清楚的，为了帮助理解，我们把样例中依次启动的机器输出的序列和合法的启动方案放在一起看。（{\color{red} 第一台机器}，{\color{green} 第二台机器}，{\color{blue} 第三台机器}）

因为每个数都出现了 k 次，所以正好于 k 台机器匹配。注意到题目中说“输出一种合法的启动方案”就可以，所以我们可以调整一下：

我们可以让该数字第 j 次出现被第 j 台机器打印，这样可以直接用一个数组记录。设 pos_{i,j} 为数字 i 第 j 次出现的位置，那么 pos_{1,1} < pos_{1,2} < \dots < pos_{1,k},pos_{2,1} < pos_{2,2} < \dots < pos_{2,k}\dots 一定成立。而输入的依次启动的机器输出的序列一定是合法的，这样 pos_{1,j},pos_{2,j},\dots,pos_{n,j} 位置上的数字就可以匹配到第 j 台机器上啦。

为什么 m 对 (a_i,b_i) 没有用呢？因为依次启动的机器输出的序列一定是合法的，即一定满足每个存储的 a_i 都在 b_i 前面，不需要开数组进行存储。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5; 
int n,k,m,a,b,x,nk[N];
int main()
{
    cin >> n >> k >> m;
    for (int i = 1;i <= m;i++)
        cin >> a >> b;
    for (long long i = 1;i <= n * k;i++)
    {
        cin >> x;
        cout << ++nk[x] << " ";
    }
    return 0;
}