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 \(\rm{MEX}\) of an array is the smallest non-negative integer that does not belong to the array. e.g., \(\rm{MEX}(0, 3, 1, 4)=2\) because \(2\) does not belong to the array.

\(n\times m\) (\(\sum n_i\times m_i\leq 2\times10^6\)) 的矩阵 \(M\)，要求填满这一矩阵，使得：

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

Tutorial

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

• 若 \(arr\) 数组的最大值为 \(c\)，则 \({\rm{MEX}}(arr)\leq c+1\)。
• 若 \(arr\) 数组的长度为 \(d\)，则 \({\rm{MEX}}(arr)\leq d\)。

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

• \(v_i={\rm{MEX}}(M_{1,i},...,M_{n,i})\leq n\), (\(n\) 为 \(\{v_i\}\) 的最大值) 因此 \(s\leq n+1\)。
• \(s={\rm{MEX}}(v_1,v_2,...,v_m)\), \(s\leq m\).

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

当 \(n+1\leq 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;
}