ABC346 A-G 题解

下面的内容不包括题目翻译，要想获取题目翻译，请参照 这篇教程 来获取题目翻译。

A

题目

循环处理每一个数字即可，不再赘述。

AC Code：

#include <iostream>
using namespace std;
int n, a[200100];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) cout << a[i] * a[i + 1] << ' ';
	return 0;
}

时间复杂度

$O(N)$。

B

题目

由于键盘是有规律的，所以任何子串都可以从从 $12$ 以内开始的子串提取出来。暴力即可，$200$ 够用了。

时间复杂度

$O(200^2)$。

AC Code：

#include <iostream>
#include <cstring>
using namespace std;
int w, b;
string s = "wbwbwwbwbwbw";
string s1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> w >> b;
	for (int i = 0; i <= 20; i++) {
		for (int j = 0; j < (int)s.length(); j++) {
			s1.push_back(s[j]);
		}
	}
	for (int i = 0; i < (int)s1.size(); i++) {
		int cntw = 0, cntb = 0;
		for (int j = i; j < (int)s1.size(); j++) {
			if (w == cntw && b == cntb) {
				cout << "Yes\n";
				return 0;
			}
			if (s1[j] == 'b') cntb++;
			else cntw++;
		}
	}
	cout << "No";
	return 0;
}

C

题目

我们发现，与其一个一个找没有出现在 $A$ 里面的数，不如从小于等于 $K$ 的所有数字里面寻找在 $A$ 里出现过的数字。我们使用一个 map 记录这个数字有没有被去除。对于每一个 $A_i$，如果 $A_i\le K$ 且没有被去除，就从所有小于等于 $K$ 的数字的和里面减去这个数字，把这个数字标记为已去除。

时间复杂度

$O(N\log (10^9))$。

AC Code：

#include <iostream>
#include <map>
using namespace std;
int n;
long long k, a[200100];
long long ans;
map<long long, bool> m;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	ans = (k + 1ll) * k / 2ll;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (!m[a[i]] && a[i] <= k) {
			ans -= a[i];
			m[a[i]] = 1;
		}
	}
	cout << ans;
	return 0;
}

D

题目

我们发现，一个好字串无非就是可以从某个位置切成两个字串，字串里相邻两个字符不一样，字串切开的位置的字符相同。

我们计算前缀后缀以 0 或 1 开始的相邻两个字符不一样的代价，即使这个字串变为 10101... 的代价。对于每一个分割点，如果原串长度是偶数，那么这两个分割后的字串另外一边要一样，否则，不一样。计算代价，取最小值即可。

时间复杂度

$O(N)$。

AC Code：

#include <algorithm>
#include <iostream>
using namespace std;
int n;
char s[200100];
int c[200100];
long long sum[200100];
long long c00[200100], c01[200100], c10[200100], c11[200100];
long long ans = 1e18;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> s[i];
	for (int i = 1; i <= n; i++) cin >> c[i];
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + c[i];
	for (int i = 1; i <= n; i++) {
		c00[i] = c00[i - 1] + ((i - 1) % 2 == s[i] - '0') * c[i];
		c01[i] = c01[i - 1] + (i % 2 == s[i] - '0') * c[i];
	}
	for (int i = n; i >= 1; i--) {
		c10[i] = c10[i + 1] + ((n - i) % 2 == s[i] - '0') * c[i];
		c11[i] = c11[i + 1] + ((n - i + 1) % 2 == s[i] - '0') * c[i];
	}
	for (int i = 1; i < n; i++) {
		if (n % 2 == 0) {
			ans = min({ans, c00[i] + c10[i + 1], c01[i] + c11[i + 1]});
		}
		else {
			ans = min({ans, c01[i] + c10[i + 1], c00[i] + c11[i + 1]});
		}
	}
	cout << ans;
	return 0;
}

E

题目

我们倒着考虑所有操作，对于每一个横排操作，如果之前（指更晚的操作）把这一排覆盖了，那么跳过这个操作，否则统计没被覆盖的列数，该颜色数量加上这个值，把这一排标记为操作了，剩余横排数量减一，结束。
如果这是一个竖列操作，如果这一列没有被覆盖，该颜色数量加上没被覆盖的横排数，把这一列标记为被覆盖，没被覆盖的列数减去一，结束。

时间复杂度

$O(1)$。

AC Code：

#include <iostream>
#define int long long
using namespace std;
int h, w;
int m;
int t[200100], a[200100], x[200100];
int c_h, c_w;
int cnt[200100];
int cnt1;
bool vis_h[200100], vis_w[200100];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> h >> w;
	cin >> m;
	c_h = h, c_w = w;
	for (int i = m; i >= 1; i--) cin >> t[i] >> a[i] >> x[i];
	for (int i = 1; i <= m; i++) {
		if (t[i] == 1) {
			if (c_h && !vis_h[a[i]]) {
				c_h--;
				cnt[x[i]] += c_w;
				vis_h[a[i]] = 1;
			}
		}
		else {
			if (c_w && !vis_w[a[i]]) {
				c_w--;
				cnt[x[i]] += c_h;
				vis_w[a[i]] = 1;
			}
		}
	}
	cnt[0] += c_h * c_w;
	for (int i = 0; i <= 200000; i++) {
		if (cnt[i]) cnt1++;
	}
	cout << cnt1 << '\n';
	for (int i = 0; i <= 200000; i++) {
		if (cnt[i]) {
			cout << i << ' ' << cnt[i] << '\n';
		}
	}
	return 0;
}

F

题目

如果重复三次的情况可以，那么二次，一次的情况也可以。如果重复四次的情况不可以，重复五次，六次也不可以。可以看出这东西满足单调性，可以二分。

我们判断这个情况可不可以时，如果暴力在重复 $N$ 次的串中寻找的话，$N$ 很大，会爆炸。我们记录现在找到了重复第几遍的串中的第几个字符，分情况讨论找完后会不会跳到下一遍即可。如果跳不到下一遍，找到刚刚好重复我们要重复的次数的位置，否则，让总共要重复的次数除以这一边中字符个数就是要重复的次数，还要考虑这个坐标多的次数。

如果重复了 $N+1$ 边才找完或没找完，就说明不行。

细节很多，考验你的调试技术。

时间复杂度

$O(|T|\log (N|S|))$。

AC Code：

#include <iostream>
#define int long long

using namespace std;
int n;
string s, t;
int cnt[200100][50];
int idx[200100][50];
bool check(int x) {
	int now1 = 0, now2 = 0;
	for (int i = 0; i < (int)t.size(); i++) {
		if (!cnt[0][t[i] - 'a']) return 0;
		if (cnt[now2][t[i] - 'a'] >= x) {
			int tmp = x;
			if (now2) tmp += cnt[0][t[i] - 'a'] - cnt[now2][t[i] - 'a'];
			now2 = idx[tmp][t[i] - 'a'] + 1;
		}
		else {
			int tmp = x;
			tmp -= cnt[now2][t[i] - 'a'];
			now1++;
			now2 = 0;
			if (cnt[0][t[i] - 'a'] >= tmp) {
				now2 = idx[tmp][t[i] - 'a'] + 1;
			}
			else {
				now1 += tmp / cnt[0][t[i] - 'a'];
				now2 = idx