时间是晚上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;