A – Attack (abc302 a)题目大意
给定怪物的血量\(a\)和你每次攻击扣除的血量 \(b\)，问打多少次怪物才会死。
解题思路
答案即为\(\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b – 1}{b} \rfloor\)
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); LL a, b; cin >> a >> b; cout << (a + b - 1) / b << '\n'; return 0;}B – Find snuke (abc302 b)题目大意
给定一个二维网格，格子上有字母，找到一连串位置，使得其字符串为\(snuke\)，要求这一连串位置俩俩相邻，即有共边或共点。这意味着可以横竖对角线。
解题思路
枚举起点，枚举方向（8个方向），依次判断即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int h, w; cin >> h >> w; vector a(h); for(auto &i : a) cin >> i; string target = "snuke"; vector<array> ans; auto check = [&](int x, int y, int dx, int dy){ vector<array> tmp; for(int i = 0; i = h || x = w || y < 0) return false; if (a[x][y] != target[i]) return false; tmp.push_back({x, y}); x += dx; y += dy; } ans = tmp; return true; }; auto solve = [&](){ for(int i = 0; i < h; ++ i){ for(int j = 0; j < w; ++ j){ for(int x = -1; x <= 1; ++ x) for(int y = -1; y <= 1; ++ y){ if (x == 0 && y == 0) continue; if (check(i, j, x, y)){ return; } } } } }; solve(); for(auto &i : ans) cout << i[0] + 1 << ' ' << i[1] + 1 << '\n'; return 0;}C – Almost Equal (abc302 c)题目大意
给定\(n\)个字符串，问能否排个序，使得俩俩字符串恰好仅一个位置上的字母不同。
解题思路
范围不大，直接\(O(n!)\)枚举排序，再 \(O(nm)\)判断即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector s(n); for(auto &i : s) cin >> i; vector id(n); iota(id.begin(), id.end(), 0); auto check = [&](){ do{ bool ok = true; for(int i = 0; i < n - 1; ++ i){ int x = id[i], y = id[i + 1]; int cnt = 0; for(int j = 0; j < m; ++ j) cnt += (s[x][j] != s[y][j]); if (cnt != 1){ ok = false; break; } } if (ok) return true; }while(next_permutation(id.begin(), id.end())); return false; }; if (check()) cout << "Yes" << '\n'; else cout << "No" << '\n'; return 0;}D – Impartial Gift (abc302 d)题目大意
给定两个数组\(a,b\)，要求从中各选一个数，使得俩数的差值不超过 \(d\)，问俩数和的最大值。
解题思路
先排个序，然后枚举\(a\)的每个数，在\(b\)中找到第一个不大于 \(a+d\)的值 ，然后取最大值即可。因为排了序，可以二分找，也可以因为枚举的\(a\)是递增的，一个指针从\(b\)中一路扫过去。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; LL d; cin >> n >> m >> d; vector a(n), b(m); for(auto &i : a) cin >> i; for(auto &i : b) cin >> i; sort(a.begin(), a.end()); sort(b.begin(), b.end()); int pos = 0; LL ans = -1; for(int i = 0; i < n; ++ i){ while(pos < m && b[pos] - a[i] <= d){ ++ pos; } if (pos != 0 && abs(a[i] - b[pos - 1]) <= d){ ans = max(ans, a[i] + b[pos - 1]); } } cout << ans << '\n'; return 0;}E – Isolation (abc302 e)题目大意
给定一张图，\(n\)个点，无边。有以下两种操作：
1 u v，为\(u, v\)连一条边2 u，删除与\(u\)相连的每条边
对于每个操作，输出孤立点数量，即度数为 \(0\)的数量。
解题思路
按照上述题意模拟即可，每条边只会添加一次，删除一次，因此复杂度为\(O(q)\)。
因为存的是双向边，删\(u\)的边时，比如删除的边是 \((u,v)\)，要避免在删 \(v\)的边时将 \((u,v)\)再删一次，因此用了一个 \(set\)记录当前的边，其中规定了编号小的在前。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vector du(n, 0); vector<vector> edge(n); int ans = n; auto add = [&](int x){ if (du[x] == 0) -- ans; du[x] ++; }; auto mine = [&](int x){ if (du[x] == 1) ++ ans; du[x] --; }; set<array> edges; while(q--){ int op; cin >> op; if (op == 1){ int u, v; cin >> u >> v; -- u, -- v; edge[u].push_back(v); edge[v].push_back(u); add(u); add(v); int minn = min(u, v), maxx = u + v - minn; edges.insert({minn, maxx}); }else{ int u; cin >> u; -- u; for(auto &v : edge[u]){ int minn = min(u, v), maxx = u + v - minn; auto it = edges.find({minn, maxx}); if (it != edges.end()){ edges.erase(it); mine(u); mine(v); } edge[u].clear(); } } cout << ans << '\n'; } return 0;}F – Merge Set (abc302 f)题目大意
给定\(n\)个集合，每个集合包含了 \(1 \sim m\)的一些数。可以进行一种操作，选择两个交集不为空的集合，得到它们的并集。
问最少进行多少次操作，可以得到一个包含 \(1\)和 \(m\)的集合。
解题思路
集合与集合之间，根据交集不为空的关系，有连边。但由于\(n\)有 \(10^5\)的大小，因此不能 \(O(n^2)\)建边。
但由于所有集合的所有数加起来只有 \(5e5\)，如果一个集合 \(i\)有数字 \(j\)，我们可以 连一条\(i \to j\)的边，让数字 \(j\)充当集合与集合之间的中介。这样边数只有 \(5e5\)条。
即有两类点，一类是表示集合的点，一类是表示数字的点，集合\(\to\)数字的边权为 \(0\)，数字\(\to\)集合的边权为 \(1\) 。
答案就是从\(1\)号点到 \(m\)号点的最短路距离减一。
因为边权只有 \(0\)和 \(1\)，且在搜索时边权是交替出现的，所以直接 \(BFS\)即可。
神奇的代码
#include using namespace std;using LL = long long;const int inf = 1e9 + 7;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<vector<array>> edge(n + m); for(int i = 0; i > x; while(x--){ int v; cin >> v; -- v; edge[v].push_back({m + i, 1}); edge[m + i].push_back({v, 0}); } } vector dis(n + m, inf); dis[0] = 0; queue<array> team; team.push({dis[0], 0}); while(!team.empty()){ auto [expect, u] = team.front(); team.pop(); for(auto &[v, w] : edge[u]){ if (dis[u] + w < dis[v]){ dis[v] = dis[u] + w; team.push({dis[v], v}); } } } if (dis[m - 1] == inf) dis[m - 1] = 0; cout << dis[m - 1] - 1 << '\n'; return 0;}G – Sort from 1 to 4 (abc302 g)题目大意
给定一个仅包含\(1,2,3,4\)的数组，一次操作可以交换任意两个数。
问最少进行多少次交换，使得数组不严格升序。
解题思路
神奇的代码
Ex – Ball Collector (abc302 h)题目大意
给定一棵树，每个点有两个值。
对于\(v = 2,3,…,n\) ，问从点\(1\)到点 \(v\)的最短路径途径的每个点中，各选一个数，其不同数的个数的最大值。
解题思路
神奇的代码