devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十四届蓝桥杯javaA组2023年省赛初赛题解_2023蓝桥杯javaa 平均

作者：小小林熬夜学编程 | 2024-04-16 19:25:51

赞

踩

2023蓝桥杯javaa 平均

题目pdf下载：第十四届蓝桥杯省赛pdf下载

目录

试题 A: 特殊日期

试题 B: 与或异或

试题 C: 平均

试题 D: 棋盘

试题 E: 互质数的个数

试题 F: 阶乘的和

试题 G: 小蓝的旅行计划

试题 H: 太阳

试题 I: 高塔

试题 J: 反异或 01 串

试题 A: 特殊日期

题意：找出指定时间内，年数是月数和天数的倍数，也就是年%月==0 && 年%日==0

思路：模拟，我的答案是：35813063

就是用for来枚举天数，蓝桥杯挺经常出这个的

代码：

  1. import java.util.*;
  2. public class Main {
  3.     static int pre[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  4.     public static void main(String[] args) {
  5.         int sum=0;
  6.         //i是年，j是月，k是日
  7.         for(int i=2000;i<=2000000;i++){
  8.             for(int j=1;j<=12;j++){
  9.                 int r=pre[j];
  10.                 if(j==2 && (i%400==0 || (i%100!=0 && i%4==0))) r++;
  11.                 //2月的闰年是29天
  12.                 for(int k=1;k<=r;k++){
  13.                     if(i%j==0 && i%k==0) sum++;
  14.                     if(i==2000000) {        //2000000年1月1号过后，直接跳出
  15.                         i=2000001;
  16.                         j=13;
  17.                         break;
  18.                     }
  19.                 }
  20.             }
  21.         }
  22.         System.out.println(sum);
  23.     }
  24. }

试题 B: 与或异或

题意：5个数从上往下，相邻的两个两两计算，运算符是&,或|,或^。已知这5个数，求多少种运算符情况可以最后答案是1

思路：dfs搜索，我的答案是：30528

dfs枚举所有运算符的排列情况，就是pow(3,10)=59049种，然后把这5个数从上往下计算，要是最后结果为1答案数+1。

代码（c++写的）：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int sum=0;
  4. int a[100005];
  5. int dp[10][10];
  6. int mp[10][10];
  7. void dfs(int d){
  8.     if(d==11){
  9.         for(int i=1;i<=4;i++) mp[1][i]=a[i];
  10.         for(int i=1;i<=3;i++) mp[2][i]=a[i+4];
  11.         for(int i=1;i<=2;i++) mp[3][i]=a[i+7];
  12.         for(int i=1;i<=1;i++) mp[4][i]=a[10];
  13.         for(int i=1;i<=4;i++){
  14.             for(int j=1;j<=4-i+1;j++){
  15.                 if(mp[i][j]==0) dp[i][j]=dp[i-1][j]|dp[i-1][j+1];
  16.                 if(mp[i][j]==1) dp[i][j]=dp[i-1][j]^dp[i-1][j+1];
  17.                 if(mp[i][j]==2) dp[i][j]=dp[i-1][j]&dp[i-1][j+1];
  18.             }
  19.         }
  20.         if(dp[4][1]==1)
  21.             sum++;
  22.         return;
  23.     }
  24.     a[d]=0;
  25.     dfs(d+1);
  26.     a[d]=1;
  27.     dfs(d+1);
  28.     a[d]=2;
  29.     dfs(d+1);
  30. }
  31. int main()
  32. {
  33.     dp[0][1]=1;
  34.     dp[0][2]=0;
  35.     dp[0][3]=1;
  36.     dp[0][4]=0;
  37.     dp[0][5]=1;
  38.     dfs(1);
  39.     cout<<sum<<endl;
  40.     return 0;
  41. }

试题 C: 平均

题意：给若干个数（范围是0-9），和他们的更改的花费，求最小花费，使得0-9最终数量相同

思路：贪心

只将数量>n/10的数改为其他数，也就是数量>n/10要改掉 （数量-n/10）个。当然是找其中最小的改

通过：思路的时间复杂度可以100%，具体通过看情况

代码：

  1. import java.util.*;
  2. public class Main{
  3. 	public static void main(String[] args){
  4. 		Scanner cin =new Scanner(System.in);
  5. 		int n=cin.nextInt();
  6. 		int A[][]=new int[11][100005];
  7. 		int len[]=new int[15];
  8. 		for(int i=1;i<=n;i++) {
  9. 			int x=cin.nextInt();
  10. 			int y=cin.nextInt();
  11. 			A[x][++len[x]]=y;
  12. 		}
  13. 		for(int i=0;i<10;i++) 
  14. 			Arrays.sort(A[i],1,len[i]+1);    //排序，不用list是因为没有板子，手敲不出来
  15. 		long sum=0;
  16. 		for(int i=0;i<10;i++) {
  17. 			for(int j=1;j<=len[i]-n/10;j++) {
  18. 				sum+=A[i][j];
  19. 			}
  20. 			
  21. 		}
  22. 		System.out.println(sum);
  23. 	}
  24. }

试题 D: 棋盘

 

题意：一个n*m的棋盘，开始全是白子，选择一个矩形全部反转，最后的棋盘情况打印一下

思路：差分前缀和

就是将这个矩形全部数+1（刚开始全是0），最后%2就是答案

因为最大数据也只是2000，每次在将要改变的行中，差分修改。总执行次数也不过是2000*2000。

最后逐行前缀和，打印这些数%2，注意打印时没有空格

通过：思路的时间复杂度可以100%，具体通过看情况

代码：

  1. import java.util.*;
  2. public class Main{
  3. 	public static void main(String[] args){
  4. 		Scanner cin =new Scanner(System.in);
  5. 		int n=cin.nextInt();
  6. 		int m=cin.nextInt();
  7. 		int A[][]=new int[2005][2005];
  8. 		for(int i=1;i<=m;i++) {
  9. 			int x1=cin.nextInt();
  10. 			int y1=cin.nextInt();
  11. 			int x2=cin.nextInt();
  12. 			int y2=cin.nextInt();
  13. 			for(int j=x1;j<=x2;j++) {
  14. 				A[j][y1]++;        //差分
  15. 				A[j][y2+1]--;
  16. 			}
  17. 		}
  18. 		for(int i=1;i<=n;i++) {
  19. 			for(int j=1;j<=n;j++) {
  20. 				A[i][j]+=A[i][j-1];        //前缀和
  21. 				System.out.print(A[i][j]%2);
  22. 			}
  23. 			System.out.println();
  24. 		}
  25. 	}
  26. }

试题 E: 互质数的个数

题意：1-pow(a,b)中有多少个数，和pow(a,b)互质

思路：思维+gcd+快速幂

答案就是pow(a,b-1)*r，r是1-a中和a互质的数量

和a*a*a*a....互质，就是和a互质的数。

a,b互质就是gcd(a,b)==1。而(a,b)和(a，b+a)，和(a,b+a*2)...的互质情况是一样的，求gcd()那个公式应该能看出来

也就是有循环，只看1-a就行。而r就是欧拉函数

通过：

欧拉函数求可以100%

100%代码：

  1. import java.util.*;
  2. public class Main{
  3.     static long mod=998244353;
  4.     static long Euler(long n){        //求欧拉函数值
  5.         long res=n;
  6.         for(long i=2;i*i<=n;++i){
  7.             if(n%i==0){
  8.                 res=res/i*(i-1);
  9.                 while(n%i==0)
  10.                     n/=i;
  11.             }
  12.         }
  13.         if(n>1)
  14.             res-=res/n;
  15.         return res;
  16.     }
  17.     static long qpow(long a,long b){
  18.         long ans=1;
  19.         while(b!=0){
  20.             if(b%2==1)
  21.                 ans=ans*a%mod;
  22.             a=a*a%mod;
  23.             b/=2;
  24.         }
  25.         return ans;
  26.     }
  27.     public static void main(String[] args){
  28.         Scanner cin =new Scanner(System.in);
  29.         long a=cin.nextLong();
  30.         long b=cin.nextLong();
  31.         long r=Euler(a);        //1-a中有多少个数和a互质
  32.         System.out.println(qpow(a,b-1)*(r%mod)%mod);
  33.     }
  34. }

试题 F: 阶乘的和

题意：

思路：这题没有比较好的思路。

只有用乘法求余公式，暴力计算最大的m。

ans=1,2,6,24,120...。计算这些阶乘的和是否是能被ans其整除，也就是判断：

A[1]!%ans+A[2]!%ans+....+A[n]!%ans==0

要是不行的话，就输出当前ans对应的阶乘数。

通过：

可以看到方法不一定能过前40%，但是大多情况下，也有可能过些

代码：

  1. import java.util.*;
  2. public class Main{
  3. 	public static void main(String[] args){
  4. 		Scanner cin =new Scanner(System.in);
  5. 		int n=cin.nextInt();
  6. 		int a[]=new int[n+10];
  7. 		for(int i=1;i<=n;i++) {
  8. 			a[i]=cin.nextInt();
  9. 		}
  10. 		long ans=1,p=1;
  11. 		while(true) {
  12. 			long sum=0;
  13. 			for(int i=1;i<=n;i++) {
  14. 				long res=1;
  15. 				for(int j=2;j<=a[i];j++) {
  16. 					res=res*j%ans;
  17. 				}
  18. 				sum=(sum+res)%ans;        //算和
  19. 			}
  20. 			if(sum==0) {
  21. 				ans*=(++p);
  22. 			}else {
  23. 				break;
  24. 			}
  25. 		}
  26. 		System.out.println(p-1);
  27. 	}
  28. }

试题 G: 小蓝的旅行计划

思路：思维+优先队列

把前面的所有能买的单价和其数量记录下来，然后一旦没有油就从中去除最小的价格。

100%的思路应该是优先队列，存储长度为2的list，每次弹出最小价格，并修改其数量。一旦为0就不再压入。

根据评论，因为油箱有m的上限，所以这个思路不完全正确，具体我也想不到完全正确的思路了

通过：

优先队列，存储长度为2的list可以100%。

代码（优先队列按数量存60%）：

  1. import java.util.*;
  2. public class Main{
  3.     public static void main(String[] args){
  4.         Scanner cin =new Scanner(System.in);
  5.         PriorityQueue q=new PriorityQueue();
  6.         int n=cin.nextInt();
  7.         int m=cin.nextInt();
  8.         long sum=0;
  9.         for(int i=1;i<=n;i++) {
  10.             int x=cin.nextInt();
  11.             int y=cin.nextInt();
  12.             int z=cin.nextInt();
  13.             m-=x;
  14.             while(m<0) {
  15.                 if(q.isEmpty()) {
  16.                     sum=-1;
  17.                     i=n+1;
  18.                     break;
  19.                 }
  20.                 int r=(int)q.poll();
  21.                 sum+=r;
  22.                 m++;
  23.             }
  24.             for(int j=1;j<=z;j++) {
  25.                 q.add(y);
  26.             }
  27.         }
  28.         System.out.println(sum);
  29.     }
  30. }

代码（优先队列按序列存100%）：

  1. import java.lang.reflect.Array;
  2. import java.util.*;
  3. public class Main{
  4.     static ArrayList fun(int x,int y){
  5.         ArrayList<Integer> t=new ArrayList();
  6.         t.add(x);
  7.         t.add(y);
  8.         return t;
  9.     }
  10.     public static void main(String[] args){
  11.         Scanner cin =new Scanner(System.in);
  12.         PriorityQueue<ArrayList<Integer>> q=new PriorityQueue<>(new Comparator<ArrayList<Integer>>(){
  13.             @Override
  14.             public int compare(ArrayList<Integer> a, ArrayList<Integer> b){
  15.                 return a.get(0)-b.get(0);
  16.             }
  17.         });
  18.         int n=cin.nextInt();
  19.         int m=cin.nextInt();
  20.         long sum=0;
  21.         for(int i=1;i<=n;i++) {
  22.             int x=cin.nextInt();
  23.             int y=cin.nextInt();
  24.             int z=cin.nextInt();
  25.             m-=x;
  26.             while(m<0) {
  27.                 if(q.isEmpty()) {
  28.                     sum=-1;
  29.                     i=n+1;
  30.                     break;
  31.                 }
  32.                 List<Integer> r=q.poll();       //前面价格最小的
  33.                 int res=Math.min(r.get(1),-m);      //这次使用r的数量
  34.                 sum+=(long)res*r.get(0);
  35.                 m+=res;
  36.                 if(res!=r.get(1))       //要是还有剩余，将剩余数量再加入q中
  37.                     q.add(fun(r.get(0),r.get(1)-res));
  38.             }
  39.             q.add(fun(y,z));
  40.         }
  41.         System.out.println(sum);
  42.     }
  43. }

试题 H: 太阳

 

题意：给若干个线段，和一个光源。判断有多少个线段可以被光源找到

思路：计算几何

100%的思路没有，只有30%的，也就是双for判断有没有被其他挡到

显示判断可能被挡的，高度至少是被挡<档<光源 or 被挡>档>光源 才有可能会挡到

接下来是被挡线段的两个端点，连接光源后不能与挡的线段相交

方法是叉积求两个线段不相交，要在两点同一侧才不相交

通过：

该思路时间复杂度可以30%，再优的应该是极角排序了

核心代码：

  1.     static double add(Node a,Node x,Node y) {        //叉积
  2.         return (a.x-x.x)*(a.y-y.y)-(a.y-x.y)*(a.x-y.x);
  3.     }
  4.     static boolean solve(int i,int j) {
  5.         //只有高度合适的时候，i才有可能被j挡到
  6.         if((b[i]<=b[j] && b[j]<=y) || (y<=b[j] && b[j]<=b[i])) {
  7.             double h1 = add(new Node(a[j], b[j]), new Node(a[i], b[i]), new Node(x, y));
  8.             double h2 = add(new Node(a[j] + l[j], b[j]), new Node(a[i], b[i]), new Node(x, y));
  9.             if ((h1 * h2) < 0) return true;
  10.             h1 = add(new Node(a[j], b[j]), new Node(a[i] + l[i], b[i]), new Node(x, y));
  11.             h2 = add(new Node(a[j] + l[j], b[j]), new Node(a[i] + l[i], b[i]), new Node(x, y));
  12.             if ((h1 * h2) < 0) return true;
  13.         }
  14.         return false;
  15.     }

代码：

  1. import java.util.*;
  2. public class Main{
  3.     static int n,x,y;
  4.     static int a[]=new int[1000000],b[]=new int[1000000],l[]=new int[1000000];
  5.     static double add(Node a,Node x,Node y) {        //叉积
  6.         return (a.x-x.x)*(a.y-y.y)-(a.y-x.y)*(a.x-y.x);
  7.     }
  8.     static boolean solve(int i,int j) {
  9.         if((b[i]<=b[j] && b[j]<=y) || (y<=b[j] && b[j]<=b[i])) {
  10.             double h1 = add(new Node(a[j], b[j]), new Node(a[i], b[i]), new Node(x, y));
  11.             double h2 = add(new Node(a[j] + l[j], b[j]), new Node(a[i], b[i]), new Node(x, y));
  12.             if ((h1 * h2) < 0) return true;
  13.             h1 = add(new Node(a[j], b[j]), new Node(a[i] + l[i], b[i]), new Node(x, y));
  14.             h2 = add(new Node(a[j] + l[j], b[j]), new Node(a[i] + l[i], b[i]), new Node(x, y));
  15.             if ((h1 * h2) < 0) return true;
  16.         }
  17.         return false;
  18.     }
  19.     public static void main(String[] args){
  20.         Scanner cin =new Scanner(System.in);
  21.         n=cin.nextInt();
  22.         x=cin.nextInt();
  23.         y=cin.nextInt();
  24.         for(int i=1;i<=n;i++) {
  25.             a[i]=cin.nextInt();
  26.             b[i]=cin.nextInt();
  27.             l[i]=cin.nextInt();
  28.         }
  29.         int sum=0;
  30.         for(int i=1;i<=n;i++) {
  31.             for(int j=1;j<=n;j++) {
  32.                 if(i!=j && solve(i,j)) {
  33.                     break;
  34.                 }
  35.                 if(j==n) sum++;
  36.             }
  37.         }
  38.         System.out.println(sum);
  39.     }
  40. }
  41. class Node{
  42.     public double x,y;
  43.     public Node(){}
  44.     public Node(double a,double b){
  45.         this.x=a;
  46.         this.y=b;
  47.     }
  48. }

试题 I: 高塔

 样例算不出来，什么都没有

通过：0%

试题 J: 反异或 01 串

题意：

思路：前缀和+回文字串判断

这种题思路感觉细究下就会错

我的思路：反异或操作后，字串只能是以0为中心的奇数长度回文串，或者是偶数长度的任意回文串。只有一次这个操作，且其他都是在两边添加0和1，那么这个回文字串一定还在给的字符串中

所以在其中找回文子串，我用的中心扩展法。用1的数量=左端点的左边1的数量+右端点的右边1的数量+回文字串中的1数量/2

也就是O（n的平方）求出所有情况的最小1的数量

通过：

时间复杂度是O（n的平方），也就是60%。

O（n）或者O（nlogn）求回文子串（不是最长）不知道有没有方法。当然是建立在这个思路正确的前提下

代码：

  1. import java.util.*;
  2. public class Main{
  3.     static String s;
  4.     static int f[]=new int[1000000];
  5.     static int n,mi=10000000;
  6.     static int get(int x,int y){        //前缀和
  7.         if(y<1 || x>n || x>y) return 0;
  8.         return f[y]-f[x-1];
  9.     }
  10.     static void solve(int l,int r){
  11.         while(l-1!=0 && r+1!=n+1 && s.charAt(l-1)==s.charAt(r+1)){
  12.             l--;
  13.             r++;
  14.         }
  15.         mi=Math.min(mi,get(l,r)/2+get(1,l-1)+get(r+1,n));
  16.     }
  17.     public static void main(String[] args){
  18.         Scanner cin =new Scanner(System.in);
  19.         s=cin.next();
  20.         n=s.length();
  21.         s=" "+s;
  22.         for(int i=1;i<=n;i++){
  23.             f[i]+=f[i-1]+(s.charAt(i)=='1'?1:0);
  24.         }
  25.         for(int i=1;i<=n;i++){
  26.             if(s.charAt(i)=='0')
  27.                 solve(i,i);
  28.             if(i!=n && s.charAt(i)==s.charAt(i+1))
  29.                 solve(i,i+1);
  30.         }
  31.         System.out.println(mi);
  32.     }
  33. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/436019
推荐阅读
相关标签

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

  

闽ICP备14008679号