小红的子树操作
小红的子树操作
题意
小红拿到了一棵有根树,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++低不少啊。谁能救救我?