网易互娱 8.27 笔试题解
第三题真恶心,全枚举了一遍踩点完成
// 第1题 #include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int T; while (cin >> T) { int N, M; for (int t = 0; t < T; ++t) { cin >> N >> M; vector<vector<char>> v(N, vector<char>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) cin >> v[i][j]; } if (M <= N) { int idx = (N - M) / 2; for (int i = idx; i < N - idx; ++i) { for (int j = idx; j < N - idx; ++j) { cout << v[i][j]; } cout << endl; } if (t != T - 1) cout << endl; } else { float left = (float(M - N)) / 2 / N; int times = ceil(left) * 2 + 1; times *= N; vector<vector<char>> wall(times, vector<char>(times)); for (int i = 0; i < times; ++i) { for (int j = 0; j < times; ++j) { wall[i][j] = v[i%N][j%N]; } } int center = ceil(times / 2); int width = ceil(M / 2); for (int i = center - width; i <= center + width; ++i) { for (int j = center - width; j <= center + width; ++j) { cout << wall[i][j]; } cout << endl; } if (t != T - 1) cout << endl; } } } return 0; } // 第2题 #include <iostream> #include <vector> #include <set> using namespace std; bool is_intersect(const vector<int>& a, const vector<int>& b) { int xmin = max(a[0], b[0]); int xmax = min(a[2], b[2]); int ymin = max(a[1], b[1]); int ymax = min(a[3], b[3]); return (xmin < xmax && ymin < ymax); } int main() { int T; while (cin >> T) { int N; for (int t = 0; t < T; ++t) { cin >> N; vector<vector<int>> v; int x0, y0, x1, y1; for (int i = 0; i < N; ++i) { cin >> x0 >> y0 >> x1 >> y1; v.push_back({x0, y0, x1, y1}); } if (N == 1) { cout << 0; if (t != T - 1) cout << endl; continue; } set<vector<int>> ss; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { if (is_intersect(v[i], v[j])) { ss.emplace(v[i]); ss.emplace(v[j]); } } } if (ss.empty()) { cout << 0; if (t != T - 1) cout << endl; continue; } int res = 0; vector<vector<int>> grid(1005, vector<int>(1005, 0)); for (auto it = ss.begin(); it != ss.end(); ++it) { for (int i = (*it)[0]; i < (*it)[2]; ++i) { for (int j = (*it)[1]; j < (*it)[3]; ++j) { if (grid[i][j] == 0) { ++res; } grid[i][j] = 1; } } } cout << res; if (t != T - 1) cout << endl; } } return 0; } // 第3题 #include <iostream> #include <vector> #include <unordered_set> using namespace std; // 构造 string,24位可以用int,用哈希表缓存 /* - - |\/|/\| - - |\/|\/| _ _ 前8位代表边框,后12位代表内部,还有8位是陡的斜线 */ int connect(int x, int y, int nx, int ny) { if (x < nx) { swap(x, nx); swap(y, ny); } if (x == 0) { if (y == 0) { if (nx == 0 && ny == 1) return (1 << 1); else if (nx == 0 && ny == 2) return (1 << 1) | (1 << 2); else if (nx == 1 && ny == 0) return (1 << 8); else if (nx == 2 && ny == 0) return (1 << 7) | (1 << 8); else if (nx == 1 && ny == 1) return (1 << 9); else if (nx == 1 && ny == 2) return (1 << 17); else if (nx == 2 && ny == 1) return (1 << 24); else if (nx == 2 && ny == 2) return (1 << 9) | (1 << 13); } else if (y == 1) { if (nx == 0 && ny == 0) return (1 << 1); else if (nx == 0 && ny == 2) return (1 << 2); else if (nx == 1 && ny == 0) return (1 << 28); else if (nx == 1 && ny == 1) return (1 << 10); else if (nx == 1 && ny == 2) return (1 << 25); else if (nx == 2 && ny == 0) return (1 << 18); else if (nx == 2 && ny == 1) return (1 << 10) | (1 << 14); else if (nx == 2 && ny == 2) return (1 << 19); } else if (y == 2) { if (nx == 0 && ny == 0) return (1 << 1) | (1 << 2); else if (nx == 0 && ny == 1) return (1 << 2); else if (nx == 1 && ny == 0) return (1 << 20); else if (nx == 1 && ny == 1) return (1 << 11); else if (nx == 1 && ny == 2) return (1 << 3); else if (nx == 2 && ny == 0) return (1 << 11) | (1 << 15); else if (nx == 2 && ny == 1) return (1 << 21); else if (nx == 2 && ny == 2) return (1<<3) | (1<<4); } } else if (x == 1) { if (y == 0) { if (nx == 0 && ny == 0) return (1 << 8); else if (nx == 0 && ny == 1) return (1 << 28); else if (nx == 0 && ny == 2) return (1 << 20); else if (nx == 1 && ny == 1) return (1 << 16); else if (nx == 1 && ny == 2) return (1 << 12) | (1 << 16); else if (nx == 2 && ny == 0) return (1 << 7); else if (nx == 2 && ny == 1) return (1 << 27); else if (nx == 2 && ny == 2) return (1 << 23); } else if (y == 1) { if (nx == 0 && ny == 0) return (1 << 9); else if (nx == 0 && ny == 1) return (1 << 10); else if (nx == 0 && ny == 2) return (1 << 11); else if (nx == 1 && ny == 0) return (1 << 16); else if (nx == 1 && ny == 2) return (1 << 12); else if (nx == 2 && ny == 0) return (1 << 15); else if (nx == 2 && ny == 1) return (1 << 14); else if (nx == 2 && ny == 2) return (1 << 13); } else if (y == 2) { if (nx == 0 && ny == 0) return (1 << 17); else if (nx == 0 && ny == 1) return (1 << 25); else if (nx == 0 && ny == 2) return (1 << 3); else if (nx == 1 && ny == 0) return (1 << 16) | (1 << 12); else if (nx == 1 && ny == 1) return (1 << 12); else if (nx == 2 && ny == 0) return (1 << 22); else if (nx == 2 && ny == 1) return (1 << 26); else if (nx == 2 && ny == 2) return (1 << 4); } } else { if (y == 0) { if (nx == 0 && ny == 0) return (1 << 7) | (1 << 8); else if (nx == 0 && ny == 1) return (1 << 18); else if (nx == 0 && ny == 2) return (1 << 15) | (1 << 11); else if (nx == 1 && ny == 0) return (1 << 7); else if (nx == 1 && ny == 1) return (1 << 15); else if (nx == 1 && ny == 2) return (1 << 22); else if (nx == 2 && ny == 1) return (1 << 6); else if (nx == 2 && ny == 2) return (1 << 5) | (1 << 6); } else if (y == 1) { if (nx == 0 && ny == 0) return (1 << 24); else if (nx == 0 && ny == 1) return (1 << 10) | (1 << 14); else if (nx == 0 && ny == 2) return (1 << 21); else if (nx == 1 && ny == 0) return (1 << 27); else if (nx == 1 && ny == 1) return (1 << 14); else if (nx == 1 && ny == 2) return (1 << 26); else if (nx == 2 && ny == 0) return (1 << 6); else if (nx == 2 && ny == 2) return (1 << 5); } else if (y == 2) { if (nx == 0 && ny == 0) return (1 << 9) | (1 << 13); else if (nx == 0 && ny == 1) return (1 << 19); else if (nx == 0 && ny == 2) return (1 << 3) | (1 << 4); else if (nx == 1 && ny == 0) return (1 << 23); else if (nx == 1 && ny == 1) return (1 << 13); else if (nx == 1 && ny == 2) return (1 << 4); else if (nx == 2 && ny == 1) return (1 << 5); else if (nx == 2 && ny == 0) return (1 << 5) | (1 << 6); } } return 0; } void dfs(int x, int y, int cur, vector<vector<char>> &grid, unordered_set<int> &ss) { grid[x][y] = 'X'; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { if (grid[i][j] == '.') { int val = connect(x, y, i, j); int nex = cur | val; ss.emplace(nex); dfs(i, j, nex, grid, ss); } } } grid[x][y] = '.'; } int main() { int T; while (cin >> T) { for (int t = 0; t < T; ++t) { vector<vector<char>> v(3, vector<char>(3)); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) cin >> v[i][j]; } unordered_set<int> ss; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { if (v[i][j] == '.') dfs(i, j, 0, v, ss); } } cout << ss.size(); if (t != T - 1) cout << endl; } } return 0; }