2023年14界蓝桥杯省赛题解

news/2024/9/23 20:19:15/

2023年14界蓝桥杯省赛题解

蒟蒻笔者大二，第一次省赛。总结一下：“300块没了，退钱！”

A、日期统计

问题描述

小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示：

5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

现在他想要从这个数组中寻找一些满足以下条件的子序列：

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

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

答案：235

暴力枚举就可以了，比赛的时候没看到子序列，直接跑题hhhhh😭。

省赛过去了，看看题目就会了，以下是线下写的，关键一写还对了，真难过

时间复杂度：近似O(n 4)，因为前四个for只找一个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int maxl = 1e5 + 7;int a[maxl], t[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};//月份
set<string> st;//存日期
char ch[4];//格式化的日期int main(){for (int i = 0; i < 100; i++)	cin >> a[i];//存数for (int i = 0; i < 100; i++){if (a[i] != 2 )	continue;for (int j = i + 1; j < 100; j++){if (a[j] != 0)	continue;for (int k = j + 1; k < 100; k++){if (a[k] != 2)	continue;for (int l = k + 1; l < 100; l++){if (a[l] != 3)	continue;//前4个for循环，表示不是2023直接跳过for (int m = l + 1; m < 100; m++){for (int n = m + 1; n < 100; n++){for (int o = n + 1; o < 100; o++){for (int p = o + 1; p < 100; p++){int month = a[m] * 10 + a[n];//这里把月份求出来if (month <= 0 || month	> 12)	continue;//如果不是1-12月，就不成立int day = a[o] * 10 + a[p];//这里把天数写出来if (day > t[month] || day < 1)	continue;//最大不能超过当月最大日期，最小不能小于1sprintf(ch, "%02d%02d", month, day);//因为2023是一样的笔者就只格式化了月份和天数。最后就是格式化字符串函数，不会的值得学一学，可以省很多事st.insert(ch);//把格式好的日期存到set中去重}}}}}} }}//for (string va : st)	cout << va << endl;//打印有哪些日期cout << st.size() << endl;//打印个数return 0;
}
/*
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9
5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5
8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4
6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 
8 0 9 1 2 8 5 0 2 5 3 3
20230101
*/

B、01串的熵

问题描述

请添加图片描述

答案：11027421

这题笔者做对了，5分到手！笔者还算幸运，虽然笔者也不知到算log2 的函数，但是被笔者试出来了，还算幸运把！😝

以下是笔者的，比赛上的代码，双手奉上！

时间复杂度：O(n),最大值是23333333也就是1e8的数量级，直接枚举即可

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int maxl = 1e5 + 7;int total = 23333333;
//11027421
double ans = 11625907.5798;
int main(){for (int i = 1; i <=  total ; i++){double a = (double) i / total , b = (double)(total - i) / total, sum;//a、b是各自的占比sum = -(i* (a * log2(a)) + (total - i) * (b * log2(b)));//算出来的值if (abs(sum - ans) <= 1e-4 ){//浮点数的判断方法cout <<i <<'\t' << (total - i) <<endl;}}return 0;
}

C、冶炼金属

请添加图片描述
请添加图片描述

题解：

笔者写的时候看这1e4的数据，立马条件反射是二分。但是数据过不去（c语言网的，只能过样例😑）哎，应该是写错了。

对于标准写法，个人认为应该要看懂以下几个问题：

  1. 所取得最大值应该是a/b的最小值
  2. 从a/(b + 1) ， 开始寻找第二个值

时间复杂度：O(n2),1e4的数据范围，正常来说过不了。但是他的第二重for循环，并没有遍历n次，因此可以过

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int maxl = 1e5 + 7;int n, a, b, maxv = 1e9 + 7, minv = 0;void slove(){cin >> n;for (int i = 0; i < n; i++){cin >> a >> b;maxv = min(maxv, a/b);//上限收紧 满足每组数据 int c = a/(b + 1);while (a/c != b)	c++;minv = max(minv, c);//下限上调 满足每组数据}cout << minv << " " << maxv << endl;
} 
int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while (t--){slove();}return 0;
}
/*
3
75 3
53 2
59 2
*/

D、飞机降落

问题描述：

请添加图片描述
请添加图片描述

题解：

笔者写过的题目好像有类似的，贪心题。哎，不说了，错了、错了。直接面向样例编程了。哈哈哈…😅

正经题解。用全排列模板爆搜就可以过了。学长说数据范围就10肯定爆搜啊！

时间复杂度：N、T的数据范围为10，最大的话也就10*10！能过！

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int maxl = 1e5 + 7;int n, T[maxl], D[maxl], L[maxl];
bool vis[maxl];bool dfs(int step, int nowT){if (step == n)	return true;bool flag = 0;//标记 for (int i = 0; i < n; i++){if (!vis[i]){if (nowT > T[i] + D[i])	return false;//如果现在的时间超过了最大起飞时间，则就直接返回 vis[i] = !vis[i];int nextT = (nowT < T[i]) ? T[i] + L[i] : nowT + L[i];//下次起飞时间：如果现在的起飞时间小于下一个飞机的到达时间，则以现在的到达时间为准，反之以现在的飞机到达时间为准 flag |= dfs(step + 1, nextT);//这么多种情况，有一种情况可以就为真 vis[i] = !vis[i];}}return flag;//反回flag 
}
void slove(){memset(vis, 0, sizeof(vis));cin >> n;for (int i = 0; i < n; i++)	cin >> T[i] >> D[i] >> L[i];cout << (dfs(0, 0) ? "YES" : "NO") << endl;//简单判断一下 
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){slove();}return 0;
}
/*
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
*/

E、接龙数列

请添加图片描述
请添加图片描述

题解：

作者写的最长上升子序列的板子。完美掉进坑里😐。

正经题解：

  1. 由“删除最少的数”，可得所求的是最长接龙数列的个数
  2. 其实题目已经把递推式给出了，当前状态是以**“Ai结尾的数字”转移到“Ai开头的数字”**
  3. 那么可设dp下标的含义为：dp[i]是以数字i开头的最长接龙序列。
  4. 遍历顺序：从前往后
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int maxl = 1e5 + 7;int n, maxlen;
string s;
int dp[maxl];//dp[i]是以数字i开头的最长接龙序列。void slove(){cin >> n;for (int i = 0; i < n; i++) {cin >> s;int pre = s[0] - '0';//第一个数字 int now = s.back() - '0';//最后一个数字 dp[now] = max(dp[now], dp[pre] + 1);//看上一个接龙数列，和现在的接龙数列谁长 }for (int i = 0; i < 10; i++)	maxlen = max(maxlen, dp[i]);//看看是以那个数字开头，接龙数列最长 cout << n - maxlen;
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while (t--){slove();}return 0;
}
/*
5
11 121 22 12 2023
*/

F、岛屿个数

请添加图片描述

在这里插入图片描述
在这里插入图片描述

题解：

笔者只会普通的bfs、dfs模板。这真上难度了。笔者真不会😔。笔者还在想到底怎么才能判断环的个数😶‍🌫️。想不明白

正经题解：

  1. 如何判断环、并且判断是否在另一个环内。

    1. 从地图外的一个地方，用bfs标记所有的海水联通的地方。这样就可以找出每个单独的岛屿（不算子岛屿）。
    2. 再遍历子岛屿的个数，并且把遍历过的岛屿标记。

    答：形象的说就是“发动一场洪水没被淹到的地方就是环内” —— 好好理解吧🤮。建议直接看操作，怎么个淹法。

  2. 然后就是基本的bfs或者dfs。不会的话可以看这道题P1596 [USACO10OCT]Lake Counting S ，可以说就是这道题的子题了。会那道题，再来看这道题会好很多

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int maxl = 1e2 + 7;
struct point{int x, y;
};int n, m, ans = 0;
char g[maxl][maxl];
int flag[maxl][maxl];//这里用int是因为有3种状态要表示。0 -- 海水、1 -- 陆地、2 -- 环外 
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
queue<point> q;
point tp;void bfs1(){//标记外围海水联通的地方 ， 找出每个单独的岛屿（不算子岛屿）。q.push({0, 0});//我们选一个地图外的地方加入队列 flag[0][0] = 1;//标记来过 while (!q.empty()){tp = q.front();q.pop();for (int i = 0; i < 8; i++){int x = tp.x + dx[i];int y = tp.y + dy[i];if (x < 0 || y < 0 || x > n + 1 || y > m + 1 || g[x][y] != '0' || flag[x][y])	continue;//这里的意思是：比地图大一圈、是海水、没被标记过 flag[x][y] = 1;//进行标记 q.push({x, y});}}
}void bfs2(int x0, int y0){//标记单个岛屿 flag[x0][y0] = 1;//把岛屿边放进去 q.push({x0, y0});while (!q.empty()){tp = q.front();q.pop();for (int i = 0; i < 4; i++){int x = tp.x + dx[i];int y = tp.y + dy[i];if (x < 1 || y < 1 || x > n || y > m || flag[x][y])	continue;flag[x][y] = 1;q.push({x, y});}}
}void slove(){memset(flag, 0, sizeof(flag));//初始化 memset(g, '0', sizeof(g)); //每个点都赋为海水 ans = 0; cin >> n >> m;for (int i = 1; i <= n; i++){//地图是从1-n for (int j = 1; j <= m; j++){//地图是从1-m cin >> g[i][j];}}bfs1();//标记外围海水 for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (!flag[i][j] && g[i][j] == '1'){ ans++;bfs2(i, j);//标记该岛屿内的子岛屿和 海水 }}}cout << ans << endl;
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){slove();}return 0;
}
/*
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
*/

G、子串简写

问题描述

在这里插入图片描述
在这里插入图片描述

笔者暴力模拟的，学了一年就会模拟😂

正经题解：

  1. 存以c2结尾的下标。
  2. 遍历字符串s，如果是c1则就查找最近的c2结尾的下标。
  3. 加上结果，输出。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int maxl = 1e5 + 7;int k, ans = 0;
string s;
char c1, c2;
vector<int> pos;//用vector好求下标、不用再开数组了 void slove(){cin >> k >> s >> c1 >> c2;for (int i = 0; i < int(s.size()); i++){if (s[i] == c2)	pos.push_back(i);}int posCount = pos.size();//c2下标的个数 for (int i = 0; i < int(s.size()); i++){if (s[i] == c1){int l = 0, r = posCount - 1, mid;while (l < r){mid = l + ((r - l) >> 1); if (pos[mid] - i + 1 >= k)	r = mid;//长度为k个 else	l = mid + 1;}if (pos[l] - i + 1 >= k)	ans += posCount - l;//这里是能找到满足要求的l，才加 }}cout << ans;
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while (t--){slove();}return 0;
}
/*
4
abababdb a b
*/

结束

蒟蒻之旅，到此结束。后面太难了，真的看不懂。😭

等下次，变成神犇了再来补上！

创作不易，点个赞吧！
最后，算了一下，笔者这次应该有个20分hhhh。交学费了。哎


http://www.ppmy.cn/news/42972.html

相关文章

【机器学习】P17 梯度下降 与 梯度下降优化算法（BGD 等 与 Adam Optimizer、AdaGrad、RMSProp）

【机器学习】P17 梯度下降 与 梯度下降优化算法（BGD 等 与 Adam Optimizer、AdaGrad、RMSProp）

梯度下降与梯度下降算法梯度下降梯度下降算法基础优化算法批量梯度下降 BGD随机梯度下降 SGD小批量梯度下降 MBGD动量梯度下降 MGD基础优化算法上的改进和优化的算法自适应梯度算法 Adagrad均方根传播算法 RMSProp自适应矩估计算法 Adam代码如何实现梯度下降如何判断收敛梯度下…
阅读更多...
为什么工控行业生意越来越难做了？

为什么工控行业生意越来越难做了？

前段时间跟几个做工业品销售的朋友聚了一下&#xff0c;大家都说去年一年挺难的&#xff0c;有些甚至想把小店关了。为什么现在工业品领域越来越难做了呢&#xff1f;今天也想给大家说一说我的一些看法。 以前的工控生意相对现在来说较为有限和封闭&#xff0c;技术上也没有现今…
阅读更多...
简易糖尿病胰岛素注射量推荐系统运行记录（github项目）

简易糖尿病胰岛素注射量推荐系统运行记录（github项目）

前言 在github上找案例推理相关实现代码&#xff0c;找到这个项目&#xff0c;记录一下运行过程。项目地址&#xff1a;https://github.com/jcf-junior/Diabetes-CBR 运行记录 运行项目的前提是已经装好的所有request的包&#xff0c;电脑里已经安装过mongodb数据库。 原项目…
阅读更多...
含分布式电源的配电网日前两阶段优化调度模型（Matlab代码实现）

含分布式电源的配电网日前两阶段优化调度模型（Matlab代码实现）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
阅读更多...
Qt·核心机制

Qt·核心机制

★了解Qt和C的关系 ★掌握Qt的信号/槽机制的原理和使用方法 ★了解Qt的元对象系统 ★掌握Qt的架构 ★理解Qt的事件模型&#xff0c;掌握其使用的时机 目录 一、信号与槽 二、元对象系统 三、Qt的架构 四、Qt的事件模型 信号与槽、元对象系统、事件模型是Qt机制的核心&…
阅读更多...
104.（cesium篇）cesium卫星轨道模拟

104.（cesium篇）cesium卫星轨道模拟

听老人家说：多看美女会长寿 地图之家总目录（订阅之前建议先查看该博客） 文章末尾处提供保证可运行完整代码包，运行如有问题，可“私信”博主。 效果如下所示： 下面献上完整代码，代码重要位置会做相应解释 <html lang="en"> <
阅读更多...
从零学习python - 13模块的导入与使用(实现单例模式)

从零学习python - 13模块的导入与使用(实现单例模式)

模块基础知识 # 项目 > 包 > 模块 > 变量\方法\类 # 在python中,模块是代码组织的一种方式,把功能相近的函数或类放到一个文件中,一个文件(.py)就是一个模块,模块名就是文件名去掉py后缀. # 好处:提高代码可复用性和可维护性,一个模块编写完成后,很方便在其他项目中导…
阅读更多...
day9 条件变量的基本使用

day9 条件变量的基本使用

目录 条件变量 条件变量 应用场景&#xff1a;生产者消费问题&#xff0c;是线程同步的一种手段&#xff1b; 必要性&#xff1a;为了实现等待某个资源&#xff0c;让线程休眠&#xff0c;提高运行效率&#xff1b; 等待资源&#xff1a; //1、一直等待资源 int pthread_c…
阅读更多...
最新文章

Copyright @ 2022~2023