蓝桥杯第六届C/C++ B组真题详解

Myth丶恋晨 2022-11-16 13:56 168阅读 0赞

**上一篇博客：[分解质因数][Link 1]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  A 奖券数目
 *   *  题目描述
     *  题解
 *  B 星系炸弹
 *   *  题目描述
     *  题解
 *  C 三羊献瑞
 *   *  题目描述
     *  题解
 *  D 格子中输出
 *   *  题目描述
     *  题解
 *  E 九数组分数
 *   *  题目描述
     *  题解
 *  F 加法变乘法
 *   *  题目描述
     *  题解
 *  G 牌型种数
 *   *  题目描述
     *  题解
 *  H 移动距离
 *   *  题目信息
     *   *  题目描述
         *  资源约定
         *  提示
     *  题解
     *   *  解题思路
         *  解题代码

# A 奖券数目 #

## 题目描述 ##

有些人很迷信数字，比如带 `“4”` 的数字，认为和“死”谐音，就觉得不吉利。虽然这些说法纯属无稽之谈，但有时还要迎合大众的需求。某抽奖活动的奖券号码是 `5` 位数`（10000-99999）`，要求其中不要出现带 `“4”` 的号码，主办单位请你计算一下，如果任何两张奖券不重号，最多可发出奖券多少张。

请提交该数字（一个整数），不要写任何多余的内容或说明性文字。

## 题解 ##

本题可以直接使用暴力枚举判断统计，也可以使用数学方法解决。这其实是一个组合问题问题就转换成了从 **0， 1， 2， 3， 5， 6， 7， 8， 9** 九个数字中任意选五个数字有多少种组合方法。最高位不能为 **0** 有 **8** 种选法，其余四位均有 **9** 中选法，所以总共有  8 ∗ 9 ∗ 9 ∗ 9 ∗ 9 = 52488 8 \* 9 \* 9 \* 9 \* 9 = 52488 8∗9∗9∗9∗9=52488 种组合方式。

当然也可以直接暴力枚举统计一下。代码如下：

#include<iostream>
    
    using namespace std;
    
    bool chack(int x) { 
        while (x) { 
            if (x % 10 == 4) return false;
            x /= 10;
        }
        return true;
    }
    
    int main() { 
        int cnt = 0;
        for (int i = 10000; i < 100000; i++) { 
            if (chack(i)) cnt++;
        }
        cout << cnt;
        return 0;
    }

# B 星系炸弹 #

## 题目描述 ##

在X星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。每个炸弹都可以设定多少天之后爆炸。比如：阿尔法炸弹2015年1月1日放置，定时为15天，则它在2015年1月16日爆炸。有一个贝塔炸弹，2014年11月9日放置，定时为1000天，请你计算它爆炸的准确日期。

请填写该日期，格式为 yyyy-mm-dd 即4位年份2位月份2位日期。比如：2015-02-19。请严格按照格式书写。不能出现其它文字或符号。

## 题解 ##

本题是一个日期模拟题，直接按照日期的规律进行模拟计算即可。注意要考虑闰平年问题。答案为：**2017-08-05**

#include<iostream>
    
    using namespace std;
    
    int mounth_day[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    int main() { 
        int year = 2014, mounth = 11, day = 9;
        int cnt = 0;
        while (cnt < 1000) { 
            if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) { 
                mounth_day[2] = 29;
            } else mounth_day[2] = 28;
            if (day == mounth_day[mounth]) { 
                if (mounth == 12) mounth = 1, year++, day = 1, cnt++;
                else mounth++, day = 1, cnt++;
            } else day++, cnt++;
        }
        cout << year << ' ' << mounth << ' ' << day << endl;
        return 0;
    }

# C 三羊献瑞 #

## 题目描述 ##

观察下面的加法算式：

>  祥 瑞 生 辉  
> `+`三 羊 献 瑞  
> `-------------------`  
> 三 羊 生 瑞 气

(如果有对齐问题，可以参看下图)  
![图例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]  
 其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。

## 题解 ##

根据加法原理，可以判定 **三** 一定是 **1**，那么 **祥** 一定是 **9**，**羊** 则一定是 **0**。所以只需要枚举 **2 ~ 8** 全排列之后的结果即可。答案：`1085`

#include<iostream>
    #include<cstdio>
    using namespace std;
    
    const int N = 9;
    
    int n;
    
    int state[N];    // 0 表示还没有放数字， 1 ~ n 表示放了哪个数
    bool used[N];    // true 表示用过了，false 表示没有用过
    int x1, y1, z1;
    
    void dfs(int x) { 
        if (x == n) { 
            x1 = 9000 + state[0] * 100 + state[1] * 10 + state[2];
            y1 = 1000 + state[3] * 10 + state[0];
            z1 = 10000 + state[1] * 100 + state[0] * 10 + state[4];
            if (x1 + y1 == z1) { 
                for (int i = 0; i < n; i++) { 
                    cout << state[i] << ' ';
                }
                cout << endl;
                cout << x1 << ' ' << y1 << ' ' << z1 << endl;
            }
            // for (int i = 0; i < n; i++) printf("%d ", state[i]);
            // cout << endl;
            return;
        }
        
        // 按照顺序依次枚举每个分支，即当前位置可以填哪些数
        for (int i = 0; i < n; i++) { 
            if (!used[i]) { 
                
                state[x] = i + 2;
                used[i] = true;
                
                dfs(x + 1);
                
                // 恢复现场
                state[x] = 0;
                used[i] = false;
            }
        }
    }
    
    int main() { 
        scanf("%d", &n);
        dfs(0);
        return 0;
    }

# D 格子中输出 #

## 题目描述 ##

StringInGrid函数会在一个指定大小的格子中打印指定的字符串。  
要求字符串在水平、垂直两个方向上都居中。如果字符串太长，就截断。如果不能恰好居中，可以稍稍偏左或者偏上一点。

下面的程序实现这个逻辑，请填写划线部分缺少的代码。

#include <stdio.h>
    #include <string.h>
    
    void StringInGrid(int width, int height, const char* s)
    { 
    	int i,k;
    	char buf[1000];
    	strcpy(buf, s);
    	if(strlen(s)>width-2) buf[width-2]=0;
    	
    	printf("+");
    	for(i=0;i<width-2;i++) printf("-");
    	printf("+\n");
    	
    	for(k=1; k<(height-1)/2;k++){ 
    		printf("|");
    		for(i=0;i<width-2;i++) printf(" ");
    		printf("|\n");
    	}
    	
    	printf("|");
    	
    	printf("%*s%s%*s",_____________________________________________);  //填空
    	          
    	printf("|\n");
    	
    	for(k=(height-1)/2+1; k<height-1; k++){ 
    		printf("|");
    		for(i=0;i<width-2;i++) printf(" ");
    		printf("|\n");
    	}	
    	
    	printf("+");
    	for(i=0;i<width-2;i++) printf("-");
    	printf("+\n");	
    }
    
    int main()
    { 
    	StringInGrid(20,6,"abcd1234");
    	return 0;
    }

对于题目中数据，应该输出：  
![图例][20210408095108915.png]  
 注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

## 题解 ##

主要考察了字符串的输入输出。`printf("%*s, len, str);` 的作用是输出字符串 **str** 但是至少要占 **len** 个位置，**str** 的长度不足 **len** 个位置则在左侧补空格。本题答案：

(width - 2 - strlen(s))/ 2, " ", buf, (width - 2 - strlen(s))/ 2, " "

# E 九数组分数 #

## 题目描述 ##

1,2,3…9 这九个数字组成一个分数，其值恰好为1/3，如何组法？

下面的程序实现了该功能，请填写划线部分缺失的代码。

#include <stdio.h>
    
    void test(int x[])
    { 
    	int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
    	int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
    	
    	if(a*3==b) printf("%d / %d\n", a, b);
    }
    
    void f(int x[], int k)
    { 
    	int i,t;
    	if(k>=9){ 
    		test(x);
    		return;
    	}
    	
    	for(i=k; i<9; i++){ 
    		{ t=x[k]; x[k]=x[i]; x[i]=t;}
    		f(x,k+1);
    		_____________________________________________ // 填空处
    	}
    }
    	
    int main()
    { 
    	int x[] = { 1,2,3,4,5,6,7,8,9};
    	f(x,0);	
    	return 0;
    }

注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

## 题解 ##

这是一个 **dfs** 暴搜代码，考察我们 **恢复现场** 的代码。因为搜索完成之后需要恢复现场，然后进行下一个分支的搜索。  
本题答案：

{ t = x[i], x[i] = x[k], x[k] = t;}

# F 加法变乘法 #

## 题目描述 ##

我们都知道：**1+2+3+ … + 49 = 1225**，现在要求你把其中两个不相邻的加号变成乘号，使得结果为 **2015**。比如：**1+2+3+…+10 \* 11+12+…+27 \* 28+29+…+49 = 2015**就是符合要求的答案。

请你寻找另外一个可能的答案，并把位置靠前的那个乘号左边的数字提交（对于示例，就是提交10）。

注意：需要你提交的是一个整数，不要填写任何多余的内容。

## 题解 ##

本题是一个枚举题目，刚开始看的时候没有什么思路，但是我们要善于将问题转换为数学问题。经过分析我们发现这个题目其实是让我们解了一个方程：我们假设两个乘号左边的数字分别是 **a** 和 **b** ，那么式子就可以列为：  
**1 + 2 + 3 + …… + a + (a + 1) + …… + b + (b + 1) + …… + 48 + 49 = 1225 —— ①**

**1 + 2 + 3 + …… + a \* (a + 1) + …… + b \* (b + 1) + …… + 48 + 49 = 1225 —— ②**

我们让①式减去②式然后整理一下就可以得到：**a2 \+ b2 \- a - b = 792**。所以我们只需要从小到大开始枚举 **1 ~ 49** 输出符合条件的答案即可。注意题目让我们寻找 **10** 以外的另一个答案，所以除了 **10** 从输出的答案中找出第一组答案即可。

#include<iostream>
    
    using namespace std;
    
    int main() { 
        for (int i = 1; i < 47; i++) { 
            for (int j = i + 2; j < 49; j++) { 
                if (i * i - i + j * j - j == 792) cout << i << ' ' << j << endl;
            }
        }
    	return 0;  
    }

**本题答案：16**

# G 牌型种数 #

## 题目描述 ##

小明被劫持到X赌城，被迫与其他 **3** 人玩牌。一副扑克牌（去掉大小王牌，共 **52** 张），均匀发给 **4** 个人，每个人 **13** 张。这时，小明脑子里突然冒出一个问题：如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？

请填写该整数，不要填写任何多余的内容或说明文字。

## 题解 ##

dfs枚举一下即可。答案：**3598180**

#include<iostream> 
    using namespace std;  
     
    int sum=0;  
     
    void dfs(int n,int cartNum){ 
    	if(n > 13){  
    	    return;  // 剪枝
    	}
    	if(cartNum >= 13) { 
    		if(cartNum == 13) { 
    		    sum++;  //每次取够13，则加1 
    		    return;  
    		} 
    	} else { 
    	    //依次往下，每种牌取到 0 到 4 张
    	    dfs(n + 1, cartNum);  
    		dfs(n + 1, cartNum + 1);  
    		dfs(n + 1, cartNum + 2);  
    		dfs(n + 1, cartNum + 3);  
    		dfs(n + 1, cartNum + 4);
    	}  
    }
     
    int main(){ 
    	dfs(0, 0);  
    	cout << sum << endl;  
    	return 0;
    }

# H 移动距离 #

## 题目信息 ##

### 题目描述 ###

X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为1,2,3…当排满一行时，从下一行相邻的楼往反方向排号。  
比如：当小区排号宽度为6时，开始情形如下：

> 1 2 3 4 5 6  
> 12 11 10 9 8 7  
> 13 14 15 …

我们的问题是：已知了两个楼号 **m** 和 **n**，需要求出它们之间的最短移动距离（不能斜线方向移动）

输入为 **3** 个整数 **w m n**，空格分开，都在 **1** 到 **10000** 范围内。**w**为排号宽度，**m,n**为待计算的楼号。

要求输出一个整数，表示 **m n** 两楼间最短移动距离。

例如：  
用户输入：  
6 8 2  
则，程序应该输出：  
4

再例如：  
用户输入：  
4 7 20  
则，程序应该输出：  
5

### 资源约定 ###

> 峰值内存消耗 < 256M  
> CPU消耗 < 1000ms

### 提示 ###

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

*  注意: main函数需要返回0
 *  注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
 *  注意: 所有依赖的函数必须明确地在源文件中 \#include ， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

## 题解 ##

### 解题思路 ###

题目的数据范围是 **w, n, m <= 10000**。所以本题如果暴力枚举的话时间复杂度是 **O(n2)**，有超时的风险，但是也不是不可以做。最好的方法为直接计算两个房子的坐标，然后进行坐标相减的结果取绝对值，将横纵坐标分别相减去绝对值，然后相加即可。为了方便计算下标，在计算时将每个数减一，表示在矩阵中是从零开始存储的，这样算 **x** 在第几行只需要使 **x / w** 即可求出，算第几列时如果是奇数行需要进行翻转一下该行。

### 解题代码 ###

#include<iostream>
    #include<cmath>
    
    using namespace std;
    
    int main() { 
        int w, n, m;
        cin >> w >> n >> m;
        n--, m--;   // 从零开始计算，方便计算坐标
        int hn, wn, hm, wm;
        
        hn = n / w; // 计算横坐标
        if (hn % 2) wn = w - 1 - n % w; // 如果该行是奇数行，那么需要将该行翻转一下
        else wn = n % w;    // 偶数行不需要进行翻转
        
        hm = m / w;
        if (hm % 2) wm = w - 1 - m % w;
        else wm = m % w;
        
        cout << fabs(hm - hn) + fabs(wm - wn);
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![20210326120556284.png][]

[Link 1]: https://ac-fun.blog.csdn.net/article/details/115417602
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221022/649bff8fe8384fceb2730f8c61885f6e.png
[20210408095108915.png]: /images/20221022/8a4fcc5280984894b0c309306a28db74.png
[20210326120556284.png]: /images/20221022/82fe7b6288de471a9990f1ccd5aaf06f.png