2024年“蓝桥杯”软件设计大赛选拔赛参考答案与说明

xuelanghanbao

7338人浏览 · 2023-12-12 20:05:00

xuelanghanbao · 2023-12-12 20:05:00 发布

2024年“蓝桥杯”软件设计大赛选拔赛参考答案与说明

A：神秘的邀请函：数字构桥穿越数字门径

本题改编自 第十二届蓝桥杯省赛试题B

题目描述：

2023年即将过去，阿彬突然收到一个神秘的邀请函，其中包含了很多数字卡片，每张卡片上都镌刻着数字 0 到 9，仿佛是连接数字世界的钥匙。邀请函上述道：“利用这些卡片构建通向数字世界的桥梁，数字世界的大门将在你眼前展现。”

阿彬被此邀请挑起好奇心，决定运用这些卡片拼凑数字。他计划从 1 开始拼出正整数，每拼一个就保存起来，卡片就不能用来拼其它数了。阿彬渴望知晓，在这手中拥有 0 至 9 各有多达 $N$ 张的卡片，共计 $10 \times N$ 张的情况下，他能够拼接出多少个连续的正整数。

例如，当阿彬有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。

现在阿彬手里有 0 到 9 的卡片各 $N$ 张，共 $10 * N$ 张，请问阿彬可以从 1 拼到多少？

这道题目的一个思路是：从 1 开始遍历正整数，统计其中出现的 0 到 9 的数量，当任意数字的数量超过 $N$ 时，上一个数就是可以拼到的最大的数。

参考代码：

#include<iostream>
#include<vector>

using namespace std;

vector<int> count;

void init_count(){
	int n;
	cin>>n;
	count = vector<int>(10,n);
	return;
}

bool update(int n){
	while(n){
		int i = n%10;
		n /= 10;
		count[i]--;
		if(count[i]<0){
			return false;
		}
	}
	return true;
}

int search(){
	int n = 1;
	while(true){
		if(!update(n)){
			break;
		}
		n++;
	}
	return n-1;
}

int main(){
	init_count();
	int result = search();
	cout<<result;
    return 0;
}

可以看到，这里首先使用 while 循环对正整数进行遍历，随后在update 函数中取出正整数每一位上的数字，并利用 count 数组对其出现次数进行统计，当 count[i] < 0 时，就代表已经没有数字 i 了。

B：数字时光探险：揭秘2023年的密码之旅

本题改编自 第十四届蓝桥杯省赛试题A

题目描述：

在拼数字的过程中，阿彬发现有些卡片发出了特殊的光芒，将这些卡片按顺序排列后长达 100 个数字，同样，数字串中的每个元素的值都在 0 到 9 的范围之内。这串数字仿佛是时间的密码，隐藏着着一段段神秘的日期。阿彬渴望探索这些数字中蕴藏的 2023 年的奥秘。
现在他想要从这个数组中寻找一些满足以下条件的子序列：

子序列的长度为 8 ：

这个子序列可以按照下标顺序组成一个yyyymmdd格式的日期，并且要求这个日期是2023年中的某一天的日期，例如20230902,20231223。yyyy表示年份，mm表示月份，dd表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。

请你帮阿彬计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。

这道题目的一个思路是：找到所有长度为8的子序列并判断其是否为2023年的日期。

参考代码：

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

int result=0;
vector<int> num;
unordered_map<int,int> data_map;

void read_data(){
	for(int i=0;i<100;i++){
    	int temp;
    	cin>>temp;
    	num.push_back(temp);
	}
}

void init_data_map(){
	int dom[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	int m = 1;
	int d = 1;
	for(int i=0;i<365;i++){
		int data = 100*m+d;
		data_map[data] = 1;
		if(++d>dom[m])
        {
            d=1;
            m++;
        }
	}
}

void search_data(int loc){
	for(int m1=loc+1;m1<100;m1++){
		if(num[m1]>=2) continue;
		for(int m2=m1+1;m2<100;m2++){
			int mm = 10*num[m1]+num[m2];
			if(mm>12||mm==0) continue;
			for(int d1=m2+1;d1<100;d1++){
				if(num[d1]>3) continue;
				for(int d2=d1+1;d2<100;d2++){
					int dd = 10*num[d1]+num[d2];
					if(dd>32||dd==0) continue;
					int data = 100*mm+dd;
					if (data_map[data]==1){
						data_map[data]=0;
						result++;
					}
				}
			}
		}
	}
	
}

void search(){
	for(int y1=0;y1<100;y1++){
		if(num[y1]!=2) continue;
		for(int y2=y1+1;y2<100;y2++){
			if(num[y2]!=0) continue;
			for(int y3=y2+1;y3<100;y3++){
				if(num[y3]!=2) continue;
				for(int y4=y3+1;y4<100;y4++){
					if(num[y4]!=3) continue;
					search_data(y4);
				}
			}
		}
	}
}


int main(){
	read_data();
	init_data_map();
	search();
	cout<<result;
    return 0;
}

这里先生成2023年的全部日期放入哈希表中，后续只需要判断子序列是否在哈希表中即可，同时可以利用哈希表来计数，过滤重复的日期。当然，这里因为对每一位都进行了剪枝，所以代码会比较臃肿一些。

当然，在比赛中有同学反过来，遍历2023年的全部日期，并检查是否存在相同的子序列。如果序列长度很长的话，这种方法理论上会更好一些。下面是这位同学的代码，也可以学习一下：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

const int days[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int main() {
    int ans = 0;
    int numbers[100] = { 0 };
    for (int i = 0;i < 100;i++)
    {
        cin >> numbers[i];
    }
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= days[i]; j++) {
            string str = "2023";
            if (i < 10)str += "0";
            str += to_string(i);
            if (j < 10)str += "0";
            str += to_string(j);
            int k = 0;
            for (int l = 0; l < 100 && k < 8; l++) {
                if (numbers[l] == str[k] - '0') k++;
            }
            if (k >= 8) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

C：徘徊于数字迷宫：揭秘混乱的信息世界

本题改编自 第十四届蓝桥杯省赛试题B

题目描述：

随着数字中蕴藏的奥秘被揭开，阿彬发现自己被传送到了由 0 和 1 组成的数字世界中，阿彬发现自己深处一片混乱之中难以抽身。

在数字世界中，有一种神奇的度量叫做香农信息熵，用于衡量一串由0和1构成的信息的混乱程度。想象一下，有一串长度为 $n$ 的01串 $S=x_1x_2x_3 \dots x_n$ ，其信息熵 $H (S)$ 可以被定义为一种精妙的计算，根据 0 和 1 在这串信息中出现的频率来描述其混乱程度。如果0和1在串中的出现比例分别是 $p (0)$ 和 $p (1)$ ，那么 $H(S)=-\sum_1^n p(x_i)\log_2(p(x_i))$ 。

比如，对于 $S = 100$ 来说，信息熵 $H(S)=-\frac{1}{3}\log_2(\frac{1}{3})-\frac{2}{3}\log_2(\frac{2}{3})-\frac{2}{3}\log_2(\frac{2}{3})=1.3083$ 。

现在，假设有一串长度为 $n$ 的01串，它的信息熵为 $m$ ，而且 0 出现的次数比 1 少。这串神秘的 01 串中究竟出现了多少次 0 呢？

首先，假设 0 有 a 个，那么信息熵的计算可以简化如下：
$-\frac {a^2} {n}\log_2(-\frac {a} {n}) -\frac {(n-a)^2} {n}\log_2(-\frac {n-a} {n})$
因此，本题的一个想法就是搜索 0 到 n ，计算其信息熵，查看是否与给出的信息熵相符。

参考代码：

#include<iostream>
#include<cmath>

using namespace std;

double log2(double x){
	return log(x)/log(2);
}

double h(double n, double m){
    double l = n+m;
    return -n*n/l*log2(n/l) - m*m/l*log2(m/l);
}

int search(double n, double m){
	double left = 0;
	double right = n/2+1;
	double mid = (left+right)/2;
	while(true){
		double i = floor(mid);
		double h_i = h(i, n-i);
		if (abs(h_i-m)<1e-4) return i;
		
		if(h_i<m) left=i;
		
		if(h_i>m) right=i;
		
		mid = (left+right)/2;
	}
}

int main(){
	double n, m;
    cin>>n>>m;
    int result = search(n, m);
    cout<<result;
    return 0;
}

可以看到，由于题目中给出 0 的出现的次数比 1 少。因此，实际上只需要搜索 0 到 n/2 的范围即可。同时，由于在 0 到 n/2 这个区间上，信息熵是递增的，因此，可以使用二分查找来提高查找速度。

D：当数字的魔法相遇：探寻素数之门

本题为签到题

题目描述：

经过不断的探索，阿彬终于在数字世界中找到了一扇神秘的小门，但门上好像写着什么：

寻找素数的魔法之门。挑战来自于数字的神秘奥秘。给定一个正整数 $N$ ，你的任务是探索从 0 到 $N$ 之间所有素数的和。这个挑战充满了数字的无限可能性，因为结果可能异常庞大。但你需要勇敢地探索，并找到这个和值。当你完成计算后，需以对 1000000007 取余的方式呈现你的答案。只有真正的数字勇士才能突破这道门，揭示出素数的神秘奥秘。

这道题目的一个思路是：遍历 0 到 $N$ 之间所有素数

参考代码：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int n;
vector<int> primes;
unordered_map<int,int> isprime;


bool isPrime(int n){
    for(int i=0;i<primes.size();i++){
    	int temp = primes[i];
    	if (temp*temp>n) break;
        if(n%temp==0) return false;
    }
    isprime[n]=1;
    primes.push_back(n);
    return true;
}

int sum_mod(int a, int b){
	int c = 1000000007;
	a %= c;
	b %= c;
	return (a+b)%c;
}

int search(){
	int result=0;
	primes.push_back(2);
	for(int i=2;i<=n;i++){
		if(isPrime(i)) result=sum_mod(result,i);
	}
	return result;
}

int main()
{
	cin>>n;
	int result = search();
	cout<<result;
    return 0;
}

可以看到，这里对 0 到 $N$ 进行了遍历，而在判断素数上，由于这里是从小到大依次遍历的，因此可以使用数组来记录遍历过的素数，并在后续判断素数时，只需要遍历这个素数数组即可，由于本题是签到题，因此并没有在这上面做要求，不这么写也可以通过全部样例。当然，还有一个细节，就是在取余时先对两边取余再相加取余，这样可以避免数据溢出。当然，在本题中，a 和 b 都在安全范围内，这里只是展示一下。

其他说明

值得注意的是，本次比赛可以实时看到自己的提交结果，但在蓝桥杯中，选手是无法看到自己代码的评测结果的，因此选手需要时刻注意代码的时间复杂度，并不是求出结果就可以的，需要考虑在一定数据规模上能否在给定时间限制内求出。

同时，本次比赛中有同学直接提交了题目描述中的输出样例，并得到了对应的分数。这在真实比赛中是不可能发生的。因为真是比赛中题目描述中的输出样例是不包含在测试样例中的。去年提到的“骗分”主要指的是提交一个时间复杂度高的算法获取部分分数，而不是指提交固定答案。当然，后续我也会注意将示例从测试样例中去除。

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m