蓝桥杯真题05

迷南。 2024-03-24 15:45 81阅读 0赞

## 重新排序 ##

### 问题描述 ###

给定一个数组 A 和一些查询 Li,Ri 求数组中第 Li 至第 Ri个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?

### 输入格式 ###

输入第一行包含一个整数 n 。

第二行包含 n 个整数 A1,A2,⋯ ,An相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m 表示查询的数目。

接下来 m 行, 每行包含两个整数 Li、Ri相邻两个整数之间用一个空格分隔。

#### 输出格式 ####

输出一行包含一个整数表示答案。

#### 样例输入 ####

5
    1 2 3 4 5
    2
    1 3
    2 5

#### 样例输出 ####

#### 样例说明 ####

原来的和为 6+14=206+14=20, 重新排列为 (1,4,5,2,3)(1,4,5,2,3) 后和为 10+14=2410+14=24, 增 加了 4。

#### 运行限制 ####

*  最大运行时间：1s
 *  最大运行内存: 512M

### 思路分析 ###

要想排列前后差值最大，排列前的初始数组我们无法控制，那么就只能想办法改变排列后的数组，让最大的数放在位置出现最多次的地方，进一步来说就是，最大的数要出现最多次，然后依次递减数的大小和位置出现的次数，那么如何去判断哪个位置出现了多少次呢？

不妨定义一个count数组来表示，如果l,r这段被求一次，那么这一段区间内的出现次数就都需要+1，这不正是差分所能实现的吗，因此我们不妨每次`count[l]++;count[r+1]--;`然后进行差分操作，自然就将每个位置的出现次数计算出了，再将其排序，同时与排序过的原数组对应位置一一相乘，得到的值无疑是最大的，

为什么直接相乘就可以，

因为我们的count数组存的是位置出现次数，我们要求的让他是和最大的数相乘，而较小的那些数刚好会乘以count数组中的0，因此得到的值就是要求。

### 代码实现 ###

package com.zxy.exam;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.PrintWriter;
    import java.util.Arrays;
    
    public class _重新排序 {
        
        static  int N = 100010;
        static long[] arr = new long[N];//原数组
        static long[] count = new long[N];//位置出现次数
        static long[] b = new long[N];//前缀和数组
        static int n,m;
        static long sum1,sum2;
        static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        static PrintWriter pw = new PrintWriter(System.out);
        public static void main(String[] args) throws IOException {
        
            String s = bf.readLine();
            n = Integer.parseInt(s);
            String[] s1 = bf.readLine().split(" ");
            for (int i = 1; i <= n; i++) {
        
                arr[i]=Integer.parseInt(s1[i-1]);//读入数据
                b[i]=b[i-1]+arr[i];//前缀和
            }
            s = bf.readLine();
            m = Integer.parseInt(s);
            while(m --> 0){
        
                String[] s2 = bf.readLine().split(" ");
                int l = Integer.parseInt(s2[0]);
                int r = Integer.parseInt(s2[1]);
                sum1+=b[r]-b[l-1];
                count[l]++;
                count[r+1]--;
            }
            for (int i = 1; i <= n; i++) {
        
                count[i]+=count[i-1];
            }
            Arrays.sort(arr);
            Arrays.sort(count);//count数组特别大，而且有很多0，因此一定要遍历到最后一位，或者就从最后一位倒着遍历
            /*int p=N-1;
            while (count[p]!=0){
                sum2 += count[p]*arr[p];//更新后的和
                p--;
            }*/
            for (int i = 1; i <= N-1; i++) {
        
                sum2+= count[i]*arr[i];
            }
    
            System.out.println(sum2-sum1);
        }
    }

## 找素数 ##

这道题目很简单找到第1000002个素数，但是素数是蓝桥杯的高频考点，一定要复习一下！

import java.util.Scanner;
    // 1:无需package
    // 2: 类名必须Main, 不可修改
    
    public class Main {
        
         public static void main(String[] args) {
        
            int ans = 0;
            int i = 2;
            while(true){
        
                if (isPrime(i)){
        
                    ans++;
                    if(ans == 100002){
        
                      System.out.println(i);
                      return;
                    }
                }
               i++;
            }  
        }
    
         static boolean isPrime(int n) {
        
    
            for(int i = 2; i <= (int) Math.sqrt(n); i++){
        
                if (n % i == 0){
        
                    return false;
                }
            }
            return true;
        }
    }

## 卡牌 ##

### 问题描述 ###

这天, 小明在整理他的卡牌。

他一共有 n 种卡牌, 第 i 种卡牌上印有正整数数 i(i∈\[1,n\]), 且第 i 种卡牌 现有 ai 张。

而如果有 n 张卡牌, 其中每种卡牌各一张, 那么这 nn 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 m 张空白牌, 他可以在上面写上数 i, 将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 ii 种牌最多手写 bi 张。

请问小明最多能凑出多少套牌?

### 输入格式 ###

输入共 3 行, 第一行为两个正整数 n,m。

第二行为 n 个正整数 a1,a2,…,an。

第三行为 n 个正整数 b1,b2,…,bn 。

### 输出格式 ###

一行, 一个整数表示答案。

#### 样例输入 ####

4 5  
1 2 3 4  
5 5 5 5

#### 样例输出 ####

### 样例说明 ###

这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了 3,3,3,4, 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。

评测用例规模与约定  
对于 30%的数据, 保证 n≤2000;

对于 100% 的数据, 保证 n≤2×105;ai,bi≤2\*n;m≤n2 。

### 运行限制 ###

最大运行时间：1s  
最大运行内存: 512M

### 分析 ###

很明显的二分题目，mid是可以凑出的套数，如果mid可以满足条件，也就是mid这个套数是可以实现的，那么比mid小的所有套数也一定是可以实现的，因此答案在`mid-r`中也就是l=mid。

另一个难点就是如何判断这个套数是否能实现，也即是check函数的写法，我们定义t为套数，还要定义tmp表示万能牌的数量，这里需要枚举每一种牌，如果`t<=a[i]`那么这种牌就可以实现，直接continue节省时间，如果`t>a[i]+b[i]`那么很明显，实现不了，如果`t>a[i]+tmp`那么也是实现不了的，那么剩下的就是a\[i\]配合万能牌可能实现t的情况了，`t-a[i]<=tmp`那么我们的万能拍就被消耗了这么多张，tmp就要减去差值，如果a\[i\]配合万能牌也不够t，那就实现不了。

### 代码实现 ###

package com.zxy.exam;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.PrintWriter;
    
    public class _卡牌 {
        
        static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        static PrintWriter pw = new PrintWriter(System.out);
        static int N = 100010;
        static int[] a = new int[N];
        static int[] b = new int[N];
        static int n ;
        static long m;
        public static void main(String[] args) throws IOException {
        
            String[] s = bf.readLine().split(" ");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            s = bf.readLine().split(" ");
            for (int i = 0; i < s.length; i++) {
        
                a[i]=Integer.parseInt(s[i]);
            }
            s = bf.readLine().split(" ");
            for (int i = 0; i < s.length; i++) {
        
                b[i]=Integer.parseInt(s[i]);
            }
            int l = 0;
            int r = n*2;
            while (l < r){
        
                int mid = l + r + 1 >> 1;
                if (check(mid)){
        
                    l = mid;
                }else r = mid - 1;
            }
            pw.println(l);
            pw.flush();
        }
    
        private static boolean check(int t) {
        
            long tmp = m;
            for (int i = 0; i < n; i++) {
        
                if (a[i]>=t) continue;
                if (b[i]+a[i]<t) return false;
                if (tmp + a[i] < t) return false;
                if (t - a[i] <= tmp){
        
                    tmp -= (t-a[i]);
                }else {
        
                    return false;
                }
            }
            return true;
        }
    }

## 染色时间 ##

#### 问题描述 ####

小蓝有一个 *n* 行 m\* 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。

每个方格有一个染色时间 t**i**j\*, 不同方格的染色时间可能不同。如果一个方 格被触发了染色, 这个方格就会在 *t**i**j* 秒之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。

给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。

#### 输入格式 ####

输入的第一行包含两个整数 *n*,*m*, 分别表示棋盘的行数和列数。

接下来 n\* 行, 每行 *m* 个正整数, 相邻的整数之间用一个空格分隔, 表示每 个方格的染色时间。该部分的第 i\* 行第 j\* 个整数表示 *t**i**j*, 即第 i\* 行第 j\* 列的方 格的染色时间。

#### 输出格式 ####

输出一行包含一个整数, 表示整个棋盘完成染色的时间。

#### 样例输入 ####

2 3
    
    1 2 3
    
    4 5 6

#### 样例输出 ####

#### 运行限制 ####

*  最大运行时间：1s
 *  最大运行内存: 256M

### 分析 ###

这道题目很明显的dfs模板题，需要注意的是这个染色时间，他是四个方向同时进行的，因此我们要找的是最大的时间，所以count要不断进行比较，从而找到消耗时间最多的那个格子。

需要注意的是，自己手写的这个储存坐标的类，一定要重写Comparable方法，否则无法顺利存如队列中！

### 代码实现 ###

package com.zxy.exam;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class _染色时间 {
        
        static int N = 510;
        static int[][] a = new int[N][N];
        static int[] dx = {
        -1,0,1,0};
        static int[] dy = {
        0,1,0,-1};
        static int count = 0;
        static int n,m;
        public static void main(String[] args) {
        
            Scanner scan = new Scanner(System.in);
            n = scan.nextInt();
            m = scan.nextInt();
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < m; j++) {
        
                    a[i][j]=scan.nextInt();
                }
            }
            dfs();
        }
    
        private static void dfs() {
        
            Queue<Color> q = new LinkedList<>();
            q.add(new Color(0,0,a[0][0]));
            a[0][0]=0;
            while (!q.isEmpty()){
        
                Color tmp = q.poll();
                if (tmp.getTime() > count ){
        
                    count = tmp.getTime();
                }
                for (int i = 0; i < 4; i++) {
        
                    int x = dx[i]+tmp.x;
                    int y = dy[i] + tmp.y;
                    if (x >= 0 && x < m && y >= 0 && y < m && a[x][y]>0){
        
                        q.add(new Color(x,y,tmp.time+a[x][y]));
                        a[x][y]=0;
                    }
                }
            }
            System.out.println(count);
        }
    
    }
    class Color implements Comparable<Color>{
        
        int x;
        int y;
        int time;
    
        @Override
        public int compareTo(Color o) {
        
            return this.time - o.time;
        }
    
        public Color(int x, int y, int time) {
        
            this.x = x;
            this.y = y;
            this.time = time;
        }
    
        public int getX() {
        
            return x;
        }
    
        public void setX(int x) {
        
            this.x = x;
        }
    
        public int getY() {
        
            return y;
        }
    
        public void setY(int y) {
        
            this.y = y;
        }
    
        public int getTime() {
        
            return time;
        }
    
        public void setTime(int time) {
        
            this.time = time;
        }
    }