前言
本来晚上在打Acwing周赛，最后一题Trie想不出来咋写，看群里有人说ABC要开始了，想着没打过ABC就去报了一下，感觉难度大概是cf的Div3到Div4之间吧，总共写了五个题，E题想复杂了快结束才交过。总的来说手速很重要。
Q1 A - CAPS LOCK
题意：给一个字符串，要求把小写字母改成大写。
分析: 循环模拟下就可以了，时间复杂度
O
(
n
)
O(n)
O(n)
void solve()
{
string s;
cin >> s;
for(auto &c : s)
{
if(c >= 'a' && c <= 'z') c += 'A' - 'a';
}
cout << s << endl;
}
Q2 Yellow and Red Card
题意：有n个人，发生过q个事件，每个事件要么是某人领黄牌/红牌/询问某人是否出局，累计获得两张黄牌或者是得到过红牌就会出局。
分析：开一个数组cnt记录即可，黄牌+1， 红牌+2. 大于等于2的就要出局了。时间复杂度
O
(
q
)
O(q)
O(q)
{
cin >> n >> q;
vector<int> cnt(n + 1);
while(q--)
{
int t, x;
cin >> t >> x;
if(t == 1) cnt[x] += 1;
else if(t == 2) cnt[x] += 2;
else cout << (cnt[x] >= 2 ? "Yes" : "No") << endl;
}
}
Q3 Four Variables
题意：问四元组（A， B， C， D）满足AB + CD = n 的个数。
分析：先考虑简单的问题，如果问X + Y = n，求（X， Y）的数量，答案显然。然后再考虑怎么凑成X，就是X的因子对的数量，Y也是同理。设
f
[
x
]
f[x]
f[x]表示x的因子对数量，那么答案就是
f
[
1
]
∗
f
[
n
−
1
]
+
f
[
2
]
∗
f
[
n
−
2
]
+
.
.
.
+
f
[
n
−
1
]
∗
f
[
1
]
。
f[1] * f[n - 1] + f[2] * f[n - 2] + ... + f[n - 1] * f[1]。
f[1]∗f[n−1]+f[2]∗f[n−2]+...+f[n−1]∗f[1]。 时间复杂度
O
(
n
n
)
O(n\sqrt{n})
O(nn)
#define int long long
void solve()
{
cin >> n;
vector<int> f(n + 1);
for(int i = 1; i <= n; ++i)
{
int t = i;
for(int j = 1; j <= t / j; ++j)
if(t % j == 0) f[i] += 1 + (j != t / j);
}
int ans = 0;
for(int i = 1; i <= n; ++i)
{
int j = n - i;
ans += f[i] * f[j];
}
cout << ans << endl;
}
Q4 D - Unicyclic Components
题意：给一张有向图图，询问是否每个连通分量内点的数量都等于边的数量。
分析：据说分别维护点和边的并查集和集合内元素数量的做法可以过，貌似官方给的题解也是这么做的，但是我写的是维护连通块内环的个数。把题目给出的有向图当作无向图，什么时候连通分量里面的点的数量会等于边的数量呢？设点数为
x
x
x, 边数为
y
y
y.如果连通分量内无环，因为各点都连通，所以
y
=
x
−
1
y = x - 1
y=x−1。可以发现如果要让
x
=
=
y
x == y
x==y, 需要在原图上补充一条边，因为原图已经连通，加上的这条边一定会增添一个环。用
c
n
t
cnt
cnt维护并查集集合内环数量，合并
a
,
b
a, b
a,b的时候，如果
a
,
b
a, b
a,b之前不在一个集合内，那么他们环的数量相加（因为此前这两个连通分量并不连通，所以环数量直接相加即可）。如果a, b之前已经在一个集合，那么这个集合的环数量+1. 最后判断每个集合的环数量是否恰好等于1.时间复杂度
O
(
n
)
O(n)
O(n)
/*
* @Author: gorsonpy
* @Date: 2023-03-04 20:21:52
* @LastEditors: gorsonpy
* @LastEditTime: 2023-03-04 20:26:28
* @FilePath: \vscode-c\D_-_Unicyclic_Components.cpp
* @Description:
*/
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
int p[N], cnt[N];
int n, m;
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) p[i] = i, cnt[i] = 0;
while(m--)
{
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if(pa != pb) p[pa] = pb, cnt[pb] += cnt[pa];
else ++cnt[pb];
}
bool ok = true;
for(int i = 1; i <= n; ++i)
if(p[i] == i)
{
if(cnt[i] != 1) ok = false;
}
cout << (ok ? "Yes" : "No") << endl;
return 0;
}
Q5 E - Transitivity
写完D看了一下群，有人说E是搜索。。当时就紧张了因为不太会写搜索，导致把题目想歪了。。其实不用搜索也可以做的，比赛后一个小时都在写E，不过F那个几何去想应该也做不出来吧（
题意：给定一张有向图，每次操作可以加一条边，问最少操作次数，使得对于整张图，若存在a到b的边，存在b到c的边，那么一定也有a到c的边。文章来源：https://www.toymoban.com/news/detail-418732.html
分析：注意到数据规模并不大，只有2000点，2000边。考虑一下暴力做法。实际上，只需要开数组记录对于每个点， 进入他的点集合in， 和他出去的out。 然后循环所有的点i，看每个（x， y)是否有x到y的边，x是进入i的一个点，y是i出去的一个点。如果没边加上就行了，答案加1， 就这么简单。但是可能会想，为什么做一次就可以了？会不会存在比如说第一次加的边引起后续反应了，导致还要再加一轮边？实际上并不会。因为本题除了暴力还有一个性质：在最终的图中，x所直接连的点一定是在原始的图中x所能抵达的点（不一定是直接相连）。反之亦然。这个用归纳法是显然的，因为每次我们添加边（x, y)的时候并没有改变x ->y的可达性。所以这个做法实际上等价于搜索，也就是找原图中点i所能抵达的点p，然后计算i到p路径上的边数量，最后减去原图已有的边。 时间复杂度 O ( n m ) O(nm) O(nm)文章来源地址https://www.toymoban.com/news/detail-418732.html
#define pb push_back
int g[N][N];
void solve()
{
cin >> n >> m;
vector<vector<int>> in(n + 1), out(n + 1);
while(m--)
{
int x, y;
cin >> x >> y;
out[x].pb(y);
in[y].pb(x);
g[x][y] ++;
}
int ans = 0;
for(int i = 1; i <= n; ++i)
{
auto din = in[i], dout = out[i];
for(auto x : din)
for(auto y : dout)
{
if(x == y) continue;
if(!g[x][y])
{
++ans;
g[x][y] ++;
in[y].pb(x);
out[x].pb(y);
}
}
}
cout << ans << endl;
}
到了这里，关于AtCoder Beginner Contest 292 (A - E) 记录第一场ABC的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
