2015年蓝桥杯第六届CC++大学B组真题及代码
目录
1A：奖券数目（填空_简单枚举）
2B：星系炸弹（填空_日期计算）
3C：三羊献瑞（填空_全排列）
4D：格子中输出（代码填空）
5E：九数组分数（代码填空）
6F：加法变乘法（填空）
7G：牌型种数（填空）
8H：移动距离（编程）
解析代码
9I：垒骰子（编程）
解析代码
10J：生命之树（编程）
解析代码（ 树形DP）
1A：奖券数目（3分填空_简单枚举）
题目分析：简单的循环枚举。答案52488
#include<iostream>
using namespace std;
bool check(int num)
{
while (num)
{
int j = num % 10;
if (j == 4)
return false;
num /= 10;
}
return true;
}
int main()
{
int cnt = 0;
for (int i = 10000; i <= 99999; ++i)
{
if (check(i))
++cnt;
}
cout << cnt << endl;
return 0;
}
// 答案524882B：星系炸弹（5分填空_日期计算）
题目解析：
打开计算器两步搞定：答案2017-08-05
‘
但还是贴个代码：
#include<iostream>
using namespace std;
int months[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
bool is_leap(int year)
{
return (year % 400 == 0 || (year % 100 != 0 && year % 4 == 0));
}
int main()
{
int year = 2014;
int month = 11;
int day = 9;
int T = 1000;
while (T--)
{
day++;
if (month == 2)
{
if (is_leap(year)) months[2] = 29;//如果是闰年
}
if (day > months[month])//如果天数已经大于该月的天数时
{
if (month == 12)//如果该月是12月，那么就++年
{
year++;
month = 1;//月份重新变为1
day = 1;
}
else
{
++month; // 否则只是月份++
day = 1;
}
}
months[2] = 28;//还原
}
printf("%d-%02d-%02d\n", year, month, day);//2017-08-05
return 0;
}3C：三羊献瑞（9分填空_全排列）
从文字中可以得出 祥 三 为非零的数，且 三 为1。这里可以用暴力，7层循环，具体不写了。这里使用全排列算法实现，数组中：num[0]~num[6]分别代表 祥 瑞 生 辉 羊 献 气
答案1085
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int num[9] = { 0,2,3,4,5,6,7,8,9 };
do {
if (num[0] != 0)//数字的开头不能为0
{
int a = num[0] * 1000 + num[1] * 100 + num[2] * 10 + num[3];
int b = 1000 + num[4] * 100 + num[5] * 10 + num[1];
int c = 10000 + num[4] * 1000 + num[2] * 100 + num[1] * 10 + num[6];
if (a + b == c)
{
cout << "1" << num[4] << num[5] << num[1] << endl;
break; // 答案1085
}
}
} while (next_permutation(num, num + 9));
return 0;
}4D：格子中输出（11分代码填空）
题目描述：
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; }
题目解析：
就是要控制这个字符串在中间输出。因为这两行两边有两个字符，所以字符串剩余的空间，就是总的宽度width减减去字符串的，再减去两边方框的字符，然后再除二即可，然后因为存在基数的情况，所以还会有后面的考虑。
此外：使用%*s，表示这里的具体域宽值由后面的实参决定，如printf(“%*s”,6, “abc”)就是把”abc”放到在域宽为6的空间中右对齐。 *就是用来控制域宽而已。
答案：
(width-2-strlen(s))/2," ",s,width-2-strlen(s)-(width-2-strlen(s))/2," "5E：九数组分数（13分代码填空）
题目描述：
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; }
题目解析：
这题按照固定思维，我第一次想到的就是填空处是一个递归，然而，我看到递归外面有一个for循环，对于这种for循环的递归，一般只有一个出入口，那么这个填空处就不是填递归函数入口，{t=x[k]; x[k]=x[i]; x[i]=t;}表示的在进入递归前需要进行交换值，那么我们想想，如果递归进去后，再出来，发现不满足值，是不是需要进行一个值的还原，所以接着使用{t=x[k]; x[k]=x[i]; x[i]=t;}进行还原，这题考察对于递归的熟练程度。。答案：
{t=x[k]; x[k]=x[i]; x[i]=t;}
题目解析：
这里使用递归的猜想，对于这里，我们要修改的就是递归函数里后面两个参数里的三个变量col,row,w，这里使用的方法是修改参数，然后通过结果发现,col控制列，col控制行，w控制空格数，所以最后调调答案就出来了，这种递归题在蓝桥杯中通过边调试边看结果最快。
所以三层递归就是这个意思：
f(a, rank - 1, row, col + w / 2); // 处理最上面的三角形
f(a, rank - 1, row + w / 2, col); // 处理左下角三角形
f(a, rank - 1, row + w / 2, col + w); // 处理右下角三角形答案：
f(a, rank-1, row, col + w / 2)6F：加法变乘法（17分填空）
题目描述：
我们都知道：1+2+3+ … + 49 = 1225
现在要求你把其中两个不相邻的加号变成乘号，使得结果为2015
比如：
1+2+3+…+10*11+12+…+27*28+29+…+49 = 2015
就是符合要求的答案。请你寻找另外一个可能的答案，并把位置靠前的那个乘号左边的数字提交（对于示例，就是提交10）。
注意：需要你提交的是一个整数，不要填写任何多余的内容。
题目分析：
暴力枚举，这里的话将乘号的位置看做是要遍历的变量，一共两个值。知道两个乘号的位置，然后模拟计算就可以了。
答案16
#include<iostream>
using namespace std;
int main()
{
for (int i = 1; i < 49; i++) // 第一个*的位置
{
for (int j = i + 2; j < 49; j++) // 第二个*的位置
{
int sum = 0;
for (int k = 1; k < 50; ++k) // 进行运算
{
if (k == i || k == j)
{
sum += k * (k + 1);
++k;
}
else
sum += k;
}
if (sum == 2015)
{
cout << i << " " << j << endl;
}
}
}
return 0;
}7G：牌型种数（21分填空）
题目描述：
小明被劫持到X赌城，被迫与其他3人玩牌。
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。
这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？
请填写该整数，不要填写任何多余的内容或说明文字。
题目解析：
答案3598180
dfs代码：
#include <iostream>
#include <algorithm>
using namespace std;
int num[9] = { 2,4,5,6,7,9,10,11,12 };
bool jude() // 判断六条直线是否相等
{
int ans1 = 1 + num[1] + num[4] + num[8];
int ans2 = 1 + num[0] + num[3] + num[5];
int ans3 = 8 + num[0] + num[1] + num[2];
int ans4 = 8 + num[3] + num[6] + 3;
int ans5 = 3 + num[7] + num[4] + num[2];
int ans6 = num[5] + num[6] + num[7] + num[8];
return ans1 == ans2 && ans1 == ans3 && ans1 == ans4 && ans1 == ans5 && ans1 == ans6;
}
int main()
{
do
{
if (jude())
break;
} while (next_permutation(num, num + 9));
cout << num[3] << endl;
return 0;
}8H：移动距离（15分编程）
题目描述：
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
解析代码
题目分析：
先算纵向距离，再算横向距离，通过行数的差的奇偶判断行序是否一致（升序降序）。一致的话取余相减即可，主要是不一致的情况，这部分没有什么推理，凭借简单的小学数学逻辑代数硬推的。
#include <bits/stdc++.h>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int w, m, n;
cin >> w >> m >> n;
--m; // 为了对应
--n;
int x1 = m / w, x2 = n / w;
int y1 = m % w, y2 = n % w;
if (x1 % 2 != 0) // 奇偶情况
y1 = w - 1 - y1;
if (x2 % 2 != 0)
y2 = w - 1 - y2;
cout << abs(x1 - x2) + abs(y1 - y2) << endl;
return 0;
}9I：垒骰子（25分编程）
题目描述：
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。地宫的入口在左上角，出口在右下角。小明被带到地宫的入口，国王要求他只能向右或向下行走。走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。请你帮小明算一算，在给定的局面下，他有 多少种不同的行动方案能获得这k件宝贝。
【数据格式】
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
例如，输入：
2 2 2
1 2
2 1
程序应该输出：
2
再例如，输入：
2 3 2
1 2 3
2 1 5
程序应该输出：
14
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
解析代码
题目解析：
AcWing 1217. 垒骰子 - AcWing
第六届蓝桥杯【省赛试题9】垒骰子 ( 矩阵快速幂 )-CSDN博客
待续10J：生命之树（31分编程）
题目描述：
在X森林里，上帝创建了生命之树。他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个非空节点集S，使得对于S中的任意两个点a,b，都存在一个点列 {a, v1, v2, …, vk, b} 使得这个点列中的每个点都是S里面的元素，且序列中相邻两个点间有一条边相连。
在这个前提下，上帝要使得S中的点所对应的整数的和尽量大。这个最大的和就是上帝给生命之树的评分。经过atm的努力，他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算，他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。「输入格式」
第一行一个整数 n 表示这棵树有 n 个节点。
第二行 n 个整数，依次表示每个节点的评分。
接下来 n-1 行，每行 2 个整数 u, v，表示存在一条 u 到 v 的边。由于这是一棵树，所以是不存在环的。「输出格式」
输出一行一个数，表示上帝给这棵树的分数。「样例输入」
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5「样例输出」
8「数据范围」
对于 30% 的数据，n <= 10
对于 100% 的数据，0 < n <= 10^5, 每个节点的评分的绝对值不超过 10^6 。资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
解析代码（ 树形DP）
树形DP：
（1）dp数组的定义：表示以u为根节点的子树中所有连通块的的权值的最大值
（2）dp数组的属性：最大值
（3）dp数组的递推公式：如果大于0，则把它加入dp数组中，核心就是贪心的思想，因为要求的是连通块的最大值
- dp[1]是：以1为根节点，包括1的所有联通块的最大值
- dp[2]是：以2为根节点，包括2的所有连通块的最大值（注意此时不包括1）
- dp[3]是：以3为根节点，包括3的所有连通块的最大值（注意此时不包括1）
同理dp[4]=4 dp[5]=5（也就是说不能向上寻找只能向下寻找），所以dfs深搜的第一步是：将f[u]=w[u] （将该根节点的值存入dp数组）。之后才是向下搜索，注意此时的f[j]只是可能是的单个节点的值，它指的是这个节点之下包括这个节点的值，所以是大于0，才把它加入进去。
解析代码（ 树形DP）
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define endl '\n'
#define int long long
const int N = 100010, M = N * 2;
int n;
int w[N];
int h[N], e[M], ne[M], idx;
int f[N];
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u, int father)
{
f[u] = w[u];
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j != father)
{
dfs(j, u);
f[u] += max(0ll, f[j]);
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; ++i)
{
cin >> w[i];
}
for (int i = 0; i < n - 1; ++i)
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs(1, -1);
int res = f[1];
for (int i = 2; i <= n; ++i)
{
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}