AtCoder Beginner Contest 352题解

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++) { //枚举整数as.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++) { //枚举edgsint 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;elsecout << -1 << endl;}

F,G 等待更新...