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)
题目大意
<++>
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 304beginner atcoder contest 304 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315 beginner atcoder contest 334