AtCoder Beginner Contest 327 题解 A-D

本文主要是介绍AtCoder Beginner Contest 327 题解 A-D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - ab

原题链接

题目描述
判断一个给定的字符串是否存在字符a和字符b相邻。

public static void solve() throws IOException{int a = readInt();String s = readString();boolean f = s.contains("ab") || s.contains("ba");printWriter.println(f ? "Yes" : "No");
}

B - A^A

原题链接

题目描述
给定一个整数B，判断是否存在一个整数A，使得 $A^A=B$ ，如果存在，输出 $A$ ，否则输出 $- 1$ 。

思路：枚举

public static void solve() throws IOException{long a = readLong();boolean f = false;for (int i = 1; i <= 100; i++) {long q = 1;for (int j = 1; j <= i; j++) {q *= i;}if (q == a) {printWriter.println(i);f = true;break;}if (q > a) break;}if (!f) {printWriter.println(-1);}
}

C - Number Place

原题链接

题目描述
给定义一个 $\times 9$ 的二维矩阵，判断这个矩阵是否满足以下全部条件，如果满足输出Yes，否则输出No。

$\sim 9$ 的数字分别都在每行每列出现一次。
将该二维矩阵按顺序拆为 $9$ 个 $\times 3$ 的二维矩阵后， $\sim 9$ 的数字分别都在每个矩阵出现一次。

思路：模拟+技巧

先判断每行每列是否满足条件。
再判断每个小二维矩阵是否满足条件。

public static void solve() throws IOException{int[][] map = utils.nextIntArray(9, 9);boolean f = true;// 判断行n = 9;for (int i = 1; i <= n; i++) {Set<Integer> set = new HashSet<>();for (int j = 1; j <= n; j++) {set.add(map[i][j]);}if (set.size() != 9) f = false;}// 判断列for (int i = 1; i <= n; i++) {Set<Integer> set = new HashSet<>();for (int j = 1; j <= n; j++) {set.add(map[j][i]);}if (set.size() != 9) f = false;}// 判断小圈int[] x = new int[] {1, 4, 7}, y = new int[] {3, 6, 9};for (int a = 0; a < 3; a++) {// 控制行for (int b = 0; b < 3; b++) {// 控制列Set<Integer> set = new HashSet<>();for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 处于该小圈范围内if (i >= x[a] && i <= y[a] && j >= x[b] && j <= y[b]) {set.add(map[i][j]);}}}if (set.size() != 9) {f = false;break;}}}printWriter.println(f ? "Yes" : "No");
}

D - Good Tuple Problem

原题链接

题目描述
给定一个数组 $S$ 和一个数组 $T$ ，长度都为 $M$ 。问是否存在一个长度为 $N$ 的 01 数组 $X$ ，使得 $X_{S_i} \neq X_{T_i}(1 \leq i \leq N)$ ，如果存在，输出 Yes，否则输出 No。

输入样例
3 3
1 2 3
2 3 1
输出样例
No
思路：并查集+技巧

这题仅问我们是否存在，而不要求求出序列 $X$ ，那么可以使用并查集，将 $X$ 存在矛盾的两个位置记录下来，关键在于怎么维护存在矛盾的两个位置。
使用 $N$ 作为偏移量，每遍历到一对 $S_i$ 和 $T_i$ 时，可以理解为都是在染色。
① 如果 $p[S_i] \neq p[T_i]$ ，那么就分别更新他们的父节点为 $find(T_i + n)$ 和 $find(S_i + n)$ ，表示 $S_i$ 不能和 $find(T_i + n)$ 染同一种颜色， $T_i$ 不能和 $find(S_i + n)$ 染同一种颜色。
② 如果 $p[S_i] = p[T_i]$ ，假设为 $p$ ，此时 $S_i$ 不能和 $p$ 染同一种颜色， $T_i$ 不能和 $p$ 染同一种颜色，但是 $S_i$ 又不能和 $T_i$ 染同一种颜色，但是总共又只能染两种颜色，这时就出现了矛盾。

static int[] p;public static void solve() throws IOException{int n = readInt(), m = readInt();int[] s = new int[m + 1], t = new int[m + 1];for (int i = 1; i <= m; i++) s[i] = readInt();for (int i = 1; i <= m; i++) t[i] = readInt();p = new int[2 * n + 1];for (int i = 1; i <= 2 * n; i++) p[i] = i;boolean f = true;for (int i = 1; i <= m; i++) {int a = s[i], b = t[i];int pa = find(a), pb = find(b);if (pa == pb) {// 出现矛盾f = false;break;}p[pa] = find(b + n);p[pb] = find(a + n);}printWriter.println(f ? "Yes" : "No");
}public static int find(int x) {if (x != p[x]) {p[x] = find(p[x]);}return p[x];
}