AtCoder Regular Contest 170 A~D

本文主要是介绍AtCoder Regular Contest 170 A~D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.Yet Another AB Problem（贪心）

题意：

给定两个字符串$S$，$T$，可以对$S$进行如下操作：选择两个字符，将前面的改为$A$，后面的改为$B$，询问至少需要几次可以将$S$变为$T$，如果不能，输出$-1$。

分析：

分类讨论，如果$S_i=A$，$T_i=B$，在$T$字符串中$i$位置前一定要有$T_j=A$，否则无法修改。如果$S_i=B$，$T_i=A$，在$T$字符串中$i$位置后一定要有$T_j=B$，否则无法修改，如果$S$之后存在$S_j=A$，$T_j=B$，可以做到一次修改完成两次对应。贪心进行修改即可。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
int sum[maxn];int main() {int n;string s, t;cin >> n >> s >> t;queue<int> q;for (int i = 0; i < n; i++) {if (t[i] == 'B' and s[i] == 'A')q.push(i);}for (int i = n - 1; i >= 0; i--) {if (t[i] == 'B')sum[i]++;if (i >= 1)sum[i - 1] = sum[i];}int num = 0, ans = 0, flag = 0;for (int i = 0; i < n; i++) {if (t[i] == 'A')num++;if (s[i] != t[i]) {if (s[i] == 'A') {if (!num) {cout << -1 << endl;flag = 1;break;}ans++;} else {if (!sum[i + 1]) {cout << -1 << endl;flag = 1;break;}ans++;while (!q.empty() && q.front() < i)q.pop();if (!q.empty()) {s[q.front()] = 'B';q.pop();}}}}if (!flag)cout << ans << endl;return 0;
}

B.Arithmetic Progression Subsequence（思维）

题意：

给出一个长度为$n$的序列$a$，$a_i$是$1-10$的任意数字，一个区间$[l,r]$被认为是好区间当且仅当满足以下条件：

• 存在三元组$(i,j,k)$ $(l\le i<j<k\le r)$，满足$a_j-a_i=a_k-a_j$

询问好区间的数量。

分析：

对于一个固定的左端点$i$，如果$k$越小，包含这个三元组的区间将会越多。遍历每一个$a_i$，枚举$a_j$的值，再通过差值找出符合条件的最小的$k$，$k$可以通过维护$next1[i][j]$ 即下标$j$之后第一个数字$i$的位置求得。将每一个$i$所对应的最小$k$存入$r_i$，相加即可。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int a[N], next1[13][N], r[N];
vector<int> pos[13];
vector<array<int, 3>> num;int main() {int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];pos[a[i]].push_back(i);}for (int d = 0; d <= 10; ++d) {for (int i = 1; i + 2 * d <= 10; ++i) {num.push_back({i, i + d, i + 2 * d});if (d)num.push_back({i + 2 * d, i + d, i});}}for (int i = 1; i <= 10; ++i) {next1[i][n + 1] = n + 1;for (int j = n; j >= 1; --j) {if (a[j + 1] == i)next1[i][j] = j + 1;elsenext1[i][j] = next1[i][j + 1];}}for (int i = 1; i <= n; ++i)r[i] = n + 1;for (auto &[x, y, z]: num) {for (auto p: pos[x]) {int id = p;id = next1[y][id];id = next1[z][id];if (id <= n)r[p] = min(r[p], id);}}for (int i = n - 1; i >= 1; --i)r[i] = min(r[i], r[i + 1]);LL ans = 0;for (int i = 1; i <= n; ++i)ans += n - r[i] + 1;cout << ans << endl;return 0;
}

C.Prefix Mex Sequence（dp）

题意：

给出一个长度为$n$的序列$s$，$s_i=0$或者$s_i=1$。
询问满足以下条件的序列$a$的数量：

• 如果$s_i=1,a_i=mex(a_1,a_2\dots a_{i-1})$

• 如果$s_i=0,a_i\ne mex(a_1,a_2\dots a_{i-1})$

请将答案对$998244353$取模。

分析：

$f[i][j]$表示序列$a$前$i-1$个元素，一共使用了$j$种不同元素的方案数。

• $s_i=1:f[i][j]=f[i-1][j-1]$ 填入一个新的数字。

• $s_i=0:$ 分两种情况：

  • 填入的这个数字在之前没有出现过，除去前缀$mex$不可以选，那么还剩下$(m-j+1)$种数字。$f[i][j]=f[i-1][j-1]\times (m-j+1)$。
  • 填入的数字之前出现过，$f[i][j]=f[i-1][j]\times j$。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int mod = 998244353;
const int N = 5e3 + 5;
int s[N];
LL f[N][N];int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i)cin >> s[i];int k = min(n, m + 1);f[0][0] = 1;for (int i = 1; i <= n; ++i) {if (s[i]) {for (int j = 1; j <= k; ++j) {f[i][j] = f[i - 1][j - 1];}} else {for (int j = 0; j <= k; ++j) {if (j)f[i][j] = (f[i][j] + (m - j + 1) * f[i - 1][j - 1]) % mod;f[i][j] = (f[i][j] + j * f[i - 1][j]) % mod;}}}LL ans = 0;for (int i = 0; i <= k; ++i)ans = (ans + f[n][i]) % mod;cout << ans << endl;return 0;
}

D Triangle Card Game（博弈）

题意：

给出两个数组$A$，$B$，询问$B$数组中是否存在一个数字使得无论从$A$数组中取出哪两个数字都无法组成三角形，如果存在这样的数字，Bob获胜，否则Alice获胜。

分析：

先将$A$，$B$从大到小排序，设$A$数组中取出的第一个数字为$x$，第二个数字为$z$，$B$数组中取出的数字为$y$。

当$y<x$时，组成三角形的条件为$y+z>x$或者$x+y>z$，对于Bob来说，选择最小的$y$更不容易组成三角形。所以Bob会选择$b_1$。

当$x\le y$时，组成三角形的条件为$x+y>z$或者$x+z>y$，那么组不成三角形的条件变为$min|y-z|\ge x$，利用双指针进行维护。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int mod = 998244353;
const int N = 2e5 + 5;
int a[N], b[N], v[N];int main() {int t;cin >> t;while (t--) {int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)cin >> b[i];a[0] = -1e9, a[n + 1] = 2e9;for (int i = 0; i <= n; i++)v[i] = 1;sort(a + 1, a + 1 + n);sort(b + 1, b + 1 + n);for (int i = 1; i <= n; i++) {if (b[1] <= a[i]) {if (b[1] + a[i - 1] <= a[i] && b[1] + a[i] <= a[i + 1])v[i] = 0;}}int num = 0, ans = 0;for (int i = n, j = n; i; i--) {if (num >= a[i])v[i] = 0;while (j && b[j] >= a[i]) {if (a[i - 1] + a[i] <= b[j] && a[i] + b[j] <= a[i + 1])v[i] = 0;num = max(num, min(b[j] - a[i], a[i + 1] - b[j]));j--;}ans |= v[i];}if (ans)cout << "Alice" << endl;elsecout << "Bob" << endl;}return 0;
}

学习交流

​
以下为学习交流QQ群，群号： 546235402，每周题解完成后都会转发到群中，大家可以加群一起交流做题思路，分享做题技巧，欢迎大家的加入。
​

这篇关于AtCoder Regular Contest 170 A~D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---