构造数独【牛客tracker & 每日一题】

Source

构造数独

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
在这里插入图片描述

题目描述

旺仔哥哥是一位数独爱好者。在本题中，数独被定义为一个 n × n n×n n×n 的整数矩阵 B B B，其中所有元素均为非负整数，并满足：

  • 矩阵 B B B 的第 i i i 行所有元素之和等于 k k k；
  • 矩阵 B B B 的第 j j j 列所有元素之和也等于 k k k。
    给定正整数 n n n 与 k k k，旺仔哥哥想构造任意一个符合上述条件的数独。请你帮助他完成这一目标；如果不存在这样的矩阵，请你指出无解。

【名词解释】

  • 数独：数独指的是一个满足 "各行和各列和均为同一个整数 k k k " 条件的 n × n n×n n×n 非负整数矩阵。

输入描述：

在一行上输入两个整数 n , k ( 1 ≦ n ≦ 1 0 3 ; 1 ≦ k ≦ 1 0 9 ) n,k(1≦n≦10^3; 1≦k≦10^9) n,k(1≦n≦103;1≦k≦109) ，分别表示矩阵的阶数和每行（列）元素之和。

输出描述：

输出 n n n 行，每行 n n n 个整数，表示构造出的矩阵。行内元素以单个空格分隔。保证所有元素都是非负整数，并且矩阵满足题目要求。
如果不存在满足条件的矩阵，只需输出一行一个正整数 − 1 −1 −1。

示例1

输入：

2 4

输出：

1 3
3 1

说明：

矩阵的每一行、每一列之和均为 4 4 4，因此符合要求。

示例2

输入：

4 7

输出：

2 1 0 4
4 0 2 1
1 3 3 0
0 3 2 2

说明：

矩阵的 4 4 4 行之和均为 7 7 7；同样可验证 4 4 4 列之和也均为 7 7 7，故满足要求。

解题思路

题目要求构造 n × n n×n n×n 的非负整数矩阵，满足每行、每列和为 k k k，由于非负整数无其他限制，直接构造对角线矩阵即可——矩阵主对角线位置 （ i = j ） （i=j） （i=j） 填 k k k，其余位置填 0 0 0；该构造方式下，每行仅有主对角线元素为 k k k，和为 k k k，每列也仅有主对角线元素为 k k k，和为 k k k，完全满足条件；且 n n n 和 k k k 为正整数时必然有解（无需输出 − 1 -1 −1），此方法简单高效，适配 n n n 达 1 e 3 1e3 1e3 的规模，能快速输出符合要求的矩阵。

代码内容

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

typedef long long ll;
typedef pair<ll,ll> pii;
const ll N=1e5+10;

int main()
{
    
      
    ll n,k;
    cin>>n>>k;

    for(ll i=1;i<=n;i++)
    {
    
      
        for(ll j=1;j<=n;j++)
        {
    
      
            if(i==j) cout<<k<<" ";
            else cout<<0<<" ";
        }
        
        cout<<"\n";
    }

    return 0;
}