T2201G. Codeforces Heuristic Contest 1001
constructive algorithms, 3500, https://codeforces.com/problemset/problem/2201/G
There is a graph of 𝑛^2 vertices, where vertices are labeled by integer pairs (𝑟,𝑐) such that 1≤𝑟,𝑐≤𝑛. Vertices (𝑟1,𝑐1) and (𝑟2,𝑐2) are directly connected if and only if (𝑟1−𝑟2)^2+(𝑐1−𝑐2)^2=13. This graph is called the Zebra Graph of dimensions 𝑛×𝑛.
Please find a subset of vertices 𝑆 in the Zebra Graph of dimensions 𝑛×𝑛, which satisfies the following condition.
- The graph induced∗ by the subset 𝑆 is isomorphic to a cycle graph of at least ⌊𝑛2𝑒⌋ vertices†.
It can be shown that such a subset of vertices exists under the constraints of this problem.
∗The induced graph of a subset of vertices 𝑋 is a graph that contains all vertices in 𝑋 and all edges whose both endpoints are in 𝑋.
†Here, 𝑒 is the mathematical constant equal to the limit lim𝑛→∞(1+1/𝑛)^𝑛≈2.71828182. Note that the value of 1/𝑒 is approximately 0.36787944.
Input
The first and only line of input contains a single integer 𝑛 (𝑛∈{5,1001}).
There are only two input files for this problem:
- The first input file (the example input) has 𝑛=5;
- The second input file has 𝑛=1001.
Hacks are disabled for this problem.
Output
Output 𝑛 lines, each containing a string 𝑠𝑖 of length 𝑛 denoting the 𝑖-th row of the graph. If the vertex (𝑟,𝑐) is an element of 𝑆, then the 𝑐-th letter of 𝑠𝑟 should be '1'. Otherwise, the 𝑐-th letter of 𝑠𝑟 should be '0'.
If there are multiple solutions, print any of them.
Example
input
5output
01110
11011
10001
11011
01110Note
For the example output, the induced graph corresponding to the subset 𝑆 is shown below.
This graph is isomorphic to the cycle graph 𝐶_16 consisting of 16 vertices. As 16≥⌊𝑛^2/𝑒⌋=9, the output satisfies the problem's condition.
【尹显齐 25物理学院】
题目大意：现在有一个
前言：这个题的自由度很大，希望你能在充分思考后决定是否观看题解。并且题解不会包含所有细节与具体方法。
这里有ds写的一个检查程序，可以帮你看看你的构造是否有效。
python
def check_pattern(n, matrix):
"""
检查矩阵是否满足要求
n: 矩阵大小
matrix: 二维矩阵
"""
if n == 5:
# 检查5x5的固定图案
expected = [[0,1,1,1,0],[1,1,0,1,1],[1,0,0,0,1],[1,1,0,1,1],[0,1,1,1,0]]
for i in range(5):
for j in range(5):
if matrix[i][j] != expected[i][j]:
return False, f"位置({i},{j})的值不正确"
return True, "5x5图案正确"
elif n == 1001:
# 找出所有为1的点
points = []
for i in range(1001):
for j in range(1001):
if matrix[i][j] == 1:
points.append((i, j))
print(f"总共找到{len(points)}个为1的点")
# 距离为√13的偏移量（平方和为13）
# 可能的偏移组合：2^2+3^2=13
offsets = [
(2, 3), (3, 2), (2, -3), (3, -2),
(-2, 3), (-3, 2), (-2, -3), (-3, -2)
]
# 将点转换为集合，便于快速查找
point_set = set(points)
# 检查1：每个点是否有且仅有两条边与之相连
all_degree_2 = True
invalid_points = []
for x, y in points:
degree = 0
# 检查8个方向的点是否存在
for dx, dy in offsets:
nx, ny = x + dx, y + dy
if 0 <= nx < 1001 and 0 <= ny < 1001 and (nx, ny) in point_set:
degree += 1
if degree != 2:
all_degree_2 = False
invalid_points.append(((x, y), degree))
if not all_degree_2:
print("度数不为2的点：")
for point, degree in invalid_points[:10]: # 只显示前10个
print(f" 点{point}，度数为{degree}")
return False, f"存在度数不为2的点，共有{len(invalid_points)}个"
# 检查2：所有点是否互相连通（BFS，只遍历边，即距离为√13的点）
from collections import deque
visited = set()
queue = deque([points[0]])
visited.add(points[0])
while queue:
x, y = queue.popleft()
# 只检查距离为√13的邻居
for dx, dy in offsets:
nx, ny = x + dx, y + dy
if 0 <= nx < 1001 and 0 <= ny < 1001:
neighbor = (nx, ny)
if neighbor in point_set and neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
if len(visited) != len(points):
return False, f"图不连通，只有{len(visited)}/{len(points)}个点连通"
return True, f"检查通过！共有{len(points)}个点，每个点度数均为2，且全部连通"
else:
return False, f"不支持的矩阵大小: {n}"
def main():
# 直接读取你的程序输出
n = int(input())
matrix = []
for _ in range(n):
row = list(map(int, input().strip()))
matrix.append(row)
result, message = check_pattern(n, matrix)
print(message)
if __name__ == "__main__":
main()提示：伸缩门
说明：对于
正式开始！ 我的方法主要基于一个思想，就是使用不断重复的小单元去密铺整个平面，在多次尝试后，我找到了如下方法：
这种形状像伸缩门的形状可以轻松密铺平面，现在只需要把它的各个端点接起来即可（这并不容易！），最终效果如图：
至于这个东西我也不知道叫啥，看到题解的人可以顺便想个名字。
最终，我成功覆盖了
代码：
python
def out(i,arr):
for j in range(i):
print(*arr[j],sep = "")
n = int(input())
pat = [[0,1,1,1,0],[1,1,0,1,1],[1,0,0,0,1],[1,1,0,1,1,],[0,1,1,1,0]]
if n == 5:
out(5,pat)
else:
ans = [[0]*1001 for _ in range(1001)]
corn = [(0,2),(1,1),(2,0),(2,2),(2,5),(5,2),(3,4),(4,3),(4,5),(5,4),(8,4),(4,8)]# 其他三个角
tail = [(0,11),(11,0),(2,8),(8,2),(3,9),(9,3),(4,10),(10,4),(1,12),(12,1),(4,11),(11,4)]# 尾部（右下角）
# 主体部分
for i in range(328):
for j in range(328):
for rx,ry in [(1,0),(0,1),(2,1),(1,2)]:
ans[i*3+rx+8][j*3+ry+8] = 1
# 边上延展出去
for i in range(328):
for k in [0,2]:
ans[i*3+k+8][6] = 1
ans[i*3+k+8][993] = 1
ans[6][i*3+k+8] = 1
ans[993][i*3+k+8] = 1
for i in range(1,327):
ans[i*3+9][3] = 1
ans[i*3+9][996] = 1
ans[3][i*3+9] = 1
ans[996][i*3+9] = 1
for a,b in [(1,1),(-1,1),(1,-1),(-1,-1)]:
if a > 0 or b > 0:
for cx,cy in corn:
ans[int(a<0)*999+a*cx][int(b<0)*999+b*cy] = 1
else:
for cx,cy in tail:
ans[1000+a*cx][1000+b*cy] = 1
out(1001,ans)【熊江凯，元培】搞了一个454486。
cpp
#include <bits/stdc++.h>
using namespace std;
static string core_row(int w) {
string s(w, '0');
for (int c = 0; c < w; ++c) {
int x = c % 8;
if (x == 0 || x == 3 || x == 4 || x == 7) s[c] = '1';
}
return s;
}
static vector<string> family32(int H) {
const vector<string> TOP = {
"00000110010000100100001001100000",
"00000000001000000000010000000000",
"01000000100010000001000100000010",
"01111000100110011001100100011110",
"00001000100110011001100100010000",
"10011001100110011001100110011001",
};
const vector<string> BOT = {
"00011001100110011001100110011000",
"01011000100110011001100100011011",
"11001000100010000001000100010001",
"00000000001000000000110100000100",
"00000110010000100100000000100100",
"00100000000000000100000000100100",
};
vector<string> g;
g.reserve(H);
for (auto &row : TOP) g.push_back(row);
string mid = core_row(32);
for (int r = 6; r < H - 6; ++r) g.push_back(mid);
for (auto &row : BOT) g.push_back(row);
return g;
}
static vector<string> family44(int H) {
const vector<string> TOP = {
"00100100000000100100000000000100000001000000",
"00100100001000000110000000100100000001000010",
"00100000101000000000100001000000010000000000",
"10001000100010001001000100010001010100010010",
"11011000100110011001100110010001000100011110",
"00011001100110011001100110011001100100010000",
};
const vector<string> BOT = {
"00001000100110011001100110011001100110011000",
"01111000100010001001100110011001100100011011",
"01001000101010001000100010010001000100010001",
"00000000001000000010000100000000010100000100",
"01000010000000100100000001100000010000100100",
"00000010000000100000000000100100000000100100",
};
vector<string> g;
g.reserve(H);
for (auto &row : TOP) g.push_back(row);
string mid = core_row(44);
for (int r = 6; r < H - 6; ++r) g.push_back(mid);
for (auto &row : BOT) g.push_back(row);
return g;
}
static vector<string> seam32_44(int H) {
const vector<string> TOP = {
"000001100",
"010000100",
"010100000",
"000101011",
"101101011",
"000000001",
"100110001",
};
const string A = "100000011";
const string B = "000100011";
const string C = "000110001";
const string D = "100010001";
const vector<string> BOT = {
"100000001",
"000100101",
"010001101",
"011010000",
"000001000",
"010000010",
};
vector<string> p;
p.reserve(H);
for (auto &row : TOP) p.push_back(row);
int mid_len = H - (int)TOP.size() - (int)BOT.size();
for (int i = 0; i < mid_len / 4; ++i) {
p.push_back(A);
p.push_back(B);
p.push_back(C);
p.push_back(D);
}
for (auto &row : BOT) p.push_back(row);
return p;
}
static vector<string> seam44_44(int H) {
const vector<string> TOP = {
"010000100",
"000000100",
"000100000",
"001101111",
"111000001",
"000010001",
"100100001",
};
const string A = "000110011";
const string B = "000100001";
const string C = "100010011";
const string D = "100000001";
const vector<string> BOT = {
"000001101",
"111011001",
"000010000",
"010000000",
"010000110",
};
vector<string> p;
p.reserve(H);
for (auto &row : TOP) p.push_back(row);
int mid_len = H - (int)TOP.size() - (int)BOT.size();
for (int i = 0; i < (mid_len - 1) / 4; ++i) {
p.push_back(A);
p.push_back(B);
p.push_back(C);
p.push_back(D);
}
p.push_back(B);
for (auto &row : BOT) p.push_back(row);
return p;
}
static void paint(vector<string>& g, int r0, int c0, const vector<string>& patch) {
for (int i = 0; i < (int)patch.size(); ++i) {
for (int j = 0; j < (int)patch[i].size(); ++j) {
g[r0 + i][c0 + j] = patch[i][j];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
if (n == 5) {
const vector<string> g = {
"01110",
"11011",
"10001",
"11011",
"01110",
};
for (const string &row : g) cout << row << '\n';
return 0;
}
const int N = 1001;
vector<string> g(N, string(N, '0'));
const vector<string> F32 = family32(N);
const vector<string> F44 = family44(N);
const vector<string> S3244 = seam32_44(N);
const vector<string> S4444 = seam44_44(N);
int off = 0;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < 32; ++c) g[r][off + c] = F32[r][c];
}
off += 32;
for (int blk = 0; blk < 22; ++blk) {
for (int r = 0; r < N; ++r) {
for (int c = 0; c < 44; ++c) g[r][off + c] = F44[r][c];
}
off += 44;
}
// Base seams.
for (int r = 0; r < N; ++r) {
for (int j = 0; j < 9; ++j) g[r][28 + j] = S3244[r][j];
}
for (int s = 76; s <= 956; s += 44) {
for (int r = 0; r < N; ++r) {
for (int j = 0; j < 9; ++j) g[r][s - 4 + j] = S4444[r][j];
}
}
// Edge improvements already present in v3.
const vector<string> TL32 = {
"0001011001000",
"0010000000100",
"1100000010001",
"0111100010011",
"1000100010011",
"1011000110011",
"1001100010011",
"1101100010011",
"0001100110011",
};
paint(g, 0, 0, TL32);
const vector<string> TR45 = {
"0000101000100",
"0000001101000",
"0100001100000",
"0001100011100",
"0011001100010",
"1000000010100",
"1001100110000",
"1001000110110",
"1001100110000",
};
paint(g, 0, 988, TR45);
// New bottom-right patch (+2 over v3).
const vector<string> BR16 = {
"0011001100110010",
"0011001100110010",
"0011001100110000",
"0011001000110100",
"0011001000110110",
"0011001000010010",
"0011001000001010",
"0011001000101110",
"0010001000101110",
"0000101000001110",
"0000100000011000",
"1000000011111000",
};
paint(g, 989, 985, BR16);
// New top patch for every 44|44 seam (+4 per seam, 21 seams).
const vector<string> TOP44_PATCH = {
"01101010000111100",
"00000100000000000",
"00100101101000011",
"00011010111010001",
"00011010100110001",
"00001000100000011",
"10011101000010011",
"00000001110110001",
"10010101000010011",
"00000000100110011",
"10011100000010011",
"00010001100110011",
};
for (int s = 76; s <= 956; s += 44) paint(g, 0, s - 8, TOP44_PATCH);
// Bottom patches for the three seam classes.
// Class 0: seams 76, 208, ..., 868 (+4 each).
const vector<string> BOT44_CLASS0 = {
"10010001100110011",
"10010001000010001",
"10010000101110011",
"10011000100000001",
"00010000001010001",
"00010101011000001",
"00010101111110001",
"10000100010000000",
"00000010010100100",
"01110010010010100",
};
for (int s = 76; s <= 868; s += 132) paint(g, 991, s - 8, BOT44_CLASS0);
// Class 1: seams 120, 252, ..., 912 (+4 each).
const vector<string> BOT44_CLASS1 = {
"10011000110110001",
"10011000000010011",
"10010001100000001",
"10010001101010011",
"10011000110100001",
"10010000100110001",
"10010001001100001",
"00010001111110001",
"00011110100010011",
"10000000001000000",
"00000000001010100",
"01110000001001100",
};
for (int s = 120; s <= 912; s += 132) paint(g, 989, s - 8, BOT44_CLASS1);
// Improved class-2 bottom seam patch: +2 on each class-2 seam over v4.
const vector<string> BOT44_CLASS2_V2 = {
"1001100010011001",
"1001100000011001",
"1001000110001000",
"1001000110101001",
"1001100011010000",
"1001100000011001",
"0001000100010000",
"0001010011101000",
"0001111010000001",
"0000000010110000",
"0000010000001010",
"0110010100000110",
};
for (int s = 164; s <= 956; s += 132) paint(g, 989, s - 8, BOT44_CLASS2_V2);
// Improved unique bottom patch for the first 32|44 seam: +2 over v4.
const vector<string> BOT3244_V2 = {
"1001000110001001",
"1001100010011001",
"1001000000001000",
"0001000111111000",
"1001010101000000",
"1001000000010001",
"1001100001000000",
"0001001011101000",
"1001010110110001",
"0001000000000101",
"0010001000011100",
"0010001001001100",
};
paint(g, 989, 24, BOT3244_V2);
// v6: larger bottom seam upgrades discovered by local exact MILP search.
// Class 0 seams: rows 989..1000, cols (s-10)..(s+10), +2 per seam over v5.
const vector<string> BOT44_CLASS0_V3 = {
"011001100110011001100",
"011001100000001001100",
"010001100110001000100",
"011001010000101000100",
"010000001101110000100",
"010001000000001001100",
"010000010000000001000",
"010001010100000101110",
"010001111101111101100",
"011000000101000100001",
"000001011000101000000",
"000111101001001110000",
};
for (int s = 76; s <= 868; s += 132) paint(g, 989, s - 10, BOT44_CLASS0_V3);
// Class 1 seams: rows 991..1000, cols (s-10)..(s+10), +2 per seam over v5.
const vector<string> BOT44_CLASS1_V2 = {
"011001000110010001100",
"011001000100001000100",
"011001000011111000100",
"011001000100001001100",
"010001100000010001000",
"010001010100010101110",
"010000111111111101100",
"010000101010000000001",
"000000000000101010000",
"000110001010000110000",
};
for (int s = 120; s <= 912; s += 132) paint(g, 991, s - 10, BOT44_CLASS1_V2);
// Class 2 seams: rows 989..1000, cols (s-10)..(s+10), +2 per seam over v5.
const vector<string> BOT44_CLASS2_V3 = {
"011001100011011000100",
"011001100000011000100",
"011001000110110001100",
"011001000110000000100",
"011001000011111000100",
"011001000000001000100",
"010001000000110001000",
"010001110100000100110",
"010000111001111001100",
"011000100101001000001",
"000001001000001110000",
"000111001000100101000",
};
for (int s = 164; s <= 956; s += 132) paint(g, 989, s - 10, BOT44_CLASS2_V3);
for (const string &row : g) cout << row << '\n';
return 0;
}