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

## 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/

``````#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;
}
``````