美团0311所有AC代码
Q1
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
char[] cs = scan.next().toCharArray();
int ans = 0;
for (int i = 0; i < cs.length - 1; i++) {
if (cs[i] == cs[i + 1]) {
ans++;
i++;
}
}
System.out.println(ans);
}
}
@Q2
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(), m = scan.nextInt(), k = scan.nextInt();
char[][] grid = new char[n][m];
for (int i = 0; i < n; i++) {
grid[i] = scan.next().toCharArray();
}
int[][] matrix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = scan.nextInt();
}
}
int[][] dp = new int[n][m];
for (int[] ints : dp) Arrays.fill(ints, -1);
dp[0][0] = 0;
int max = 0;
for (int j = 1; j < m; j++) {
if (grid[0][j] == grid[0][j - 1]) dp[0][j] = dp[0][j - 1] + matrix[0][j];
else {
if (dp[0][j - 1] >= k) dp[0][j] = dp[0][j - 1] - k + matrix[0][j];
}
max = Math.max(max, dp[0][j]);
}
for (int i = 1; i < n; i++) {
if (grid[i][0] == grid[i - 1][0]) dp[i][0] = dp[i - 1][0] + matrix[i][0];
else {
if (dp[i - 1][0] >= k) dp[i][0] = dp[i - 1][0] - k + matrix[i][0];
}
max = Math.max(max, dp[i][0]);
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (dp[i - 1][j] != -1) {
if (grid[i][j] == grid[i - 1][j]) {
dp[i][j] = dp[i - 1][j] + matrix[i][j];
} else if (dp[i - 1][j] >= k) {
dp[i][j] = dp[i - 1][j] - k + matrix[i][j];
}
}
if (dp[i][j - 1] != -1) {
if (grid[i][j] == grid[i][j - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + matrix[i][j]);
} else if (dp[i][j - 1] >= k) {
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] - k + matrix[i][j]);
}
}
max = Math.max(dp[i][j], max);
}
}
System.out.println(max);
}
}
Q3
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] array = new int[n][2];
for (int i = 0; i < n; i++) array[i][0] = in.nextInt();
for (int i = 0; i < n; i++) array[i][1] = in.nextInt();
// 按照出现时间排序
Arrays.sort(array, (a, b) -> a[0] - b[0]);
int max = 0, t = 0;
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 小顶堆
for (int i = 0; i < n; i++) {
int left = array[i][0], right = array[i][1];
while (!queue.isEmpty() && queue.peek()[1] <= left) {
// 弹出所有比left 小的值
queue.poll();
}
queue.add(new int[]{left, right});
if (queue.size() == max) {
t += queue.peek()[1] - left + 1;
} else if (queue.size() > max) {
t = queue.peek()[1] - left + 1;
max = queue.size();
}
}
System.out.println(max + " " + t);
}
}
Q4
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int[][] grid = new int[16][16];
for (int[] ints : grid) Arrays.fill(ints, 0);
Map<Character, int[]> map = new HashMap<>();
Set<Integer> set1 = new HashSet<>(), set2 = new HashSet<>();
set1.add(0);
set2.add(15 * 16 + 15);
map.put('U', new int[]{-1, 0});
map.put('D', new int[]{1, 0});
map.put('L', new int[]{0, -1});
map.put('R', new int[]{0, 1});
grid[0][0] = 1;
grid[15][15] = 2;
int[] player1 = {0, 0}, player2 = {15, 15};
char[] cs1 = scan.next().toCharArray();
char[] cs2 = scan.next().toCharArray();
char d1 = '.', d2 = '.';
boolean flag = false;
for (int i = 0; i < cs1.length; i++) {
if (cs1[i] == 'F' && cs2[i] != 'F') {
if (check(player1, player2, d1)) {
System.out.println(i + 1);
System.out.println("D");
flag = true;
break;
}
d2 = cs2[i];
int[] dir = map.get(d2);
int x = player2[0] + dir[0], y = player2[1] + dir[1], hash = x * 16 + y;
if (x >= 0 && x < 16 && y >= 0 && y < 16 && !set1.contains(hash)) {
player2[0] = x;
player2[1] = y;
set2.add(hash);
}
} else if (cs1[i] != 'F' && cs2[i] == 'F') {
if (check(player2, player1, d2)) {
System.out.println(i + 1);
System.out.println("W");
flag = true;
break;
}
d1 = cs1[i];
int[] dir = map.get(d1);
int x = player1[0] + dir[0], y = player1[1] + dir[1], hash = x * 16 + y;
if (x >= 0 && x < 16 && y >= 0 && y < 16 && !set2.contains(hash)) {
player1 = new int[]{x, y};
set1.add(hash);
}
} else if (cs1[i] == 'F' && cs2[i] == 'F') {
boolean f1 = check(player1, player2, d1), f2 = check(player2, player1, d2);
if (f1 && f2) {
System.out.println(i + 1);
System.out.println("P");
flag = true;
break;
} else if (f1) {
System.out.println(i + 1);
System.out.println("D");
flag = true;
break;
} else if (f2) {
System.out.println(i + 1);
System.out.println("W");
flag = true;
break;
}
} else {
d1 = cs1[i];
d2 = cs2[i];
int[] dir1 = map.get(d1), dir2 = map.get(d2);
int x1 = player1[0] + dir1[0], y1 = player1[1] + dir1[1];
int x2 = player2[0] + dir2[0], y2 = player2[1] + dir2[1];
int hash1 = x1 * 16 + y1, hash2 = x2 * 16 + y2;
if (x1 >= 0 && x1 < 16 && y1 >= 0 && y1 < 16 && !set1.contains(hash2) && x2 >= 0 && x2 < 16 && y2 >= 0 && y2 < 16 && !set2.contains(hash1)) {
if (x1 == x2 && y1 == y2) {
System.out.println(i + 1);
System.out.println("P");
flag = true;
break;
}
player1 = new int[]{x1, y1};
player2 = new int[]{x2, y2};
set1.add(hash1);
set2.add(hash2);
} else if (x1 >= 0 && x1 < 16 && y1 >= 0 && y1 < 16 && !set2.contains(hash1)) {
player1 = new int[]{x1, y1};
set1.add(hash1);
} else if (x2 >= 0 && x2 < 16 && y2 >= 0 && y2 < 16 && !set1.contains(hash2)) {
player2 = new int[]{x2, y2};
set2.add(hash2);
}
}
}
if (!flag) {
System.out.println(256);
if (set1.size() == set2.size()) {
System.out.println("P");
} else if (set1.size() > set2.size()) {
System.out.println("D");
} else {
System.out.println("W");
}
}
}
public static boolean check(int[] player1, int[] player2, int d) {
if (d == 'U') {
return player1[1] == player2[1] && player1[0] > player2[0];
} else if (d == 'D') {
return player1[1] == player2[1] && player1[0] < player2[0];
} else if (d == 'L') {
return player1[0] == player2[0] && player1[1] > player2[1];
} else {
return player1[0] == player2[0] && player1[1] < player2[1];
}
}
}
Q5
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int ans = 0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
char[] colors = scan.next().toCharArray();
List<Integer>[] list = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) list[i] = new ArrayList<>();
for (int i = 2; i <= n; i++) list[scan.nextInt()].add(i);
dfs(list, colors, 1);
System.out.println(ans);
}
public static int[] dfs(List<Integer>[] lists, char[] colors, int node) {
int[] ret = new int[2];
for (int next : lists[node]) {
int[] ints = dfs(lists, colors, next);
ret[0] += ints[0];
ret[1] += ints[1];
}
if (ret[0] == ret[1]) ans++;
if (colors[node - 1] == 'R') ret[0] += 1;
else ret[1] += 1;
return ret;
}
}