Codeforces 1869C Fill in the Matrix

题目来自 Codeforces Round #896 (Div.2) C。link

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

The $\mathrm{M}\mathrm{E}\mathrm{X}$ of an array is the smallest non-negative integer that does not belong to the array. e.g., $\mathrm{M}\mathrm{E}\mathrm{X}(0,3,1,4)=2$ because $2$ does not belong to the array.

$n\times m$ ($\sum n_i\times m_i\le 2\times {10}^6$) 的矩阵 $M$，要求填满这一矩阵，使得：

• 矩阵的每一行是一个长为 $m$ 的排列 ($0$ 到 $m-1$)。
• 定义该矩阵每一列的 value $v_i=\mathrm{M}\mathrm{E}\mathrm{X}(M_{1,i},M_{2,i},...,M_{n,i})$，最大化 $s=\mathrm{M}\mathrm{E}\mathrm{X}(v_1,v_2,...,v_m)$。

Tutorial

$\mathrm{M}\mathrm{E}\mathrm{X}$ 函数的一个重要性质：$\mathrm{M}\mathrm{E}\mathrm{X}(arr)$ 的值不仅与 $arr$ 数组的值有关，还与 $arr$ 数组的长度有关。

• 若 $arr$ 数组的最大值为 $c$，则 $\mathrm{M}\mathrm{E}\mathrm{X}(arr)\le c+1$。
• 若 $arr$ 数组的长度为 $d$，则 $\mathrm{M}\mathrm{E}\mathrm{X}(arr)\le d$。

根据这一性质，我们能够得到 $s$ 的 upper bound：

• $v_i=\mathrm{M}\mathrm{E}\mathrm{X}(M_{1,i},...,M_{n,i})\le n$, ($n$ 为 $\{v_i\}$ 的最大值) 因此 $s\le n+1$。
• $s=\mathrm{M}\mathrm{E}\mathrm{X}(v_1,v_2,...,v_m)$, $s\le m$.

因此 $m$ 与 $n+1$ 是 $s$ 的上界的两种形式；$s$ 将被较小的上界限制。

当 $n+1\le m$ 时，$s=n+1$。

被 $n+1$ 上界限制

当 $n+1>m$ 时，$s=m$。

被 $m$ 上界限制

Code Implementation

#include <iostream>

using namespace std;

int main() {

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n + 1 <= m) {
            cout << n + 1 << endl;
            for (int i = 1; i <= n; ++i) {
                for (int j = i; j <= i + n; ++j) {
                    cout << j % (n + 1) << " ";
                }
                for (int j = n + 1; j < m; ++j) {
                    if (j == m - 1)
                        cout << j << "\n";
                    else 
                        cout << j << " ";
                }
            }
        } else {
            if (m == 1)
                cout << "0" << endl;
            else
                cout << m << endl;
            for (int i = 1; i <= m - 1; ++i) {
                for (int j = i; j <= i + m - 1; ++j) {
                    if (j == i + m - 1)
                        cout << j % m << "\n";
                    else
                        cout << j % m << " ";
                }
            }
            for (int i = 1; i <= n - m + 1; ++i) {
                for (int j = 1; j <= m; ++j) {
                    if (j == m)
                        cout << 0 << "\n";
                    else
                        cout << j << " ";
                }
            }
        }
    }

    return 0;
}