跳转至

算法笔记

BISHI28 构造数独

w3903771/algorithm

BISHI28　构造数独¶

简单通过率 67.12%python3样例通过牛客 AC

牛客原题　源码

讲解章节：构造、高级搜索与精确覆盖

一句话

构造 n*n 非负整数矩阵，使每行和、每列和都等于 k。

解题思路¶

这题考什么¶

只要想到「对角线矩阵」就结束了：主对角线全填 k，其余填 0。第 i 行只有 B[i][i] = k，行和 = k；第 j 列只有 B[j][j] = k，列和 = k。对任意 n >= 1、k >= 1 都成立，所以永远有解，-1 是永远不会输出的分支（题面要求写上而已）。

数据规模与复杂度¶

n <= 1e3，矩阵有 1e6 个元素，必须 O(n^2) 输出且 IO 要省。如果逐元素 print 会被 IO 打死；这里用「'0 'i + str(k) + ' 0'(n-1-i)」直接靠字符串重复拼出一整行，每行 O(n) 的 C 级操作，最后一次性 sys.stdout.write("\n".join(...))。输出总长约 2e6 字符，稳。

坑在哪¶

别去照抄样例那种「每格都非零」的花式矩阵，对角线最省事也最不会错；
k 可以到 1e9，元素本身是大数，但只有 n 个非零元素，输出量不会爆；
n = 1 时只有一行一个 k，拼接时 n-1-i = 0 要能正确退化成空串；
答案不唯一：题面只要求行和、列和都等于 k，满足条件的矩阵数量极多，样例给的就是一个「每格都非零」的解，而本解法给的是对角线解。所以本地要用 special judge（特殊评测程序，按题目条件验证选手输出是否合法，而不是与标准答案逐字符比对）：本题配了 solutions/_spj/BISHI28.py，它读入 n*n 个数，逐行逐列真的把和算一遍。

参考实现¶

solutions/BISHI28.py
import sys

n, k = map(int, sys.stdin.buffer.read().split()[:2])
ks = str(k)
# 第 i 行： i 个 0，一个 k，n-1-i 个 0
rows = ["0 " * i + ks + " 0" * (n - 1 - i) for i in range(n)]
sys.stdout.write("\n".join(rows) + "\n")