快手笔试A卷 4题100

package 快手.c0825.a;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            String versionA = scanner.next();
            String versionB = scanner.next();
            System.out.println(helper(versionA, versionB));
        }
    }

    private static boolean helper(String versionA, String versionB) {
        int[] va = parseVersion(versionA);
        int[] vb = parseVersion(versionB);
        for (int i = 0; i < 4; i++) {
            if (va[i] < vb[i]) {
                return true;
            } else if (va[i] > vb[i]) {
                return false;
            }
        }
        return false;
    }

    private static int[] parseVersion(String v) {
        String[] strings = v.split("\\.");
        int[] version = new int[4];
        for (int i = 0; i < Math.min(strings.length, 4); i++) {
            version[i] = Integer.parseInt(strings[i]);
        }
        return version;
    }
}

package 快手.c0825.b;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            int num = scanner.nextInt();
            Set<Integer> set = new HashSet<>();
            boolean res = helper(num, set);
            System.out.println(res);
        }
    }

    private static boolean helper(int num, Set<Integer> set) {
        if (num == 1) {
            return true;
        }
        if (set.contains(num)) {
            return false;
        }
        set.add(num);
        int cur = 0;
        while (num != 0) {
            cur += (num % 10) * (num % 10);
            num /= 10;
        }
        return helper(cur, set);
    }
}

package 快手.c0825.c;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] a = scanner.nextLine().split(" ");
        String[] b = scanner.nextLine().split(" ");
        int count = Math.min(a.length / 4, b.length);
        int ia = 0, ib = 0;
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(a[ia++]);
                System.out.print(" ");
            }
            System.out.print(b[ib++]);
            System.out.print(" ");
        }
        while (ia < a.length) {
            System.out.print(a[ia++]);
            System.out.print(" ");
        }
        while (ib < b.length) {
            System.out.print(b[ib++]);
            System.out.print(" ");
        }
    }
}

package 快手.c0825.d;

import java.util.*;


class Node {
    int label;
    List<Node> neighbors;
    List<Boolean> edgeColors;

    public static final Boolean RED = false;
    public static final Boolean BLACK = true;

    public Node(int label) {
        this.label = label;
        neighbors = new ArrayList<>();
        edgeColors = new ArrayList<>();
    }

    public static Boolean parseColor(int color) {
        return color == 1 ? BLACK : RED;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        Node[] graph = new Node[n + 1];
        for (int i = 0; i < (n - 1); i++) {
            int e1 = scanner.nextInt();
            int e2 = scanner.nextInt();
            int color = scanner.nextInt();
            if (graph[e1] == null) {
                graph[e1] = new Node(e1);
            }
            if (graph[e2] == null) {
                graph[e2] = new Node(e2);
            }
            graph[e1].neighbors.add(graph[e2]);
            graph[e1].edgeColors.add(Node.parseColor(color));
            graph[e2].neighbors.add(graph[e1]);
            graph[e2].edgeColors.add(Node.parseColor(color));
        }
        System.out.println(helper(graph, k));
    }

    private static final int MOD = 1000000007;

    private static int helper(Node[] graph, int k) {
        int n = graph.length - 1;
        long total = pow(n, k);
        List<Integer> setList = new ArrayList<>();
        Set<Node> visited = new HashSet<>();
        Queue<Node> q = new LinkedList<>();
        for (int i = 1; i < graph.length; i++) {
            if (visited.contains(graph[i])) {
                continue;
            }
            Set<Node> redSet = new HashSet<>();
            redSet.add(graph[i]);
            visited.add(graph[i]);
            q.offer(graph[i]);
            while (!q.isEmpty()) {
                Node node = q.poll();
                for (int j = 0; j < node.neighbors.size(); j++) {
                    if (node.edgeColors.get(j) == Node.RED && !visited.contains(node.neighbors.get(j))) {
                        Node next = node.neighbors.get(j);
                        q.offer(next);
                        redSet.add(next);
                        visited.add(next);
                    }
                }
            }
            setList.add(redSet.size());
        }
        for (Integer size : setList) {
            total = (total + MOD - pow(size, k)) % MOD;
        }
        return (int) total;
    }

    private static long pow(int n, int k) {
        long total = 1;
        for (int i = 0; i < k; i++) {
            total = (total * n) % MOD;
        }
        return total;
    }
}