构造数独

思路

题目要求构造一个 的非负整数矩阵，使得每行每列的和都等于 。

最直接的想法：先均匀分配，再处理余数。

设 ，。如果所有格子都填 ，那么每行每列的和是 ，还差 。

怎么把每行每列各补上 呢？只需要在每行恰好选 个格子加 1，同时保证每列也恰好被选中 次。

用循环移位就能优雅地搞定：第 行把列 （下标对 取模）的格子加 1。这样每列 恰好在 行中被选中（因为是循环的），行列对称性完美满足。

最终每个格子的值：

$$

整个构造 ，非常简洁。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, s;
    cin >> n >> s;
    int base = s / n;
    int r = s % n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int diff = (j - i % n + n) % n;
            int val = base;
            if (diff < r) val++;
            if (j > 0) cout << " ";
            cout << val;
        }
        cout << "\n";
    }
    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 base = s / n;
        int r = s % n;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int diff = (j - i % n + n) % n;
                int val = base;
                if (diff < r) val++;
                if (j > 0) sb.append(' ');
                sb.append(val);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
base = s // n
r = s % n
out = []
for i in range(n):
    row = []
    for j in range(n):
        diff = (j - i % n + n) % n
        val = base + (1 if diff < r else 0)
        row.append(str(val))
    out.append(' '.join(row))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const [n, s] = line.trim().split(' ').map(Number);
    const base = Math.floor(s / n);
    const r = s % n;
    const out = [];
    for (let i = 0; i < n; i++) {
        const row = [];
        for (let j = 0; j < n; j++) {
            const diff = (j - i % n + n) % n;
            const val = diff < r ? base + 1 : base;
            row.push(val);
        }
        out.push(row.join(' '));
    }
    console.log(out.join('\n'));
    rl.close();
});

复杂度

  • 时间复杂度：，遍历整个矩阵。
  • 空间复杂度：（不计输出），逐行输出无需存储矩阵。