devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十届蓝桥杯大赛软件类省赛Java研究生组-题解_蓝桥杯研究生组java真题

作者：我家小花儿 | 2024-03-30 23:55:54

赞

踩

蓝桥杯研究生组java真题

目录

试题A：立方和

试题B：子串数字

试题C：质数

试题D：最短路

试题E：RSA解密

试题F：Fibonacci数列与黄金分割

试题G：扫地机器人

试题H：修改数组

试题I：组合数问题

试题J：空间跳跃

试题A：立方和

答案：4097482414389

思路：直接枚举就可以，不过要用long，用int会爆的。

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         long sum = 0 ;
  4.         for(long i=1; i<=2019; i++){
  5.             if(f(i)){
  6.                 long ans = i * i * i ;
  7.                 sum += ans ;
  8.             }
  9.         }
  10.         System.out.println(sum);
  11.     }
  12.     private static boolean f(long x){
  13.         String s = String.valueOf(x) ;
  14.         for(int i=0; i<s.length(); i++){
  15.             if(s.charAt(i)=='2' || s.charAt(i)=='0' || s.charAt(i)=='1' || s.charAt(i)=='9'){
  16.                 return true ;
  17.             }
  18.         }
  19.         return false ;
  20.     }
  21. }

试题B：子串数字

答案：3725573269

思路：逻辑题，AC代码如下：

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner input = new Scanner(System.in) ;
  6.         long sum = 0 ;
  7.         int num = 0 ;
  8.         String s = input.next() ;
  9.  
  10.         for(int i=0; i<s.length(); i++){
  11.             num = s.charAt(s.length()-i-1) -'A' + 1 ;
  12.             sum += num * Math.pow(26,i) ;
  13.         }
  14.         System.out.println(sum);
  15.     }
  16. }

 

试题C：质数

答案：17569

 思路：枚举1~2019，写个方法判断是否是质数就可以了。

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         int ans=0, cnt = 0 ;
  4.         for(int i=2; cnt!=2019; i++){
  5.             if(f(i)){
  6.                 cnt ++ ;
  7.                 ans = i ;
  8.             }
  9.         }
  10.         System.out.println(ans);
  11.     }
  12.     private static boolean  f(int x){
  13.         for(int i=2; i<x; i++){
  14.             if(x%i==0){
  15.                 return false ;
  16.             }
  17.         }
  18.         return true ;
  19.     }
  20. }

试题D：最短路

答案：6

 思路：这题不需要写代码，我没看错的话是6，这题和最短路算法没毛线关系，倒是可以区分红绿色盲。

试题E：RSA解密

答案：579706994112328949

 

思路：扩展欧几里得原理+快速幂+快速乘

这题要求数论要好，这题我参考的别人的代码，如下所示：

  1. public class Main {
  2.     static long p, q, m, x, y;
  3.     static long n = 1001733993063167141L;
  4.  
  5.     public static void main(String[] args) {
  6.  
  7.         long d = 212353L;
  8.         long c = 20190324L;
  9.         p = 2;
  10.         // 先求p、q
  11.         while (true) {
  12.             if ((n / p) * p == n) {
  13.                 q = n / p;
  14.                 break;
  15.             }
  16.             p++;
  17.         }
  18.         // 再求e
  19.         m = (p - 1) * (q - 1);
  20.         // ans[1] == x ans[2] = y
  21.         long[] ans = exgcd(d, m);
  22.         ans[1] = (ans[1] + m) % m; // 579706994112328949
  23.         // X = C^e % n
  24.         System.out.println(qpow(c, ans[1]));
  25.     }
  26.     
  27.     public static long[] exgcd(long a, long b) {
  28.         long ans;
  29.         long[] result = new long[3];
  30.         if (b == 0) {
  31.             result[0] = a;
  32.             // 这里的result[1]、result[2]分别相当于一个解中的x、y
  33.             result[1] = 1;
  34.             result[2] = 0;
  35.             return result;
  36.         }
  37.         // temp数组中存储的是上一组的解，temp[1]相当于X2，temp[2]相当于Y2
  38.         long[] temp = exgcd(b, a % b);
  39.         // result[0]存储的就是两个数的最大公约数
  40.         ans = temp[0];
  41.         result[0] = ans;
  42.         // 这里result[1]相当于X1，result[2]相当于Y1
  43.         result[1] = temp[2];
  44.         result[2] = temp[1] - (a / b) * temp[2];
  45.         return result;
  46.     }
  47.     
  48.     public static long qpow(long a, long b) {
  49.         // 累乘就初始为1
  50.         long ans = 1;
  51.         while (b > 0) {
  52.             if (b % 2 == 1)
  53.                 ans = qmul(ans, a);
  54.             a = qmul(a, a);
  55.             b /= 2;
  56.         }
  57.         return ans;
  58.     }
  59.     
  60.     public static long qmul(long a, long b) {
  61.         // 累加就初始为0
  62.         long ans = 0;
  63.         while (b > 0) {
  64.             if (b % 2 == 1) {
  65.                 ans += a;
  66.                 ans %= n;
  67.             }
  68.             a *= 2;
  69.             a %= n;
  70.             b /= 2;
  71.         }
  72.         return ans;
  73.     }
  74. }

试题F：Fibonacci数列与黄金分割

思路：N到达20就比值就恒定了，20之前调用函数计算，20之后直接打印输出。 

  1.  
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner input = new Scanner(System.in) ;
  7.         int N = input.nextInt() ;
  8.         if(N<=20) {
  9.             System.out.printf("%.8f", 1.0 * f(N) / f(N + 1));
  10.         }else{
  11.             System.out.println(0.61803399);
  12.         }
  13.  
  14.     }
  15.     private static double f(int n){
  16.         if(n==1 || n==2){
  17.             return 1 ;
  18.         }
  19.         return f(n-1) + f(n-2) ;
  20.     }
  21. }

试题G：扫地机器人

思路： 这题最初没想到，参考别人的思路，二分+贪心的思想。

二分机器人的扫地范围，当每个机器人清扫的面积相差很小时，耗时较少，
* 假设二分的扫地范围是x，对于每一个扫地机器人，我们尽可能让它扫地的右边界大一些，
* 也就是扫过的格子，没有必要绝对不扫。最后看扫地的右边界是否大于等于格子的边界，
* 如果是的话，就说明符合条件，否则就不符合条件。

  1.  
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. public class Main {
  6.     static int N, K ;
  7.     static int [] a ;
  8.     public static void main(String[] args) {
  9.         Scanner input = new Scanner(System.in) ;
  10.          N = input.nextInt() ;
  11.          K = input.nextInt() ;
  12.          a = new int [K+1] ;
  13.  
  14.         for(int i=1; i<=K; i++){
  15.             a[i] = input.nextInt() ;
  16.         }
  17.  
  18.         Arrays.sort(a) ;
  19.  
  20.         int l = 0, r = N, mid, ans=0 ;
  21.  
  22.         while(l<=r){
  23.             mid = (l+r)>>1 ;
  24.             if(check(mid)){
  25.                 r = mid - 1 ;
  26.                 ans = mid ;
  27.             }else{
  28.                 l = mid + 1 ;
  29.             }
  30.         }
  31.         System.out.println((ans-1)*2);
  32.     }
  33.     private static boolean check(int x){
  34.         int sum = 0 ;
  35.         for(int i=1; i<=K; i++){
  36.             if(a[i]-x<=sum)
  37.             {
  38.                 if(a[i]<=sum) sum=a[i]+x-1;
  39.                 else sum=sum+x;
  40.             }
  41.             else return false;
  42.         }
  43.         return sum >= N;
  44.     }
  45. }

试题H：修改数组

思路1：第一想法，开辟一个标记数组flag，去标记之前出现过，从前向后遍历，遇到出现过的就加1再判断，这种方法简单快捷，不过对于最后20%的测试数据可能超时。

 

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner input = new Scanner(System.in) ;
  6.         int N = input.nextInt() ;
  7.         int [] a = new int [N] ;
  8.         boolean [] flag = new boolean [1000001] ;
  9.  
  10.         for(int i=0; i<N; i++){
  11.             a[i] = input.nextInt() ;
  12.         }
  13.  
  14.         for(int i=0; i<N; i++){
  15.            if(!flag[a[i]]){
  16.                flag[a[i]] = true ;
  17.            }else{
  18.                int num = a[i] + 1 ;
  19.                while(flag[num]){
  20.                    num ++ ;
  21.                }
  22.                a[i] = num ;
  23.                flag[num] = true ;
  24.            }
  25.         }
  26.         for(int ans : a){
  27.             System.out.print(ans + " ");
  28.         }
  29.  
  30.     }
  31. }

思路2：标准解法，并查集，乍一下没想到这题竟然考的并查集。如果出现过，就将该数字加1作为该数字的爹，下次直接找它爹就行，不要再找它，就不重复了。

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     static int N;
  5.     static int [] A ;
  6.     static int [] parent ;
  7.     public static void main(String[] args) {
  8.         Scanner input = new Scanner(System.in) ;
  9.         N = input.nextInt() ;
  10.         A = new int [N] ;
  11.         parent = new int [1000001] ;
  12.  
  13.         for(int i=1; i<parent.length; i++){
  14.             parent[i] = i ;
  15.         }
  16.         for(int i=0; i<N; i++){
  17.             A[i] = input.nextInt() ;
  18.         }
  19.  
  20.         for(int i=0; i<A.length; i++){
  21.             int k = find(A[i]) ;
  22.             A[i] = k ; //将它爹赋值给它
  23.             parent[A[i]] = find(parent[A[i]+1]) ; //更新爹
  24.         }
  25.  
  26.         for(int ans : A){
  27.             System.out.print(ans + " ");
  28.         }
  29.  
  30.     }
  31.     private static int find(int x){
  32.         if(x!=parent[x]){
  33.             parent[x] = find(parent[x]) ;
  34.         }
  35.         return parent[x] ;
  36.     }
  37.  
  38. }

试题I：组合数问题

思路：拿分为主，面向测试用例编程，直接组合数递推公式暴力求解，可以通过40%的测试用例。

满分解法是数位dp，卢卡斯定理！！！

  1.  
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     static int mod = 1000000007 ;
  6.     static int [][] c ;
  7.     public static void main(String[] args) {
  8.         Scanner input = new Scanner(System.in) ;
  9.         int t = input.nextInt() ;
  10.         int k = input.nextInt() ;
  11.         c = new int [2001][2001] ;
  12.  
  13.         init();
  14.         for(int i=0; i<t; i++){
  15.             int ans = 0 ;
  16.             int n = input.nextInt() ;
  17.             int m = input.nextInt() ;
  18.             for(int j=1; j<=n; j++){
  19.                 for(int l=0; l<=Math.min(j,m); l++){
  20.                     if(c[j][l]%k==0){
  21.                         ans = (ans + 1) % mod ;
  22.                     }
  23.                 }
  24.             }
  25.             System.out.println(ans%mod);
  26.         }
  27.  
  28.     }
  29.  
  30.     private static void init(){
  31.         for(int i=0; i<=2000; i++){
  32.             for(int j=0; j<=i; j++){
  33.                 if(j==0){
  34.                     c[i][j] = 1 ;
  35.                 }else{
  36.                     c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod ;
  37.                 }
  38.             }
  39.         }
  40.     }
  41. }

试题J：空间跳跃

这题没思路，题解参考链接：https://www.icode9.com/content-1-628488.html

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/342391?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号