0319 米哈游笔试AC代码

Q1-100%

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int[][] dirs = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) grid[i] = scan.next().toCharArray();
        int[][] hashs1 = new int[n][m], hashs2 = new int[n][m];
        for (int[] hash : hashs1) Arrays.fill(hash, -1);
        for (int[] hash : hashs2) Arrays.fill(hash, -1);
        int ans1 = 0, ans2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (hashs1[i][j] == -1) {
                    int idx = i * n + j;
                    dfs(grid, hashs1, i, j, idx, false);
                    ans1++;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (hashs2[i][j] == -1) {
                    int idx = i * n + j;
                    dfs(grid, hashs2, i, j, idx, true);
                    ans2++;
                }
            }
        }
        System.out.println(ans1 - ans2);
    }

    public static void dfs(char[][] grid, int[][] hashs, int i, int j, int idx, boolean flag) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || hashs[i][j] != -1) return;
        hashs[i][j] = idx;
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || hashs[x][y] != -1) continue;
            if (!flag) {
                if (grid[i][j] != grid[x][y]) continue;
            } else {
                if (grid[i][j] != grid[x][y] && !((grid[i][j] == 'B' && grid[x][y] == 'G') || (grid[i][j] == 'G' && grid[x][y] == 'B'))) continue;
            }
            dfs(grid, hashs, i + dir[0], j + dir[1], idx, flag);
        }
    }
}

Q2-100%（测试用例不行，没考虑字符顺序也A了）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int q = scan.nextInt();
        String[][] queries = new String[q][2];
        for (int i = 0; i < q; i++) {
            queries[i] = new String[]{scan.next(), scan.next()};
        }
        for (String[] query : queries) {
            String s = query[0], t = query[1];
            System.out.println(solve(s, t) ? "Yes" : "No");
        }
    }

    public static boolean solve(String s, String t) {
        if (s.length() < t.length()) return solve(t, s);
        char[] cs1 = s.toCharArray(), cs2 = t.toCharArray();
        int[] cnts = new int[26];
        for (char c : cs1) cnts[c - 'a']++;
        for (char c : cs2) if (--cnts[c - 'a'] < 0 && "mhy".indexOf(c) == -1) return false;
        for (int i = 0; i < 26; i++) {
            if (i != ('m' - 'a') && i != ('h' - 'a') && i != ('y' - 'a') && cnts[i] != 0) return false;
        }
        int m1 = cnts['m' - 'a'], h1 = cnts['h' - 'a'], y1 = cnts['y' - 'a'];
        return m1 == h1 && m1 == y1;
    }
}

Q3-100%

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokenizer = new StringTokenizer("");

    public static void main(String[] args) {
        int n = nextInt(), mod = (int) 1e9 + 7;
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = nextInt();
        Arrays.sort(nums);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) map.put(nums[i], i);
        long[] dp = new long[n];
        long ans = 0;
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            // 暴力法 - 20%
//            for (int j = i - 1; j >= 0; j--) {
//                if (nums[i] % nums[j] == 0) {
//                    dp[i] = (dp[i] + dp[j]) % mod;
//                }
//            }
            // 求数nums[i]的因数
            for (int j : factorization(nums[i])) {
                if (map.containsKey(j)) {
                    dp[i] = (dp[i] + dp[map.get(j)]) % mod;
                }
            }
        }
        for (int i = 0; i < n; i++) ans = (ans + dp[i]) % mod;
        ans = (ans - n + mod) % mod;
        System.out.println(ans);
    }

    public static String next() {
        while (!tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public static int nextInt() {
        return Integer.parseInt(next());
    }

    public static long nextLong() {
        return Long.parseLong(next());
    }

    private static Set<Integer> factorization(int a) {
        Set<Integer> ans = new HashSet<>();
        for (int i = 1; i * i <= a; i++) {
            if (a % i == 0) {
                ans.add(i);
                ans.add(a / i);
            }
        }
        ans.remove(a);
        return ans;
    }
}