M-SOLUTIONS Programming Contest 2021(AtCoder Beginner Contest 232)

A - QQ solver

题意：自己看题目

思路：根据题意模拟即可

参考代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int main() {
	cin >> s;
	int a = s[0] - '0', b = s[2] - '0';
	cout << a * b << endl;
	return 0;
}

B - Caesar Cipher

题意：给你两个长度都为\(n\)且都由小写字母组成的串\(s\) ， \(t\)，如果存在一个确定的非负整数\(k\)使得对于所有的\(1 \leq i \leq n\)有\(s[i] + k = t[i]\)，需要特别说明的是\('z' + 1 = 'a'\) 。

思路：

​ 方法一：考虑到\(k\)最大不会超过\(26\)，所以可以从\(0\)开始枚举检验到\(26\)，看是否存在符合条件的\(k\)值，时间复杂度是\(O(26n)\)。

​ 方法二： 考虑到这个加法是在模\(26\)意义下进行的，所以可以对\(s\)和\(t\)的每一项做差然后模\(26\)看所有的差值是否相同，相同就是存在，不相同就是不存在。

时间复杂度：\(O(n)\)

参考代码：

string s, t;
void solve() {
	cin >> s >> t;
	int dx = (s[0] - t[0] + 26) % 26;
	int n = s.size();
	for (int i = 1; i < n; ++i) {
		int dy = (s[i] - t[i] + 26) % 26;
		if (dx != dy) {
			puts("No");
			return;
		}
	}
	puts("Yes");
	return;
}

C - Graph Isomorphism

题意：给你两个有\(n\)个点和\(m\)条边的无向图\(A\)和\(B\)，问你这两个图的形状是否相同，形状相同的定义为：

存在一个长度为\(n\)的排列\(P\)，使得对于任意的\(i\),\(j\)，都满足\(A_{i , j} = B_{p_i , p_j}\)

思路：考虑到这题的数据范围\(1 \leq n \leq 8\) 所以考虑直接暴力枚举每一个排列进行检验即可

时间复杂度:\(O(n^2 \times n!)\)

参考代码：

const int N = 9;
int a[N][N], b[N][N];
int p[N], n, m, u, v;
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> u >> v;
		a[u][v] = a[v][u] = 1;
	}
	for (int i = 1; i <= m; ++i) {
		cin >> u >> v;
		b[u][v] = b[v][u] = 1;
	}
	for (int i = 1; i <= n; ++i) p[i] = i;
	do {
		bool res = true;
		for(int i = 1 ; i <= n && res; ++i)
			for (int j = 1; j <= n && res; ++j) {
				if (a[i][j] != b[p[i]][p[j]]) res = false;
			}
		if (res) {
			puts("Yes");
			return;
		}
	} while (next_permutation(p + 1, p + 1 + n));
	puts("No");
	return;
}

D - Weak Takahashi

题意：有一个\(H \times W\)的网格，\((i , j)\)表示第\(i\)行\(j\)列，\(C_{i , j} = '.'\)表示空地,\(C_{i , j} = '\#'\) 表示墙，你从\((1 , 1)\)开始，每次只能向下走或者向右走，但不能走到墙所在的位置，问你能走到最大的空地的数量。

思路：考虑倒着做，也就变成你可以以任意点作为起点，每次只能向左走或者向上走，走到\((1 , 1)\)所经过的空地的最大数量，转移方程为:

\[f_{i , j} = max(f_{i + 1 , j} , f_{i , j + 1}) + 1 \;\; c_{i , j} != '\#' \]

时间复杂度：\(O(H \times W)\)

参考代码：

const int N = 105;
char strs[N][N];
int n, m;
int f[N][N];
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> strs[i] + 1;
	for(int i = n ; i >= 1 ; --i)
		for (int j = m; j >= 1; --j) {
			if (strs[i][j] == '#') continue;
			f[i][j] = max(f[i + 1][j], f[i][j + 1]) + 1;
		}
	cout << f[1][1] << '\n';
	return;
}