题目链接

构造数独

题目描述

给定一个 的矩阵，要求矩阵中每一行的元素之和都等于 ，每一列的元素之和也等于 ，且所有元素都为非负整数。请构造出任意一个满足条件的矩阵。如果不存在，则输出 -1。

输入:

  • 一行两个正整数：、，分别表示矩阵的阶数和每行（列）元素之和。

输出:

  • 行，每行 个整数，表示构造的矩阵。如果不存在，则输出 -1。

解题思路

这是一个构造性问题。我们需要找到一个 的矩阵，使其每行和每列的和都等于 。

一个简单而有效的构造方法是使用循环矩阵（Circulant Matrix）。循环矩阵的特点是每一行都是前一行的循环移位。这样的结构保证了如果第一行的元素和为 ，那么每一行的和都为 ；同时，每一列的和也都相等。

具体构造步骤如下：

  1. 首先确定第一行的元素。为了使元素尽可能均匀，我们可以将 分配给 个元素。令 (整数除法)，。我们可以构造一个包含 个 和 个 的序列，其总和恰好为 。
  2. 将这个序列作为矩阵的第一行。
  3. 后续的每一行都由前一行向右循环移动一位得到。具体来说，矩阵的第 行第 列的元素 可以由第一行的元素 通过 得到。

这种构造方法对于任意给定的正整数 和 总是能产生一个有效的解，因为 和 都是非负的。因此，本题不存在无解的情况。

代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    int n, s;
    cin >> n >> s;

    vector<int> first_row(n);
    int q = s / n;
    int r = s % n;

    // 构造第一行
    for (int i = 0; i < n; ++i) {
        if (i < r) {
            first_row[i] = q + 1;
        } else {
            first_row[i] = q;
        }
    }

    // 构造并打印整个矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // 通过循环移位确定当前元素
            cout << first_row[(j - i + n) % n] << (j == n - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();

        int[] firstRow = new int[n];
        int q = s / n;
        int r = s % n;

        // 构造第一行
        for (int i = 0; i < n; i++) {
            if (i < r) {
                firstRow[i] = q + 1;
            } else {
                firstRow[i] = q;
            }
        }

        // 构造并打印整个矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 通过循环移位确定当前元素
                System.out.print(firstRow[(j - i + n) % n] + (j == n - 1 ? "" : " "));
            }
            System.out.println();
        }
    }
}

# 读取输入
n, s = map(int, input().split())

first_row = [0] * n
q = s // n
r = s % n

# 构造第一行
for i in range(n):
    if i < r:
        first_row[i] = q + 1
    else:
        first_row[i] = q

# 构造并打印整个矩阵
for i in range(n):
    row_to_print = []
    for j in range(n):
        # 通过循环移位确定当前元素
        row_to_print.append(str(first_row[(j - i + n) % n]))
    print(" ".join(row_to_print))

算法及复杂度

  • 算法：构造法、循环矩阵
  • 时间复杂度： - 我们需要构造并输出一个 的矩阵。
  • 空间复杂度： - 我们需要一个大小为 的数组来存储第一行的元素。