← 返回题目列表

Codeforces · 2219/E

E. 奇怪的棋盘

中文机器翻译题面 查看原题

考虑一个大小为 $$$n \times n$$$ 的棋盘(网格)。你想在棋盘上放置尽可能多的棋子。这些棋子的行为方式如下:如果我们用 $$$(1,1)$$$ 表示左上角的单元格,那么放置在单元格 $$$(i,j)$$$ 中的棋子可以攻击每个单元格 $$$(x,y)$$$,使得 $$$x \ge i$$$ 和 $$$y \ge j$$$ 除外,$$$(i,j)$$$ 本身除外。

例如,在 $$$10 \times 10$$$ 棋盘上,放置在 $$$(3,4)$$$ 的棋子可以攻击下面突出显示的单元格:

给定一个棋盘,上面放置了一些棋子,我们说一个单元格是 好 如果攻击该单元格的棋子数量是偶数。

构造一个棋子配置,使得每个单元都很好,无论单元本身是否包含棋子,并且棋盘至少包含 $$$\lfloor \frac{n^2}{10} \rfloor \cdot 3$$$ 棋子。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$)。

保证所有测试用例的 $$$n^2$$$ 总和最多为 $$$25\,000\,000 = 5000^2$$$。

输出

对于每个测试用例,打印 $$$n$$$ 行。在第 $$$i$$$ 行中,打印由空格分隔的 $$$n$$$ 整数,其中 $$$1$$$ 表示该单元格中有一块,$$$0$$$ 表示该单元格中没有。

第 $$$i$$$ 行中的第 $$$j$$$ 整数对应于单元格 $$$(i,j)$$$。

示例

输入
复制

1
3

输出
复制

0 0 1 
0 1 1 
1 0 1

注意

这个例子是一个尺寸为 $$$3 \times 3$$$ 的棋盘,其中每个单元格都是 好.

单元格 $$$(3, 3)$$$ 是 好 因为棋子$$$(1, 3), (2, 3), (2, 2), (3, 1)$$$的细胞攻击它,这个计数是4,是偶数。

单元格 $$$(1, 3)$$$ 是 好 因为没有棋子攻击它,所以攻击这个单元格的棋子数量为0。

单元格 $$$(3, 2)$$$ 是 好,并注意该单元格需要 好 即使它没有一块。