AtCoder Beginner Contest 302
A - Attack (abc302 a)
题目大意
给定怪物的血量\(a\)和你每次攻击扣除的血量 \(b\)，问打多少次怪物才会死。
解题思路
答案即为\(\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b - 1}{b} \rfloor\)
神奇的代码
#include <bits/stdc++.h>
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 <bits/stdc++.h>
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<string> a(h);
for(auto &i : a)
cin >> i;
string target = "snuke";
vector<array<int, 2>> ans;
auto check = [&](int x, int y, int dx, int dy){
vector<array<int, 2>> tmp;
for(int i = 0; i < target.size(); ++ i){
if (x >= h || x < 0 || y >= 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 <bits/stdc++.h>
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<string> s(n);
for(auto &i : s)
cin >> i;
vector<int> 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 <bits/stdc++.h>
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<LL> 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 <bits/stdc++.h>
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<int> du(n, 0);
vector<vector<int>> 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<int, 2>> 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 <bits/stdc++.h>
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<int, 2>>> edge(n + m);
for(int i = 0; i < n; ++ i){
int x;
cin >> x;
while(x--){
int v;
cin >> v;
-- v;
edge[v].push_back({m + i, 1});
edge[m + i].push_back({v, 0});
}
}
vector<int> dis(n + m, inf);
dis[0] = 0;
queue<array<int, 2>> 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\)的最短路径途径的每个点中，各选一个数，其不同数的个数的最大值。
解题思路
<++>
神奇的代码