感觉手速场，后 \(80\) 分钟纯纯坐牢，
A - First Player
一些人坐成一个环，从年龄最小开始输出名字
const int N = 2e5 + 10;
int n;
string s[N];
int a[N];
void solve()
{
int m = 1e9 + 2, p = 1;
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>s[i]>>a[i];
if(m > a[i])
m = a[i], p = i;
}
for(int i = p; i <= n; i++)
cout<<s[i]<<'\n';
for(int i = 1; i <= p - 1; i++)
cout<<s[i]<<'\n';
return;
}
B - Subscribers
对在范围内的数，将后几位变为0
void solve()
{
int n;
cin>>n;
if(n <= 1e3 - 1)
cout<<n<<endl;
else if(n <= 1e4 - 1)
cout<<n / 10 * 10<<endl;
else if(n <= 1e5 - 1)
cout<<n / 100 * 100<<endl;
else if(n <= 1e6 - 1)
cout<<n / 1000 * 1000<<endl;
else if(n <= 1e7 - 1)
cout<<n / 10000 * 10000<<endl;
else if(n <= 1e8 - 1)
cout<<n / 100000 * 100000<<endl;
else if(n <= 1e9 - 1)
cout<<n / 1000000 * 1000000<<endl;
return;
}
C - Virus
染病毒的点可以传染给欧几里得距离小于等于 \(d\) 的点，并查集 + 暴力dfs即可
int n, d, fa[N];
vector<pair<int, int>> a(2001);
int find(int x)
{
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
void dfs(int u)
{
int fu = fa[u];
for(int i = 1; i <= n; i++)
{
int fv = find(i);
int dis = (a[u].first - a[i].first) * (a[u].first - a[i].first) +
(a[u].second - a[i].second) * (a[u].second - a[i].second);
if(fu != fv && i != u && dis <= d)
{
fa[fv] = fu;
dfs(i);
}
}
}
void solve()
{
cin>>n>>d;
d = d * d;
for(int i = 1; i <= n; i++)
{
fa[i] = i;
int x, y; cin>>x>>y;
a[i] = {x, y};
}
dfs(1);
for(int i = 1; i <= n; i++)
if(find(i) == 1)
cout<<"Yes\n";
else
cout<<"No\n";
return;
}
D - A Piece of Cake
如何确定这块蛋糕有没有草莓，草莓左边的竖直方向切了一刀，上边的水平方向切了一刀，通过二分查找出分别是哪刀切的,通过竖直的刀和水平的刀确定这个蛋糕块，用个map<array<int, 2>, int> mp;记录，并将贡献加1。最后判断 \(\text{map.size()} = (A + 1) \times(B + 1)\)， 若相等，最小值为map中 \(\min\text{key}\)，否则为 \(0\)，最大值为 \(\max\text{key}\)
int n, m, k, a, b;
map<array<int, 2>, int> mp;
vector<pair<int, int>> p;
vector<int> A, B;
void solve()
{
cin>>n>>m>>k;
for(int i = 1; i <= k; i++)
{
int x, y; cin>>x>>y;
p.push_back({x, y});
}
cin>>a;
A.push_back(0), A.push_back(n);
for(int i = 1; i <= a; i++)
{
int x; cin>>x;
A.push_back(x);
}
cin>>b;
B.push_back(0), B.push_back(m);
for(int i = 1; i <= b; i++)
{
int x; cin>>x;
B.push_back(x);
}
sort(A.begin(), A.end()); sort(B.begin(), B.end());
for(auto &it : p)
{
int p1 = *lower_bound(A.begin(), A.end(), it.first);
int p3 = *lower_bound(B.begin(), B.end(), it.second);
array<int, 2> q = {p1, p3};
mp[q]++;
}
int r1 = 1e9, r2 = 0;
if((ll)mp.size() < (a + 1) * 1ll * (b + 1))
r1 = 0;
else
for(auto &it : mp)
r1 = min(r1, it.second);
for(auto &it : mp)
r2 = max(r2, it.second);
cout<<r1<<" "<<r2<<'\n';
return;
}
E - Good Graph
已给出好图，通过并查集确定各个连通块集合及编号。给出约束，两点不能有路径到达，用 \(\text{set}\) 记录两点分别属于哪个连通块。给出询问 \(u\), \(v\)；若 \(find(u)\) 与 \(find(v)\) 在 \(\text{set}\) 出现过，则输出\(\text{No}\) ，否则输出\(\text{Yes}\)。
int n, m, k, q, fa[N];
vector<int> e[N];
set<pair<int, int>> S;
int find(int x)
{
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
fa[i] = i;
for(int i = 1; i <= m; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
int fu = find(u), fv = find(v);
if(fu != fv)
fa[fu] = fv;
}
cin>>k;
for(int i = 1; i <= k; i++)
{
int u, v; cin>>u>>v;
int fu = find(u), fv = find(v);
S.insert({fu, fv}); S.insert({fv, fu});
}
cin>>q;
for(int i = 1; i <= q; i++)
{
int u, v; cin>>u>>v;
int fu = find(u), fv = find(v);
if(S.count({fu, fv}))
cout<<"No\n";
else
cout<<"Yes\n";
}
return;
}
F - Shift Table
等等
标签：AtCoder,fu,int,ABCDE,304,back,fa,push,find From： https://www.cnblogs.com/magicat/p/17455486.html