2019年第十届蓝桥杯大赛软件类省赛C/C++大学B组#
试题 A:组队#
本题总分：5分
【问题描述】
作为篮球队教练，你需要从以下名单中选出 1号位至 5号位各一名球员，
组成球队的首发阵容。
每位球员担任 1号位至 5号位时的评分如下表所示。请你计算首发阵容 1
号位至5号位的评分之和最大可能是多少？
此题需要注意的是：一个人可能在很多个位分数都是最高的，但是一个人只能打一个位
1: 98 2:99 3: 98 4:97 5:98 == 490(认真理解题真的很重要 ┭┮﹏┭┮)
试题 B:年号字串#
本题总分：5分
【问题描述】
小明用字母 A对应数字 1，B对应 2，以此类推，用 Z对应 26。对于 27
以上的数字，小明用两位或更长位的字符串来对应，例如 AA对应27，AB对
应28，AZ对应52，LQ对应329。
请问2019对应的字符串是什么？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个大写英文字符串，在提交答案时只填写这个字符串，注意全部大写，填写多
余的内容将无法得分
//答案BYQ
#include <bits/stdc++.h>
using namespace std;
void dfs(int N) {
if (N > ) dfs((N - ) / );//其中(N - 1)为将26进制转换为以0开头的,以前是以1开头满27进
putchar('A' + (N - ) % );
}
int main() {
int N;
while (cin >> N) {
dfs(N); cout << endl;
}
return ;
}
试题 C:数列求值#
本题总分：10分
【问题描述】
给定数列1,1,1,3,5,9,17,…，从第4项开始，每项都是前3项的和。求
第20190324项的最后4位数字。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个4位整数（提示：答案的千位不为0），在提交答案时只填写这个整数，填写
多余的内容将无法得分。
#include <iostream>
using namespace std;
int main(){
int a[] = {, , , };//第四为用来存储所求的值
for(int i = ; i < ; i++){
a[] = (a[] + a[] + a[]) % ;
a[] = a[] % ;
a[] = a[] % ;
a[] = a[];
}
cout << a[] << endl;
return ;
}
答案：4659
试题 D:数的分解#
本题总分：10分
【问题描述】
把 2019分解成 3个各不相同的正整数之和，并且要求每个正整数都不包
含数字2和4，一共有多少种不同的分解方法？
注意交换 3个整数的顺序被视为同一种方法，例如 1000+1001+18和
1001+1000+18被视为同一种。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
bool check(int n){
if(n < ){
return false;
}
string s1;
stringstream ss;
ss << n;
ss >> s1;
for(int i = ; i < s1.size(); i++){
if(s1[i] == '' || s1[i] == ''){
return false;
}
}
return true;
}
int main(){
int count = ;
for(int i = ; i < ; i++){
if(check(i)){
for(int j = i + ; j < - i - j; j++){
if(check(j) && check( - i - j)){
count++;
}
}
}
}
cout << count;
return ;
}
答案 ： 40785
五、 迷宫
下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可以通行的地方。
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中D<L<R<U。
答案：
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
#include <iostream>
#include <map>
#include <vector>
#include <deque>
using namespace std;
char a[][];
struct node{
int x;
int y;
int stepNum; //用来记录步数
int l[]; //用来记录路径
};
deque<node> q;
void printRoad(node n){
int direction[][] = {, , , -, , , -, }; // D < L < R < U
int backTx = direction[n.l[]][];
int backTy = direction[n.l[]][];
for(int i = ; i < n.stepNum; i++){
int tx = direction[n.l[i]][];
int ty = direction[n.l[i]][];
//int direction[4][2] = {1, 0, 0, -1, 0, 1, -1, 0}; // D < L < R < U
if(tx == && ty == ){
cout << "D";
}else if(tx == && ty == -){
cout << "L";
}else if(tx == && ty == ){
cout << "R";
}else if(tx == - && ty == ){
cout << "U";
}
backTx = tx;
backTy = ty;
}
}
void bfs(){
node nextNode;
node curNode;
curNode.x = ;
curNode.y = ;
curNode.stepNum = ;
curNode.l[curNode.stepNum] = ;
a[curNode.x][curNode.y] = '';
q.push_back(curNode);
while(!q.empty()){
curNode = q.front();
int curX = curNode.x;
int curY = curNode.y;
if(curX == && curY == ){
printRoad(curNode);
return;
}
a[curX][curY] = ''; // 出队前先去除标记
q.pop_front();
int direction[][] = {, , , -, , , -, }; // D < L < R < U
for(int i = ; i < ; i++){
int tx = curX + direction[i][];
int ty = curY + direction[i][];
if(tx < || tx > || ty < || ty > ){
continue;
}
if(a[tx][ty] == ''){
nextNode = curNode;
a[tx][ty] = '';
nextNode.x = tx;
nextNode.y = ty;
nextNode.stepNum = curNode.stepNum + ;
nextNode.l[curNode.stepNum] = i;
q.push_back(nextNode);
} }
}
}
int main(){
for(int i = ; i < ; i++){
for(int j = ; j < ; j++){
cin >> a[i][j];
}
} bfs();
return ;
}
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
bool check(int n){
stringstream ss;
string s1;
ss << n;
ss >> s1;
if(string::npos != s1.find('')){
return true;
}else if(string ::npos != s1.find('')){
return true;
}else if(string::npos != s1.find('')){
return true;
}else if(string::npos != s1.find('')){
return true;
}else{
return false;
} }
int main(){
int n;
cin >> n;
int sum = ;
for(int i = ; i < n + ; i++){
if(check(i)){
sum += i;
}
}
cout << sum;
return ;
}
【输出格式】
输出一个整数代表答案。
【样例输入】
7
1 6 5 4 3 2 1
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例，1≤N≤100000 1 \leq N \leq 1000001≤N≤100000，−100000≤Ai≤100000 -100000 \leq Ai \leq 100000−100000≤Ai≤100000。
思路:
枚举。时间复杂度: O(N) O(N)O(N)
注意: 最大和可能为负数
数据1：
- - -
答案1：
数据2：
- - -
答案2：
八、等差数列
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N 个整数。
现在给出这N 个整数，小明想知道包含这N 个整数的最短的等差数列有几项？
【输入格式】
输入的第一行包含一个整数N。
第二行包含N 个整数A1,A2,...,AN A_{1}, A_{2}, ..., A_{N}A
1
,A
2
,...,A
N
。(注意A1 A_{1}A
1
~ AN A_{N}A
N
并不一定是按等差数列中的顺序给出)
【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10
【样例说明】
包含2、6、4、10、20 的最短的等差数列是2、4、6、8、10、12、14、16、18、20。
【评测用例规模与约定】
对于所有评测用例，2≤N≤100000 2 \leq N \leq 1000002≤N≤100000，0≤Ai≤109 0 \leq Ai \leq 10^90≤Ai≤10
9
。
思路:
排序+遍历求两数之差的gcd。时间复杂度: O(NlogN) O(NlogN)O(NlogN)
注意: d=0为常数数列, 答案为N
九、后缀表达式
相似题 (N=0, 感觉表达式这题应该是改编的): Slime
给定N 个加号、M 个减号以及N + M + 1 个整数A1,A2,...,AM+N+1 A_{1}, A_{2}, ..., A_{M + N + 1}A
1
,A
2
,...,A
M+N+1
，小明想知道在所有由这 N 个加号、M 个减号以及 N + M +1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用1 2 3 + -，则“2 3 + 1 -” 这个后缀表达式结果是4，是最大的。
【输入格式】
第一行包含两个整数N 和M。
第二行包含N + M + 1 个整数A1,A2,...,AM+N+1 A_{1}, A_{2}, ..., A_{M + N + 1}A
1
,A
2
,...,A
M+N+1
。
【输出格式】
输出一个整数，代表答案。
【样例输入】
1 1
1 2 3
【样例输出】
4
【评测用例规模与约定】
对于所有评测用例，1≤N,M≤100000 1 \leq N, M \leq 1000001≤N,M≤100000，−109≤Ai≤109 -10^9 \leq A_{i} \leq 10^9−10
9
≤A
i
≤10
9
。