本文主要是介绍Codeforces Round 605 (Div. 3) A~D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本人水平不高，开这个专栏主要是督促自己补题，有些题对目前的我来说还比较难，还补不动，等以后能力上来了再补。。。
原题链接：Dashboard - Codeforces Round 605 (Div. 3) - Codeforces
目录
A. Three Friends
B. Snow Walking Robot
C. Yet Another Broken Keyboard
D. Remove One Element
A. Three Friends
让三个人尽可能接近，让左边的人和右边的人尽量往中间靠，a与b的距离| a-b |会减1，b与c的距离| b-c |也会 减1，而a与c的距离| a-c |会 减2。但是又因为是三个绝对值的式子相加，所以这三个式子之和必然大于等于0，取max(0ll,abs(a-b)+abs(b-c)+abs(a-c)-4) 即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'void solve() {int a, b, c; cin >> a >> b >> c;cout << max(0ll, abs(a - b) + abs(b - c) + abs(a - c) - 4) << endl;
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T; cin >> T;while (T--) {solve();}return 0;
}B. Snow Walking Robot
让机器人走一个（先向左再向上再向右再向下的）L—>U—>R—>D的矩形即可。
选择矩形的原因是“凹”形（下图左半部分）相比于与其效果相同的矩形，浪费了两个AB的长度。而“凸”形（下图右半部分）等价于虚线的矩形，而矩形比“凸”形简单，所以选择矩形。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'void solve() {string s; cin >> s;int l=0, r=0, u=0, d = 0;for (auto i : s) {if (i == 'L') l++;else if (i == 'R') r++;else if (i == 'U') u++;else if (i == 'D') d++;}int x = min(l, r), y = min(u, d);if (x && y) {cout << 2 * x + 2 * y << endl;for (int i = 1; i <= x; i++) cout << 'L';for (int i = 1; i <= y; i++) cout << 'U';for (int i = 1; i <= x; i++) cout << 'R';for (int i = 1; i <= y; i++) cout << 'D';}else if (x) {cout << 2 << endl << "LR";}else if (y) {cout << 2 << endl << "UD";}else if (x == 0 && y == 0) {cout << 0 << endl;}cout << endl;
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T; cin >> T;while (T--) {solve();}return 0;
}C. Yet Another Broken Keyboard
写法一：
开一个标记数组f[26]表示从'a'~'z’的字母是否是好的，如果是好的标记为1，否则为0。
遍历字符串s，开一个计数的变量cnt，初始化为0。当遇到好的字母（也就是f[s[i]-'a']为1），让cnt++。否则让ans+=cnt*(cnt+1)/2，并重新让cnt=0。因为末尾的那段不会在循环中被累加，所以在循环外我们还需要让ans再累加一次cnt*(cnt+1))/2 。
写法二：
可以用set代替标记数组。一开始将好的字母都存到set，后面使用set的s.find()函数（s.find() !=s.end() ）来判断字符串中的字母是否是好的。
写法一代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int f[26];signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, k; cin >> n >> k;string s; cin >> s;while (k--) {char c; cin >> c;f[c - 'a' ] = 1;}int cnt = 0, ans = 0;;for (int i = 0; i < n; i++) {if (f[s[i]-'a']) {cnt++;}else {ans += cnt * (cnt + 1) / 2;cnt = 0;}}ans += cnt * (cnt + 1) / 2;cout << ans << endl;return 0;
}写法二代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
set<char> a;signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, k; cin >> n >> k;string s; cin >> s;while (k--) {char c; cin >> c;a.insert(c);}int cnt = 0, ans = 0;;for (int i = 0; i < n; i++) {if (a.find(s[i]) != a.end()) {cnt++;}else {ans += cnt * (cnt + 1) / 2;cnt = 0;}}ans += cnt * (cnt + 1) / 2;cout << ans << endl;return 0;
}D. Remove One Element
既然是求最长上升子序列，那必然是dp。由题意知，可以删除一个或者不删除。
1. 如果不删除，就是最长连续上升子段：
for(int i = 1;i <= n;i++) {
if(a[i] > a[i - 1]) dp1[i] = dp1[i - 1] + 1;
else dp1[i] = 1;
}
for(int i = n;i >= 1;i--){
if(a[i] < a[i + 1]) dp2[i] = dp2[i + 1] + 1;
else dp2[i] = 1;
}
2. 如果要删除，我们就枚举要删除的数：
枚举下标i，如果删除掉 i 时，剩下的能连续（a[i-1]<a[i+1]），我们就可以将以a[i-1]为结尾最长连续上升子段和以a[i+1]为开头最长连续上升子段连接起来，长度为dp1[i-1] + dp2[i+1]。
注意事项：
1. 要求的是最长连续上升子段，而不是最长连续不下降子段（也就是1 1 1 1 这个最长子段长度为1）
2. 也可以不用删除数。（1 2 3 4 这个最长子段长度为4）
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 2e5 + 10;
int a[N], dp1[N], dp2[N], ans;signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) {if (a[i] > a[i - 1]) dp1[i] = dp1[i - 1] + 1;else dp1[i] = 1;}for (int i = n; i >= 1; i--) {if (a[i] < a[i + 1]) dp2[i] = dp2[i + 1] + 1;else dp2[i] = 1;}for (int i = 1; i <= n; i++) {if (a[i - 1] < a[i + 1]) ans = max(ans, dp1[i - 1] + dp2[i + 1]);else ans = max({ ans,dp1[i],dp2[i] });}cout << ans << endl;return 0;
}这篇关于Codeforces Round 605 (Div. 3) A~D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
