Untitled
unknown
plain_text
22 days ago
5.7 kB
7
Indexable
Never
A: #include <bits/stdc++.h> using namespace std; void dfs(int row, int col, vector<vector<char>> &map, vector<vector<bool>> &visited) { visited[row][col] = true; int n = map.size(); int m = map[0].size(); for (int i = -1; i <= 1; i++) { int newRow = row + i; if (newRow >= 0 && newRow < n && col >= 0 && col < m && !visited[newRow][col] && map[newRow][col] == '.') { dfs(newRow, col, map, visited); } } for (int j = -1; j <= 1; j++) { int newCol = col + j; if (row >= 0 && row < n && newCol >= 0 && newCol < m && !visited[row][newCol] && map[row][newCol] == '.') { dfs(row, newCol, map, visited); } } } int countRooms(int n, int m, vector<vector<char>> &map, vector<vector<bool>> &visited) { int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!visited[i][j] && map[i][j] == '.') { dfs(i, j, map, visited); cnt++; } } } return cnt; } int main() { int n, m; cin >> n >> m; vector<vector<char>> map(n, vector<char>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } vector<vector<bool>> visited(n, vector<bool>(m, false)); int ans = countRooms(n, m, map, visited); cout << ans << endl; return 0; } B: #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<tuple<int, int, int>> edges; vector<int> dist(n + 1, 30000); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; edges.push_back(make_tuple(u, v, w)); } dist[1] = 0; for (int i = 1; i <= n - 1; i++) { for (const auto& edge : edges) { int u, v, w; tie(u, v, w) = edge; if (dist[u] < 30000) { dist[v] = min(dist[v], dist[u] + w); } } } for (int i = 1; i <= n; i++) { cout << dist[i] << " "; } cout << endl; return 0; } D: #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; unordered_set<string> umap; unordered_set<string> umap2; for (int i = 0; i < n; i++) { string s; cin >> s; if (s[0] == '!') { umap2.insert(s.substr(1)); } else { umap.insert(s); } } string ans = "satisfiable"; for (auto it: umap) { if (umap2.find(it) != umap2.end()) { ans = it; break; } } cout << ans << endl; return 0; } G: #include <bits/stdc++.h> using namespace std; long printResult(long child, long position) { if (child == 1) return 1; if (position <= (child + 1) / 2) { if (2 * position > child) { return (2 * position) % child; } else { return 2 * position; } } else { long temp = printResult(child / 2, position - (child + 1) / 2); if (child % 2 == 1) return 2 * temp + 1; else return 2 * temp - 1; } } int main() { long q; cin >> q; for (int i = 0; i < q; i++) { long child, position; cin >> child >> position; cout << printResult(child, position) << endl; } return 0; } H: #include <iostream> #include <vector> #include <unordered_map> using namespace std; void findPostorder(int preStart, int inStart, int inEnd, vector<int>& preorder, vector<int>& inorder, unordered_map<int, int>& inIndexMap) { if (inStart > inEnd) return; int root = preorder[preStart]; int rootIndex = inIndexMap[root]; int leftSubtreeSize = rootIndex - inStart; findPostorder(preStart + 1, inStart, rootIndex - 1, preorder, inorder, inIndexMap); findPostorder(preStart + leftSubtreeSize + 1, rootIndex + 1, inEnd, preorder, inorder, inIndexMap); cout << root << " "; } int main() { int n; cin >> n; vector<int> preorder(n), inorder(n); unordered_map<int, int> inIndexMap; for (int i = 0; i < n; i++) { cin >> preorder[i]; } for (int i = 0; i < n; i++) { cin >> inorder[i]; inIndexMap[inorder[i]] = i; } findPostorder(0, 0, n - 1, preorder, inorder, inIndexMap); return 0; } I: #include <bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a, ll b) { while (b != 0) { ll temp = b; b = a % b; a = temp; } return a; } pair<ll, ll> parseFraction(string s) { int divPos = s.find('/'); ll num = stoll(s.substr(0, divPos)); ll den = stoll(s.substr(divPos + 1)); return {num, den}; } pair<ll, ll> simplify(ll num, ll den) { ll g = gcd(abs(num), abs(den)); return {num / g, den / g}; } int main() { string x, y; char z; while (cin >> x) { cin >> z >> y; pair<ll, ll> frac1 = parseFraction(x); pair<ll, ll> frac2 = parseFraction(y); ll numX = frac1.first, denX = frac1.second; ll numY = frac2.first, denY = frac2.second; ll commonDen = denX * denY; numX *= denY; numY *= denX; ll numSum = 0; if (z == '+') { numSum = numX + numY; } else if (z == '-') { numSum = numX - numY; } pair<ll, ll> res = simplify(numSum, commonDen); if (res.second < 0) { res.first = -res.first; res.second = -res.second; } cout << res.first << "/" << res.second << endl; } return 0; }
Leave a Comment