CF2201G Codeforces Heuristic Contest 1001

给定一个包含 $n^2$ 个顶点的图，顶点用整数对 $(r,c)$ 表示，其中 $1 \leq r,c \leq n$。当且仅当 $(r_1-r_2)^2+(c_1-c_2)^2=13$ 时，顶点 $(r_1,c_1)$ 与顶点 $(r_2,c_2)$ 直接连接。这样的图被称为尺寸为 $n \times n$ 的“斑马图”。 请在尺寸为 $n \times n$ 的斑马图中，找出一个顶点子集 $S$，使其满足以下条件： - 由子集 $S$ 所诱导$^*$的子图同构于一个包含至少 $\left\lfloor{\frac{n^2}{e}}\right\rfloor$ 个顶点$^\dagger$的环图。 可以证明，对于本题的约束条件，必然存在这样一个顶点子集。 $^*$ 一个顶点子集 $X$ 的诱导子图是这样一个图：包含 $X$ 中所有的顶点，以及所有两个端点都在 $X$ 中的边。 $^\dagger$ 这里，$e$ 是数学常数，其极限定义为 $\lim \limits_{n \to \infty} \left (1 + \frac{1}{n} \right )^n \approx 2.71828182$。注意 $\frac{1}{e}$ 的近似值是 $0.36787944$。

输入的第一行包含一个整数 $n$，其中 $n\in \{5, 1001\}$。 此题仅有两个输入文件： - 第一个输入文件（示例输入）为 $n=5$； - 第二个输入文件为 $n=1001$。 本题不支持 Hack。

输出 $n$ 行，每行包含一个长度为 $n$ 的字符串 $s_i$，表示图的第 $i$ 行。如果顶点 $(r,c)$ 属于集合 $S$，则 $s_r$ 的第 $c$ 个字符应为 '1'，否则应为 '0'。 如果有多组解，输出任意一组均可。

对于示例输出，子集 $S$ 对应的诱导子图如下所示。  该图同构于 $16$ 个顶点组成的环图 $C_{16}$。由于 $16 \geq \left\lfloor{\frac{n^2}{e}}\right\rfloor = 9$，因此输出满足题目的条件。 由 ChatGPT 5 翻译