小红的子树操作

小红的子树操作

题意

小红拿到了一棵有根树,i 号节点的权值为 ai 。已知1号节点为根节点。

小红有q次操作,每次操作会选择一个节点x,使得x为根的子树上,所有节点的权值乘以y。

小红想知道,在q次操作结束以后,对于节点 i,以节点 i 为根的子树的所有点权值乘积末尾有多少个0?

1 <= n, q <= 10^5

1 <= ai, y <= 10^9

作者:今夕kpole链接:https://www.nowcoder.com/discuss/475037372275523584来源:牛客网

我的解答1

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static Set<Integer> visited = new HashSet<>();
    // 每个子树的所有的节点id
    public static Map<Integer, Set<Integer>> subTreeNodes = new HashMap<>();

    public static Set<Integer> DFS(Map<Integer, List<Integer>> edges, int nodeId) {
        Set<Integer> ret = new HashSet<>();

        //if(visited.contains(nodeId)) return ret;

        ret.add(nodeId);
        visited.add(nodeId);

        // 遍历所有子节点
        List<Integer> children = edges.get(nodeId);
        if (children != null) {
            for (int childNodeId : children) {
                // 如果子节点被遍历过
                if (visited.contains(childNodeId)) {
                    continue;
                }

                Set<Integer> childNodeSet = DFS(edges, childNodeId);
                ret.addAll(childNodeSet);
            }
        }

        subTreeNodes.put(nodeId, ret);

        return ret;
    }

    public static int getFiveCount(int value) {
        int ret = 0;
        while (value % 5 == 0) {
            ret++;
            value /= 5;
        }

        return ret;
    }

    public static int getTwoCount(int value) {
        int ret = 0;
        while (value % 2 == 0) {
            ret++;
            value /= 2;
        }

        return ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int ai[] = new int[n + 1];
        int aitwoCount[] = new int[n + 1];
        int aifiveCount[] = new int[n + 1];

        for (int i = 1; i < n + 1; i++) {
            ai[i] = in.nextInt();
            aifiveCount[i] = getFiveCount(ai[i]);
            aitwoCount[i] = getTwoCount(ai[i]);

        }

        // Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();
        // Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();

        Map<Integer, List<Integer>> edges = new HashMap<>();
        for (int i = 0; i < n - 1; i++) {
            int a = in.nextInt();
            int b = in.nextInt();

            List<Integer> child1 = edges.get(a);
            if (child1 == null) {
                child1 = new ArrayList<Integer>();
                edges.put(a, child1);

            }
            child1.add(b);

            List<Integer> child2 = edges.get(b);
            if (child2 == null) {
                child2 = new ArrayList<Integer>();
                edges.put(b, child2);

            }
            child2.add(a);
        }

        // 找到所有子树的所有节点集合,建立映射关系。
        DFS(edges, 1);


        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            int x = in.nextInt();
            int y = in.nextInt();

            Set<Integer> allNodes = subTreeNodes.get(x);
            // Integer[] temp = allNodes.toArray(new Integer[0]);
            // Arrays.stream(temp).forEach(item -> System.out.print(item + " "));
            // System.out.println();
            for (int nodeId : allNodes) {

                aifiveCount[nodeId] += getFiveCount(y);
                aitwoCount[nodeId] += getTwoCount(y);
            }
        }

        // Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();
        // Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();

        StringBuilder resultStr = new StringBuilder();

        for (int i = 1; i <= n; i++) {

            Set<Integer> allNodes = subTreeNodes.get(i);
            int twoCount = 0;
            int fiveCount = 0;
            for (int nodeId : allNodes) {
                twoCount += aitwoCount[nodeId];
                fiveCount += aifiveCount[nodeId];
            }


            resultStr.append(Math.min(twoCount, fiveCount) + " ");
            
        }

        System.out.print(resultStr.toString());

        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
    }
}

运行超时,通过率40%。

我的解答2

将保存每个子树的所有的节点id的Map<Integer, Set<Integer>>改为Map<Integer, List<Integer>>:

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static Set<Integer> visited = new HashSet<>();
    // 每个子树的所有的节点id
    public static Map<Integer, List<Integer>> subTreeNodes = new HashMap<>();

    public static List<Integer> DFS(Map<Integer, List<Integer>> edges, int nodeId) {
        List<Integer> ret = new ArrayList<>();

        //if(subTreeNodes.containsKey(nodeId)) return subTreeNodes.get(nodeId);
        

        ret.add(nodeId);
        visited.add(nodeId);

        // 遍历所有子节点
        List<Integer> children = edges.get(nodeId);
        if (children != null) {
            for (int childNodeId : children) {
                // 如果子节点被遍历过
                if (visited.contains(childNodeId)) {
                    continue;
                }

                List<Integer> childNodeSet = DFS(edges, childNodeId);
                ret.addAll(childNodeSet);
            }
        }

        subTreeNodes.put(nodeId, ret);

        return ret;
    }

    public static int getFiveCount(int value) {
        int ret = 0;
        while (value % 5 == 0) {
            ret++;
            value /= 5;
        }

        return ret;
    }

    public static int getTwoCount(int value) {
        int ret = 0;
        while (value % 2 == 0) {
            ret++;
            value /= 2;
        }

        return ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int ai[] = new int[n + 1];
        int aitwoCount[] = new int[n + 1];
        int aifiveCount[] = new int[n + 1];

        for (int i = 1; i < n + 1; i++) {
            ai[i] = in.nextInt();
            aifiveCount[i] = getFiveCount(ai[i]);
            aitwoCount[i] = getTwoCount(ai[i]);

        }

        // Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();
        // Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();

        Map<Integer, List<Integer>> edges = new HashMap<>();
        for (int i = 0; i < n - 1; i++) {
            int a = in.nextInt();
            int b = in.nextInt();

            List<Integer> child1 = edges.get(a);
            if (child1 == null) {
                child1 = new ArrayList<Integer>();
                edges.put(a, child1);

            }
            child1.add(b);

            List<Integer> child2 = edges.get(b);
            if (child2 == null) {
                child2 = new ArrayList<Integer>();
                edges.put(b, child2);

            }
            child2.add(a);
        }

        // 找到所有子树的所有节点集合,建立映射关系。
        DFS(edges, 1);


        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            int x = in.nextInt();
            int y = in.nextInt();

            List<Integer> allNodes = subTreeNodes.get(x);
            // Integer[] temp = allNodes.toArray(new Integer[0]);
            // Arrays.stream(temp).forEach(item -> System.out.print(item + " "));
            // System.out.println();
            for (int nodeId : allNodes) {

                aifiveCount[nodeId] += getFiveCount(y);
                aitwoCount[nodeId] += getTwoCount(y);
            }
        }

        // Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();
        // Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();

        StringBuilder resultStr = new StringBuilder();

        for (int i = 1; i <= n; i++) {

            List<Integer> allNodes = subTreeNodes.get(i);
            int twoCount = 0;
            int fiveCount = 0;
            for (int nodeId : allNodes) {
                twoCount += aitwoCount[nodeId];
                fiveCount += aifiveCount[nodeId];
            }


            resultStr.append(Math.min(twoCount, fiveCount) + " ");
            
        }

        System.out.print(resultStr.toString());

        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
    }
}

运行超时,通过率70%。可见Hashset的运行效率比ArrayList低。

我的解答3

按照作者:今夕kpole的如下链接帖子的思路实现,程序还是运行超过1s,依然无法AC。

https://www.nowcoder.com/discuss/475037372275523584

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static int aitwoCount[] = new int[1];
    public static int aifiveCount[] = new int[1];
    public static int multiplyTwoCount[] = new int[1];
    public static int multiplyFiveCount[] = new int[1];


    public static void DFS(List<List<Integer>> edges, int nodeId, int parentNodeId, int twoCount,
                            int fiveCount) {
        aitwoCount[nodeId] += twoCount;
        aifiveCount[nodeId] += fiveCount;

        // 遍历所有子节点
        List<Integer> children = edges.get(nodeId);
        if (children != null) {
            for (int childNodeId : children) {
                // 如果子节点被遍历过
                if (childNodeId == parentNodeId) {
                    continue;
                }

                DFS(edges, childNodeId, nodeId, 
                                         twoCount + multiplyTwoCount[childNodeId],
                                         fiveCount + multiplyFiveCount[childNodeId]);

                aitwoCount[nodeId] += aitwoCount[childNodeId];
                aifiveCount[nodeId] += aifiveCount[childNodeId];
            }
        }

    }

    public static int getFiveCount(int value) {
        int ret = 0;
        while (value % 5 == 0) {
            ret++;
            value /= 5;
        }

        return ret;
    }

    public static int getTwoCount(int value) {
        int ret = 0;
        while (value % 2 == 0) {
            ret++;
            value /= 2;
        }

        return ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int ai[] = new int[n + 1];
        aitwoCount = new int[n + 1];
        aifiveCount = new int[n + 1];

        for (int i = 1; i < n + 1; i++) {
            ai[i] = in.nextInt();
            aifiveCount[i] = getFiveCount(ai[i]);
            aitwoCount[i] = getTwoCount(ai[i]);

        }

        // Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();
        // Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();

        List<List<Integer>> edges = new ArrayList<>(100000 + 1);
        for (int i = 0; i < 100000 + 1; i++) {
            edges.add(new ArrayList<Integer>());

        }
        for (int i = 0; i < n - 1; i++) {
            int a = in.nextInt();
            int b = in.nextInt();

            List<Integer> child1 = edges.get(a);
            if (child1 == null) {
                child1 = new ArrayList<Integer>();
                edges.set(a, child1);

            }
            child1.add(b);

            List<Integer> child2 = edges.get(b);
            if (child2 == null) {
                child2 = new ArrayList<Integer>();
                edges.set(b, child2);

            }
            child2.add(a);
        }



        multiplyTwoCount = new int[n + 1];
        multiplyFiveCount = new int[n + 1];
        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            int x = in.nextInt();
            int y = in.nextInt();

            //List<Integer> allNodes = subTreeNodes.get(x);
            // Integer[] temp = allNodes.toArray(new Integer[0]);
            // Arrays.stream(temp).forEach(item -> System.out.print(item + " "));
            // System.out.println();
            int fiveSum = getFiveCount(y);
            int twoSum = getTwoCount(y);
            multiplyFiveCount[x] += fiveSum;
            multiplyTwoCount[x] += twoSum;

        }

        DFS(edges, 1, -1, multiplyTwoCount[1], multiplyFiveCount[1]);

        // Arrays.stream(aitwoCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();
        // Arrays.stream(aifiveCount).forEach(item -> System.out.print(item + " "));
        // System.out.println();

        StringBuilder resultStr = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            resultStr.append(Math.min(aitwoCount[i], aifiveCount[i]) + " ");

        }

        System.out.print(resultStr.toString());

    }
}

运行超时,通过率80%。运行时间1149ms

java语言的运行效率比C++低不少啊。谁能救救我?

全部评论

相关推荐

程序员小白条:你得在IDEA工程里面,开启AI 插件,然后他直接训练工程,一般大项目很难的啦,你得丢很多代码,很超过长度的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务