米哈游 笔试 09.14 AC

第一题     包含 k 个 "mihoyo" 的字串的最短长度 (start end)

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();
        String tmp = "mihoyo";
        List<Integer> l = new ArrayList<>();
        // 先尝试获取 mihoyo 的位置，这里用list存储m的索引
        for(int i = 0; i < n - 5; i++){
            boolean ok = true;
            for(int j = 0; j < 6; j++){
                if(s.charAt(i+j) != tmp.charAt(j)){
                    ok = false;
                }
            }
            if(ok){
                l.add(i);
                i += 5;
            }
        }
        // 不够 k 个
        if(l.size() < k){
            System.out.println(-1);
            return;
        }
        // 判断比较
        int retIdx = 0;
        int len = l.get(k-1) - l.get(0);
        for(int i = k; i < l.size(); i++){
            int tmplen = l.get(i) - l.get(i-k+1);
            if(tmplen <= len){
                retIdx = i-k+1;
                len = tmplen;
            }
        }
        System.out.println(l.get(retIdx)+" "+(l.get(retIdx+k-1)+5));
    }

第二题 如下

    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
        int a = sc.nextInt(), b = sc.nextInt();
        Arrays.sort(arr);
        if(b == 0){ // 全部是小于等于的
            System.out.println(arr[0]);
            return;
        }
        if(a == 0) { // 全部是大于的
            System.out.println("infinity");
            return;
        }
        int left = arr[b-1], right = arr[b];
        if(left == right){ // left < x <= right 不成立
            System.out.println(-1);
            return;
        }else{
            System.out.println(right-left);
        }

    }

第三题 树的题

    static Map<Integer, Integer> map;
    static long ret;
    static List<List<Integer>> l;
    static boolean vis[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();

        vis = new boolean[n+1];
        map = new HashMap<>();
        ret = 0;

        l = new ArrayList<>();
        for(int i = 0; i <= n; i++){
            l.add(new ArrayList<>());
        }
        for(int i = 0; i < n-1; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            l.get(a).add(b);
            l.get(b).add(a);
        }

        dfs(root);
        System.out.println(ret);
    }

    public static int dfs(int pos) {
        List<Integer> childs = l.get(pos);
        vis[pos] = true;
        // 当前节点是一个连通分量
        int tmp = 1;
        for(int child: childs){
            if(!vis[child]){
                // 获取 child 的连通分量
                tmp += dfs(child);
                // 如果同奇偶，则连通分量个数-1
                if(child % 2 == pos%2) {
                    tmp -=1;
                }
            }
        }
        ret += tmp;
        return tmp;
    }