第十届蓝桥杯大赛软件类省赛
发布时间
阅读量：
阅读量
文章目录
第十届全国软件能力与创新大赛 软件类省赛
- C++ 大学 B 组
-
- 试题 A: 组队问题 -- 已解决/完成
- 试题 B: 年份数字串
- 试题 C: 数列求值问题已解决
- 试题 D: 数的分解问题已解决
- 试题 E: 迷宫问题已解决
- 试题 F: 特别数的总和已解决
- 试题 G: 完全二叉树的权值计算已解决
- 试题 H: 等差数列相关问题已解决
- 试题 I: 后缀表达式运算已解决
- 试题 J: 灵能传输现象相关问题已解决
计算机学院 A 组 Java/C++课程
* 试题 A: 平方与求和问题
* 试题 B: 数列求值问题已完成
* 试题 C: 最大降水量计算
* 试题 D: 迷宫问题已完成
* 试题 E: RSA解密重点掌握
* 试题 F: 完全二叉树权值计算已完成
* 试题 G: 外卖店优先级计算已完成
* 试题 H: 数组修改重点掌握
* 试题 I: 糖果分配重点掌握
* 试题 J: 组合数问题重点掌握
第十届蓝桥杯大赛软件类省赛
这些题目官方发布的平台还没有给出解答的，在学习过程中我主要参考了B站UP主大雪菜的解法（绝大多数题目都是自己先做了一遍），此外还查阅了一些网络上的解答资料。但发现目前在网络上的一些解法存在不足之处，并希望通过本篇文章为广大学习者提供一些参考建议。
官网提供详细的具体题目下载；其中Java和C++大学A组的题目相同（两道题顺序可能不同），集中呈现。
我的代码可能会有无法规避的漏洞（填空类题目常有这类问题 o_o …），如有任何疑问或错误，请随时评论指正。
Java 大学 B 组
试题 A: 组队
问题描述
编号 1 号位 2 号位 3 号位 4 号位 5 号位
1 97 90 0 0 0
2 92 85 96 0 0
3 0 0 0 0 93
4 0 0 0 80 86
5 89 83 97 0 0
6 82 86 0 0 0
7 0 0 0 87 90
8 0 97 96 0 0
9 0 0 89 0 0
10 95 99 0 0 0
11 0 0 96 97 0
12 0 0 0 93 98
13 94 91 0 0 0
14 0 83 87 0 0
15 0 0 98 97 98
16 0 0 0 93 86
17 98 83 99 98 81
18 93 87 92 96 98
19 0 0 0 89 92
20 0 99 96 95 81
（如果你把以上文字复制到文本文件中，请务必检查复制的内容是否与文
档中的一致。在试题目录下有一个文件 team.txt，内容与上面表格中的相同，
请注意第一列是编号）
我想到的一种直接且粗暴的方法是暴力枚举法（怪不得叫暴力杯），通过对每一种可能性都进行了穷举分析，并最终计算得出了490的结果。不过通过观察和分析也可以得出同样的结论。
#include<vector>
#include<iostream>
using namespace std;
vector<int> peo[21];
int main(){
int a,x;
for(int i=0;i<20;i++){
cin >> a;
for(int j=0;j<5;j++){
cin >> x;
peo[a-1].push_back(x);
}
}
int res = 0;
for(int i=0;i<20;i++)
for(int j=0;j<20;j++){
if(i == j) continue;
for(int jj=0;jj<20;jj++){
if(i == jj || j == jj) continue;
for(int jjj=0;jjj<20;jjj++){
if(jjj == i || jjj == jj || jjj == i) continue;
for(int jjjj=0;jjjj<20;jjjj++){
if(jjjj == i || jjjj == j || jjjj == jj || jjjj == jjj) continue;
res = max(res,peo[i][0]+peo[j][1]+peo[jj][2]
+peo[jjj][3]+peo[jjjj][4]);
}
}
}
}
cout << res;
return 0;
}
cpp
试题 B: 不同子串
问题描述
问题描述
思路
枚举起点和终点，答案是100。
#include<vector>
#include<iostream>
#include<unordered_set>
using namespace std;
unordered_set<string> st;
int main(){
string str = "0100110001010001";
for(int i=0;i<str.size();i++)
for(int j=i+1;j<=str.size();j++)
st.insert(str.substr(i,j-i));
cout << st.size();
return 0;
}
cpp
试题 C: 数列求值
【问题描述】
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求
第 20190324 项的最后 4 位数字。
思路
直接算就可以了，答案是4659。
#include<iostream>
using namespace std;
int dp[20190334];
int main(){
dp[0] = dp[1] = dp[2] = 1;
for(int i=3;i<20190334;i++){
dp[i] = ((dp[i-1]+dp[i-2])%10000+dp[i-3])%10000;
}
cout << dp[20190324 - 1] << endl;
return 0;
}
cpp
试题 D: 数的分解
问题描述
改写说明
思路
直接算就可以了，答案是40785。
#include<iostream>
using namespace std;
inline bool is_ok(int x){
while(x){
if(x % 10 == 2 || x % 10 == 4) return false;
x /= 10;
}
return true;
}
int main(){
int res = 0;
for(int i=1;i<2019;i++){
if(!is_ok(i)) continue;
for(int j=1;j<2019;j++){
if(!is_ok(j)) continue;
if(2019-i-j <= 0 || !is_ok(2019-i-j)) continue;
if(i < j && j < 2019-i-j) res++;
}
}
cout << res << endl;
return 0;
}
cpp
试题 E: 迷宫 – important
问题描述
思路
原本认为BFS无法记录最短路径的具体路径。于是实现了DFS算法并成功运行了4×6网格迷宫（未考虑字典序）。然而，在尝试解决30×50网格迷宫时遇到了困难。由于其较高的时间复杂度导致无法正常运行。
#include<iostream>
#include<queue>
using namespace std;
const int ROW = 30;
const int COL = 50;
int X[] = {0,0,-1,1};
int Y[] = {1,-1,0,0};
char C[] = {'R','L','U','D'};
char g[ROW][COL];
bool vis[ROW][COL];
inline bool is_ok(int x,int y){
if(x < 0 || x >= ROW || y < 0 || y >= COL) return false;
if(vis[x][y] || g[x][y] == '1') return false;
return true;
}
string res = "";
void dfs(int x,int y,string temp){
if(res != "" && temp.size() > res.size()) return;
if(x == ROW-1 && y == COL-1){
if(res == "" || res.size() > temp.size())
res = temp;
return;
}
for(int i=0;i<4;i++){
int newx = x+X[i];
int newy = y+Y[i];
if(is_ok(newx,newy)){
vis[newx][newy] = true;
dfs(newx,newy,temp+C[i]);
vis[newx][newy] = false;
}
}
}
int main(){
for(int i=0;i<ROW;i++)
for(int j=0;j<COL;j++)
cin >> g[i][j];
dfs(0,0,"");
cout << res << endl;
return 0;
}
cpp
然而实际上BFS还是可以通过一定手段得到具体路径的。
输出为：
该编码方案通过一系列复杂的操作流程实现了数据的安全传输目标
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int ROW = 30;
const int COL = 50;
int X[] = {1,0,0,-1};
int Y[] = {0,-1,1,0};
char C[] = {'D','L','R','U'};
char g[ROW][COL];
bool vis[ROW][COL];
inline bool is_ok(int x,int y){
if(x < 0 || x >= ROW || y < 0 || y >= COL) return false;
if(vis[x][y] || g[x][y] == '1') return false;
return true;
}
struct node{
int x,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,""));
vis[0][0] = true;
while(q.size()){
int len = q.size();
while(len--){
auto item = q.front();
q.pop();
if(item.x == ROW-1 && item.y == COL-1){
cout << item.str << endl;
cout << item.str.size() << endl;
return;
}
for(int i=0;i<4;i++){
int newx = item.x+X[i];
int newy = item.y+Y[i];
if(is_ok(newx,newy)){
q.push(node(newx,newy,item.str+C[i]));
vis[newx][newy] = true;
}
}
}
}
}
int main(){
for(int i=0;i<ROW;i++)
for(int j=0;j<COL;j++)
cin >> g[i][j];
bfs();
return 0;
}
cpp
试题 F: 特别数的和
问题描述
输入格式
输出格式
样例输入
样例输出
由于蓝桥杯可能不支持C++11标准，在处理非填空题部分时我会选择使用不依赖C++11编程语言的方式完成代码编写
这道题目相对容易得分
#include<iostream>
using namespace std;
inline bool is_ok(int x){
while(x){
int d = x % 10;
if(d == 2 || d == 0 || d == 1 || d == 9) return true;
x /= 10;
}
return false;
}
int main(){
int x;
cin >> x;
int res = 0;
for(int i=1;i<=x;i++)
if(is_ok(i))
res+=i;
cout << res;
return 0;
}
cpp
试题 G: 外卖店优先级 – todo
问题描述
输入格式
输出格式
样例输入
样例输出
恶心的模拟题 (；′⌒`)
试题 H: 人物相关性分析
问题描述
输入格式
输入格式
按照题意写应该就可以了。记住读入一行字符串的写法getline(cin,str);。
#include<iostream>
#include<vector>
#include<string>
using namespace std;
const string a = "Alice";
const string b = "Bob";
struct word{
int b,e;
string w;
word(string w,int b,int e):w(w),b(b),e(e){}
};
vector<word> vec;
inline bool check(char c) {
return c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z';
}
int main(){
int n;
cin >> n;
getchar();
string str;
getline(cin,str);
for(int i=0;i<str.size();i++){
if(!check(str[i])) continue;
int j = i;
while(j<str.size() && check(str[j])) j++;
vec.push_back(word(str.substr(i,j-i),i,j));
i = j;
}
int res = 0;
word last("",-1,-1);
for(int i=0;i<vec.size();i++){
if(vec[i].w == a){
if(vec[i].b - last.e <= n && last.w == b) res++;
last = vec[i];
}
else if(vec[i].w == b){
if(vec[i].b - last.e <= n && last.w == a) res++;
last = vec[i];
}
}
cout << res << endl;
return 0;
}
cpp
试题 I: 后缀表达式 – todo
问题描述
输入格式
输出格式
样例输入
样例输出
原本以为只需对数据进行简单排序后再进行加减运算就可以了；然而，在实际操作中发现后缀表达式能够一次性处理多个数值，并不需要每次都按照负号和负数的数量进行具体分析。
试题 J: 灵能传输 – todo
题目背景
问题描述
输入格式
输出格式
样例输入
样例输出
好让人头晕的题目呀！！！
C++ 大学 B 组
试题 A: 组队 – completed
试题 B: 年号字串
问题描述
思路
直接采用26进制的方式会导致在字母Z处出现问题；然而，在解决这个填空题时是可以准确计算得出结果为BYQ的。参考了一些其他人的解决方案后发现：将每个英文字母视为一个基数为26的数字进行运算；需要注意的是这种运算并不完全是标准意义上的基数转换；具体来说，在某些情况下（即当数值能被26整除时）应特别处理以避免出现错误的结果；因此，在设计递归算法时应当特别注意这些边界条件并采取相应的措施来确保运算结果的准确性。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
void re(int x){
if(x == 0) return;
if(x%26 == 0){ // 这里
re((x-1)/26);
cout << "Z";
}else{
re(x/26);
char s = 'A'+x%26-1;
cout << s;
}
}
int main(){
for(int x=1;x<=2019;x++){
re(x);
cout << endl; // BYQ
}
return 0;
}
cpp
试题 C: 数列求值 – completed
试题 D: 数的分解 – completed
试题 E: 迷宫 – completed
试题 F: 特别数的和 – completed
试题 G: 完全二叉树的权值
问题描述
输入格式
输出格式
样例输入
样例输出
需要注意的是，在使用整型变量时可能会遇到溢出风险存在的情况。因此，在这种情况下必须使用long \ long类型变量来避免溢出问题。此外，在存在负数的情况下应将初始值设置为INT\_MIN而不是采用0作为初始值的做法。
#include<iostream>
using namespace std;
int a[100010];
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
long long res = 0,max_ = INT_MIN;
int depth = 0;
int i = 0;
while(i<n){
int num = 1<<depth;
long long temp = 0;
while(num-- && i<n) temp+=a[i++];
if(temp > max_){
max_ = temp;
res = depth;
}
depth++;
}
cout << res+1 << endl;
return 0;
}
cpp
试题H：等差数列
问题描述
思路
核心在于计算等差数列公差d值。其中公差d即为所有相邻两项之差的最大公约数。需要注意的地方包括：例如如何处理公差d等于零的情况；还有误区在于简单取最小的相邻项之差作为公差。这些细节对正确理解问题至关重要。
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int a[100010];
int gcd(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}
int main(){
// 若为1 3 6,那么q != 2 && q != 3, q == gcd(2,3)
int n;
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
sort(a,a+n);
set<int> d;
for(int i=0;i<n-1;i++) d.insert(a[i+1]-a[i]);
int gcdv = -1;
for(set<int>::iterator it=d.begin();it!=d.end();++it){
// cout << *it << endl;
if(gcdv == -1) gcdv = *it;
else gcdv = gcd(gcdv,*it);
}
if(gcdv == 0) cout << n << endl; // 这里容易没考虑
else cout << (a[n-1]-a[0])/gcdv+1 << endl;
return 0;
}
cpp
试题 I: 后缀表达式 – completed
试题 J: 灵能传输 – completed
Java/C++ 大学 A 组
试题 A: 平方和
问题描述
思路
送分题吧，注意使用long long，结果为：
2019
2658417853
#include<iostream>
using namespace std;
inline bool is_ok(int x){
while(x){
int d = x%10;
if(d == 2 || d == 0 || d == 1 || d == 9) return true;
x /= 10;
}
return false;
}
int main(){
int n; cin >> n;
long long res = 0;
for(int i=1;i<=n;i++){
if(is_ok(i)){
res += i*i;
}
}
cout << res << endl;
return 0;
}
cpp
试题 B: 数列求值 – completed
试题 C: 最大降雨量
问题描述
思路
直接暴力算不完呀！完全没有思路，看了看其他大佬的思路，orz
探讨一下这道题的思路，就是每周用的符列在一起就是一个7*7的矩阵
###=###
###=###
###=###
###&###
###=###
###=###
###=###
其中=表示每周的中位数，&表示最后的中位数，所以，&后面和下面的数字一定要比&大，所以
###=###
###=###
###=###
###& 35 36 37
###38 39 40 41
###42 43 44 45
###46 47 48 49
所以最后的数字是34.
试题 D: 迷宫 – completed
试题 E: RSA 解密 – important
问题描述
在了解扩展欧几里得算法的过程中
推导参考文章：`
扩展欧几里得算法可以在 O(logn)的时间复杂度内求出系数 x,y。
C++ 代码
int exgcd(int a, int b, int &x, int &y){
if (b == 0){
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}
cpp还需要会快速幂算法 ，这里就不介绍了。
// 快速计算 a^b%c
long long fast_pow(long long a,long long b,long long c){
long long res = 1%c, temp = a;
while(b){
if(b & 1) res = (res*temp)%c;
temp = (temp*temp)%c;
b >>= 1;
}
return res;
}
cpp
自己编写的C++代码中缺乏大数乘法的支持，在执行快速幂运算时容易导致数值溢出。因此，在计算函数fast_pow(C, e, n)时必须依赖Python实现的快速幂算法来处理。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
// ax + by == gcd(a,b)
long long exgcd(long long a,long long b,long long& x,long long& y){
if(b == 0){
x = 1;y = 0;
return a;
}
long long d = exgcd(b,a%b,y,x);
y -= (a/b)*x;
return d;
}
long long fast_pow(long long a,long long b,long long c){
long long res = 1%c, temp = a;
while(b){
if(b & 1) res = (res*temp)%c;
temp = (temp*temp)%c;
// cout << res << " " << temp << endl;
b >>= 1;
}
return res;
}
int main(){
long long n = 1001733993063167141, d = 212353;
long long C = 20190324;
// long long n = 55, d = 3;
// long long C = 19;
long long p,q;
for(long long i=3;i<n;i+=2) // 找质数
if(n%i == 0){
p = i;
q = n/i;
break;
}
cout << p << " " << q << endl; // 891234941 1123984201
// d*e + fn*k == 1 且 gcd(d,fn) == 1
long long fn = (p-1)*(q-1);
long long e,k;
exgcd(d,fn,e,k);
// e移动到正数 这里溢出了?
e = e%fn + fn;
e = e%fn;
cout << e << " " << k << " " << fn << endl; // 823816093931522017 37716 1001733991047948000
// cout << (d*e % fn == 1) << endl; // 在python上验证成立
// X = pow(C,e) mod n C++的取模快速幂还是要溢出 python直接**运算，算不完也得快速幂
long long X = fast_pow(C,e,n); // 这里要用python，也可以C++大整数实现乘法，但是太麻烦
cout << X << endl; // 因为快速幂溢出，结果为-774706639346732542
return 0;
}
cpp
python测试代码，输出为
579706994112328949
20190324
答案即为579706994112328949。
def fast_pow(C, e, n):
res = 1%n
temp = C
while(e > 0):
if(e & 1):
res = (res*temp)%n
temp = (temp*temp)%n
e >>= 1
return res
C = 20190324
e = 823816093931522017
n = 1001733993063167141
print(fast_pow(C,e,n))
d = 212353
print(fast_pow(C,e,n)**d%n)
python
尽管破译RSA密码令人感到兴奋和愉悦；然而，在现实情况下（例如寻找素数p和q的过程往往耗时耗力），当n非常大时（例如寻找素数p和q的过程往往耗时耗力）。
试题 F: 完全二叉树的权值 – completed
试题 G: 外卖店优先级 – completed
试题 H: 修改数组 – important
问题描述
输入格式
样例输入
问题描述
输入格式
输出格式
思路 最直观的想法自然是直接模拟。接着我自行构建了极端情况的数据集，并发现在这种特殊场景下程序运行时间达到了惊人的7秒（虽然如此，在大多数情况下仍能顺利运行 o_o …）。
#include<iostream>
#include<string>
#include<fstream>
using namespace std;
int a[2000010];
bool vis[2000010];
int main(){
// 坏情况 7.772 seconds
// ofstream outf("abc.txt");
// outf << 100000 << endl;
// for(int i=100000;i>=1;i--)
// if(i > 50000) outf << i << " ";
// else outf << 50000 << " ";
// outf.close();
//
// ifstream inf("abc.txt");
// int n;
// inf >> n;
// for(int i=0;i<n;i++){
// inf >> a[i];
// while(vis[a[i]]) a[i]++;
// vis[a[i]] = true;
// }
// inf.close();
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> a[i];
while(vis[a[i]]) a[i]++;
vis[a[i]] = true;
}
for(int i=0;i<n;i++){
string s = (i == n-1)?"":" ";
cout << a[i] << s;
}
return 0;
}
cpp
标准方法应是保存区间。可以使用C++中的set<pair<int, int>>来实现这一功能吗？但并查集的实现更为巧妙且高效。
#include<iostream>
#include<string>
using namespace std;
int a[100010];
int father[2000010];
int findFather(int a){
if(a != father[a]) father[a] = findFather(father[a]);
return father[a];
}
void Union(int a,int b){
int fathera = findFather(a);
int fatherb = findFather(b);
if(a != b) father[fathera] = fatherb;
}
int main(){
// 并查集 findFather保存区间右端点
for(int i=0;i<2000010;i++) father[i] = i;
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> a[i];
a[i] = findFather(a[i]);
Union(a[i],a[i]+1); // 让a[i]的father的father为a[i]+1;
}
for(int i=0;i<n;i++){
string s = (i == n-1)?"":" ";
cout << a[i] << s;
}
return 0;
}
cpp
试题 I: 糖果 – important
问题描述
输入格式
输出格式
样例输入
评测用例规模与约定
采用广度优先搜索算法来解决这个问题。具体来说，我们通过节点记录已选取的袋子及其对应的糖果信息。由于数据规模较小，在本题中没有遇到大的计算复杂度问题。对于这道题目而言，在算法设计上仍有一定的挑战性
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
int a[105][25];
struct node{
bool vis[105];
int now; // 当前选了那些糖果
node(){
memset(vis,0,sizeof vis);
now = 0;
}
};
int main(){
int n,m,k;
int fed;
cin >> n >> m >> k;
fed = (1<<m)-1;
for(int i=0;i<n;i++)
for(int j=0;j<k;j++)
cin >> a[i][j];
queue<node> q;
q.push({});
int res = 0;
while(q.size()){
int len = q.size();
while(len--){
node it = q.front();
q.pop();
if(it.now == fed){
// 测试查看选了哪些行
// for(int i=0;i<105;i++) if(it.vis[i]) cout << i << " ";
cout << res << endl;
return 0;
}
for(int i=0;i<n;i++){
node newIt = it;
if(newIt.vis[i]) continue;
newIt.vis[i] = true;
for(int j=0;j<k;j++)
newIt.now |= 1<<(a[i][j]-1);
q.push(newIt);
}
}
res++;
}
cout << -1 << endl;
return 0;
}
cpp
试题 J: 组合数问题 – important
问题描述
输入格式
输出格式
样例输入
样例输出
样例解释
评测用例编号 t n; m k
1; 2 ≤ 1 ≤ 2000 ≤ 100
3; 4 ≤ 10^5 ≤ 2000 ≤ 100
5; 6; 7 ≤ 100 ≤ 10^18 ≤ 100
8; 9; 10 ≤ 10^5 ≤ 10^18 ≤ 10^8思路
本来是准备放弃治疗 ○|￣|_，但是找到了该题的一个题解地址：
https://www.luogu.com.cn/problemnew/solution/P2822
大佬们太强了，我感觉我的数论还可以抢救一波！
为了更好地理解相关概念，请您首先了解一些定义。令m为一个大于1的正整数，在此情况下我们考虑其中两个整数a和b之间的关系。若m能被(a−b)整除，则我们称这两个整数在模m下同余，并表示为a≡b (mod m)。显然以下几点成立：
- 若a≡0(mod m)，则m|a;
- a≡b(mod m)等价于a与b分别用m去除，余数相同。
然后是组合数和杨辉三角的关系，具体查看上面的题解。
在洛谷平台上的测试可以获得95分的成绩；然而，在针对题目给定的数据规模的情况下，“这种解法仅适用于少量测试案例”。
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const int N = 2001;
long long C[N][N];
void init(int k){
// 想象杨辉三角
C[0][0] = 1;
C[1][0] = 1,C[1][1] = 1;
for(int i=2;i<N;i++) C[i][0] = 1;
// C j上i下
for(int i=2;i<N;i++)
for(int j=1;j<=i;j++)
C[i][j] = (C[i-1][j-1] + C[i-1][j])%k;
}
int main(){
int t,k;
scanf("%d%d",&t,&k);
init(k);
while(t--){
int n,m;
int res = 0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int min_ = min(i,m);
for(int j=0;j<=min_;j++)
if(C[i][j] == 0) res++;
}
cout << res << endl;
}
return 0;
}
cpp
该问题的最佳解决方法是Lucas定理。
全部评论 (0)
还没有任何评论哟~