1 小美的树上染色

太妙了，要不然我还想怎么把点标记为红色… …二叉树+dp还是有难度，感觉自己太菜了…

我感觉再做可能还是不太会这题（，虽然看懂题解自己又写了一遍

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 放n和节点
        int n = scanner.nextInt();
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i ++) {
            int temp = scanner.nextInt();
            a.add(temp);
        }

        // 边数只有n-1条，若用邻接矩阵表示会空间浪费，多开辟n*n-(n-1)格
        // 故用邻接表
        List<List<Integer>> g = new ArrayList<>(n);
        for (int i = 0; i < n; i ++) {
            g.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i ++) {
            // 初始化邻接表
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            g.get(u).add(v);
            g.get(v).add(u);
        }

        // dp[i][0]:以i为根，不要i,当前子树最大值
        // dp[i][0]:以i为根，  要i,当前子树最大值
        int[][] dp = new int[n][2];

        dfs(0, -1, g, a, dp);
        System.out.println(Math.max(dp[0][0], dp[0][1]));
        
    }

    public static void dfs(int cur, int father, List<List<Integer>> g, List<Integer> a, int[][] dp) {
        // dp[i][0]。related为对与cur节点相连所有节点的遍历
        for (int related : g.get(cur)) {
            if (related == father) {
                // 遇父节点，下一个。因为父已访问过
                continue;
            } else {
                dfs(related, cur, g, a, dp);
                // 当前节点不要，那就加上子节点为根的树的最大值
                dp[cur][0] += Math.max(dp[related][0], dp[related][1]);
            }
        }

        // dp[i][1]
        for (int related : g.get(cur)) {
            if (related == father) {
                continue;
            } else {
                // 如果两个int都是10^9,相乘溢出为：2,147,483,647，会把溢出值赋给product
                // 先显示转化a.get(cur)为long,然后long*int自动类型提升
                long product = (long) a.get(cur) * a.get(related);
                // Math.sqrt返回的是double,需要转化
                long sqrt = (long) Math.sqrt(product);
                if (sqrt * sqrt == product) {
                    // 不计cur的值，减去要和不要子节点的最大值（因为dp[i][0]加的是最大的）,再加上不计入子节点，再加2
                    int addCurRes = dp[cur][0] - Math.max(dp[related][0], dp[related][1]) + dp[related][0] + 2;
                    dp[cur][1] = Math.max(dp[cur][1], addCurRes);                    
                }
            }
        }
    }
}

2 小美的字符串变换

调换行列数可能结果不同，如69拆为323和233, 最小会不同
我还傻乎乎举个几个简单例子蒙蔽自己以为是一样的... ...

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String str = scanner.nextLine();
        int res = 100000000;

        for (int i = 1; i <= n; i ++) {
            if (n % i == 0) {
                // 找到一种矩阵的形状
                int row = i;
                int col = n / row;
                int index = 0;

                char[][] grid = new char[row][col];
                for (int j = 0; j < row; j ++) {
                    for (int k = 0; k < col; k ++) {
                        grid[j][k] = str.charAt(index ++);
                    }
                }

                int tempRes = 0;
                boolean[][] visited = new boolean[row][col];

                for (int j = 0; j < row; j ++) {
                    for (int k = 0; k < col; k ++) {
                        if (visited[j][k] == false) {
                            tempRes ++;
                            // 当前节点没有被访问过
                            visited[j][k] = true;
                            dfs(grid, visited, j, k, row, col, grid[j][k]);
                        }
                    }
                }

                if (tempRes < res) {
                    res = tempRes;
                }
            }
        }

        System.out.println(res);
    }

    public static void dfs(char[][] grid, boolean[][] visited, int x, int y, int row, int col, char value) {
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < dir.length; i ++) {
            int x_new = x + dir[i][0];
            int y_new = y + dir[i][1];

            if (x_new < 0 || x_new >= row || y_new < 0 || y_new >= col) {
                // 越界
                continue;
            } else {
                if (visited[x_new][y_new] == false && grid[x_new][y_new] == value) {
                    // 当前节点没有被访问过，且和上一个字符相同
                    visited[x_new][y_new] = true;
                    dfs(grid, visited, x_new, y_new, row, col, value);
                }
            }
        }
    }   
}

3 小美的蛋糕切割

// 8:56 -- 9:09
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[][] grid = new int[n][m];

        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        int res = Integer.MAX_VALUE;

        // 按列切的前缀和
        int col[] = new int[m];
        int colSum = 0;
        for (int j = 0; j < m; j ++) {
            for (int i = 0; i < n; i ++) {
                colSum += grid[i][j];
            }
            col[j] = colSum;
        }

        for (int j = 0; j < m; j ++) {
            int tempRes = Math.abs((col[col.length - 1] - col[j]) - col[j]);
            if (tempRes < res) {
                res = tempRes;
            }
        }
        
        // 按行切的前缀和
        int row[] = new int[n];
        int rowSum = 0;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                rowSum += grid[i][j];
            }
            row[i] = rowSum;
        }

        for (int i = 0; i < n; i ++) {
            int tempRes = Math.abs((row[row.length - 1] - row[i]) - row[i]);
            if (tempRes < res) {
                res = tempRes;
            }
        }

        System.out.println(res);


    }
}

4 小美走公路

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] a = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i ++) {
            a[i] = (long) scanner.nextInt();
            sum += a[i];
        }

        int x = scanner.nextInt();
        int y = scanner.nextInt();

        // x 小 y 大
        if (y < x) {
            int temp = x;
            x = y;
            y = temp;
        }

        long res = 0;

        for (int i = 0; i < y - x; i ++) {
            res += a[i + x - 1];
        }


        res = Math.min(res, sum - res);

        System.out.println(res);
    }
}

5 小美的排列询问

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];

        // [0]放左，[1]放右
        int[][] leftAndRight = new int[n][2];

        for (int i = 0; i < n; i ++) {
            a[i] = scanner.nextInt();
            
            if (i >= 1) {
                leftAndRight[i][0] = a[i - 1];
                leftAndRight[i - 1][1] = a[i];
            }
        }

        int x = scanner.nextInt();
        int y = scanner.nextInt();

        int flag = 0;
        for (int i = 0; i < n; i ++) {
            if (a[i] == x) {
                for (int j = 0; j < 2; j ++) {
                    if (leftAndRight[i][j] == y) {
                        flag = 1;
                        System.out.println("Yes");
                    }
                }

                if (flag == 1) {
                    break;
                }
            }
        }

        if (flag == 0) {
            System.out.println("No");
        }
    }
}