AtCoder Beginner Contest 346

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

A. Adjacent Product(循环)

题意

给出$N$个数字$A_1,A_2,\dots ,A_N$。定义$B_i=A_i\times A_{i+1}(1\le i\le N-1)$。

请你打印$B_1,B_2,\dots ,B_{N-1}$。

分析

输入后使用循环计算出$B$数组中每一项的值，并将对应的值输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int a[105];void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 2; i <= n; i++) {if (i - 2) cout << ' ';cout << a[i - 1] * a[i];}cout << endl;
}int main() {solve();return 0;
}

B. Piano(暴力)

题意

给出一个以"wbwbwwbwbwbw"无限循环的字符串，问，能否取出该字符串中的一个子串，使得子串中字符'w'的出现次数恰好为$W$，字符'b'的出现次数恰好为$B$。

思路1：构造字符串

可以将字符串拼接若干次，保证长度能够满足题目要求，然后检查该字符串中所有长度为$W+B$的子串是否满足要求，如果满足要求，输出"Yes"，否则，输出"No"。

hint: 由于题目数据范围较小，因此枚举子串并检查的方法可以使用暴力枚举，前缀和，双指针等方式进行均可。

思路2：取模

由于字符串是循环的，那么字符串第$i$个字符与第$i$个字符是相同的，因此，不需要拼接字符串，直接对该长度为12的字符串进行枚举检查即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;string s = "wbwbwwbwbwbw";
string str = "";void solve() {while (str.size() < 20000) {str += s;}int W, B;cin >> W >> B;int w = 0, b = 0;for (int i = 0; i < W + B; i++) {if (str[i] == 'w') w++;else b++;}if (w == W && B == b) {cout << "Yes" << endl;return;} else {for (int i = W + B; i < str.size(); i++) {if (str[i] == 'w')  {w++;} else {b++;}if (str[i - W - B] == 'w') {w--;} else {b--;}if (w == W && B == b) {cout << "Yes" << endl;return;}}}cout << "No" << endl;
}int main() {solve();return 0;
}

C. Σ (set)

题意

给出$N$个数字$A_1,A_2,\dots ,A_N$，问$1\sim K$之间所有未在数组$A$中出现的数字之和是多少？

分析

对于$1\sim K$之间的数字之和，可以通过等差数量的求和公式直接得到($\frac{(1+K)\times K}{2}$)。

然后考虑怎么减去范围内在数字$A$中出现过的数字，由于数组$A$中的数字可能出现重复，因此，需要对数组中的元素进行去重，可以使用set, map, unique等容器或函数来进行。

去重完成后，遍历剩余的元素，如果在$1\sim K$范围内，就将这个数字从答案中减掉。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;set<int> S;void solve() {ll n, k;cin >> n >> k;for (int i = 1; i <= n; i++) {int a;cin >> a;S.insert(a);}ll ans = (1ll + k) * k / 2;for (auto i : S) {if (i > k) break;ans -= i;}cout << ans << endl;
}int main() {solve();return 0;
}

D. Gomamayo Sequence(DP)

题意

给出一个仅包含0或1的字符串，然后给出对于好字符串的定义：

• 对于字符串中所有相邻的字符，如果只存在一对相邻的字符是相等的，那么就认为这个字符是好字符串。

对于字符串中第$i$个字符，你可以花费$C_i$的费用将该字符变成另一个字符（0变1，1变0），问，最少花费多少，可以使得字符串变成好字符串。

分析

考虑$DP$,定义$dp[i][j][k]$为第$i$个字符为$j$，$k=0$表示当前字符为$j$时前面所有相邻的字符中未出现相同的，$k=1$表示当前字符为$j$时前面所有字符中已经出现相同的。

转移方程：

• 对于$dp[i][0][0]$，由于当前字符为0，且前面所有相邻字符均未出现相同的情况，那么能继承的只有上一个字符选择1，且也没有出现相邻相同的状态$dp[i-1][1][0]$

• 对于$dp[i][1][0]$，由于当前字符为1，且前面所有相邻字符均未出现相同的情况，那么能继承的只有上一个字符选择0，且也没有出现相邻相同的状态$dp[i-1][0][0]$

• 对于$dp[i][0][1]$，由于当前字符为0，且包含当前字符时已经出现相邻相同的情况了，那么就可以分为以下两种情况，选择两种情况中的较小值：

  • 前面没有出现相邻相同的情况，但当前字符与上一个字符相同，此时刚好出现相邻相同的情况：$dp[i-1][0][0]$

  • 前面已经出现相邻相同的情况，此时字符必须与前一个字符不同：$dp[i-1][1][1]$

• 对于$dp[i][1][1]$，由于当前字符为1，且包含当前字符时已经出现相邻相同的情况了，那么就可以分为以下两种情况，选择两种情况中的较小值：

  • 前面没有出现相邻相同的情况，但当前字符与上一个字符相同，此时刚好出现相邻相同的情况：$dp[i-1][1][0]$

  • 前面已经出现相邻相同的情况，此时字符必须与前一个字符不同：$dp[i-1][0][1]$

hint:

1. 如果$j$与当前字符不同，需要加上修改字符的费用。

2. 只有$i>1$时，才可能出现$k=1$的情况，因此$i=1$时，$dp[1][j][1]$不能继承状态，可以将所有$dp[0][j][1]$和$dp[1][j][1]$初始化为极大值，并在状态转移时特判跳过。

结束状态转移后，由于要求必须存在恰好一对相邻相同的情况，因此答案为$min(dp[n][0][1],dp[n][1][1])$。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;ll n, c[200005], dp[200005][2][2];
string s;int main() {cin >> n >> s;s = "#" + s;for (int i = 1; i <= n; i++) {cin >> c[i];}dp[0][0][1] = dp[0][1][1] = dp[1][0][1] = dp[1][1][1] = 0x3f3f3f3f3f3f3f3f;for (int i = 1; i <= n; i++) {if (s[i] == '0') {dp[i][0][0] = dp[i - 1][1][0];dp[i][1][0] = dp[i - 1][0][0] + c[i];if (i == 1) continue;dp[i][0][1] = min(dp[i - 1][1][1], dp[i - 1][0][0]);dp[i][1][1] = min(dp[i - 1][1][0], dp[i - 1][0][1]) + c[i];} else {dp[i][0][0] = dp[i - 1][1][0] + c[i];dp[i][1][0] = dp[i - 1][0][0];if (i == 1) continue;dp[i][0][1] = min(dp[i - 1][1][1], dp[i - 1][0][0]) + c[i];dp[i][1][1] = min(dp[i - 1][1][0], dp[i - 1][0][1]);}}cout << min(dp[n][0][1], dp[n][1][1]) << endl;return 0;
}

E. Paint(思维)

题意

有一个$H$行$W$列的网格，开始时，所有的格子都被涂上了颜色0。

你将在$i=1,2,\dots ,M$时执行以下操作：

• 如果$T_i=1$，将第$A_i$行涂成颜色$X_i$

• 如果$T_i=2$，将第$A_i$列涂成颜色$X_i$

请你输出操作结束后网格上剩余的颜色以及这些颜色所占的网格数量。

分析

对于每个网格结束操作后的颜色，实际上只取决于最后一次操作时涂上的颜色，因此，可以对每一行，每一列的操作进行标记，如果后面操作过了这一行或这一列，那么前面对这一行或这一列的操作就可以忽略了。

因此，可以从后往前遍历操作，如果当前操作的行和列没被涂色过，就将该行（或列）进行标记，并记录当前涂上的颜色的个数(涂行就记录剩余列数，涂列就记录剩余行数)。

然后对于每个涂色操作，可以将被涂色的行（或列）视为涂完色后就被删除了，那么每次涂色就是对于剩余部分的行数（或列数）进行涂色的，也便于计算每个颜色的个数。

结束涂色后，剩余的行数$\times$列数就是颜色0的数量。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll H, W, M, h[200005], w[200005], t[200005], a[200005], x[200005];ll vis[200005], cnt[200005];vector<pair<ll, ll> > ans;int main() {cin >> H >> W >> M;for (int i = 1; i <= M; i++) {cin >> t[i] >> a[i] >> x[i];}for (int i = M; i >= 1; i--) {if (t[i] == 1) {if (!h[a[i]]) {h[a[i]] = 1;cnt[x[i]] += W;H--;}} else {if (!w[a[i]]) {w[a[i]] = 1;cnt[x[i]] += H;W--;}}}cnt[0] += H * W;for (int i = 0; i <= 2e5; i++) {if (cnt[i]) {ans.push_back(make_pair(i, cnt[i]));}}cout << ans.size() << endl;for (auto i : ans) {cout << i.first << ' ' << i.second << endl;}return 0;
}

$F\sim G$，更新中…

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。

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

---