蓝桥杯矩阵求和_2019 第十届蓝桥杯省赛B组题解
B组试题难度(对专业算法竞赛选手来说)相比于A组来说是可以秒杀级别，几乎不需要思考时间。但是B组的确是为一般院校选手准备的，虽然难度低，但是对于没有经过专业算法竞赛的选手来说仍然是一个挑战。不仅考验基本的编程基本功，也考察数学思维，因此更多的是需要细心。
按照某些博主的做法，“模拟”、“简单贪心”、“随便讨论一下”这种风格的题解，对于真的需要了解算法思想的同学来说，帮助较小。我尝试本文使用尽可能简单详细的语言介绍算法题做法。
至于C/C++还是Java我觉得不重要，因为题目除了顺序有点不同，内容是一样的。而且核心在于算法。
2019年A组题解：kkksc03：2019 第十届蓝桥杯省赛A组题解?zhuanlan.zhihu.com
文章图片
文章图片
答案：490
你可以写程序爆搜，因为每一人都有两三个成绩，除了#17#18这两个狠人。由于这个数据比较简单，也可以目测。首先先把全场最高的2个能力 #20(2号)#17(3号)拉出来，然后依次找到剩下的位置最高的。如果遇到矛盾就微调一下。
虽然编程用贪心算法是错的，但是这个题数据的确简单，也很好调整，所以不写程序也可以找到答案(方法不唯一)。
文章图片
文章图片
答案：BYQ
解析：
依然没有写程序的必要。但是这不是单纯的进制转换。因为如果A是零，0和00是相同的，但是A和AA不一样。所以要去除掉一个字母或者两个字母。
1 个字母有 26 个；2 个字母 626 个；所以就是 3 个字母。
ZZ 对应 26+676=702。所以要求三个字母中的第 2019-652=1317是啥。
将其转换成 26 进制，1317=1×262+24×26+17
那么，A代表0，B代表1……ABCDEFGHIJKLMNOPQRSTUVWXYZ
当然，电脑中大概率是有Excel的，那么你可以借助这样的表格(也就是复制黏贴的事情了)
文章图片
文章图片
答案：4659
类似于斐波那契数列。由于数据范围才是
文章图片
，完全可以暴力一重 O(n) 的复杂度循环解决，可以开数组记录 f[1]，f[2]...f[20190324]，注意每次加后要 mod 10000。也可以使用循环变量只记录计算到的前面三项节约内存空间。
其实对于这种题目，即使数据范围到 int (
文章图片
)，也是可以这么做，因为你可以挂机让电脑运算，跑个几分钟还是可以跑出来的。
但是，如果数据范围再大一些，就要用矩阵快速幂加速递推式了，不过也不算难。
本题在同年 A 组也出现过。
代码：
#include #include using namespace std;
int main() {
int a, b, c, d;
a = b = 1;
c = 3;
for(int i = 4;
i < 20190324;
i++) {
d = (a + b + c) % 10000;
a = b;
b = c;
c = d;
}
cout << d << endl;
return 0;
}
文章图片
答案：40785
虽然这个问题解法非常显然，就是直接几重循环枚举判断。但是希望大家在写这种暴力枚举的题目尽可能考虑如何尽可能减少枚举次数。可以的优化如下：枚举假设获得 3 个数 i,j,k ，保证 i
i 从 1 开始枚举，到 673 结束，因为 i 是最小的，所以必须小于 2019 的 1/3.
j 从 i+1 开始枚举，到 (2019-i)/2 结束。这是因为这样的话可以保证 i
k 不用枚举，直接就是 2019-i-j 计算得到。
其实每次枚举出 i 和 j 时，可以先判断这个数是否符合数字的要求。如果不符合，就不用继续枚举下一个数字，而是枚举这个数字的下一个。当然这个程序里面没有加上这个优化，因为写起来有点麻烦，这个程序已经效率够高了。
代码：
#include #include using namespace std;
int ans = 0;
int is_24(int x) {
while (x) {
int t = x % 10;
if (t == 2 || t == 4)
return 1;
x /= 10;
}
return 0;
}
int main() {
for (int i = 1;
i <= 673;
i++)
for (int j = i + 1;
j <= (2019 - i) / 2;
j++) {
int k = 2019 - i - j;
if (i < j && j < k && !is_24(i) && !is_24(j) && !is_24(k)) {
//cout << i << ' ' << j << ' ' << k << endl;
ans++;
}
}
cout << ans << endl;
return 0;
}
文章图片
答案：DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
求最短迷宫问题是广度优先搜索的入门题，所以直接进行广度优先搜索就是了。使用一个队列，将入口位置放入队首。
当队伍非空，或者找到答案时，循环截止。每次从队首出队，分别从 下、上、左、右 进行扩展，注意要使用 vis 数组记录是否已经访问过了，还要记录更新结点遇到的方向。
本题在同年 A 组也出现过。
代码：
#include #include #include using namespace std;
const int n = 30, m = 50;
int delta[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
int way[n + 5][m + 5], map[n + 5][m + 5], vis[n + 5][m + 5];
char cc[5] = "DLRU";
char ans[n * m + 5];
struct node {
int x, y;
};
int main() {
freopen("maze.txt", "r", stdin);
for(int i = 0;
i < n;
i++)
for(int j = 0;
j < m;
j++) {
char a = ' ';
while(a != '1' && a != '0')cin >> a;
map[i][j] = a == '1' ? 1 : 0;
}
【蓝桥杯矩阵求和_2019 第十届蓝桥杯省赛B组题解】queue q;
node tmp = {0, 0};
q.push(tmp);
vis[0][0] = 1;
while(!q.empty()) {
node now = q.front();
q.pop();
for(int k = 0;
k < 4;
k++) {
int x = now.x + delta[k][0], y = now.y + delta[k][1];
if(x < 0 || y < 0 || x >= n || y >= m
|| vis[x][y] || map[x][y])
continue;
vis[x][y] = 1, way[x][y] = k;
node tmp = {x, y};
q.push(tmp);
}
}
int x = n - 1, y = m - 1, num = 0;
while(x != 0 || y != 0) {
int k = way[x][y];
ans[num++] = cc[k];
x -= delta[k][0], y -= delta[k][1];
}
num--;
do {
cout << ans[num];
} while(num--);
return 0;
}
文章图片
送分题。两重循环，大循环从 1 到 2019，小循环一依次剥离每一位(一直 % 10 后整除 10)，进行判断，然后求和。
本题在 A 组是以提交答案的形式的，但是 A 组的那题要求计算平方和，因为有使用 int 类型导致运算溢出的风险而使用 long long。本题就算从 1 加到 10000 也不会超过 int 的最大值，所以可以用 int。但是以后遇到这种题目的时候要估计一下极端情况，看看会不会爆 int 而要去使用 long long，避免无谓失分。
#include #include using namespace std;
typedef long long ll;
ll ans = 0, n;
int is_2019(int x) {
while (x) {
int t = x % 10;
if (t == 2 || t == 0 || t == 1 || t == 9)
return 1;
x /= 10;
}
return 0;
}
int main() {
cin >> n;
for (int i = 1;
i <= n;
i++)
if (is_2019(i)) ans += i;
cout << ans <
return 0;
}
文章图片
解析：
首先需要了解什么是完全二叉树。
文章图片
二叉树定义，节选自《深基》
因此，存储一个完全二叉树，可以使用一维数组存下所有结点。从上到下，从左到右，编号依次增加。可以发现，第一层有 1 个结点，第二层有 2 个，第三层有 4 个，第四层有 8 个……第 i 层有
文章图片
个结点。还可以发现，结点编号为 i 的话，它的左右子节点的编号分别是 2×i 和 2×i+1，不过这个和本题无关。
文章图片
由于我们知道每一层的节点个数，可以直接输入数据后按层统计，甚至都可以不用数组把这些数字存下来。只要记录好读入的数字个数，在合适的时间退出循环就行。注意 << 符号是左移，1<
文章图片
。如果读到的数字到了 n，那么就可以跳出循环，使用变量 flag 进行标记和判断。
本题有两个需要注意的地方数据可能有小于 0 的，导致每层总和可能小于 0。
最多的一层可能有 100000-2^16 大约是 35000 个结点，所以要用 long long 防止总合爆 int。
本题在 A 组也有同样的题目。
代码：
#include
#include
using namespace std;
int main() {
long long n, maxnum = -3500000000ll, maxlayer, cnt = 0, flag = 0;
cin >> n;
for(int layer = 0;
;
layer++) { // 枚举每一层，习惯上从 0 开始
long long sum = 0, a;
//cout << "<
for(int i = 0;
i < (1 << layer);
i++) { // 每一层的结点个数
cin >> a;
sum += a;
if(++cnt >= n) {
flag = 1;
break;
}
}
//cout << sum << endl;
if(sum > maxnum)
maxnum = sum, maxlayer = layer + 1;
if(flag) break;
}
cout << maxlayer;
return 0;
}
文章图片
解析：
假设这个等差数列是上升的，那么就是将输入的数字从小到大排序，然后往里面插入一些数字，使其变成一个等差数列。这样的话，假设公差为 d，数字的个数就是 (max-min)/d。
如何求 d 呢？可以知道，排序后的数字，每两个数字之间的间隔都是 d 的倍数，所以只需要把所有两个数字的差做一遍求最大公约数即可。
有个我没有想到的坑点：如果所有的数相同，它也是等差数列。这种情况下就特殊判断，直接输出 N。
代码：
#include #include using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int a[100005], n, ans;
int main() {
cin >> n;
for(int i = 0;
i < n;
i++)
cin >> a[i];
sort(a, a + n);
ans = a[1] - a[0];
for(int i = 2;
i < n;
i++)
ans = gcd(ans, a[i] - a[i - 1]);
if(a[n - 1] - a[0] == 0)
cout << n;
else
cout << (a[n - 1] - a[0]) / ans + 1;
return 0;
}
文章图片
解析：
所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右进行(不用考虑运算符的优先级)。
换句话说，像 2 3 + 1 - 这个式子，先计算前面三个元素 2 3 +，得到 5 1 -，然后计算剩余的三个元素，最后答案就是 4，原式就是 (2+3)-1。使用后缀表达式的话，就可以不用考虑括号了，直接从左到右进行计算，对于计算机来说更好处理。
因为符号和数字的顺序可以随意安排，那么可以考虑这样几种情况：如果都是加号：那么没有其他的办法，只能把所有的数字加起来了。
如果一个减号：可以转化为 ...+... - (....+....+...) 的形式，也就是分为两部分，中间使用一个减号。所以只要出现一个减号，就可以视为出现一个或多个减号等同的效果。
如果出现多个减号：也可以转化为 ...+... - (....+....-...) 的形式，也就是说你希望它是减号时，这个符号可以放进括号外；希望它是加号时，你可以把他放在括号里面。这样的话，也可以视为一个或者多个减号。实际上这种情况和上一种情况时一样的。
因此一言以蔽之：只要M>0，那么减号的数量实际上可以是1到N+M的任何一个数字。
基于以上的引理，可以进行如下讨论：如果全是加号，那么答案只能是全部加起来。
如果存在减号：如果全是正数，那么至少有一个得被减。所以把那个最小的拿去减。
如果有正有负，那么所有正数都配正号，所有负数都配负号，因此将全部的绝对值加起来。
或者全是负数，那么除了一个还是得维持负数以外，别的都可以翻正。和 2.1 其实是一样的情况。
#include #include using namespace std;
int a[200005], n, m;
int main() {
cin >> n >> m;
long long ans = 0;
int minnum = 1000000000;
int flagp = 1, flagm = 1;
//全是正数或全是负数 for(int i = 0;
i < n + m + 1;
i++) {
cin >> a[i];
if(!m)//没有减号 ans += a[i];
else {
if(a[i] < 0)flagp = 0;
if(a[i] > 0)flagm = 0;
if(abs(a[i]) < minnum)minnum = abs(a[i]);
ans += abs(a[i]);
}
}
if(m && (flagp || flagm)) // 有减号，且全是正数或负数 ans = ans - minnum - minnum;
cout << ans;
return 0;
}
未完待续
欢迎前往洛谷 https://www.luogu.com.cn/ 练习各类算法，其训练功能提供了完整的算法体系练习题，所有题目均提供详细解答。
收藏数是点赞数量好几倍……可否点个赞再走？
还有别适用于算法竞赛的文章，不如一起看看刘汝佳的《算法竞赛入门经典》该怎么学？?www.zhihu.com
文章图片
kkksc03：我的程序评测不通过怎么办？?zhuanlan.zhihu.com
文章图片
如何理解算法时间复杂度的表示法，例如 O(n2)、O(n)、O(1)、O(nlogn) 等？?www.zhihu.com
文章图片
推荐阅读
- 算法|第十届蓝桥杯省赛B组题解记录
- 算法与数据结构|第十届蓝桥杯大赛软件类省赛Java研究生组-题解
- 蓝桥杯|2019第十届蓝桥杯B组决赛题解第二题
- 蓝桥杯|第十届蓝桥杯省赛编程题题解（C++A组）
- 第十届蓝桥杯省赛C++大学B组
- 蓝桥杯|第八届蓝桥杯省赛代码+题解
- 蓝桥杯|第九届蓝桥杯省赛代码+题解
- 算法|蓝桥 小明的游戏1 博弈论 nim
- java|2022蓝桥杯备赛 python 真题大联赛 第1期
- opencv-python cv2.getRotationMatrix2D(获得仿射变化矩阵) 2. cv2.warpAffine(进行仿射变化)