1、组队(枚举)
【题目】
作为篮球队教练,你需要从以下名单中选出 1 号位至 5 号位各一名球员,组成球队的首发阵容。
每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分之和最大可能是多少?
【题解】
过于简单,直接爆破就不贴源码了
2、年号字符串
【题目】
字母 A 对应数字 1,B 对应 2,以此类推,用 Z 对应 26。对于 27 以上的数字,用两位或更长位的字符串来对应,例如 AA 对应 27,AB 对 应 28,AZ 对应 52,LQ 对应 329。 请问 2019 对应的字符串是什么?
【题解】
#include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <string>
using std::endl;
using std::cout;
int main()
{
using std::string;
char num[27] = {0, 'A'};
for(int i = 2; i < 27; i++) num[i] = num[i-1] + 1;
string ans = "";
int year = 2019;
while(year) { int t = year % 26; ans = num[t] + ans; year /= 26; }
cout << ans << endl;
return 0;
}
3、数列
【题目】
给定数列 1, 1, 1, 3, 5, 9, 17, …,从第 4 项开始,每项都是前 3 项的和。求第 20190324 项的最后 4 位数字。
【题解】
#include <iostream>
using std::cout;
using std::endl;
const int mod = 10000;
int num[20190324] = {1, 1, 1};
int main()
{
for(int i = 3; i < 20190324; i++)
num[i] = (num[i-3] + num[i-2] + num[i-1]) % mod;
cout << num[20190323] << endl;
return 0;
}
4、数值分解
【题目】
把 2019 分解成 3 个各不相同的正整数之和,并且要求每个正整数都不包含数字 2 和 4,一共有多少种不同的分解方法?注意交换 3 个整数的顺序被视为同一种方法,例如 1000+1001+18 和 1001+1000+18 被视为同一种。
【题解】
#include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <string>
using std::endl;
using std::cout;
bool CheckNum(int num)
{
while(num)
{
if(num % 10 == 2 || num % 10 == 4)
return false;
num /= 10;
}
return true;
}
int main()
{
int ang = 0;
for(int i = 1; i < 2019; i++)
{
if(!CheckNum(i))
continue;
for(int j = i+1; j < 2019 - i; j++)
{
if(!CheckNum(j))
continue;
for(int k = j+1; k < 2019 - j; k++)
{
if(!CheckNum(k))
continue;
if(2019 == i+j+k)
ang++;
}
}
}
cout << ang << endl;
return 0;
}
5、迷宫求解
【题目】
下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可 以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫,从入口开始,可以按DRRURRDDDR 的顺序通过迷宫,一共 10 步。 其中 D、U、L、R 分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫(30 行 50 列), 请找出一种通过迷宫的方式, 其使用的步数最少,在步数最少的前提下,请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。
测试迷宫:
BFS(宽度优先搜索算法)
【题解】
#include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <string>
#include <stdio.h>
#include <queue>
using std::endl;
using std::cout;
using std::queue;
using std::string;
const int N = 30;
const int M = 50;
char map[N][M];
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; // D<L<R<U
char ch[4] = {'D', 'L', 'R', 'U'};
int vis[N][M] = {0}; // 记录路径
class Point
{
public:
int x;
int y;
string road;
Point(int inX, int inY)
{
this->x = inX;
this->y = inY;
}
};
void BFS()
{
queue<Point> quQ;
Point pBegin(0, 0);
pBegin.road = "";
quQ.push(pBegin);
vis[0][0] = 1;
while(!quQ.empty())
{
Point t = quQ.front();
quQ.pop();
if(t.x == N-1 && t.y == M-1)
{
cout << t.road << endl;
break;
}
for(int i = 0; i < 4; i++)
{
int dx = t.x + dir[i][0];
int dy = t.y + dir[i][1];
if(dx >= 0 && dx < N && dy >= 0 && dy < M)
{
if(map[dx][dy] == '0' && !vis[dx][dy]) // 能走但没走
{
Point tt(dx, dy);
tt.road = t.road + ch[i]; // 记录路径
quQ.push(tt);
vis[dx][dy] = 1;
}
}
}
}
cout << pBegin.road << endl;
}
int main()
{
cout << "input map:" << endl;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
scanf("%s", &map[i][j]);
getchar();
}
BFS();
return 0;
}
6、数字求和
【题目】
小明对数位中含有 2、0、1、9 的数字很感兴趣(不包括前导 0),在 1 到 40 中 这样的数包括 1、2、9、10 至 32、39 和 40,共 28 个,他们的和是 574。 请问,在 1 到 n 中,所有这样的数的和是多少?
【题解】
#include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <string>
#include <queue>
#include <string.h>
using std::endl;
using std::cout;
bool check(int n)
{
char* str = new char[20];
itoa(n, str, 10);
// 方法一:
// std::string s = str;
// if(s.find("2") == std::string::npos && s.find("0") == std::string::npos \
// && s.find("1") == std::string::npos && s.find("9") == std::string::npos)
// return false;
// else
// return true;
// 方法二:
if(strstr(str, "2") == NULL && strstr(str, "0") == NULL \
&& strstr(str, "1") == NULL && strstr(str, "9") == NULL)
return false;
else return true;
// 方法三:
// for(int i = 0; str[i]; i++) { if(str[i] == '2' || str[i] == '0' || str[i] == '1' || str[i] == '9') return true; }
// return false;
}
int main()
{
using std::cin;
int n, ans = 0;
cin >> n;
for(int i = 1; i <= n; i++) { if(check(i)) ans += i; }
cout << ans << endl;
return 0;
}
7、完全二叉树
【题目】
给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是 A1, A2, ··· AN,如下图所示:
A1
/ \
A2 A3
/ \ / \
A4 A5 A6 A7
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是1。
【解题思路】
完全二叉树的深度是log2(n+1)向上取整,计算每个深度上的权值和进行判断即可。
【题解】
#include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <string>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <cmath>
using std::endl;
using std::cout;
#define INF 0x3f3f3f3f // 无穷大
const int N = 100005;
int num[N] = {0};
int main()
{
using std::cin;
int n, ans = 1, k = 0, max = -INF;
cin >> n;
for(int i = 0; i < n; i++) cin >> num[i];
for(int i = 1; i <= ceil(log(n+1)/log(2)); i++) // ceil向上取整
{
int sum = 0;
for(int j = 0; j < pow(2, i-1); j++) sum += num[k++];
if(sum > max) { max = sum; ans = i; }
}
cout << ans << endl;
return 0;
}
8、等差数列
【题目】
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列,只记得其中 N 个整数。现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有几项?
【解题思路】
先给数列排序,然后逐个求差,将所有的差求个最大公约数得出最大的公差,然后运用公式 n=(an-a1)/d+1,就可以求出项数了。
【题解】
#include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <string>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <cmath>
using std::endl;
using std::cout;
int gcd(int a,int b) { if(b == 0) return a; return gcd(b, a % b); }
int main()
{
using std::vector;
using std::list;
using std::cin;
int N, num;
vector<int> vecNum;
list<int> listNum;
cin >> N;
int d = N; // 公差初始化
for(int i = 0; i < N; i++) { cin >> num; listNum.push_back(num); }
listNum.sort();
vecNum.assign(listNum.begin(), listNum.end());
int x = vecNum.at(1) - vecNum.at(0);
int z; // 中间值
for(int i = 2; i < (int)vecNum.size(); i++)
{
int y = vecNum.at(i) - vecNum.at(i-1);
if(x >= y) z = gcd(x, y);
else z = gcd(y, x);
if(z < d) d = z;
}
cout << (vecNum.back() - vecNum.front()) / d + 1 << endl;
return 0;
}
9、计算式组合
【题目】
给定 N 个加号、M 个减号以及 N + M + 1 个整数 A1,A2,··· ,AN+M+1,小明想知道在所有由这 N 个加号、M 个减号以及 N + M +1 个整数凑出的合法的后缀表达式中,结果最大的是哪一个?请你输出这个最大的结果。 例如:使用1 2 3 + -,则 “2 + 3 - 1” 这个后缀表达式结果是 4,是最大的。
输入格式:
第一行包含两个整数 N 和 M。 第二行包含 N + M + 1 个整数 A1,A2,···,AN+M+1。
输出格式:
输出一个整数,代表答案。
【解题思路】
按照负号的个数和负数的个数来分类讨论:1、负号个数为0;2、负号个数等于负数个数;3、负号个数小于负数个数;4、负号个数大于负数个数。总结:第一种直接求和,第二种第三种即为求绝对值和,第四种先求和再减去多余负号个数的较小正数。
【题解】
#include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <string>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <cmath>
using std::endl;
using std::cout;
int main()
{
using std::cin;
using std::vector;
using std::list;
int n, m, num; // n表示减号数量,m表示加号数量
vector<long long> vec;
list<long long> lst;
cin >> n >> m;
int x = 0, sum = 0; // x表示负数个数
for(int i = 0; i < n + m + 1; i++)
{
cin >> num;
if(num < 0) x++;
vec.push_back(num);
}
if(n == 0) sum = accumulate(vec.begin(), vec.end(), 0);
if(n == x || n < x)
{ for(int i = 0; i < (int)vec.size(); i++) sum += bs(vec.at(i)); }
if(n > x)
{
for(auto vec_iterator = vec.begin(); vec_iterator < vec.end(); vec_iterator++)
if(*vec_iterator <= 0) vec.erase(vec_iterator);
lst.assign(vec.begin(), vec.end());
lst.sort();
sum = accumulate(lst.begin(), lst.end(), 0);
for(int i = 0; i < n - x; i++) { sum -= lst.front()*2; lst.pop_front(); }
}
cout << sum << endl;
return 0;
}
说明:由于是练手代码,所有题解源码未专门做优化处理,仅供参考,谢谢阅读!!!
感谢:3 ~ 9届蓝桥杯比赛原题点击传送