:::info[Description] Link. :::
:::infoSolution 前两个 sub 直接退火就能退出来，因此这里只考虑 时候的构造方案。
题目给的条件很奇怪，因此考虑加强构造限制，构造一张 个点的图满足图不存在四元环。
考虑取质数 满足 （这里取 ），考虑构造一个 个点的图满足其不存在四元环。考虑将每个点的编号映射成一个二元组 满足 不能同时为 且 。然后直接构造，对图上两个点，记其映射得到的二元组分别为 和 ，则两个点之间有边当且仅当 。
跑出来程序之后发现图确实不存在四元环，然后还满足构造的边数下界，因此可以通过该题。 :::
:::success[Code]
namespace lowspeed_song {
inline void init() {
}
int mp[3010][3010];
inline void sol() {
int n; cin >> n;
if (n == 4) {
cout << "1100" << '\n';
cout << "1001" << '\n';
cout << "1010" << '\n';
cout << "0011" << '\n';
} else if (n == 10) {
cout << "0101000100" << '\n';
cout << "0010010100" << '\n';
cout << "0000000001" << '\n';
cout << "1000100100" << '\n';
cout << "1001001000" << '\n';
cout << "1000010010" << '\n';
cout << "0010101000" << '\n';
cout << "0011000010" << '\n';
cout << "0100100010" << '\n';
cout << "0100011000" << '\n';
} else {
const int p = 47;
for (int x1 = 0; x1 < p; ++x1)
for (int y1 = 0; y1 < p; ++y1)
for (int x2 = 0; x2 < p; ++x2)
for (int y2 = 0; y2 < p; ++y2)
if ((x1 * x2 + y1 * y2) % p == 1) mp[x1 * p + y1][x2 * p + y2] = 1;
for (int i = 0; i < n; ++i, cout << '\n')
for (int j = 0; j < n; ++j) cout << mp[i][j];
}
}
} // namespace lowspeed_song:::
难度：黑-
鲜活指数：9
喜欢的话，留下你的评论吧～