freee Programming Contest 2022(AtCoder Beginner Contest 264) 题解 (A~D)A - “atcoder”.substr()B - Nice GridC - Matrix ReducingProblem StatementD - “redocta”.swap(i,i+1)

51 阅读 0 评论 34 点赞

我是靠谱客的博主彪壮毛衣，最近开发中收集的这篇文章主要介绍freee Programming Contest 2022(AtCoder Beginner Contest 264) 题解 (A~D)A - “atcoder”.substr()B - Nice GridC - Matrix ReducingProblem StatementD - “redocta”.swap(i,i+1)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A - “atcoder”.substr()

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $100$ points

Problem Statement

Print the $L$ -th through $R$ -th characters of the string atcoder.

Constraints

$L$ and $R$ are integers.
$1 \leq L \leq R \leq 7$

Input

Input is given from Standard Input in the following format:

$L$ $R$

Output

Print the answer.

题面翻译

给定左右边界 $L$ 和 $R$ ，求截取 $[L, R]$ 后的atcoder字符串。

Sample Input 1

3 6

Sample Output 1

code

The $3$ -rd through $6$ -th characters of atcoder are code.

Sample Input 2

4 4

Sample Output 2

Sample Input 3

1 7

Sample Output 3

atcoder

题解部分

我们用一个string类型变量记录一下字符串atcoder，
再用一重循环输出区间内的字符即可。

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int main () {
	string str = " atcoder";
	int l, r;
	scanf ("%d %d", &l, &r);
	for (int i = l; i <= r; i ++) {
		printf ("%c", str[i]);
	}
	return 0;
}

B - Nice Grid

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $200$ points

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

$1 \leq R, C \leq 15$
$R$ and $C$ are integers.

Input

Input is given from Standard Input in the following format:

$R$ $C$

Output

In the grid above, if the color of the cell at the $R$ -th row from the top and $C$ -th column from the left is black, then print black; if the cell is white, then print white. Note that the judge is case-sensitive.

题面翻译

给出坐标 $(R, C)$ ，判断上图第 $R$ 行，第 $C$ 列的颜色。

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the $3$ -rd row from the top and $5$ -th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the $4$ -th row from the top and $5$ -th column from the left is white. Thus, white should be printed.

题解部分

我们可以用用两重循环标记整个图的颜色，再输出对应字符串即可。

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

bool fl[20][20];

int main () {
	int a, b;
	scanf ("%d %d", &a, &b);
	for (int i = 1; i <= 7; i += 2) {
		for (int j = i; j <= 15 - i + 1; j ++) {//每一圈正方形的上、左边
			fl[i][j] = 1;
			fl[j][i] = 1;
		}
		for (int j = 15 - i + 1; j >= i; j --) {//每一圈正方形的下、右边
			fl[15 - i + 1][j] = 1;
			fl[j][15 - i + 1] = 1;
		}
	}
	printf ("%s", fl[a][b] == 1 ? "black" : "white");
	return 0;
}

C - Matrix Reducing

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $300$ points

Problem Statement

You are given a matrix $A$ with $H_1$ rows and $W_1$ columns, and a matrix $B$ with $H_2$ rows and $W_2$ columns.

For all integer pairs $(i, j)$ such that $1≤i≤H_1$ and $1≤j≤W_1$ , the element at the $i$ -th row and $j$ -th column of matrix $A$ is $A_{i,j}$ .
For all integer pairs $(i, j)$ such that $1≤i≤H_2$ and $1≤j≤W_2$ , the element at the $i$ -th row and $j$ -th column of matrix $B$ is $B_{i,j}$ .
You may perform the following operations on the matrix $A$ any number of (possibly $0$ ) times in any order:
Choose an arbitrary row of $A$ and remove it.
Choose an arbitrary column of $A$ and remove it.
Determine if it is possible to make the matrix $A$ equal the matrix $B$ .

Constraints

$1≤H_2≤H_1≤10$
$1≤W_2≤W_1≤10$
$1≤A_{i,j}≤10^9$
$1≤B_{i,j}≤10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

$H_1$ $W_1$
$A_{1,1}$ $A_{1,2}$ … $A_{1,W_1}$
$A_{2,1}$ $A_{2,2}$ … $A_{2,W_1}$
⋮
$A_{H_1,1}$ $A_{H_1,2}$ … $A_{H_1,W_1}$
$H_2$ $W_2$
$B_{1,1}$ $B_{1,2}$ … $B_{1,W_2}$
$B_{2,1}$ $B_{2,2}$ … $B_{2,W_2}$
⋮
$B_{H_2,1}$ $B_{H_2,2}$ … $B_{H_2,W_2}$

Output

Print Yes if it is possible to make the matrix $A$ equal the matrix $B$ ; print No otherwise. Note that the judge is case-sensitive.

题面翻译

给出两个二维数组 $A$ 、 $B$ ，你可以删除若干次 $A$ 的任意一行(列)，判断是否能将 $A$ 转化为 $B$ 。

Sample Input 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the $2$ -nd column from the initial $A$ results in:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

Then, removing the $3$ -rd row from $A$ results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the $1$ -st row from $A$ results in:

6 8 9 10
16 18 19 20

Then, removing the $4$ -th column from $A$ results in:

6 8 9
16 18 19

Now the matrix equals the matrix $B$ .
Thus, we can make the matrix $A$ equal the matrix $B$ by repeating the operations, so Yes should be printed.

Sample Input 2

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix $A$ equal the matrix $B$ , so No should be printed.

题解部分

注意数据范围，长和宽都 $\leq 10$ ，所以我们选择用两个dfs暴搜整个矩阵，如果两个矩阵完全一致，输出Yes，搜完了仍然没有输出，则输出No。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

const int MAXN = 10 + 5;
int a[MAXN][MAXN], b[MAXN][MAXN];
bool line[MAXN], col[MAXN];
int n1, m1, n2, m2;

bool check () {//判断搜索后的矩阵A是否与B相等
	int I = 1, J;
	for (int i = 1; i <= n1; i ++) {
		if (col[i]) {
			J = 1;
			for (int j = 1; j <= m1; j ++) {
				if (line[j]) {
					if (a[i][j] != b[I][J]) {
						return 0;
					}
					J ++;
				}
			}
			I ++;
		}
	}
	return 1;
}

void dfs_col (int step, int x) {//搜索每一列
	if (step > n2) {
		if (check ()) {
			printf ("Yes");
			exit (0);
		}
		return;
	}
	for (int i = x + 1; i <= n1 - (n2 - step); i ++) {
		if (!col[i]) {
			col[i] = 1;
			dfs_col (step + 1, i);
			col[i] = 0;
		}
	}
}

void dfs_line (int step, int x) {//搜索每一行
	if (step > m2) {
		dfs_col (1, 0);
		return;
	}
	for (int i = x + 1; i <= m1 - (m2 - step); i ++) {
		if (!line[i]) {
			line[i] = 1;
			dfs_line (step + 1, i);
			line[i] = 0;
		}
	}
}

int main () {
	scanf ("%d %d", &n1, &m1);
	for (int i = 1; i <= n1; i ++) {
		for (int j = 1; j <= m1; j ++) {
			scanf ("%d", &a[i][j]);
		}
	}
	scanf ("%d %d", &n2, &m2);
	for (int i = 1; i <= n2; i ++) {
		for (int j = 1; j <= m2; j ++) {
			scanf ("%d", &b[i][j]);
		}
	}
	dfs_line (1, 0);
	printf ("No");
	return 0;
}

D - “redocta”.swap(i,i+1)

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $400$ points

Problem Statement

You are given a string $S$ that is a permutation of atcoder.
On this string $S,$ you will perform the following operation $0$ or more times:

Choose two adjacent characters of $S$ and swap them.

Find the minimum number of operations required to make $S$ equal atcoder.

Constraints

$S$ is a string that is a permutation of atcoder

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the answer as an integer.

题面翻译

给出字符串 $S$ ，每次可以交换相邻的两个字母，求最少需要几次可以把 $S$ 转化为atcoder。

Sample Input 1

catredo

Sample Output 1

You can make $S$ equal atcoder in $8$ operations as follows:
catredo → [ac]tredo → actre[od] → actr[oe]d → actro[de] → act[or]de → acto[dr]e → a[tc]odre → atcod[er]
This is the minimum number of operations achievable.

Sample Input 2

atcoder

Sample Output 2

In this case, the string S is already atcoder.

Sample Input 3

redocta

Sample Output 3

题解部分

这道题我们可以运用冒泡排序的思想，按照顺序，将指定字母交换至指定位置。由于atcoder不包含两个相同的字母，所以不用考虑最小的移动方法。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main () {
	int cnt = 0;
	string str = "atcoder", s;
	cin >> s;
	for (int i = 0; i < 7; i ++) {
		int p = s.find(str[i]);//寻找子串str[i]第一次出现的位置
		if (p < i) {//往后移(理论来说不需要判断)
			for (int j = p; j < i; j ++) {
				swap (s[j], s[j + 1]);
				cnt ++;
			}
		} else if (p > i) {//往前移
			for (int j = p; j > i; j --) {
				swap (s[j], s[j - 1]);
				cnt ++;
			}
		}
	}
	printf ("%d", cnt);
	return 0;
}

最后

以上就是彪壮毛衣为你收集整理的freee Programming Contest 2022(AtCoder Beginner Contest 264) 题解 (A~D)A - “atcoder”.substr()B - Nice GridC - Matrix ReducingProblem StatementD - “redocta”.swap(i,i+1)的全部内容，希望文章能够帮你解决freee Programming Contest 2022(AtCoder Beginner Contest 264) 题解 (A~D)A - “atcoder”.substr()B - Nice GridC - Matrix ReducingProblem StatementD - “redocta”.swap(i,i+1)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：比赛题解
浏览次数：51 次浏览
发布日期：2024-01-24 15:35:51
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_okf1_13_jc3.html

freee Programming Contest 2022(AtCoder Beginner Contest 264) 题解 (A~D)A - “atcoder”.substr()B - Nice GridC - Matrix ReducingProblem StatementD - “redocta”.swap(i,i+1)

freee Programming Contest 2022(AtCoder Beginner Contest 264) 题解 (A~D)A - “atcoder”.substr()B - Nice GridC - Matrix ReducingProblem StatementD - “redocta”.swap(i,i+1)

概述

A - “atcoder”.substr()

Problem Statement

Constraints

Input

Output

题面翻译

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

题解部分

B - Nice Grid

Problem Statement

Constraints

Input

Output

题面翻译

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

题解部分

C - Matrix Reducing

Problem Statement

Constraints

Input

Output

题面翻译

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

题解部分

D - “redocta”.swap(i,i+1)

Problem Statement

Constraints

Input

Output

题面翻译

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

题解部分

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复