全国高校计算机能力挑战赛

发表于 2020-11-30 分类于竞赛

2020真题

16题：1-N整数中所有立方值的平方根为整数的数的个数

输入： 10
输出： 3

输入是10，其中1* 1* 1 = 1，平方根是1，为整数输入是4，其中4 * 4 * 4 = 64，平方根是8，为整数输入是8，其中9 * 9 * 9 = 729，平方根是27，为整数输出 3

 public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 0;
        for(int i = 1; i <= N; i++){
            int mul = i * i * i;
            int sqrt = (int)Math.sqrt(mul);
            if(sqrt * sqrt == mul){
                count++;
            }
        }
        System.out.println(count);
    }
}

17题：收到N个鸡蛋，每个鸡蛋各有重量，找出M个重量差距最小的鸡蛋摆出一盒出售，输出最重一盒鸡蛋的总重量。

输入：
8 4
11 9 12 5 10 19 8 6  

输出：
42

思路：要找出M个重量差距最小的放在一盒（即一组），可以先将所有鸡蛋的重量（数组中所有元素）从小到大排序，找出每组的最大值 - 最小值，其中差值最小的且数组元素总和最大的一组即为所求，输出这组的元素总和。

实现步骤：

将数组进行排序（采用了快速排序，具体讲解请见另一篇博文）
将N- M + 1组的差值保存在abs数组
找出abs数组的最小值（与排序后nums的索引相同）
上面找出的最小值可能有多个元素相同为最小值，从后向前遍历abs数组，找到最小值的那组nums元素，输出它们的和。
题目要求输入的N和M是整数，鸡蛋重量和最后的输出都是浮点型，输出结果保留两位小数。

public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String str1 = sc.nextLine();
      String str2 = sc.nextLine();
      String[] num = str1.split(" ");
      int N = Integer.parseInt(num[0]);
      int M = Integer.parseInt(num[1]);
      String[] ff = str2.split(" ");

      float[] nums = new float[N];
      for(int i = 0; i < N; i++){
          nums[i] = Float.parseFloat(ff[i]);
      }
      //        Arrays.sort(nums);
      quickSort(nums,0,nums.length - 1);

      float res = 0;
      //M个重量差距最小 即找出最小差值
      float[] abs = new float[N - M + 1];
      for(int i = 0; i < N - M + 1; i++){
              abs[i] = nums[i + M - 1] - nums[i];
      }
      //找出abs中的最小值
      float min = abs[0];
      for(int i = 0; i < abs.length; i++){
          if(abs[i] < min){
              min = abs[i];
          }
      }
      //返回abs[i]中元素的和
      for(int i = abs.length - 1; i >= 0 ; i--){
          if(min == abs[i]){
              //3-6 N=8 M=4 i=6
              for(int j = i + (N - M -1); j >= i ; j--){
                  res += nums[j];
              }
              break;
          }
      }
      //题目要求结果保留两位小数
      DecimalFormat fnum  =   new  DecimalFormat("##0.00");
      String dd = fnum.format(res);
      System.out.println(dd);
  }
  //快速排序
  public static void quickSort(float[] nums, int start, int end) {
      //数组有多个元素进行排序
      if (start < end) {
          float base = nums[start];//以要进行排序数组第0个元素为base
          int left = start;//左指针
          int right = end;//右指针
          while (left < right) {
              //从右向左找，比base大，right--
              while (left< right && nums[right] >= base) {
                  right--;
              }
              //比base小，替换left所在位置的数字
              nums[left] = nums[right];
              //从左向右找，比base小，left++
              while (left < right && nums[left] <= base){
                  left++;
              }
              //比base大，替换right所在位置的数字
              nums[right] = nums[left];
          }
          //交换base与此时left、right指向的元素
          float temp = nums[left];
          nums[left] = base;//此时left=right，用base替换这个位置的数字
          base = temp;
          //排列比base小的数字的数组
          quickSort(nums, start, left - 1);
          //排列比base大的数字的数组
          quickSort(nums, left + 1, end);
      }
  }
}

运行结果：

19题：一种每瓶含奶粉15g茶粉5g，另一种每瓶含奶粉10g茶粉10g。设某天消耗的奶粉和茶粉分别为x和y 求当天饮料店两种饮料的销量

输入：400 300
输出：10 25

方法一：数学方法，解一元二次方程组。

public class Main{
 	public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    //15 * m + 10 * n = 400   5 * m + 10 * n = 300
    System.out.println((a - b) / 10 + " " + (3 * b - a) / 20);
 	}
}

模拟题

题目1：给定字符数组，统计字母类型（a-z）、数字类型（0-9）和符号类型（除字母、数字及空格以外的其他字符）的字符出现次数。

输入：
Hello World!
输出：
a-z 10
0-9 0
others 1

ASCII 码一共规定了128个字符的编码，0-31及127是控制字符或通信专用字符，32-126是字符，其中：32为空格，48-57为0~9十个阿拉伯数字，65-90为26个大写英文字母，97-122为26个小写英文字母。

public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      String input = in.nextLine();

      int count1 = 0;
      int count2 = 0;
      int count3 = 0;
      int count4 = 0;
      for (int i = 0; i < input.length(); i++) {
          char temp = input.charAt(i);
          if (65 <= temp && temp <= 90 || 97 <= temp && temp <= 122) {
              count1++;
          }
          else if (48 <= temp && temp <= 57) {
              count2++;
          }
          //空格
          else if(temp <= 32)
              count3++;
          else count4++;
      }
      System.out.println("a-z" + " " + count1);
      System.out.println("0-9" + " " + count2);
      System.out.println("others" + " " + count4);
  }

题目2：输入第一行，数组中元素的个数第二行，N个正整数，空行隔开输出：3合数区间的个数。连续3个元素均为合数的区间为3合数区间

输入：
7
6 8 4 9 7 5 8
输出：
2

合数即除了能被1和它本身整除，还能被其他数整除。与质数相对，质数也叫素数。

public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);
     int N = sc.nextInt();//N个整数
     int[] nums = new int[N];
     int count = 0;
     for(int i = 0; i < nums.length; i++){
         nums[i] = sc.nextInt();

     }
     for(int i = 0; i < nums.length - 2; i++) {
         if (!isPrime(nums[i]) && !isPrime(nums[i + 1]) && !isPrime(nums[i + 2])) count++;
     }
     System.out.println(count);

 }
 //返回true,不是合数;返回false,是合数
 public static boolean isPrime(int n){
     //质数不小于2    2，3，5，7。。。
     if(n < 2) return false;
     for(int i = 2; i <= Math.sqrt(n); i++){
         if(n % i == 0) return false;
     }
     return true;
 }

题目3：统计1-N之间所有平方数的个数

输入：50
输出：7

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int count = 0;
    for(int i = 1; i <= N; i++){

        int m = (int)Math.sqrt(i);
        if(m * m == i){
            count++;
        }
    }
    System.out.println(count);
}

题目4：由N个整数组成的数组，连续K个元素构成一个区间，称为K区间。一个K区间内所有素数和记为Sk，输出所有K区间的最大Sk值。第一行是两个整数N和K，第二行为N个数，输出最大Sk值。

示例1：

输入：8 2
     12 23 27 34 19 17 45 8
输出：36

方法一：双重for循环。建立一个数组res存储所有K区间的Sk值。第一层遍历所有的N - K + 1个区间，第二层遍历区间的K个元素，如果有素数，加入到res[i]中，最后在结果数组res中取最大值。

public class Solution2_19 {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      int K = sc.nextInt();
      int[] nums = new int[N];
      for (int i = 0; i < N; i++) {
          nums[i] = sc.nextInt();
      }
      //区间个数
      int[] res = new int[N - K + 1];
      int max = 0;
      for (int i = 0; i < N - K + 1; i++) {
          for (int j = i; j < i + K; j++) {
              //是素数
              if (isPrime(nums[j])) {
                  res[i] += nums[j];

              }
          }
          int temp = 0;
          if (res[i] > max) {
              temp = max;
              max = res[i];
              res[i] = temp;
          }

      }
      System.out.println(max);
      //        Arrays.sort(res);
      //        System.out.println(res[N - K]);
      ｝
      
      //判断是否是素数
     public static boolean isPrime(int a) {
      	boolean flag = true;
      	if (a < 2) {// 素数不小于2
          	return false;
      	} else {
         	 for (int i = 2; i <= Math.sqrt(a); i++) {
              	if (a % i == 0) {// 若能被整除，则说明不是素数，返回false
                  flag = false;
                  break;// 跳出循环
              }
          }
      }
      return flag;
 	 }
  ｝

测试

题目5：由N个整数组成的数组，其中连续K（K <= 200）个元素构成一个区间，称为K区间。一个K区间中任意两个数求其差值的绝对值其中最大的绝对值记为Dk。

示例：

输入：8 2
     12 23 27 34 35 36 8 45
输出：37

方法一：和另一道题类似，在双重循环中定义最大值max，最小值min为K区间首个元素，下面再进行判断是否还有比max大的重新确定为max，比min小的重新确定为min。max-min即为Dk，保存在数组res中，res长度为N - K + 1，输出即为res中的最大值。

public class Solution4 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int K = input.nextInt();
        //先划分为 N-K+1 个 K区间，在区间内排序，计算最大绝对值
        //N-K+1 数组的区间数
        int[] nums = new int[N];
        for(int i = 0; i < N; i++){
            nums[i] = input.nextInt();
        }
        int[] res = new int[N - K + 1];
        int max = 0;int min = 0;
        for (int i = 0; i < N - K + 1; i++) {
            for (int j = i; j < i + K ; j++) {
                max = nums[i];
                min = nums[i];

                if(nums[j] > max) {
                    max = nums[j];
                }
                if(nums[j] < min) {
                    min = nums[j];
                }
            }

            res[i] = max - min;

        }
//        Arrays.sort(res);
//        System.out.println(res[N - K]);
        System.out.println(Dk(res));

    }
//找到数组最大值
    private static int Dk(int[] nums) {
        int max = nums[0];
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > max){
                max = nums[i];
            }
        }
        return max;
    }
}

测试结果

题目6：字母连连看，给定一个由小写英文字母组成的字符串，如果字符串中有两个连续的字母相同，则这两个字母可同时消除，并不断重复该操作，直到不能消除为止。

示例1：

输入：abbcddcaba
输出：YES

示例2：

输入：asdfghhgf
输出：asd

方法一：借助辅助栈。

若栈为空，将输入字母入栈。否则，比较栈顶元素与下一个入栈的字母，若相等，则弹出栈顶元素；若不同，入栈。最后判断栈是否为空，若空，输出YES；若栈不为空，倒序输出栈中元素。

借助StringBuilder，将栈中元素加入，再逆序打印。

public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String s = sc.next();
      Stack<Character> stack = new Stack<>();

      for (int i = 0; i < s.length(); i++) {
          char[] chars = new char[s.length()];
          chars[i] = s.charAt(i);
          if (!stack.isEmpty()) {
              if (stack.peek() != chars[i]) {
                  stack.push(chars[i]);
              }
              else stack.pop();
          } else
              stack.push(chars[i]);
      }
      //判断
      if (stack.isEmpty())
          System.out.println("YES");
      else {
          StringBuilder sb = new StringBuilder();
          while(!stack.isEmpty()){
              sb.append(stack.pop());
          }
          System.out.println(sb.reverse());
   }

方法二：与上面思路类似，改为使用list实现。最后一步无需逆序打印，直接遍历输出结果。

public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);
     String s = sc.next();
     List<Character> list = new ArrayList<>();

     for (int i = 0; i < s.length(); i++) {
         char[] chars = new char[s.length()];
         chars[i] = s.charAt(i);
         if(!list.isEmpty()) {
             if (!list.contains(chars[i])) {
                 list.add(chars[i]);
             } else list.remove(list.get(list.size() - 1));
         }
         else list.add(chars[i]);
     }

     if (list.isEmpty()) System.out.println("YES");
     else {
         for (char a : list) {
             System.out.print(a);
         }
     }
 }

------ 本文结束感谢您的阅读 ------