2013年蓝桥杯第四届CC++大学B组真题及代码

目录

1A：高斯日记（日期计算）

2B：马虎的算式（暴力模拟）

3C：第39级台阶（dfs或dp）

4D：黄金连分数（递推+大数运算）

5E：前缀判断（代码填空）（枚举）

6F：三部排序（代码填空）

7G：错误票据（枚举）

8H：翻硬币（找规律）

9I：带分数（全排列暴力）

10J：连号区间数（找规律）

---

        蓝桥杯大赛是从第四届才开始划分ABC组的，因此前三届的题目所有院校都是一样的。所以这里此专栏就从第四届开始刷题了，应该直接从2013年刷到2023年，十年真题了属于是，有些难题看不懂就不放代码了，读题真的痛苦。

1A：高斯日记（日期计算）

题目描述：

        大数学家高斯有个好习惯：无论如何都要记日记。他的日记有个与众不同的地方，他从不注明年月日，而是用一个整数代替，比如：4210。后来人们知道，那个整数就是日期，它表示那一天是高斯出生后的第几天。这或许也是个好习惯，它时时刻刻提醒着主人：日子又过去一天，还有多少时光可以用于浪费呢？
        高斯出生于1777年4月30日，在高斯发现的一个重要定理的日记上标注着5343，因此可算出那天是1791年12月15日。高斯获得博士学位的那天日记上标着8113，请你算出高斯获得博士学位的年月日。
        提交答案的格式是：yyyy-mm-dd，例如：1980-03-21

题目解析：

打开电脑的计算器一顿操作：

（十四岁发现重要定理，好好好）

所以找到相差8112天的，比5342多2770天，约再过七年六个月：即1799年左右，再打开计算器：

所以答案就是1799-07-16

---

2B：马虎的算式（暴力模拟）

题目描述：

题目解析：

按题目所给形式暴力模拟即可，答案142

#include<iostream>
using namespace std;int main()
{int res = 0;for (int a = 1; a <= 9; a++){for (int b = 1; b <= 9; b++){if (a != b){for (int c = 1; c <= 9; c++){if (c != b && c != a){for (int d = 1; d <= 9; d++){if (d != c && d != b && d != a){for (int e = 1; e <= 9; e++){if (e != d && e != c && e != b && e != a){int left = (a * 10 + b) * (c * 100 + d * 10 + e);int right = (a * 100 + d * 10 + b) * (c * 10 + e);if (left == right){++res;}}}}}}}}}}cout << res;return 0;
}
// 答案142

---

3C：第39级台阶（dfs或dp）

答案51167078

暴力dfs代码：

#include <iostream>
using namespace std;
int res = 0;
// total表示当前走过的台阶数量，step表示当前的步数 
void dfs(int total, int step)
{if (total > 39) // 超出边界return;if (total == 39){if (step % 2 == 0)res++; // 步数为偶数，计数器加一 return;}dfs(total + 1, step + 1); // 每次迈步都有两种选择 dfs(total + 2, step + 1);
}
int main()
{dfs(0, 0);cout << res << endl;return 0;
}

---

动态规划dp代码：

#include <iostream>
using namespace std;
int dp[40][2]; // 上到第i层台阶，最后一步是1/2步用的上法
int main()
{dp[1][1] = 1;dp[1][2] = 0;dp[2][1] = 1;dp[2][2] = 1;for (int i = 3; i <= 39; i++){dp[i][1] = dp[i - 1][2] + dp[i - 2][2];dp[i][2] = dp[i - 1][1] + dp[i - 2][1];}cout << dp[39][2] << endl;return 0;
}

---

4D：黄金连分数（递推+大数运算）

标题: 黄金连分数
    黄金分割数0.61803... 是个无理数，这个常数十分重要，在许多工程问题中会出现。有时需要把这个数字求得很精确。

    对于某些精密工程，常数的精度很重要。也许你听说过哈勃太空望远镜，它首次升空后就发现了一处人工加工错误，对那样一      个庞然大物，其实只是镜面加工时有比头发丝还细许多倍的一处错误而已，却使它成了“近视眼”!!
    言归正传，我们如何求得黄金分割数的尽可能精确的值呢？有许多方法。

    比较简单的一种是用连分数：

                  1
    黄金数 = ---------------------
                        1
             1 + -----------------
                          1
                 1 + -------------
                            1
                     1 + ---------
                          1 + ...                    

    这个连分数计算的“层数”越多，它的值越接近黄金分割数。

    请你利用这一特性，求出黄金分割数的足够精确值，要求四舍五入到小数点后100位。

    小数点后3位的值为：0.618
    小数点后4位的值为：0.6180
    小数点后5位的值为：0.61803
    小数点后7位的值为：0.6180340
   （注意尾部的0，不能忽略）

你的任务是：写出精确到小数点后100位精度的黄金分割值。

注意：尾数的四舍五入！ 尾数是0也要保留！

显然答案是一个小数，其小数点后有100位数字，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。

黄金连分数（斐波那契数列、大数运算）正确解法_用连分数证斐波那契-CSDN博客

---

5E：前缀判断（代码填空）（枚举）

题目描述：

        如下的代码判断needle_start指向的串是否为haystack_start指向的串的前缀，如不是，则返回NULL。比如："abcd1234"就包含了"abc"为前缀。

char *prefix(char *haystack_start,char *needle_start)
{ char *haystack=haystack_start;char *needle=needle_start;while(*haystack&&*needle){if(_____________________) return NULL;  //填空位置}if(*needle) return NULL;return haystack_start;
}

题目解析：

        我们可以发现 haystack为要判断的字符串，而needle是前缀。就是对于两个字符串比较。指针加一。答案：

*(haystack++)!=*(needle++)

测试：

#include<iostream>
using namespace std;char* prefix(char* haystack_start, char* needle_start)
{char* haystack = haystack_start;char* needle = needle_start;while (*haystack && *needle){if (*(haystack++) != *(needle++)) return NULL;  //填空位置}if (*needle) return NULL;return haystack_start;
}
int main()
{char haystack_start[] = "abcd123";char needle_start[] = "abcd";//char needle_start[] = "cd";char* ans = prefix(haystack_start, needle_start);if (ans != NULL)cout << ans << endl;elsecout << "空指针" << endl;return 0;
}

---

6F：三部排序（代码填空）（排序）

题目描述：

         一般的排序有许多经典算法，如快速排序、希尔排序等。但实际应用时，经常会或多或少有一些特殊要求。我们没必要套用那些经典算法，可以根据实际情况建立更好的解法。
        比如，对一个整型数组中的数字进行分类排序：使得负数都靠左端，正数都靠右端，0在中部。注意问题的特点是：负数区域和正数区域内并不要求有序。可以利用这个特点通过1次线性扫描就结束战斗！
        以下的程序实现了该目标。其中x指向待排序的整型数组，len是数组的长度。

#include <stdio.h>
void sort3p(int *x,int len)
{ int p=0;int left=0;int right=len-1;int t;while(p<=right){ if(x[p]<0){ t=x[left];  x[left]=x[p];  x[p]=t;  left++;  p++; }else if(x[p]>0) { t=x[right];  x[right]=x[p];  x[p]=t;  right--; }else { _______________________//填空位置}}
}

题目分析

        第一步是遍历下标p，第二步是最左下标left和最右下标right，第三步，利用p遍历，遍历的过程中，如果有小于0的则与下标为left的x[left]进行交换，如果有大于0的则与下标为right的x[right]进行交换，答案：

x[p++]=0;

检验：

#include <stdio.h>
void sort3p(int* x, int len)
{int p = 0;int left = 0;int right = len - 1;int t;while (p <= right){if (x[p] < 0){t = x[left];  x[left] = x[p];  x[p] = t;  left++;  p++;}else if (x[p] > 0){t = x[right];  x[right] = x[p];  x[p] = t;  right--;}else{x[p++] = 0;}}
}int main()
{int arr[] = { 5, 6, 0, -7, 9, 1, -6, 0, 0, -8, -6 };sort3p(arr, sizeof(arr) / sizeof(arr[0]));for (auto& e : arr){cout << e << " ";}return 0;
}

---

7G：错误票据（枚举）

测评链接

题目描述：

数据范围：1 <= N <= 100

例如，用户输入：
2
5 6 8 11 9
10 12 9

则程序输出：

7 9

再例如，用户输入：
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119

则程序输出：

105 120

---

代码解析

题目解析：

依题意：断号不可能发生在最小值和最大值，因此就以它们两作为边界，用哈希表记录频数即可

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;int main()
{vector<int> hash(N, 0);int n;cin >> n;int minv = INF;int maxv = -INF;int tp;while (cin >> tp) // Ctrl+z 结束输入，OJ最后会自动结束{if (tp < minv)minv = tp;if (tp > maxv)maxv = tp;hash[tp]++;}int res1 = 0, res2 = 0;for (int i = minv; i <= maxv; ++i){if (hash[i] == 0)res1 = i;if (hash[i] == 2)res2 = i;}cout << res1 << " " << res2 << endl;return 0;
}

---

8H：翻硬币（找规律）

测评链接：蓝桥杯历届试题-翻硬币 - C语言网

题目描述：

        小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用*表示正面，用o表示反面（是小写字母，不是零），比如可能情形是**oo***oooo，如果同时翻转左边的两个硬币，则变为oooo***oooo。现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

程序输入：两行等长字符串，分别表示初始状态和要达到的目标状态，每行长度<1000

程序输出：一个整数，表示最小操作步数。

例如，用户输入：
**********
o****o****

程序应该输出：5

再例如，用户输入：
*o**o***o***
*o***o**o***

程序应该输出：1

---

        此题可以用dfs/bfs暴力求解，但是细微观察一下，题目是有规律可循的：（下面说说的翻转都是指依次翻转两个相邻的位置，同题目中的意思）就用例子来说吧：

0

1

2

3

4

5

6

7

8

9

*	*	*	o	*	*	*	o	*	*
*	o	*	*	*	o	*	*	*	*

        （用表格更容易看对其效果）对于这两个链：只需要翻转4次就可以使两个链相同（只看出的），那么规律就是每两个相邻的不同位置的下标之差的和就是所求的最小次数（注意我说的是每两个相邻的位置，也就是每一个不同的位置只能用一次）。对于上述两个链计算过程就是3-1 = 2，7 - 5 = 2；那么结果就是2 + 2 = 4；再比如：

0	1	2	3	4	5
*	*	*	*	*	*
o	*	*	*	*	o

这两个链需要翻转的最少次数为：5 - 0 = 5；即5次；

上面两个例子，大家应该都可以看出了吧，或许有人想到了这个例子：

0	1	2	3	4	5	6	7	8	9
*	*	*	*	*	*	o	*	*	*
*	o	*	*	*	*	*	*	*	o

        对于这两个链上面的规律就“失效了”，但是大家仔细观察，这种情况应该是无解的，所以上面总结的规律是正确的。题目没说无解输出什么，那么就默认是肯定有解的。

注意代码中，如何来算每相邻不同位置的差的总和的，也就是start的妙用。

代码解析

#include <iostream>
#include <string>
using namespace std;
int main()
{string s1, s2; // s1:初始状态，s2:目标状态cin >> s1 >> s2;int res = 0, start = -1;for (int i = 0; i < s1.size() - 1; i++){if (s1[i] != s2[i])//第 i 个位置上状态不同，就翻转该位置和后一个位置硬币{if (start == -1) // 还没标记第一个位置{start = i;}else{res += (i - start);start = -1;}}}cout << res;//输出翻转次数return 0;
}

---

9I：带分数（全排列暴力）

测评链接：蓝桥杯2013年第四届真题-带分数 - C语言网

题目描述：

        100可以表示为带分数的形式：100=3+69258/714，还可以表示为：100=82+3546/197，注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。类似这样的带分数，100有11种表示法。
        题目要求：从标准输入读入一个正整数N（N<1000*1000）程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。注意：不要求输出每个表示，只统计有多少表示法！

例如，用户输入：100
程序输出：11

再例如，用户输入：105
程序输出：6

代码解析

题目解析：设n=a+b/c。

        第一步先将1~9全排列，把每一种情况中的9个数分成三份，分别令其为a，b，c。 这样就获得了一组满足条件的abc，然后让a+b/c 与 n判断一下是否相等，每出现一个相等的情况，就让计数变量+1，打印计数变量，就能得出最后的答案。

// n = a + b / c
// n * c = a * c + b
//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int num[20];
int fun(int left, int right)
{int res = 0;for (int i = left; i <= right; ++i){res = res * 10 + num[i];}return res;
}
int main()
{int n = 0, res = 0;cin >> n;for (int i = 1; i <= 9; ++i){num[i] = i;}do{for (int i = 1; i <= 7; ++i) // 加号前的长度{for (int j = i + 1; j <= 9; j++) // {int a = fun(1, i); // 加号前面的int b = fun(i + 1, j); // 加号和除号中间的int c = fun(j + 1, 9); // 除号后面的if (n * c == a * c + b) // 把除法转换，两边乘cres++;}}} while (next_permutation(num + 1, num + 10));cout << res << endl;return 0;
}

---

10J：连号区间数（找规律）

测评链接：蓝桥杯历届试题-连号区间数 - C语言网

题目描述：
        小明这些天一直在思考这样一个奇怪而有趣的问题：在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：如果区间[L,R]里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。
当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式：
第一行是一个正整数N（1<=N<=50000），表示全排列的规模；
第二行是N个不同的数字Pi（1<=Pi<=N），表示这N个数字的某一全排列。

输出格式：输出一个整数，表示不同连号区间的数目。

示例，用户输入：
4
3 2 4 1

程序应输出：7

用户输入：
5
3 4 2 5 1
程序应输出：9

解释：
第一个用例中，有7个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中，有9个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

代码解析

题目解析：

        题目中的连续的意思是每个数之间的差值是1，通过规律，判断一个区间是否是连号区间，可以通过这个区间的最大值与最小值的差值是否于这个区间整数的个数。

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;int n;
int a[10010];
int maxv,minv; // 所枚举区间内最值
int res=0;int main()
{scanf("%d",&n);for(int i = 1; i <= n; ++i)scanf("%d",&a[i]);for(int i=1 ; i <= n; ++i)//枚举左端点{maxv = -0x7f7f7f7f; minv = 0x7f7f7f7f;for(int j = i; j <= n; ++j)//枚举右端点{maxv=max(maxv,a[j]);minv=min(minv,a[j]);if(maxv-minv == j - i)++res;}}printf("%d",res);return 0;
}