devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：从前慢现在也慢 | 2024-03-30 23:51:41

赞

踩

蓝桥杯研究生组java分果果

目录

试题A：卡片

试题B：相乘

试题C：直线

试题D：路径

试题E：回路计数

试题F：时间显示

试题G：最少砝码

试题H：杨辉三角

试题I：双向排序

试题J：分果果

试题A：卡片

答案：3181

思路：num数组记录0-9的个数，从1开始判断，如果数字的各位中含有字母c，则num[c]减1，直至最后num[c]<0,则不能凑出。

  1. public class Main {
  2.     public static void main(String[] args) {
  3.  
  4.         int [] num = {2021,2021,2021,2021,2021,2021,2021,2021,2021,2021} ;
  5.         for(int i=1; ; i++){
  6.             String s = String.valueOf(i) ;
  7.             for(int j=0; j<s.length(); j++){
  8.                 int c = s.charAt(j) - '0' ;
  9.                 num[c] -- ;
  10.                 if(num[c]<0){
  11.                     System.out.println(i-1);
  12.                     return ;
  13.                 }
  14.             }
  15.         }
  16.     }
  17. }

试题B：相乘

答案：17812964

思路：枚举+判断即可。

  1. public class Main {
  2.     public static void main(String[] args) {
  3.  
  4.         for(long i=1; i<=1000000007; i++){
  5.             if((i * 2021)%1000000007==999999999){
  6.                 System.out.println(i);
  7.                 return ;
  8.             }
  9.         }
  10.         System.out.println(0);
  11.     }
  12. }

试题C：直线

答案：40257

思路：这题并不太容易想到，其实就是枚举所有点，判断对应的斜率和截距组成的不同坐标的个数，可以用set自动去重。

公式：y-y1=(y2-y1)/(x2-x1)*(x-x1)

故：k=(y2-y1) / (x2-x1) ; b=(x2*y1-x1*y2)/(x2-x1)

  1.  
  2. import java.util.Set;
  3. import java.util.TreeSet;
  4.  
  5. public class Main {
  6.     public static void main(String[] args) {
  7.         Set<String> set = new TreeSet<>() ;
  8.         double k, b ;
  9.         for(int x1=0; x1<20; x1++){
  10.             for(int y1=0; y1<=20; y1++){
  11.                 for(int x2=x1+1; x2<20; x2++){
  12.                     for(int y2=0; y2<=20; y2++){
  13.                         k = 1.0  * (y2 - y1) / (x2 - x1) ;
  14.                         b = 1.0 * (x2 * y1 - x1 * y2) / (x2 - x1) ;
  15.                         set.add(k+","+b) ;
  16.                     }
  17.                 }
  18.             }
  19.         }
  20.         System.out.println(set.size()+20); //要加上斜率不存在的20个
  21.     }
  22. }

试题D：路径

答案：10266837

思路：单源最短路径，Dijkstra算法，建立邻接表，如果节点之差绝对值小于等于21，建立边，对应的边权值为两节点值得最小公倍数，dist数组记录到达相应节点得最短路径，通过优先队列按照权值最小排序，每次选择更小得路径 ，更新当前路径。

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.PriorityQueue;
  4.  
  5. public class Main{
  6.     public static void main(String[] args) {
  7.         List<int []> g[] = new List [2022] ;
  8.         for(int i=0; i<2022; i++){
  9.             g[i] = new ArrayList<>() ;
  10.          }
  11.  
  12.         for(int i=1; i<=2020; i++){
  13.             for(int j=i+1; j<=2021; j++){
  14.                 if(Math.abs(i-j)<=21){
  15.                     g[i].add(new int [] {j, f(i,j)}) ;
  16.                     g[j].add(new int [] {i, f(i,j)}) ;
  17.                 }
  18.             }
  19.         }
  20.         int [] dist = new int [2022] ;
  21.         for(int i=1; i<2022; i++){
  22.             dist[i] = Integer.MAX_VALUE ;
  23.         }
  24.         dist[1] = 0 ;
  25.  
  26.         //优先队列，按权值进行升序排序
  27.         PriorityQueue<int []> queue = new PriorityQueue<int[]>((a,b)->a[1]!=b[1] ? a[1] - b[1] : a[0] - b[0]) ;
  28.         queue.add(new int[]{1,0}) ; //到达的节点和对应的权值
  29.         while(!queue.isEmpty()){
  30.             int [] p = queue.poll() ;
  31.             int x = p[0], w = p[1] ;
  32.             if(dist[x]<w){
  33.                 continue;
  34.             }
  35.             for(int [] edges : g[x]){
  36.                 int y = edges[0], d = dist[x] + edges[1]  ;
  37.                 if(d<dist[y]){
  38.                     dist[y] = d ;
  39.                     queue.add(new int [] {y, d}) ;
  40.                 }
  41.             }
  42.         }
  43.         System.out.println(dist[2021]);
  44.  
  45.  
  46.     }
  47.     private static int f(int a, int b){
  48.        return a * b /  gcd(a,b) ;
  49.     }
  50.     private static int gcd(int a, int b){
  51.         if(b==0){
  52.             return a ;
  53.         }else{
  54.             return gcd(b,a%b) ;
  55.         }
  56.     }
  57. }

试题E：回路计数

答案：881012367360

思路：状压+dp，f[i][j]表示从1出发走到j且经过i得方案数，用二进制表示经过点的状态。

  1. public class Main {
  2.     static boolean [][] edges ;
  3.     static int m = 1 << 21 ;
  4.     static long [][] f ;
  5.     public static void main(String[] args) {
  6.         edges = new boolean [21][21] ;
  7.         f = new long [m][21] ;
  8.         for(int i=1; i<=21; i++){
  9.             for(int j=1; j<=21; j++){
  10.                 if(gcd(i,j)==1){
  11.                     edges[i-1][j-1] = true ;
  12.                 }
  13.             }
  14.         }
  15.  
  16.         f[1][0] = 1 ;
  17.         for(int i=0; i<=m-1; i++){
  18.             for(int j=0; j<=20; j++){
  19.                 if((i>>j & 1) != 0){
  20.                     for(int k=0; k<=20; k++){
  21.                         if((i-(1<<j)>>k & 1)!=0 && edges[k][j]){
  22.                             f[i][j] += f[i-(1<<j)][k] ;
  23.                         }
  24.                     }
  25.                 }
  26.             }
  27.         }
  28.         long ans = 0 ;
  29.         for(int i=1; i<=20; i++){
  30.             ans += f[m-1][i] ;
  31.         }
  32.         System.out.println(ans);
  33.  
  34.     }
  35.  
  36.     private static int gcd(int m, int n) {
  37.         if(n==0){
  38.             return m ;
  39.         }else{
  40.             return gcd(n, m%n) ;
  41.         }
  42.     }
  43.  
  44. }

试题F：时间显示

思路：模拟，将总毫秒数对一天的毫秒数取余，得到的time是剩余需要操作的毫秒数，计算出时分秒即可，如果是个位数，需要在前面补零。

  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 t = input.nextLong() ;
  7.  
  8.         long ms = 24 * 60 * 60 * 1000 ;
  9.         long time = t % ms ;
  10.  
  11.         long hour = time / 3600000 ;
  12.         long min = (time % 3600000) / 60000 ;
  13.         long sec = ((time%3600000) % 60000) / 1000 ;
  14.  
  15.         String h = String.valueOf(hour) ;
  16.         String m = String.valueOf(min) ;
  17.         String s = String.valueOf(sec) ;
  18.         if(h.length()==1){
  19.             h = "0" + h ;
  20.         }
  21.         if(m.length()==1){
  22.             m = "0" + m ;
  23.         }
  24.         if(s.length()==1){
  25.             s = "0" + s ;
  26.         }
  27.  
  28.         System.out.println(h + ":" + m + ":" + s);
  29.     }
  30. }

试题G：最少砝码

思路：规律题，我们想使用最少的砝码称出任意小于等于N的正整数数量，我们用count记录 砝码个数，weight记录所需的最后一个砝码的重量，total记录砝码能称出的总重量，这样会发现weight每次应该乘以3，而total等于上一轮的toal加上这次的weight。

  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 count = 1 ; //砝码个数
  8.         int weight = 1 ; //最后一个砝码的重量
  9.         int total = 1 ; //砝码能称出的总重量
  10.  
  11.         while(total<N){
  12.             count ++ ;
  13.             weight *= 3 ;
  14.             total += weight ;
  15.         }
  16.  
  17.         System.out.println(count);
  18.  
  19.     }
  20. }

试题H：杨辉三角

思路：这题想AC，不太容易，很容易爆内存，那就先混分吧，开辟二维数组记录杨辉三角，然后转成一维数组，vis数组标记是否是第一次出现，index数组记录第一次出现的位置。

  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 [20][20] ;
  8.         int [] ans = new int [100000000] ;
  9.         int [] vis = new int [100000000] ;
  10.         int [] index = new int [100000000] ;
  11.         for(int i=0; i<20; i++){
  12.             for(int j=0; j<=i; j++){
  13.                 if(i==j || j==0){
  14.                     a[i][j] = 1 ;
  15.                 }else{
  16.                     a[i][j] = a[i-1][j-1] + a[i-1][j] ;
  17.                 }
  18.             }
  19.         }
  20.  
  21.         int k = 0 ;
  22.         for(int i=0; i<20; i++) {
  23.             for (int j = 0; j <= i; j++) {
  24.                 ans[k++] = a[i][j] ;
  25.                 if(vis[a[i][j]]==0){
  26.                     vis[a[i][j]] = 1 ;
  27.                     index[a[i][j]] = k ;
  28.                 }
  29.             }
  30.         }
  31.             System.out.println(index[N]);
  32.     }
  33. }

试题I：双向排序

思路：这题考的是线段树，对于混分大师来说，根据题意模拟双向排序就行。

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     static int [] a ;
  6.     public static void main(String[] args) {
  7.         Scanner input = new Scanner(System.in) ;
  8.         int n = input.nextInt() ;
  9.         int m = input.nextInt() ;
  10.  
  11.         a = new int [n] ;
  12.  
  13.         for(int i=1; i<=n; i++){
  14.             a[i-1] = i ;
  15.         }
  16.  
  17.         for(int i=1; i<=m; i++){
  18.             int p = input.nextInt() ;
  19.             int q = input.nextInt() ;
  20.             if(p==0) {
  21.                 desc(a,0,q-1);
  22.             }else if(p==1){
  23.                 asc(a,q-1,n-1) ;
  24.             }
  25.         }
  26.         for(int i=0; i<a.length; i++){
  27.             System.out.print(a[i]+" ");
  28.         }
  29.     }
  30.  
  31.     private static void desc(int[] a, int begin, int end) {
  32.         int [] ans = new int [end-begin+1] ;
  33.         int j = 0 ;
  34.         for(int i=begin; i<=end; i++){
  35.             ans[j++] = a[i] ;
  36.         }
  37.         Arrays.sort(ans);
  38.         j-- ;
  39.         for(int i=begin; i<=end; i++){
  40.             a[i] = ans[j--] ;
  41.         }
  42.     }
  43.  
  44.     private static void asc(int[] a, int begin, int end) {
  45.         int [] ans = new int [end-begin+1] ;
  46.         int j = 0 ;
  47.         for(int i=begin; i<=end; i++){
  48.             ans[j++] = a[i] ;
  49.         }
  50.         Arrays.sort(ans);
  51.         j = 0 ;
  52.         for(int i=begin; i<=end; i++){
  53.             a[i] = ans[j++] ;
  54.         }
  55.     }
  56. }

试题J：分果果

思路：有些难的动态规划了，思路可以参考这个：蓝桥杯 - 分果果 - SOSCHINA - 博客园

  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     public static void main(String[] args) { new Main().run(); }
  7.  
  8.     int INF = 0x3F3F3F3F;
  9.  
  10.     void run() {
  11.         InputReader in = new InputReader(System.in);
  12.         int n = in.readInt(), m = in.readInt(), ans = INF;
  13.         int[][][] dp = new int[m + 1][n + 1][n + 1];
  14.         int[] S = new int[n + 1];
  15.         for (int i = 1; i <= n; i++)
  16.             S[i] = S[i - 1] + in.readInt();
  17.         for (int i = 0; i <= m; i++)
  18.             for (int j = 0; j <= n; j++)
  19.                 for (int k = 0; k <= j; k++) dp[i][j][k] = INF;
  20.         dp[0][0][0] = 0;
  21.         for (int min = S[n] * 2 / m; min > 0; min--) {
  22.             for (int i = 1; i <= m; i++)
  23.                 for (int j = 1; j <= n; j++) {
  24.                     int trans2 = 0, trans3 = 0;
  25.                     for (int k = 1; k <= j; k++) {
  26.                         dp[i][j][k] = dp[i][j][k - 1];
  27.                         while (trans2 < k && S[j] - S[trans2 + 1] >= min &&
  28.                                 max(dp[i - 1][trans2 + 1][trans2 + 1], S[j] - S[trans2 + 1]) <= max(dp[i - 1][trans2][trans2], S[j] - S[trans2])) trans2++;
  29.                         if (S[j] - S[trans2] >= min)
  30.                             dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][trans2][trans2], S[j] - S[trans2]));
  31.                         while (trans3 < k && S[j] - S[trans3 + 1] >= min &&
  32.                                 max(dp[i - 1][k][trans3 + 1], S[j] - S[trans3 + 1]) <= max(dp[i - 1][k][trans3 + 1], S[j] - S[trans3])) trans3++;
  33.                         if (S[j] - S[trans3] >= min)
  34.                             dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][k][trans3], S[j] - S[trans3]));
  35.                     }
  36.                 }
  37.             ans = min(ans, dp[m][n][n] - min);
  38.         }
  39.         System.out.println(ans);
  40.     }
  41.  
  42.     int max(int arg1, int arg2) { return arg1 > arg2 ? arg1 : arg2; }
  43.  
  44.     int min(int arg1, int arg2) { return arg1 < arg2 ? arg1 : arg2; }
  45.  
  46.     class InputReader {
  47.  
  48.         BufferedReader reader;
  49.         StringTokenizer token;
  50.  
  51.         InputReader(InputStream in) {
  52.             this.reader = new BufferedReader(new InputStreamReader(in));
  53.         }
  54.  
  55.         String read() {
  56.             while (token == null || !token.hasMoreTokens()) {
  57.                 try {
  58.                     token = new StringTokenizer(reader.readLine());
  59.                 } catch (IOException e) {
  60.                     e.printStackTrace();
  61.                 }
  62.             }
  63.             return token.nextToken();
  64.         }
  65.  
  66.         int readInt() { return Integer.parseInt(read()); }
  67.     }
  68. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/342377?site
推荐阅读
相关标签

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

  

闽ICP备14008679号