校招全国统一模拟笔试技术类编程题参考题解(六月)

https://www.nowcoder.com/test/11086583/summary
https://www.nowcoder.com/discuss/84527?type=0&order=4&pos=49&page=1

[编程题] 牛牛数星星
数组比较小，而查询次数比较多，直接暴力先求出所有i，j到0,0位置的星星数目

package l11;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[][]pos=new int[1001][1001];
        for(int i=0;i<n;i++) pos[sc.nextInt()][sc.nextInt()]=1;
        
        int[][]dp=new int[1001][1001];
        dp[0][0] = (pos[0][0]==1?1:0);
        for(int i=1;i<1001;i++) 
            dp[i][0]=dp[i-1][0]+(pos[i][0]==1?1:0);
        for(int i=1;i<1001;i++) 
            dp[0][i]=dp[0][i-1]+(pos[0][i]==1?1:0);
        for(int i=1;i<1001;i++)
            for(int j=1;j<1001;j++) {
                dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
                if(pos[i][j]==1) dp[i][j]++;
            }
            
        
        int m=sc.nextInt();
        for(int i=0;i<m;i++) {
            int x1=sc.nextInt(),y1=sc.nextInt(),x2=sc.nextInt(),y2=sc.nextInt();
            System.out.println(dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]);
        }
    }
}

[编程题] 牛牛与世界杯门票
DP

package l12;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt()+1,m=sc.nextInt(),k=sc.nextInt();
        int[][]dp=new int[1+n][m];
        
        for(int j=0;j<m;j++) {
            int x=sc.nextInt(),y=sc.nextInt();
            for(int i=0;i<=n;i++) {
                dp[i][j] = j==0?k*i:Math.min(k*i, dp[i][j-1]);
                if(y>=i) dp[i][j]=Math.min(dp[i][j], x);
                if(i>=y)
                    dp[i][j] = Math.min(dp[i][j], dp[i-y][j]+x);
            }
        }
        
        System.out.println(dp[n][m-1]);
    }
}

[编程题] 牛牛游玩记
BFS+DP

package l13;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        char[][]cs=new char[n][n];
        for(int i=0;i<n;i++)cs[i]=sc.next().toCharArray();
        int[][]dp=new int[n][n];
        for(int[]t:dp) Arrays.fill(t, Integer.MAX_VALUE);
        int[][]dirs={{1,0},{-1,0},{0,1},{0,-1}};
        
        Queue<int[]>q=new LinkedList<int[]>(), qq=new LinkedList<int[]>();
//      boolean[][]vis=new boolean[n][n];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) {
                if(cs[i][j]=='@') {
                    q.add(new int[]{i,j});
//                  vis[i][j] = true;
                    dp[i][j] = 0;
                }
            }
        
        while(!q.isEmpty()) {
            while(!q.isEmpty()) {
                int[]t=q.remove();
                for(int[] d:dirs) {
                    int xx=t[0]+d[0],yy=t[1]+d[1];
                    if(xx<0||yy<0||xx>=n||yy>=n||cs[xx][yy]=='#') continue;
                    if(dp[t[0]][t[1]]+1>=dp[xx][yy]) continue;
                    dp[xx][yy]=dp[t[0]][t[1]]+1;
                    qq.add(new int[]{xx,yy});
                }
            }
            
            Queue<int[]>tmp=new LinkedList<int[]>();
            tmp = q;
            q=qq;
            qq=tmp;
        }
        
        int res=Integer.MAX_VALUE;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) {
                if(cs[i][j]=='*') res=Math.min(res, dp[i][j]);
            }
        System.out.println(res);
        
    }
}

[编程题] 牛牛与妞妞
循环枚举

package l14;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a1=sc.nextInt(),a2=sc.nextInt(),a3=sc.nextInt();
        int b1=sc.nextInt(),b2=sc.nextInt(),b3=sc.nextInt();
        int[]cnt=new int[14];
        Arrays.fill(cnt, 4);
        cnt[a1]--;
        cnt[a2]--;
        cnt[a3]--;
        cnt[b1]--;
        cnt[b2]--;
        cnt[b3]--;
        int b=(b1+b2+b3),a=(a1+a2+a3);
        
        double res=0;
        for(int i=1;i<=13;i++) {
            double t1=cnt[i]/46.0;
            cnt[i]--;
            for(int j=1;j<=13;j++) {
                double t2=cnt[j]/45.0;
                if(a+i>b+j) res+=t1*t2;
            }
            cnt[i]++;
        }
        System.out.printf("%.4f", res);
        
    }
}

[编程题] 牛牛偶像养成记
安装end来排序

package l15;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[][]a=new int[n][3];
        for(int i=0;i<n;i++) {
            int s=sc.nextInt(),d=sc.nextInt();
            a[i]=new int[]{s,d,s+d};
        }
        
        Arrays.sort(a, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2]-o2[2];
            }
        });
        
        int res=0,cur=0;
        for(int[]t:a) {
            if(t[0]<cur) continue;
            cur=t[2];
            res++;
        }
        System.out.println(res);
    }
}