AtCoder Beginner Contest 326 题解 A-D

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

A - 2UP3DOWN

原题链接

题目描述
给定一个X代表你当前所在楼层，再给定一个Y代表你想要到达的楼层，但是你最多只能上两层楼或者下三层楼，问是否能够到达Y。

思路：模拟

• 比较大小。

public static void solve() throws IOException {int x = readInt(), y = readInt();if (x >= y) {printWriter.println(x - 3 <= y ? "Yes" : "No");} else {printWriter.println(x + 2 >= y ? "Yes" : "No");}
}

B - 326-like Numbers

原题链接

题目描述
给定一个整数N，求出一个大于等于N的满足百位数与十位数的乘积等于个位数的数。

思路：枚举

• 不断枚举大于等于N的每个数，直至符合条件。

public static void solve() throws IOException{int n = readInt();while (true) {String s = String.valueOf(n);int a = s.charAt(s.length() - 1) - '0';int b = s.charAt(s.length() - 2) - '0';int c = s.charAt(s.length() - 3) - '0';if (b * c == a) {printWriter.println(n);break;}n++;}
}

C - Peak

原题链接

题目描述
一条无限长的数轴上只有N个点上有礼物，现在你可以在数轴上选择一段区间为M的线段，求出这条线段上最多可以有多少礼物。

思路：排序+二分

• 排序后，枚举每个礼物，二分找到最近的小于$arr[i]+m$的礼物的所在位置$arr[j]$，其中礼物数为$j-i+1$。

public static void solve() throws IOException{int n = readInt(), m = readInt();int[] arr = utils.nextIntArray(n);Arrays.sort(arr, 1, n + 1);int max = 0;for (int i = 1; i <= n; i++) {int l = i - 1, r = n + 1;while (l + 1 < r) {int mid = l + r >> 1;if (arr[i] + m > arr[mid]) {l = mid;} else {r = mid;}}max = Math.max(max, l - i + 1);}printWriter.println(max);
}

D - ABC Puzzle

原题链接

题目描述
给定一个整数N和两个长度为N且仅包含字符ABC的字符串R和C，请你构造出一个满足以下条件的$N\times N$的二维矩阵。如果无法构造出输出No，否则输出Yes，并输出任意一个满足条件的矩阵。

• 每一行和每一列仅包含一个A，一个B 和一个C。
• 每行最左边的字母组成的字符串和R相等。
• 每列最上边的字母组成的字符串和C相等。

输入样例

5
ABCBC
ACAAB

输出样例

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

思路：dfs

• 难点主要在于判断ABC的位置，使用三层循环枚举ABC每种位置的状态，每行ABC的排列情况最多只有 $5\ast 4\ast 3=60$种，同时通过R[u]进行优化枚举的情况，降低时间复杂度。

static int n;
static String s1, s2;
static char[][] map;
static boolean ok = false;public static void solve() throws IOException {n = readInt();s1 = " " + readString(); s2 = " " + readString();map = new char[n + 1][n + 1];for (int i = 0; i <= n; i++) {Arrays.fill(map[i], '.');}dfs(1);if (!ok) {printWriter.println("No");}
}public static void dfs(int u) {if (ok) return;if (u == n + 1) {// 判断行是否满足条件for (int i = 1; i <= n; i++) {Set<Character> set = new HashSet<>();for (int j = 1; j <= n; j++) {if (map[i][j] != '.') {if (set.contains(map[i][j])) return;// A,B,C只能出现一次set.add(map[i][j]);}}if (set.size() <= 2) return;//  A,B,C没有各出现一次for (int j = 1; j <= n; j++) {if (map[i][j] != '.') {if (s1.charAt(i) != map[i][j]) {// 该行首字母和 s1不对应return;}break;}}}// 判断列是否满足条件for (int j = 1; j <= n; j++) {Set<Character> set = new HashSet<>();for (int i = 1; i <= n; i++) {if (map[i][j] != '.') {if (set.contains(map[i][j])) return;// A,B,C只能出现一次set.add(map[i][j]);}}if (set.size() <= 2) return;//  A,B,C没有各出现一次for (int i = 1; i <= n; i++) {if (map[i][j] != '.') {if (s2.charAt(j) != map[i][j]) {// 该列首字母和 s2不对应return;}break;}}}ok = true;printWriter.println("Yes");for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {printWriter.print(map[i][j]);}printWriter.println();}return;}// 每行ABC的排列情况最多只有 5 * 4 * 3 = 60种for (int i = 1; i <= n; i++) {// A的位置for (int j = 1; j <= n; j++) {// B的位置if (i == j) continue;for (int k = 1; k <= n; k++) {// C的位置if (i == k || j == k) continue;if (s1.charAt(u) == 'A') {// 改行首字母为 A,那么 j和 k必须大于 i,即 B和 C必须在 A的后面 if (!(i < j && i < k)) continue;} else if (s1.charAt(u) == 'B') {if (!(j < i && j < k)) continue;} else if (s1.charAt(u) == 'C') {if (!(k < i && k < j)) continue;}map[u][i] = 'A';map[u][j] = 'B';map[u][k] = 'C';dfs(u + 1);// 恢复原状map[u][i] = '.';map[u][j] = '.';map[u][k] = '.';}}}
}

这篇关于AtCoder Beginner Contest 326 题解 A-D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---