蓝桥杯 2022 省赛 C++ B组

阳光穿透心脏的1/2处 2024-03-24 08:29 66阅读 0赞

## 填空问题 ##

### [九进制转十进制][Link 1] ###

> 九进制正整数 (2022)9 转换成十进制等于多少？

import java.util.Scanner;
    // 1:无需package
    // 2: 类名必须Main, 不可修改
    
    public class Main {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            String st = "2022";
            System.out.println(Integer.parseInt(st,9));
            scan.close();
        }
    }

### [顺子日期][Link 2] ###

![527335391d3abda353766741b1028738.png][]

public class 顺子日期 {
        //顺子数组
        static String[] str={"012","123","234","345","456","567","678","789"};
    
        public static void main(String[] args) {
            int n=20220101;
            int cnt=0;
            while (n<20221231){
                if(judge(n)){
                    if(isShun(n+"")) cnt++;
                }
                n++;
            }
            System.out.println(cnt);
        }
    
        //判断是否是合理日期
        static boolean judge(int x){
            int[] w={0,31,28,31,30,31,30,31,31,30,31,30,31}; //2022年每个月的天数
            int m = x%10000/100;//月份
            int d = x%100;//天数
            if(d<=w[m]&&d>0) return true; //天数控制在合理范围内
            return false;
        }
    
        //判断是否有顺子日期
        static boolean isShun(String s){
            for(int i=0; i<str.length; i++){
                if(s.contains(str[i])) return true;
            }
            return false;
        }
    }

## 程序设计 ##

### [刷题统计][Link 3] ###

> 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 *a* 道题目, 周六和周日每天做 *b* 道题目。请你帮小明计算, 按照计划他将在 第几天实现做题数大于等于 *n* 题?

**思路**

从数据范围上面看，我们不能模拟，我们可以计算出一周小明的刷题数 w=5a+2b。那么可以在O(1)时间内计算出需要完整的刷多少周的题目，剩下的刷不到一周的题目再单独模拟。

时间复杂度：O(1)

import java.util.Scanner;
    
    public class Main {
       public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //三数
            Long a = sc.nextLong();
            Long b = sc.nextLong();
            Long n = sc.nextLong();
            //计算一周的刷题量
            Long week_sum = a * 5 + b * 2;
            if ( n % week_sum == 0 ){
                System.out.println( ( n / week_sum ) * 7 ); //如果能被整除，直接输出
            }else {
                //过了 i个整周
                Long i = n / week_sum;
                //剩余num题没刷，这些题不必花一整周的时间
                Long num = n - i * week_sum;
                //从周一开始刷题
                int day = 0;
                int j = 0;          //还需刷j天的题
                long sum = 0L;    //这些天的刷题数
                while (sum < num){
                    if (day < 5) sum+=a;
                    else sum+=b;
                    j++; day++;
                    day = day%7;
                }
                System.out.println( i * 7 + j ) ;
            }
        }
    }

### [修剪灌木][Link 4] ###

![a8dc7b25a6d984c43b112841baa9bc85.png][]

**思路**

模拟一下，就可以发现其中的规律。爱丽丝只有向左走或者向右走，之后再回到原点，要寻找每颗灌木最高长到多少，只用看向左走再向右走长得高，还是向右走在向左走长得高。

![d87ae52d5adb8877d0884c1161898ecc.png][]

import java.util.Scanner;
    
    public class 修剪灌木 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n=sc.nextInt();
            for(int i=1; i<=n; i++){
                int max=Math.max(i-1,n-i)*2;
                System.out.println(max);
            }
        }
    }

### [X 进制减法][X] ###

![e7e894338e11a88383701f3bef110fb3.png][]

**思路**

首先要明白这个x进制是如何计算的。

先看例子，321，最低位为二进制，所以还是1，第二位为十进制，所以需要往前进位，2转为十进制就为4，第三位数，也需要向第二位进位，所以321->65: 3\*(10\*2)+2\*2+1=65。我们要让A，B两个的差值较大，就要让进制尽可能小，每个位置的进制等于A，B两个数的较大值+1.

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    // 1:无需package
    // 2: 类名必须Main, 不可修改
    
    
    public class Main {
       static int N=1000010;
        static int[]A=new int[N];//存储每一位
        static int[]B=new int[N];//存储每一位
        static int[]x;//进制表
        static int max;//最大进制
    
        static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        public static void main(String[]args) throws IOException {
            max=Integer.parseInt(cin.readLine());
            //A数组
            int ma=Integer.parseInt(cin.readLine());
            String[]as=cin.readLine().split(" ");
            for (int i =ma-1,j=0; i>=0; i--)A[i]=Integer.parseInt(as[j++]);;
    
            //B数组
            int mb=Integer.parseInt(cin.readLine());
            String[]bs=cin.readLine().split(" ");
            for (int i =mb-1,j=0; i>=0; i--)B[i]=Integer.parseInt(bs[j++]);
    
            //初始化进制表
            x=new int[Math.max(ma,mb)+1];
    
            //录入进制表
            int m = Math.max(ma, mb);
            //计算各个位置进制为，取2、a[i]+1、b[i]+1的最大值
            for (int i = 0; i < m; i ++) {
                x[i] = Math.max(Math.max(A[i] + 1, B[i] + 1), 2);
            }
            //计算A B
            f(A,B,x,ma,mb);
    
        }
        static int mod=1000000007;
    
        static void f(int[]A,int[]B,int[]x,int lenA,int lenB){
            long res=0;
            long a=0,b=0;
            for (int i =lenA-1; i>=0;i--)a=(a*x[i]+A[i])%mod;
            for (int i =lenB-1; i>=0;i--)b=(b*x[i]+B[i])%mod;
            System.out.println((a-b+mod)%mod);
        }
    }

### [统计子矩阵][Link 5] ###

![f0d105fe39bda0d844935577822f5ab7.png][]

**思路**

首先，我们有一个查询子矩阵和的需求，肯定需要使用预处理二维前缀和来优化查询。

确立一个子矩阵，需要一个左上角(x1,y1)和一个右下角(x2,y2)，如果进行暴力枚举的话复杂度将会是O(n^4)，会超时不可取。那么如何进行优化，对于x1,x2我们任然进行暴力枚举，然后我们用L表示y1，R表示y2。由于数组内不存在负数，所以随着指针右移，L也一定单调向右移动。这就转化成了一维数组内求和不大于K的数目。枚举R为右边界，此时子矩阵左上角坐标为（x1,L）,右下角坐标为（x2,R），如求得总和大于K，L向右移动，统计当前R作为右边界的答案数量为R-L+1，这样双指针做大的复杂度为O(n)。

这样使用双指针整体的复杂度为O(n^3)。

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main {
        static int N=510;
        static int[][] a = new int[N][N];
        static int[][] s = new int[N][N];
        static int n,m,k;
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        public static void main(String[] args) throws IOException {
            String[] ts = br.readLine().split(" ");
            n = Integer.parseInt(ts[0]);
            m = Integer.parseInt(ts[1]);
            k = Integer.parseInt(ts[2]);
            for(int i = 1; i <= n; i++){
                ts = br.readLine().split(" ");
                for(int j = 1; j <=m; j++){
                    a[i][j] = Integer.parseInt(ts[j-1]);
                    s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
                }
            }
            long res = 0;
            //枚举上下的边
            for(int x1=1; x1 <= n; x1++){
                for(int x2 = x1; x2<=n; x2++){
                    //枚举l和r
                    int l=1;
                    int r=1;
                    while(r<=m){
                        while(l<=r && !check(x1,l,x2,r)) l++;
                        res += (long)r-l+1;
                        r++;
                    }
                }
            }
            System.out.println(res);
        }
        static boolean check(int x1, int y1, int x2, int y2){
            return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] <= k;
        }
    }

### [积木画][Link 6] ###

![965069aebd8c743508b695c5904df850.png][]

**思路**

状态压缩dp模型，虽然N很大，但总共只有两行，只需要考虑结尾的插入情况即可。定义f\[i\]\[j\]为已经排好了前i-1列，且第i列的状态为j的方案数。当j为**0**时表示第i列上面下面都没有摆放积木。为**1**时表示上面未摆放，下面拜访了积木。为**2**时上面摆了，下面没摆。为**3**时上面下面都摆放了积木。

由定义可知最终答案为f\[0\]\[3\]

如何进行初始化？当n为0时，可以视为完全摆好的情况，则f\[0\]\[3\]=1,当n为1时，只有一种摆法f\[1\]\[3\]=1.

接下来考虑如何进行状态转移？首先考虑f\[i\]\[0\],因为0表示上下都未摆放积木。而状态定义前i-1列已经摆好了，则转移方程：f\[i\]\[0\]=f\[i-1\]\[3\]

然后考虑f\[i-1\]\[1\]如何转移：

1表示我们第 i列是下面摆放了上面未摆放，也就是下面突出了一格，我们考虑如何才会产生这样的效果。转移时不应该从 i − 1 列转移，而应该是从f \[ i − 2 \] \[ 3 \] 转移。

综上我们有两种情况可以得到f \[ i \] \[ 1 \] f\[i\]\[1\]f\[i\]\[1\]，转移方程为：f\[i\]\[1\] = (f\[i−1\]\[0\]+f\[i−1\]\[2\])

分析 f\[i\]\[2\]\]其实和 f\[i\]\[1\]同理，反过来就行，方程：f\[i\]\[1\] = (f\[i−1\]\[0\]+f\[i−1\]\[1\])

最后f\[i\]\[3\]，

可以从f \[ i − 1 \] \[ 1 \] 和f \[ i − 1 \] \[ 2 \]转移，综上：dp\[i-1\]\[0\]+dp\[i-1\]\[1\]+dp\[i-1\]\[2\]+dp\[i-1\]\[3\]

import java.util.Scanner;
    
    public class Main {
        static int N=10000010;
        static int mod=1000000007;
        static int[][] dp=new int[N][4];
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n=sc.nextInt();
            int[][] dp=new int[n+1][4];
            dp[1][0]=1;
            dp[1][3]=1; //初始化
            for(int i=2;i<=n;i++){
                dp[i][0]=dp[i-1][3]; //情况为0
                dp[i][1] = (dp[i-1][0]+dp[i-1][2])%mod; //情况为1
                dp[i][2] = (dp[i-1][0]+dp[i-1][1])%mod; //情况为2
                dp[i][3]=(((dp[i-1][0]+dp[i-1][1])%mod+dp[i-1][2])%mod+dp[i-1][3])%mod; //情况为3
            }
            System.out.println(dp[n][3]);
            sc.close();
        }
    }

上面的有一些方法不能通过，贴一个直接找规律的吧。

![f3d6b76d3d15c4ff78072c459f1ae1f2.png][]

import java.util.Scanner;
    
    public class Main {
         public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int N=10000010;
            int mod=1000000007;
            long[] dp = new long[N];
            dp[1]=dp[0]=1;
            dp[2]=2;
            for (int i = 3; i <=n ; i++) {
                dp[i]=(2*dp[i-1]+dp[i-3])%mod;
            }
            System.out.println(dp[n]);
            scan.close();
        }
    }

### 扫雷 ###

### 李白打酒加强版 ###

### 砍竹子 ###

[Link 1]: https://www.lanqiao.cn/problems/2095/learning/?page=1&first_category_id=1&sort=students_count&name=%E4%B9%9D%E8%BF%9B%E5%88%B6%E8%BD%AC%E5%8D%81%E8%BF%9B%E5%88%B6
[Link 2]: https://www.lanqiao.cn/problems/2096/learning/?page=1&first_category_id=1&sort=students_count&name=%E9%A1%BA%E5%AD%90%E6%97%A5%E6%9C%9F
[527335391d3abda353766741b1028738.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3407f330556f47cf8325a2a6fab6821b.png
[Link 3]: https://www.lanqiao.cn/problems/2098/learning/?page=1&first_category_id=1&sort=students_count&name=%E5%88%B7%E9%A2%98%E7%BB%9F%E8%AE%A1
[Link 4]: https://www.lanqiao.cn/problems/2107/learning/?page=1&first_category_id=1&sort=students_count&name=%E4%BF%AE%E5%89%AA%E7%81%8C%E6%9C%A8
[a8dc7b25a6d984c43b112841baa9bc85.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/bb72a66bcf8b4fd6bb23d9a288c73290.png
[d87ae52d5adb8877d0884c1161898ecc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/cf73913b79c14c29b020bc226fa4a0e4.png
[X]: https://www.lanqiao.cn/problems/2108/learning/?page=1&first_category_id=1&sort=students_count&name=X%20%E8%BF%9B%E5%88%B6%E5%87%8F%E6%B3%95
[e7e894338e11a88383701f3bef110fb3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/1b1feae44cd74c7bb0d8c0fd1ad9d74b.png
[Link 5]: https://www.lanqiao.cn/problems/2109/learning/?page=1&first_category_id=1&sort=students_count&name=%E7%BB%9F%E8%AE%A1%E5%AD%90%E7%9F%A9%E9%98%B5
[f0d105fe39bda0d844935577822f5ab7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/8425a4a8b6a04972bf9ecc6ba7b9eb06.png
[Link 6]: https://www.lanqiao.cn/problems/2110/learning/?page=1&first_category_id=1&sort=students_count&name=%E7%A7%AF%E6%9C%A8%E7%94%BB
[965069aebd8c743508b695c5904df850.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/849db3b8633848a1a234f896fd1c3c6a.png
[f3d6b76d3d15c4ff78072c459f1ae1f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/75c290138265406b9310dbb4c5724314.png