AtCoder Beginner Contest 352
Time : 2024-05-04(Sat) 20:00 - 2024-05-04(Sat) 21:40
A AtCoder Line
问题陈述
AtCoder 铁路线有 $N$ 个车站，编号为 $1, 2, \ldots, N$ 。
在这条线路上，有趟进站列车从 $1$ 站出发，依次停靠 $2, 3, \ldots, N$ 站，有趟出站列车从 $N$ 站出发，依次停靠 $N - 1, N - 2, \ldots, 1$ 站。
Takahashi 即将从 $X$ 站前往 $Y$ 站，只需使用进站和出站列车中的一列。
求这趟列车在 $Z$ 站是否停车。
输入
输入内容由标准输入法提供，格式如下
N X Y Z
题解
题意为检查Z是否处于X与Y之间
需根据X与Y的大小来判断乘坐进站列车还是出站列车
void solve() {
cin >> n >> x >> y >> z;
if(x > y)swap(x, y);
cout << (x <= z && z <= y ? "Yes" : "No") << endl;
}
B Typing
问题陈述
Takahashi尝试使用键盘输入由小写英文字母组成的字符串 $S$ 。
他在键入时只看键盘，不看屏幕。
每当他错误地输入一个不同的小写英文字母时，他就立即按下退格键。然而，退格键被破坏了，因此误键入的字母没有被删除，实际键入的字符串是 $T$ 。
他没有误按小写英文字母以外的任何键。
$T$ 中未被误输入的字符称为正确输入字符。
确定正确键入的字符在 $T$ 中的位置。
题解
S为理想输入, T为实际输入
题意为在T与S的字符串匹配, 每次输入S在T中的下标
算法 : 双指针
void solve() {
string s, t;
cin >> s >> t;
for(int i = 0, j = 0; i < t.size() ; i++) {
if(s[j] == t[i])cout << i + 1 << " ", j++;
}
}
C Standing On The Shoulders
问题陈述
有 $N$ 个巨人，他们的名字分别是 $1$ 到 $N$ 。当巨人 $i$ 站在地上时，他们的肩高是 $A_i$ ，头高是 $B_i$ 。
你可以选择 $(1, 2, \ldots, N)$ 的 $(P_1, P_2, \ldots, P_N)$ 排列组合，并根据以下规则堆叠 $N$ 个巨人：
-
首先，将巨人 $P_1$ 放在地上。巨人 $P_1$ 的肩膀距离地面的高度为 $A_{P_1}$ ，头部距离地面的高度为 $B_{P_1}$ 。
-
为了 $i = 1, 2, \ldots, N - 1$ 的顺序，把巨人 $P_{i + 1}$ 放在巨人 $P_i$ 的肩膀上。如果巨人 $P_i$ 的肩膀距离地面的高度是 $t$ ，那么巨人 $P_{i + 1}$ 的肩膀距离地面的高度就是 $t + A_{P_{i + 1}}$ ，他们的头距离地面的高度就是 $t + B_{P_{i + 1}}$ 。
求最上面的巨人 $P_N$ 的头部距离地面的最大可能高度。
题解
总高度为N个巨人的肩高和加上最上方巨人的头高-肩高
总高度最大即最上方巨人头肩高差最大
遍历得最大值即可, 记得开long long
void solve() {
cin >> n;
int sd, hd, mx = -1;
for(int i = 0; i < n; i++) {
cin >> sd >> hd;
res += sd;
mx = max(mx, hd - sd);
}
cout << res + mx << endl;
}
D
问题陈述
题解
题意有点绕人, 简单来说是在 1 ~ N 的排列中找到长度为 k 的下标集合, 使得该下标集合对应的排列集合排序后为k长度的连续序列(a , a + 1 , a + 2 ... a + k - 1), 找到满足该条件下标集合的极差的最小值
一开始半天没读明白题, 觉得答案有单调性决定用二分答案加上滑动窗口来做, 思路不会优化TLE了
看到jiangly大佬有一个很巧妙的做法, 下标和排列P都是1 ~ N, 可以使用数组一一对应存储
使用set维护一个 k 长度的滑动窗口, 遍历 a 来寻找最小值, 具体见代码注释
void solve() {
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> t;
p[t] = i; //存储下标
}
set<int> s;//set集合有序存储滑动窗口中的下标
for(int i = 1; i <= n; i++) { //枚举整数a
s.insert(p[i]);
if(i > k)s.erase(p[i - k]); //滑动窗口
if(i >= k)
ans = min(ans, *s.rbegin() - *s.begin()); //维护最大下标
}
cout << ans;
}
E Clique Connect
问题陈述
题解
很裸的一道求最小生成树题
稠密图, 选用Kruskal算法来完成
题目给定边的时候, 由于边权相等, 可以把给定集合看作一整个连通块, 便只相当于插入了k-1条边
int n, m, k, c, a, root, cnt;
int ans;
int p[N];//并查集维护节点的父节点
struct E {
int a, b, c;
bool operator < (const E& C) {
return c < C.c;
}
} edgs[N * 2];
int find(int u) {
if(u != p[u])p[u] = find(p[u]);
return p[u];
}
int kruskal() {
for(int i = 1; i <= n; i++)p[i] = i;//初始化
int num = 0;//存储最小生成树边的数目
sort(edgs, edgs + cnt);
for(int i = 0; i < cnt; i++) { //枚举edgs
int a = edgs[i].a, b = edgs[i].b, c = edgs[i].c;
if(find(a) != find(b)) { //如果两个节点没有联通(所在连通块根节点不同)
p[find(a)] = find(b);
ans += c;
num++;
}
}
return num;
}
void solve() {
cin >> n >> m;
while(m--) {
cin >> k >> c;//题意即给定含有k个节点的连通块
for(int i = 0; i < k; i++) {
cin >> a;
if(i > 0)
edgs[cnt ++ ] = {root, a, c};//cnt为边的数量
root = a;//以第一个节点为该连通块根节点
}
}
if(kruskal() == n - 1)
cout << ans << endl;
else
cout << -1 << endl;
}
F,G 等待更新...