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

原题链接

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

• $1\sim 9$的数字分别都在每行每列出现一次。
• 将该二维矩阵按顺序拆为 $9$ 个 $3\times 3$ 的二维矩阵后，$1\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}\ne X_{T_i}(1\le i\le N)$，如果存在，输出 Yes，否则输出 No。

输入样例

3 3
1 2 3
2 3 1

输出样例

No

思路：并查集+技巧

• 这题仅问我们是否存在，而不要求求出序列 $X$，那么可以使用并查集，将 $X$ 存在矛盾的两个位置记录下来，关键在于怎么维护存在矛盾的两个位置。
• 使用 $N$作为偏移量，每遍历到一对 $S_i$ 和 $T_i$ 时，可以理解为都是在染色。
  ① 如果 $p[S_i]\ne 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];
}