A - First Player (abc304 a)
題目大意
依次給定每個人的姓名和年齡，排成一圈，從年齡最小的人依次輸出姓名，
解題思路
找到年齡最小的，依次輸出就好了，
神奇的代碼
#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;
cin >> n;
vector<pair<int, string>> p(n);
for(auto &i : p)
cin >> i.second >> i.first;
int st = min_element(p.begin(), p.end()) - p.begin();
for(int i = 0; i < n; ++ i){
cout << p[st].second << '\n';
st = (st + 1) % n;
}
return 0;
}
B - Subscribers (abc304 b)
題目大意
給定一個數字，如果其超過三位數，則僅保留其最高三位，低位數字全部置為0，
解題思路
讀一個string，直接賦值即可，
神奇的代碼
#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);
string s;
cin >> s;
if (s.size() > 3)
fill(s.begin() + 3, s.end(), '0');
cout << s << '\n';
return 0;
}
C - Virus (abc304 c)
題目大意
給定\(n\)個人的坐標，第一個人陽了，若兩人的歐式距離\(\leq d\)，其中有一個陽了，則另一個也會陽，然后繼續傳染，
問最終每個人是否陽了，
解題思路
從第一個人直接\(BFS\)即可，時間復雜度為 \(O(n^2)\)，
神奇的代碼
#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, d;
cin >> n >> d;
d *= d;
vector<array<int, 2>> p(n);
for(auto &i : p)
cin >> i[0] >> i[1];
vector<int> ans(n, 0);
ans[0] = 1;
queue<int> team;
team.push(0);
auto dis = [&](int x, int y){
return (p[x][0] - p[y][0]) * (p[x][0] - p[y][0]) + (p[x][1] - p[y][1]) * (p[x][1] - p[y][1]);
};
while(!team.empty()){
int u = team.front();
team.pop();
for(int i = 0; i < n; ++ i){
if (ans[i])
continue;
if (dis(i, u) <= d){
ans[i] = 1;
team.push(i);
}
}
}
for(int i = 0; i < n; ++ i)
if (ans[i])
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
D - A Piece of Cake (abc304 d)
題目大意
一個\(h \times w\)的蛋糕，給定 \(n\)個草莓的位置，然后豎切 \(a\)刀，橫切 \(b\)刀，給定切的位置，問切出來的 \((a+1)(b+1)\)塊蛋糕中，草莓數量最少和最多分別是多少，不會把草莓切成兩半，
解題思路
\(a \times b \leq 4e10\)，因此不能考慮每塊蛋糕，但我們可以考慮每個草莓對蛋糕的貢獻，
根據草莓的位置，每個草莓僅對一塊蛋糕有貢獻，因此我們就遍歷每塊草莓，令其對應蛋糕的草莓數加一，而求是哪塊蛋糕，其實就看它位于哪一刀的右邊和上邊（左下坐標原點）即可，二分就可以找到，
最后看最大值和最小值即可，因為蛋糕的草莓數量是稀疏的，我們可以用 map記錄，最后看map里的元素個數是否等于\((a+1)(b+1)\)，不等于說明有的蛋糕沒有草莓，
神奇的代碼
#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 w, h, n, a, b;
cin >> w >> h >> n;
vector<array<int, 2>> s(n);
for(auto &i : s)
cin >> i[0] >> i[1];
cin >> a;
vector<int> vec(a);
for(auto &i : vec)
cin >> i;
cin >> b;
vector<int> hor(b);
for(auto &i : hor)
cin >> i;
map<LL, int> cnt;
int minn = n + 1, maxx = 0;
auto check = [&](int x, int y){
int pos1 = upper_bound(vec.begin(), vec.end(), x) - vec.begin();
int pos2 = upper_bound(hor.begin(), hor.end(), y) - hor.begin();
return 1ll * (a + 1) * pos2 + pos1;
};
for(auto &[x, y]: s){
LL id = check(x, y);
cnt[id] ++;
}
for(auto &[_, v] : cnt){
minn = min(minn, v);
maxx = max(maxx, v);
}
if (cnt.size() < 1ull * (a + 1) * (b + 1))
minn = 0;
cout << minn << ' ' << maxx << '\n';
return 0;
}
E - Good Graph (abc304 e)
題目大意
給定一張無向圖，有\(k\)個限制，第 \(i\)個限制表示 點\(x_i\)和 點\(y_i\) 不能相互到達，原圖滿足這\(k\)條限制，
依次回答\(q\)個獨立的詢問，每個詢問添加一條邊\((u,v)\)后，是否還滿足這 \(k\)個限制，
解題思路
題意相當于給了若干個連通塊，然后要求一些連通塊之間不能相互到達，然后問增加的邊，是否導致兩個不該連通的連通塊連通，
那就給每個連通塊標個號，然后把不能連通的連通塊編號用set存起來，每個詢問就問這條邊的兩個點所在的連通塊標號是否在這個set里即可，
連通塊標號、查點所在的連通塊，用并查集即可，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
dsu d(n);
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
d.unite(u, v);
}
int k;
cin >> k;
set<array<int, 2>> forbid;
for(int i = 0; i < k; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
int fu = d.get(u), fv = d.get(v);
assert(fu != fv);
if (fu > fv)
swap(fu, fv);
forbid.insert({fu, fv});
}
int q;
cin >> q;
while(q--){
int u, v;
cin >> u >> v;
-- u, -- v;
int fu = d.get(u), fv = d.get(v);
if (fu > fv)
swap(fu, fv);
if (forbid.find({fu, fv}) == forbid.end()){
cout << "Yes" << '\n';
}else{
cout << "No" << '\n';
}
}
return 0;
}
F - Shift Table (abc304 f)
題目大意
給定高橋的\(n\)天值班情況，
問滿足下述條件的青木的\(n\)天值班情況數量，滿足每天他倆至少有一人值班，且青木的值班情況是關于\(m | n\)回圈的，其中 \(m < n\)，
解題思路
<++>
神奇的代碼
G - Max of Medians (abc304 g)
題目大意
<++>
解題思路
<++>
神奇的代碼
Ex - Constrained Topological Sort (abc304 h)
題目大意
<++>
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554236.html
標籤：其他
上一篇：7.1. JDBC簡介
下一篇：返回列表