2019第十届蓝桥杯C\C++B组省赛赛后总结

总结

不愧是暴力杯，今年题目基本全是暴力模拟，没有太难的算法题，不过由于蓝桥杯的赛制没有反馈机制，也就是你不能马上知道自己的答案对错，导致会因为粗心丢分。拖到现在才写博客就是因为粗心丢了好多分。。。

因为我是开一个cpp文件，作完一道题就会把代码删完然后再重新在这个文件里写，但是这样到了最后想要检查几乎是不可能的，因为之前代码都被我删了。。不过我也没有想到检查，我做完前九道差不多用了两个半小时，后面就一直看最后一题题意，丝毫不知道瞄一眼前面提交的答案。我好SA

建议可以在比赛还没开始时建十个cpp文件，这样什么时候回头看自己的代码都没问题。另外做题要慢慢看题意，有时间要检查。

2019.3.28 省二

PDF:链接:链接: https://pan.baidu.com/s/1b7ceNpa9nyN0r6Xy3VvuLg 提取码: 33i2

题解

一、组队

题目没什么说的，要找到5个队员让评分和最大，注意有可能选出重复的人
比赛时我连程序都没写，直接找每列最大的数字相加得492，最后GG，要是后面检查一下就好了

答案：490

二、年号子串

就是十进制转26进制，

#include <bits/stdc++.h>using namespace std;
#define db(x) cout << (x) << endltypedef long long ll;
const int N = 1000 + 10;
const int INF = 0x3f3f3f3f;int main()
{int num = 2019;while(num){cout << char('A'+num%26-1) << endl;num /= 26;}return 0;
}

程序输出结果是Q Y B，要倒着输出答案，
答案：BYQ

三、数列求值

直接数组模拟，因为只需要后面4位，模10000就行

#include <bits/stdc++.h>using namespace std;
#define db(x) cout << (x) << endltypedef long long ll;
const int N = 20190324 + 10;
const int INF = 0x3f3f3f3f;int a[N];
int main()
{a[1] = 1;a[2] = 1;a[3] = 1;for (int i = 4; i <= 20190324; i++){a[i] = a[i - 1] + a[i - 2] + a[i - 3];a[i] %= 10000;}cout << a[20190324] << endl;return 0;
}

答案：4659

四、数的分解

因为只有三个数，暴力枚举即可，
比赛时没看到三个数不相同，心酸，GG。

#include <bits/stdc++.h>
using namespace std;
#define db(x) cout << (x) << endltypedef long long ll;
const int N = 20190324 + 10;
const int INF = 0x3f3f3f3f;bool judge(int n){while(n>0){int t = n%10;n /= 10;if(t == 2 || t == 4)return false;}return true;
}
int main()
{int n, ans = 0;n = 2019;for(int i = 1; i <= n; i++){for(int j = i+1; j <= n && (n-i-j)>j; j++){if(judge(i) && judge(j) && judge(n-i-j))ans++;}}cout << ans << endl;return 0;
}

答案：40785

五、迷宫

01010101001011001001010110010110100100001000101010 
00001000100000101010010000100000001001100110100101 
01111011010010001000001101001011100011000000010000 
01000000001010100011010000101000001010101011001011 
00011111000000101000010010100010100000101100000000 
11001000110101000010101100011010011010101011110111 
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010 
00111000001010100001100010000001000101001100001001 
11000110100001110010001001010101010101010001101000 
00010000100100000101001010101110100010101010000101 
11100100101001001000010000010101010100100100010100 
00000010000000101011001111010001100000101010100011 
10101010011100001000011000010110011110110100001000 
10101010100001101010100101000010100000111011101001 
10000000101100010000101100101101001011100000000100 
10101001000000010100100001000100000100011110101001 
00101001010101101001010100011010101101110000110101 
11001010000100001100000010100101000001000111000010 
00001000110000110101101000000100101001001000011101 
10100101000101000000001110110010110101101010100001 
00101000010000110101010000100010001001000100010101 
10100001000110010001000010101001010101011111010010 
00000100101000000110010100101001000001000000000010 
11010000001001110111001001000011101001011011101000 
00000110100010001000100000001000011101000000110011 
10101000101000100010001111100010101001010000001000 
10000010100101001010110000000100101010001011101000 
00111100001000010000000110111000000001000000001011 
10000001100111010111010001000110111010101101111000

BFS模板题，用了一个string输出路径，注意走的方向要按字典序，说起来比赛的时候还卡了20分钟bug，下面写的时候2分钟撸完了。。。

#include <bits/stdc++.h>
using namespace std;
#define db(x) cout << (x) << endltypedef long long ll;
const int N = 50 + 10;
const int INF = 0x3f3f3f3f;char a[N][N];
int vis[N][N];
int dir[4][2] = {{1,0},{0,-1},{0,1},{-1,0}};
string op[4] = {"D","L","R","U"};
struct node{int x;int y;string str;node(int x, int y, string str):x(x),y(y),str(str){}
};
void bfs()
{queue<node> q;q.push(node(0, 0, ""));while(!q.empty()){node cnt = q.front();q.pop();if(cnt.x == 29 && cnt.y == 49){cout << cnt.str << endl;cout << cnt.str.length() << endl;return;}for (int i = 0; i < 4; i++){int xx = cnt.x + dir[i][0];int yy = cnt.y + dir[i][1];if(!vis[xx][yy] && a[xx][yy] != '1' && xx >= 0 && xx < 30 && yy >= 0 && yy < 50){vis[xx][yy] = 1;q.push(node(xx, yy, cnt.str + op[i]));}}}
}
int main()
{for (int i = 0; i < 30; i++){scanf("%s", a[i]);}vis[0][0] = 1;bfs();return 0;
}

答案：DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

六、特别数的和

还是暴力枚举。。。

#include <bits/stdc++.h>
using namespace std;
#define db(x) cout << (x) << endltypedef long long ll;
// const int N = 50 + 10;
const int INF = 0x3f3f3f3f;int N;
bool f(int x) {for (; x > 0; x /= 10) {int t = x % 10;if (t % 10 == 2 || t % 10 == 0 || t % 10 == 1 || t % 10 == 9)return true;}return false;
}
int main() {cin >> N;int ans = 0;for (int i = 1; i <= N; ++i)if (f(i)) ans += i;cout << ans << endl;return 0;
}

七、完全二叉树的值

看题目还有二叉树，其实根本不用建树，直接模拟每一层即可，注意完全二叉树并不是满二叉树，如下图

有可能最后一行不是满的
比赛时候没有注意元素为负数，GG

#include <bits/stdc++.h>
using namespace std;
#define db(x) cout << (x) << endltypedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;int num;
ll a[N];
int cnt = 0;int main() {scanf("%d", &num);int m = 1;int mm = 1;int n;while(mm <= num){int t = m;ll ans = 0;while(t--){scanf("%d", &n);ans += n;}a[cnt++] = ans;m *= 2;mm += m;}if(mm > num){int t = num - (mm-m);ll ans = 0;while(t--){scanf("%d", &n);ans += n;}a[cnt++] = ans;}int ans = 1;ll an = a[0];for (int i = 1; i < cnt; i++){if(a[i] > an){ans = i + 1;an = a[i];}}cout << ans << endl;return 0;
}

八、等差数列

存数组里排序，取两两之间差值分别求gcd，最后就是公差，注意特判0的情况
比赛没有特判0，GG

#include <bits/stdc++.h>
using namespace std;
#define db(x) cout << (x) << endltypedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;int n;
int a[N];
int main()
{cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];sort(a+1, a+1+n);int d = a[2]-a[1];if(d==0)cout << n << endl;else{for(int i = 3; i <= n; i++)d = __gcd(d, a[i]-a[i-1]);cout << (a[n]-a[1])/d+1 << endl;;}return 0;
}

九、后缀表达式

十、 灵能传输

前九道两个半小时做完，最后一个半小时一直在看这题题意样例，对，不是想怎么做，实在看样例，实在看不懂要输出什么，神他喵的阅读理解杯，有这时间前面粗心的也能看几道了。。

最后按照自己想的规则过了两组样例就提交了，就是输出不稳定度最小的序列的最大值。

正解还不知道