Codeforces Round #753 (Div. 3)
A. Linear Keyboard
思路分析：
- 无语了，题目总是读不顺，看到output那个minimal我还以为是把手放到一个单词上，看需要多少time来完成敲出字符串。
- 写完一看，答案不对劲，然后发现这题其实就是把字母表重新排一下，然后求两个字母间的距离之差的绝对值。
代码
#include <bits/stdc++.h>
using namespace std;
map<char, int> mp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
for (int i = 0; i < s.size(); i++)
{
mp[s[i]] = i + 1;
}
string t;
cin >> t;
int ans = 0;
for (int i = 1; i < t.size(); i++)
{
ans += abs(mp[t[i]] - mp[t[i - 1]]);
}
cout << ans << endl;
}
return 0;
}
B. Odd Grasshopper
思路分析：
- 这个题目其实是找规律题，并且只和一开始给你的第一个值的奇偶有关。
- 如果给你的是偶数，那么就是-，+，+，-，-，+，+，-，-......
- 如果给你的是奇数，那么就是+，-，-，+，+，-，-，+，+......
- 我们可以看出除了第一个之外，后面每四个加起来都有规律，偶数时是-4，奇数时是4......
- 然后就是分析剩下来不能成为一组的，那么找一下规律即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
ll x, n;
cin >> x >> n;
if (n == 0)
{
cout << x << endl;
}
else
{
if (x % 2 == 0)
{
x--;
n--;
x = x + n / 4 * (-4);
if (n % 4 == 0)
{
cout << x << endl;
}
else if (n % 4 == 1)
{
x += (n + 1);
cout << x << endl;
}
else if (n % 4 == 2)
{
x += (2 * n + 1);
cout << x << endl;
}
else if (n % 4 == 3)
{
x += (n - 2);
cout << x << endl;
}
}
else
{
x++;
n--;
x = x + n / 4 * 4;
if (n % 4 == 0)
{
cout << x << endl;
}
else if (n % 4 == 1)
{
x -= (n + 1);
cout << x << endl;
}
else if (n % 4 == 2)
{
x -= (2 * n + 1);
cout << x << endl;
}
else if (n % 4 == 3)
{
x -= (n - 2);
cout << x << endl;
}
}
}
}
return 0;
}
C. Minimum Extraction
思路分析：
- 我们要求的是在删减过程中数组最小值的最大值。
- 首先我们肯定是要排序的，然后依次求最小值出来，可以肯定的是我们从最小的开始选的话，在这个过程中每个数都会减去之前删的那个数，在删到某个数前，它必然会变成他和前面那个数的差值，因为，我们从第一个开始，到删到它前面一个数时，这两个数的差值一直没变，所以最大的最小值其实就是排序后的数组的两两相邻数的差值的最大值。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
int ans = -1000000001;
for (int i = 1; i <= n; i++)
{
ans = max(ans, a[i] - a[i - 1]);
}
cout << ans << endl;
}
return 0;
}
D. Blue-Red Permutation
思路分析：
- 这个题目其实就是贪心，我们这样想，先把blue颜色的num放到前面，因为它们只能变小或者不变而不能变大，我们要得到的是一个\(1 - n\)的排列，也就是说得到的数组的值中\(1 - n\)这些数必然出现并且一个只出现一次。
- 那么我们把可以变小的num先放到前面（同颜色的按值大小排序，显然值越小越排到前面）。
- 然后就是定义一个tmp来表示当前要造的数，如果我们遍历数组时，它比tmp大而且它只能变大，那肯定就是不对的、如果它比tmp小并且它只能变小，也是不对的。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
struct node
{
int val;
char ch;
} a[maxn];
bool cmp(node a, node b)
{
if (a.ch != b.ch)
return a.ch < b.ch;
return a.val < b.val;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].val;
}
for (int i = 1; i <= n; i++)
{
cin >> a[i].ch;
}
sort(a + 1, a + 1 + n, cmp);
bool flag = 1;
int tmp = 1;
for (int i = 1; i <= n; i++)
{
if (a[i].val < tmp && a[i].ch == 'B')
{
flag = 0;
break;
}
else if (a[i].val > tmp && a[i].ch == 'R')
{
flag = 0;
break;
}
else
{
tmp++;
}
}
if (flag)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}
E. Robot on the Board 1
思路分析：
- 这题是看dalao代码学的，首先我们可以这样想，我们拿出四根线，分别放置在矩阵上下左右外，也就是放在外面，然后每次我们都更新一下上下左右边界，记录边界。
- 然后就是什么时候输出，第一种情况当然是现在左右（上下）边界相差大于\(2\)（那么我们只需要选上左边界相夹的那一块的坐标即可。），第二种情况就是至少有两个边界（l和r 或者 u和d）相差为\(1\)了，那么这个时候我们不能再更新答案了，因为那两个边界中间已经没有块可选了，所以只要输出上一次的答案即可。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
string s;
cin >> s;
pair<int, int> a;
a = {1, 1};
bool flag = 0;
int l = 0, r = m + 1, u = 0, d = n + 1;
int suml = 0, sumr = 0, sumu = 0, sumd = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == 'R')
{
sumr++;
}
else if (s[i] == 'L')
{
suml++;
}
else if (s[i] == 'U')
{
sumu++;
}
else if (s[i] == 'D')
{
sumd++;
}
l = max(l, suml - sumr);
r = min(r, m + 1 - (sumr - suml));
u = max(u, sumu - sumd);
d = min(d, n + 1 - (sumd - sumu));
if (l + 1 >= r || u + 1 >= d)
{
flag = 1;
cout << a.first << ' ' << a.second << endl;
break;
}
else
{
a = {u + 1, l + 1};
}
}
if (!flag)
cout << a.first << " " << a.second << endl;
}
return 0;
}