时间是晚上7点到8点半 总共一个半小时
已知10个元素数据(54,28,16,34,73,62,95,60,26,43)依次插入节点的方法生成一颗二叉排序树,再查找成功的情况下,每个元素的平均比较次数为?
解
理解二叉树结构
总比较次数应该为 1+2+3+3+2+3+3+4+4+4=29 平均比较次数为2.9
给定一个无向图的节点编号结合为{A,B,C,D,E,F},边的结合为{A-C,A-D,B-C,B-E,B-F,C-D,C-F,E-F},已下选项中,从顶点A出发,不可以得到的深度优先订单序列为:
A: ACDFEB
B:ACFEDB
C:ADCBFE
D:ACFEBD
解
顺一下
深度优先搜索(DFS)的顺序是由每个节点的访问顺序和访问策略 决定的
从A点出发必须遵循图的结构和路径的选择
选D
小美对gcd 最大公约数很感兴趣 会询问t次
每次给出一个大于1的正整数n 是否找到m 让gcd(n,m)为素数
ACM模式
每组包含多组测试数据
如果有多种合法答案 可以任意输出一种
想法
注意到n是(2~10e5)级别的数
可以考虑用暴力遍历
package Dduo; import java.math.BigInteger; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); static long mod = (long) (1e9 + 7); static int cnt = 0; public static void main(String[] args) { int t = 1; t=sc.nextInt(); while (t-- > 0) { solve(); } sc.close(); return; } private static void solve() { int n=sc.nextInt(); for(int i=2;i<=n;i++) { if(isPrime(gcd(i,n))) { System.out.print(i); return; } } System.out.print("-1"); } public static int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } public static boolean isPrime(int number) { if (number <= 1) { return false; } if (number <= 3) { return true; } if (number % 2 == 0 || number % 3 == 0) { return false; } for (int i = 5; i * i <= number; i += 6) { if (number % i == 0 || number % (i + 2) == 0) { return false; } } return true; } }
给出一个数组 长度为n
给出一个固定整数k
第一步 小美选择一个非空区间 区间内所有的数字乘k
第二步 小团选择一个非空区间 区间内所有的数字乘k
sum为数组所有元素之和 小美想让sum尽可能大 小团想让sum尽可能小
求最后的sum数值
想法
注意到k的范围 (-10e5~10e5)
分k大于小于等于0考虑
可以先找到和最大的连续元素段再返回新数组
再去找最小的
package Dduo; import java.math.BigInteger; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); static long mod = (long) (1e9 + 7); static int cnt = 0; public static void main(String[] args) { int t = 1; // t=sc.nextInt(); while (t-- > 0) { solve(); } sc.close(); return; } private static void solve() { int n=sc.nextInt(); int k=sc.nextInt(); long arr[]=new long[n]; for(int i=0;i<n;i++) { arr[i]=sc.nextLong(); } long sum=0; if(k>0) { long ans1[]=findAndMultiplyMaxSumSubarray(arr,k); long ans2[]=findAndMultiplyMinSumSubarray(ans1,k); for(int i=0;i<n;i++) { sum+=ans2[i]; } System.out.print(sum); }else if(k<0) { long ans1[]=findAndMultiplyMinSumSubarray(arr,k); long ans2[]=findAndMultiplyMaxSumSubarray(ans1,k); for(int i=0;i<n;i++) { sum+=ans2[i]; } System.out.print(sum); }else { for(int i=0;i<n;i++) { sum+=arr[i]; } System.out.print(sum); } } public static long[] findAndMultiplyMaxSumSubarray(long[] arr, double d) { int n = arr.length; long[] result = Arrays.copyOf(arr, n); long maxSum = Long.MIN_VALUE; long currentSum = 0; int start = 0; int end = 0; int maxStart = 0; int maxEnd = 0; for (int i = 0; i < n; i++) { currentSum += arr[i]; if (currentSum > maxSum) { maxSum = currentSum; maxStart = start; maxEnd = i; } if (currentSum < 0) { currentSum = 0; start = i + 1; } } for (int i = maxStart; i <= maxEnd; i++) { result[i] *= d; } return result;
全部评论
(3) 回帖