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\)的最短路徑途徑的每個點中，各選一個數，其不同數的個數的最大值，
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/552978.html
標籤：其他
上一篇：Codeforces Round 874 (Div. 3)
下一篇：返回列表