2022.5.15 AcWing周赛第51场[补](2022.5.15 acwing weekly game 51 [make up])

A 签到
https://www.acwing.com/problem/content/4422/

#include <bits/stdc++.h>
using namespace std;

int n;
int p, q;
int ans;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &p, &q);
		if (p <= q - 2)
			ans++;
	}

	printf("%d\n", ans);

	return 0;
}

B 并查集

https://www.acwing.com/problem/content/4423/

本题暴力使用BFS搜索会TLE,因为数据范围 n <= 1e4。
可以考虑把每次BFS四个方向的ans记录下来,下次再用。对二维数组按照一维数组重新编号,并记录每个 ‘.’ 连通块的数量,在处理询问时,对 ‘*’ 的四个方向寻找其父节点,由于四个方向的 ‘.’ 可能连成一片,所以要注意去重,再将去重后的父节点对应的s(空格连通块数)累加起来。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
int p[M], s[M];
int dx[4] = {0, 1, 0, -1};

int dy[4] = {1, 0, -1, 0};

int get(int x, int y) {
	return x * m + y;
}

int find(int x) {
	if (p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}
/*
int bfs(int x, int y) {
	int res = 0;

	queue<PII> q;
	q.push({x, y});
	while (!q.empty()) {
		auto t = q.front();
		q.pop();
//		if (x == 2 && y == 1) {
//			printf("%d %d\n", t.first, t.second);
//		}
		if (!st[t.first][t.second])
			res++;
		st[t.first][t.second] = true;
		for (int i = 0; i < 4; i++) {
			int nx = t.first + dx[i];
			int ny = t.second + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (g[nx][ny] != '.')
				continue;
			if (st[nx][ny])
				continue;

			q.push({nx, ny});
		}
	}

	return res;
}
*/
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%s", g[i]);
	for (int i = 0; i < n * m; i++)
		p[i] = i, s[i] = 1;


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (g[i][j] == '.') {
				for (int k = 0; k < 4; k++) {
					int x = i + dx[k], y = j + dy[k];
					if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') {
						int a = get(i, j), b = get(x, y);
						a = find(a), b = find(b);
						if (a != b) {
							s[b] += s[a];
							p[a] = b;
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ )
			if (g[i][j] == '.')
				printf(".");
			else {
				int fathers[4], cnt = 0;
				for (int k = 0; k < 4; k ++ ) {
					int x = i + dx[k], y = j + dy[k];
					if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') {
						int a = get(x, y);
						fathers[cnt ++ ] = find(a);
					}
				}

				int sum = 1;
				if (cnt) {
					// 防止区间重复
					sort(fathers, fathers + cnt);
					cnt = unique(fathers, fathers + cnt) - fathers;
					for (int k = 0; k < cnt; k ++ )
						sum += s[fathers[k]];
				}

				printf("%d", sum % 10);
			}
		puts("");
	}

	return 0;
}

C 重复覆盖问题 贪心问题

https://www.acwing.com/problem/content/4424/

按题意来说,是重复覆盖问题,但是由于本题是线性递增的,从前向后枚举时,如果前面的不能覆盖,则后面的也一定不能覆盖,同时后面的结点能覆盖的右端点大于前面结点能覆盖的右端点,因此可以转化为贪心问题。

#include <bits/stdc++.h>
using namespace std;

/*
重复覆盖问题

但是,由于该问题是线性问题,可以转化成贪心问题。
*/

const int N = 1010;

int n, r;
int q[N], cnt;

int main() {
	scanf("%d %d", &n, &r);
	for (int i = 1; i <= n; i++) {
		int tmp;
		scanf("%d", &tmp);
		if (tmp)
			q[cnt++] = i;
	}

	int res = 0, last = 0;
	for (int i = 0; i < cnt; i++) {
		if (last >= n)
			break;

		if (q[i] - r > last) {
			res = -1;
			break;
		}

		int j = i;
		while (j + 1 < cnt && q[j + 1] - r <= last)
			j++;
		last = q[j] + r - 1;
		res++;
		i = j;
	}

	if (last < n)
		res = -1;
	printf("%d\n", res);

	return 0;
}
————————

A 签到
https://www.acwing.com/problem/content/4422/

#include <bits/stdc++.h>
using namespace std;

int n;
int p, q;
int ans;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &p, &q);
		if (p <= q - 2)
			ans++;
	}

	printf("%d\n", ans);

	return 0;
}

B joint search set

https://www.acwing.com/problem/content/4423/

This topic uses BFS to search tle violently, because the data range is n & lt= 1e4。
Consider recording the ANS in four directions of BFS each time and reuse it next time. Renumber the two-dimensional array according to the one-dimensional array and record each ‘.’ The number of connected blocks. When processing the query, look for its parent node in the four directions of ‘*’ It may be connected together, so pay attention to < strong > de duplication < / strong >, and then add up the S (number of space connected blocks) corresponding to the parent node after de duplication.

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
int p[M], s[M];
int dx[4] = {0, 1, 0, -1};

int dy[4] = {1, 0, -1, 0};

int get(int x, int y) {
	return x * m + y;
}

int find(int x) {
	if (p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}
/*
int bfs(int x, int y) {
	int res = 0;

	queue<PII> q;
	q.push({x, y});
	while (!q.empty()) {
		auto t = q.front();
		q.pop();
//		if (x == 2 && y == 1) {
//			printf("%d %d\n", t.first, t.second);
//		}
		if (!st[t.first][t.second])
			res++;
		st[t.first][t.second] = true;
		for (int i = 0; i < 4; i++) {
			int nx = t.first + dx[i];
			int ny = t.second + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (g[nx][ny] != '.')
				continue;
			if (st[nx][ny])
				continue;

			q.push({nx, ny});
		}
	}

	return res;
}
*/
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%s", g[i]);
	for (int i = 0; i < n * m; i++)
		p[i] = i, s[i] = 1;


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (g[i][j] == '.') {
				for (int k = 0; k < 4; k++) {
					int x = i + dx[k], y = j + dy[k];
					if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') {
						int a = get(i, j), b = get(x, y);
						a = find(a), b = find(b);
						if (a != b) {
							s[b] += s[a];
							p[a] = b;
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ )
			if (g[i][j] == '.')
				printf(".");
			else {
				int fathers[4], cnt = 0;
				for (int k = 0; k < 4; k ++ ) {
					int x = i + dx[k], y = j + dy[k];
					if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') {
						int a = get(x, y);
						fathers[cnt ++ ] = find(a);
					}
				}

				int sum = 1;
				if (cnt) {
					// 防止区间重复
					sort(fathers, fathers + cnt);
					cnt = unique(fathers, fathers + cnt) - fathers;
					for (int k = 0; k < cnt; k ++ )
						sum += s[fathers[k]];
				}

				printf("%d", sum % 10);
			}
		puts("");
	}

	return 0;
}

C. repeated coverage problem and greedy problem

https://www.acwing.com/problem/content/4424/

According to the meaning of the question, it is a repeated coverage problem, but because the problem is linearly increasing, when enumerating from front to back, if the front cannot be covered, the latter must not be covered. At the same time, the right endpoint that the rear node can cover is larger than the right endpoint that the front node can cover, so it can be transformed into a greedy problem.

#include <bits/stdc++.h>
using namespace std;

/*
重复覆盖问题

但是,由于该问题是线性问题,可以转化成贪心问题。
*/

const int N = 1010;

int n, r;
int q[N], cnt;

int main() {
	scanf("%d %d", &n, &r);
	for (int i = 1; i <= n; i++) {
		int tmp;
		scanf("%d", &tmp);
		if (tmp)
			q[cnt++] = i;
	}

	int res = 0, last = 0;
	for (int i = 0; i < cnt; i++) {
		if (last >= n)
			break;

		if (q[i] - r > last) {
			res = -1;
			break;
		}

		int j = i;
		while (j + 1 < cnt && q[j + 1] - r <= last)
			j++;
		last = q[j] + r - 1;
		res++;
		i = j;
	}

	if (last < n)
		res = -1;
	printf("%d\n", res);

	return 0;
}