JAVA B组参考代码

试题 A: 重合次数

答案:494

试题 B: 数数

答案:25606

试题 C: 左移右移

思路：

对于操作从后向前记录，最后操作的肯定是在两端，并对该操作的数进行记录，方便最后保留原来未操作过数的顺序

参考代码:

import java.util.*;
public class Main {static int a[]=new int[200005];static int vis[]=new int[200005];static String op[]=new String[200005];static int num[]=new int [200005];static int ans[]=new int[200005];public static void main(String[] args)  {Scanner in = new Scanner(System.in);int n,q;n=in.nextInt();q=in.nextInt();for(int i=1;i<=n;i++){a[i]=i;}for(int i=1;i<=q;i++) {op[i] = in.next();num[i] = in.nextInt();}int left=1;int right=n;for(int j=q;j>=1;j--){if(op[j].charAt(0)=='L'){ans[left]=num[j];left++;vis[num[j]]=1;}if(op[j].charAt(0)=='R'){ans[right]=num[j];right--;vis[num[j]]=1;}}for(int i=1;i<=n;i++){if(vis[i]==0){ans[left]=a[i];left++;}}for(int i=1;i<=n;i++){if(i==1){System.out.print(ans[i]);}else{System.out.print(" "+ans[i]);}}return ;}
}

试题 D: 窗口

思路:

按照题目描述进行模拟，本人模拟很烂，就不写这题代码了

试题 E: 迷宫

思路:

Map(i,j)表示的含义是从i，j到终点n，n的步数， 根据直接跳跃距离终点(n,n)最近的进行排序，然后判断直接传送后的是否比不用传送小进行更新，然后根据期望的含义进行计算

参考代码:

import java.util.*;
public class Main {static int Map[][]=new int [2005][2005];static class node implements Comparable<node>{int x1,y1,x2,y2;int val;@Overridepublic int compareTo(node o) {return this.val-o.val;}}static node p[]=new node[2005];public static void main(String[] args)  {Scanner in = new Scanner(System.in);int n,m;n = in.nextInt();m = in.nextInt();for(int i = 1; i <= m ; i++ ){p[i] = new node();p[i].x1 = in.nextInt();p[i].y1 = in.nextInt();p[i].x2 = in.nextInt();p[i].y2 = in.nextInt();p[i].val=2*n-p[i].x2-p[i].y1;}Arrays.sort(p,1,m+1);for(int i = 1; i <= n ;i++){for( int j =1 ;j <= n;j++){Map[i][j]=Math.abs(n-i)+Math.abs(n-j);}}for(int i = 1;i <= m;i++){Map[p[i].x1][p[i].y1]=Math.min(Map[p[i].x1][p[i].y1],Map[p[i].x2][p[i].y2]+1);}double ans=0;for(int i = 1; i <= n;i++){for(int j=1 ; j <= n;j++){ans+=(double)(Map[i][j]);}}System.out.printf("%.2f\n",ans*1.0/(n*n));return ;}
}

试题 F: 小球称重

思路:

本题主要考虑次品比较轻，所以在小于的那部分，其次然后后续根据大于和等于的情况，排除掉不可能的，因为TreeSet可以做到有序，查找和删除可以在log范围内进行，还要考虑一种特别特殊的情况，就是所有都是等于，说明次品在剩下的里面，所以就是n减去出现过的

参考代码:

import java.util.*;
public class Main {public static void main(String[] args)  {Scanner in = new Scanner(System.in);int n,m;n = in.nextInt();m = in.nextInt();TreeSet<Integer>s=new TreeSet<>();TreeSet<Integer>s1=new TreeSet<>();int f=0;while(m-->0){int k = in.nextInt();int l[]=new int[k];int r[]=new int[k];for(int i=0;i<k;i++){l[i]=in.nextInt();s1.add(l[i]);}for(int i=0;i<k;i++){r[i]=in.nextInt();s1.add(r[i]);}String re=in.next();if(re.equals("<")){for(int i=0;i<k;i++){s.add(l[i]);}for(int i=0;i<k;i++){s.remove(r[i]);}f=1;}else if(re.equals(">")){for(int i=0;i<k;i++){s.remove(l[i]);}for(int i=0;i<k;i++){s.add(r[i]);}f=1;}else if(re.equals("=")){for(int i=0;i<k;i++){s.remove(l[i]);}for(int i=0;i<k;i++){s.remove(r[i]);}}}if(f==0){System.out.println(n-s1.size());return ;}System.out.println(s.size());return ;}
}

试题 G: 背包与魔法

思路:

可以参考01背包的思路，加一维判断是否使用了这个魔法

参考代码:

import java.util.*;
public class Main {static int W[]=new int[2010];static int V[]=new int[2010];static int dp[][]=new int [10010][2];public static void main(String[] args)  {Scanner in=new Scanner(System.in);int N ,M,K;N=in.nextInt();M=in.nextInt();K=in.nextInt();for(int i=1;i<=N;i++){W[i]=in.nextInt();V[i]=in.nextInt();}for(int i=1;i<=N;i++){for( int j=M;j>=W[i];j--){dp[j][0]=Math.max(dp[j-W[i]][0]+V[i],dp[j][0]);if(j-K-W[i]>=0){dp[j][1]=Math.max(dp[j-W[i]-K][0]+2*V[i],dp[j][1]);dp[j][1]=Math.max(dp[j-W[i]][1]+V[i],dp[j][1]);}}}int ans=Math.max(dp[M][0],dp[M][1]);System.out.println(ans);return ;}
}

试题H：修路

思路:

将各个顶点分为3类，第一类左上角的点，标记为0，a的为1到n,b的为m+(1到n)，然后将其建边，主要是一侧的相邻之间进行建边，相对的可以任意两两之间建边，然后跑最小生成树，得到结果

参考代码:

import java.util.*;
public class Main {static Scanner cin=new Scanner(System.in);static class node implements Comparable<node>{double val;int x;int y;@Overridepublic int compareTo(node o) {if(this.val>o.val){return 1;}else{return -1;}}}static node p[]=new node[5000005];static int a[]=new int[2005];static int b[]=new int[2005];static int fa[]=new int[5000005];static int find(int x){if(x==fa[x])return x;else{return fa[x]=find(fa[x]);}}static void Merge(int x,int y){int xx=find(x);int yy=find(y);if(xx!=yy){fa[xx]=yy;}}public static void main(String[] args) {Scanner cin = new Scanner(System.in);int n,m,d;n=cin.nextInt();m=cin.nextInt();d=cin.nextInt();for(int i=1;i<=n;i++){a[i]=cin.nextInt();}for(int i=1;i<=m;i++){b[i]=cin.nextInt();}for(int i=0;i<=n*m+n+m;i++){fa[i]=i;}Arrays.sort(a,1,n+1);Arrays.sort(b,1,m+1);int cc=0;p[cc]=new node();p[cc].val=(double)(a[1]);p[cc].x=0;p[cc].y=1;cc++;p[cc]=new node();p[cc].val=(double)(Math.sqrt((double)(b[1]*b[1]+d*d)));p[cc].x=0;p[cc].y=n+1;cc++;for(int i=2;i<=n;i++){p[cc]=new node();p[cc].val=(double)(a[i]-a[i-1]);p[cc].x=i-1;p[cc].y=i;cc++;}for(int i=2;i<=m;i++){p[cc]=new node();p[cc].val=(double)(b[i]-b[i-1]);p[cc].x=i-1+n;p[cc].y=i+n;cc++;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){p[cc]=new node();p[cc].val=(double)(Math.abs(a[i]-b[j])*Math.abs(a[i]-b[j])+d*d);p[cc].x=i;p[cc].y=j+n;cc++;}}Arrays.sort(p,0,cc);double ans=0;int cnt=0;for(int i=0;i<cc;i++){if(find(p[i].x)!=find(p[i].y)){Merge(p[i].x,p[i].y);ans+=p[i].val;cnt++;}if(cnt==n+m){break;}}System.out.printf("%.2f\n",ans);return ;}}

试题I：围栏

计算几何不咋会(弱项)

试题J: 好数之和

思路:

把其他数位进行枚举，然后将其2022插入进去进行判断即可，kkkk枚举的是插入位置，其他是代表其他几位上的数

参考代码:

import java.util.*;
public class Main {static Scanner cin=new Scanner(System.in);public static void main(String[] args) {int L, R;L = cin.nextInt();R = cin.nextInt();long res = 0;for (int kkkk = 0; kkkk < 6; kkkk++) {for (int i = 0; i <= 9; i++) {for (int j = 0; j <= 9; j++) {for (int k = 0; k <= 9; k++) {for (int kk = 0; kk <= 9; kk++) {for (int kkk = 0; kkk <= 9; kkk++) {if (kkkk == 0) {int ans = 0;ans = ans * 10 + i;ans = ans * 10 + j;ans = ans * 10 + k;ans = ans * 10 + kk;ans = ans * 10 + kkk;int a[] = {2, 0, 2, 2};for (int jj = 0; jj < 4; jj++) {ans = ans * 10 + a[jj];}if (ans >= L && ans <= R) {res += ans;}}if (kkkk == 1) {int ans = 0;ans = ans * 10 + i;ans = ans * 10 + j;ans = ans * 10 + k;ans = ans * 10 + kk;int a[] = {2, 0, 2, 2};for (int jj = 0; jj < 4; jj++) {ans = ans * 10 + a[jj];}ans = ans * 10 + kkk;if (ans >= L && ans <= R) {res += ans;}}if (kkkk == 2) {int ans = 0;ans = ans * 10 + i;ans = ans * 10 + j;ans = ans * 10 + k;int a[] = {2, 0, 2, 2};for (int jj = 0; jj < 4; jj++) {ans = ans * 10 + a[jj];}ans = ans * 10 + kk;ans = ans * 10 + kkk;if (ans >= L && ans <= R) {res += ans;}}if (kkkk == 3) {int ans = 0;ans = ans * 10 + i;int a[] = {2, 0, 2, 2};for (int jj = 0; jj < 4; jj++) {ans = ans * 10 + a[jj];}ans = ans * 10 + k;ans = ans * 10 + kk;ans = ans * 10 + kkk;if (ans >= L && ans <= R) {res += ans;}}if (kkkk == 4) {int ans = 0;ans = ans * 10 + i;int a[] = {2, 0, 2, 2};for (int jj = 0; jj < 4; jj++) {ans = ans * 10 + a[jj];}ans = ans * 10 + j;ans = ans * 10 + k;ans = ans * 10 + kk;ans = ans * 10 + kkk;if (ans >= L && ans <= R) {res += ans;}}if (kkkk == 5) {int ans = 0;int a[] = {2, 0, 2, 2};for (int jj = 0; jj < 4; jj++) {ans = ans * 10 + a[jj];}ans = ans * 10 + i;ans = ans * 10 + j;ans = ans * 10 + k;ans = ans * 10 + kk;ans = ans * 10 + kkk;if (ans >= L && ans <= R) {res += ans;}}}}}}}}System.out.println(res);return;}}