0812美团笔试AK代码

Q1

import java.util.Scanner;

public class P1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = scan.nextInt();
        int x = scan.nextInt(), y = scan.nextInt();
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                if ((nums[i] == x && nums[i - 1] == y) || (nums[i] == y && nums[i - 1] == x)) {
                    flag = true;
                    break;
                }
            }
            if (i < n - 1) {
                if ((nums[i] == x && nums[i + 1] == y) || (nums[i] == y && nums[i + 1] == x)) {
                    flag = true;
                    break;
                }
            }
        }
        System.out.println(flag ? "Yes" : "No");
    }
}

Q2

import java.util.Scanner;

public class P2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = scan.nextInt();
        int x = scan.nextInt(), y = scan.nextInt();
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }
        long ans1 = 0, ans2 = 0;
        for (int i = x; i < y; i++) {
            ans1 += nums[i - 1];
        }
        for (int i = 0; i < x - 1; i++) {
            ans2 += nums[i];
        }
        for (int i = y - 1; i < n; i++) {
            ans2 += nums[i];
        }
        System.out.println(Math.min(ans1, ans2));
    }
}

Q3

import java.util.Scanner;

public class P3 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        long sum = 0, ans = Long.MAX_VALUE;
        long[] col = new long[m], row = new long[n];
        for (int i = 0; i < n; i++) {
            long s = 0;
            for (int j = 0; j < m; j++) {
                long t = scan.nextInt();
                sum += t;
                s += t;
                col[j] += t;
            }
            row[i] = s;
        }
        long t = 0;
        for (int i = 0; i < n; i++) {
            t += row[i];
            ans = Math.min(Math.abs(sum - t - t), ans);
        }
        t = 0;
        for (int i = 0; i < m; i++) {
            t += col[i];
            ans = Math.min(Math.abs(sum - t - t), ans);
        }
        System.out.println(ans);
    }
}

Q4

import java.util.Scanner;

public class P4 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        char[] cs = scan.next().toCharArray();
        long ans = n;
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                char[][] g = new char[i][n / i];
                boolean[][] vis = new boolean[i][n / i];
                int a = 0, b = 0, t = 0;
                for (int j = 0; j < n; j++) {
                    g[b][a] = cs[j];
                    a++;
                    if (a == n / i) {
                        a = 0;
                        b++;
                    }
                }
                for (int x = 0; x < i; x++) {
                    for (int y = 0; y < n / i; ++y) {
                        if (!vis[x][y]) {
                            dfs(g, x, y, i, n / i, g[x][y], vis);
                            t++;
                        }
                    }
                }
                ans = Math.min(ans, t);
            }
        }
        System.out.println(ans);
    }

    public static void dfs(char[][] g, int i, int j, int x, int y, char c, boolean[][] vis) {
        if (i < 0 || j < 0 || i >= x || j >= y || vis[i][j] || g[i][j] != c) return;
        vis[i][j] = true;
        dfs(g, i + 1, j, x, y, c, vis);
        dfs(g, i - 1, j, x, y, c, vis);
        dfs(g, i, j + 1, x, y, c, vis);
        dfs(g, i, j - 1, x, y, c, vis);
    }
}

Q5

import java.util.*;

public class P5 {
    static int n;
    static int[] ws;
    static List<Integer>[] adjs;

    static int[][] dp; // dp[i][j] - 表示第i个节点为第j种颜色时的答案数

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        ws = new int[n];
        for (int i = 0; i < n; i++) ws[i] = scan.nextInt();
        adjs = new ArrayList[n];
        dp = new int[n][2];
        for (int i = 0; i < n; i++) adjs[i] = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            int u = scan.nextInt() - 1, v = scan.nextInt() - 1;
            adjs[u].add(v);
            adjs[v].add(u);
        }
        int ans = 0;
        dfs(0, -1);
        System.out.println(Math.max(dp[0][0], dp[0][1]));
    }

    public static void dfs(int u, int fa) {
        Set<Integer> vs = new HashSet<>();
        for (int v : adjs[u]) {
            if (v == fa) continue;
            dfs(v, u);
            dp[u][0] += Math.max(dp[v][1], dp[v][0]);
            if (check((long) ws[u] * ws[v])) vs.add(v);
        }
        for (int v : vs) {
            dp[u][1] = Math.max(dp[u][1], dp[u][0] - Math.max(dp[v][1], dp[v][0]) + dp[v][0] + 2); // 树的子节点互不影响
        }
    }

    public static boolean check(long x) {
        long t = (long) Math.sqrt(x);
        return t * t == x;
    }
}