(蓝桥杯 刷题全集)【备战(蓝桥杯)算法竞赛-第1天(基础算法-上 专题)】( 从头开始重新做题,记录备战竞赛路上的每一道题 )距离蓝桥杯还有75天

news/2024/2/29 3:44:46

🏆🏆🏆🏆🏆🏆🏆
欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录)
 
文章字体风格:
红色文字表示:重难点✔★
蓝色文字表示:思路以及想法✔★
 
如果大家觉得有帮助的话,感谢大家帮忙
点赞!收藏!转发!

 
我的qq号是:1210931886,欢迎大家加群,一起学习,互相交流,共同进步🎉🎉✨✨
🥇🥇🥇🥇🥇🥇🥇

蓝桥杯系列,为大家提供

  1. 做题全集,备战蓝桥杯,就做这个系列的题即可
  2. 一个大概的做题规划——大家最好在此基础上提前两个月准备

备战蓝桥杯就刷这些题
第一天博客链接 - 基础算法 -上
第二天博客链接 - 基础算法 -下 + 数据结构专题
第三天博客链接 - 搜索与图论-上 专题
第四天博客链接 - 搜索与图论-下 专题
第五天博客链接 - 数学知识专题
第六天博客链接 - 动态规划 专题
第七天博客链接 - 贪心算法 专题

备战(蓝桥杯)算法竞赛-第1天

  • 一、快速排序
        • 1. 快速排序例题
        • 2. 第k个数( 快速选择 )
  • 二、归并排序
        • 1. 归并排序模板题
        • ★2. 逆序对的数量
  • 三、二分
        • 1. 数的范围
        • ★2. 数的三次方根
  • 四、高精度
        • 1. 高精度加法
        • 2. 高精度减法
        • 3. 高精度乘法
        • 4. 高精度除法 10:25-10:37(12分钟)
  • 五、前缀和
        • 1. 前缀和 (2分钟)
        • 2. 子矩阵的和(7分钟)

一、快速排序

1. 快速排序例题

原题链接

#include<iostream>
using namespace std;void quick_sort(int a[],int r,int l)
{if(r >= l) return;int i = r - 1,j = l + 1,x = a[i + j >> 1];while(i < j){do i++; while(a[i] < x);do j--; while(a[j] > x);if(i < j)swap(a[i],a[j]);}quick_sort(a,r,j),quick_sort(a,j+1,l);
}int main()
{int n;cin >> n;int* a = (int*)malloc(sizeof(int)*n);for(int i = 0; i < n; i++){cin >> a[i];}quick_sort(a,0,n-1);for(int i = 0; i < n; i++){cout << a[i] << ' ';}return 0;
}

2. 第k个数( 快速选择 )

原题链接

#include<iostream>
using namespace std;const int N = 1e6+10;int a[N],k;int quick_sort(int l,int r)
{if(l>=r)return a[r];int i = l-1,j = r+1,x = a[l+r>>1];while(i<j){do i++;while(a[i]<x);do j--;while(a[j]>x);if(i<j)swap(a[i],a[j]);}if(j>=k)return quick_sort(l,j);elsereturn quick_sort(j+1,r);
}int main()
{int n;cin >> n >> k;for(int i = 1; i<= n; i++)cin >> a[i];cout << quick_sort(1,n);
}

二、归并排序

void merge_sort(int q[], int l, int r)
{if (l >= r) return;int mid = l + r >> 1;merge_sort(q, l, mid);merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

1. 归并排序模板题

原题链接

#include <iostream>
#include <algorithm>
using namespace std;const int N = 100010;
int array[N];
int nums;
unsigned long result = 0;void merge_sort(int array[], int l, int r)
{if (l >= r) return;int mid = ( l + r  ) / 2;merge_sort(array, l, mid);merge_sort(array, mid + 1, r);int temp[r - l + 1];int lptr = l;int rptr = mid + 1;int tempptr = 0;while(lptr <= mid && rptr <= r){if(array[lptr] <= array[rptr]){temp[tempptr++] = array[lptr++];} else {temp[tempptr++] = array[rptr++];result += (mid - lptr + 1);//注意这里,是直接加的,后面的不需要比较了。} } while ( lptr <= mid ){temp[tempptr++] = array[lptr++];}while ( rptr <= r ){temp[tempptr++] = array[rptr++];}for (int i = l, j = 0; i <= r; i ++, j ++){array[i] = temp[j];}
}int main(){scanf("%d", &nums);for(int i = 0; i < nums; i++){scanf("%d", &array[i]);}merge_sort(array, 0, nums-1);cout << result;return 0;
}

★2. 逆序对的数量

原题链接

#include <iostream>using namespace std;typedef long long LL;const int N = 1e5 + 10;int a[N], tmp[N];LL merge_sort(int q[], int l, int r)
{if (l >= r) return 0;int mid = l + r >> 1;LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else{res += mid - i + 1;tmp[k ++ ] = q[j ++ ];}while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];return res;
}int main()
{int n;scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);cout << merge_sort(a, 0, n - 1) << endl;return 0;
}

三、二分

1. 数的范围

原题链接

#include<iostream>
using namespace std;int n = 100010;
int a[100010] = {0};
int q,k,m;int l,r,mid;
int main()
{cin >> q >> m;for(int i = 0; i < q; i++){cin >> a[i];}while(m--){int s;cin >> s;l = 0,r = q - 1,mid;while(l<r){mid = (l + r) / 2;if(a[mid] >= s) r = mid;else l = mid + 1;}if(a[l] != s)cout << "-1 -1" << endl;else{cout << l << " ";l = 0,r = q - 1,mid;while(l<r){mid = (l + r + 1) / 2;if(a[mid] <= s) l = mid;else r = mid - 1;}cout << l << ' ' << endl;}}return 0;
}

★2. 数的三次方根

原题链接

#include<iostream>
using namespace std;int main()
{double x;cin >> x;double l = -100,r = 100;while(r - l > 1e-8){double mid = (l + r) / 2;if(mid * mid * mid >= x) r = mid;else l = mid;}printf("%.6f",l);return 0;
}

四、高精度

1. 高精度加法

原题链接

#include<iostream>
#include<vector>
using namespace std;vector<int> add(vector<int> &A,vector<int> &B)
{if(A.size() < B.size())return add(B,A);vector<int> C;int t = 0;for(int i = 0; i < A.size(); i++){t+=A[i];if(i<B.size()) t+=B[i];C.push_back(t % 10);t /= 10;    }if(t)C.push_back(t);return C;
}int main()
{string a,b;cin >> a >>b;vector<int> A,B;for(int i = a.size() - 1; i >=0; i--)A.push_back(a[i] - '0');for(int i = b.size() - 1; i >=0; i--)B.push_back(b[i] - '0');auto C = add(A,B);for(int i = C.size() - 1; i >=0; i--)cout << C[i];return 0;
}

2. 高精度减法

原题链接
在这里插入图片描述
二刷:

  1. 小减大 需要转换成 大-小
  2. 如果出现负数 (x+10)%10 t = 1不是-1
  3. t = a[i] - t; t = t - b[i]
#include <iostream>
#include <vector>using namespace std;bool cmp(vector<int> &A, vector<int> &B)
{if (A.size() != B.size()) return A.size() > B.size();for (int i = A.size() - 1; i >= 0; i -- )if (A[i] != B[i])return A[i] > B[i];return true;
}vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;for (int i = 0, t = 0; i < A.size(); i ++ ){t = A[i] - t;if (i < B.size()) t -= B[i];C.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a, b;vector<int> A, B;cin >> a >> b;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');vector<int> C;if (cmp(A, B)) C = sub(A, B);else C = sub(B, A), cout << '-';for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];cout << endl;return 0;
}

3. 高精度乘法

原题链接

#include <iostream>
#include <vector>using namespace std;vector<int> mul(vector<int> &A, int b)
{vector<int> C;int t = 0;for (int i = 0; i < A.size() || t; i ++ ){if (i < A.size()) t += A[i] * b;C.push_back(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a;int b;cin >> a >> b;vector<int> A;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');auto C = mul(A, b);for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);return 0;
}

4. 高精度除法 10:25-10:37(12分钟)

原题链接

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;void div(vector<int> a,int b)
{vector<int> ans;int t = 0;for(int i = a.size()-1; i >= 0; i--){t = t * 10 + a[i];ans.push_back(t/b);t = t-t/b*b;}reverse(ans.begin(),ans.end());while(ans.size()>1 && ans.back()==0)ans.pop_back();for(int i = ans.size()-1; i >=0; i--)cout << ans[i];cout << endl;cout << t;}int main()
{string s1;int b;vector<int>a;cin >> s1 >> b;for(int i = s1.size()-1; i >= 0; i--) a.push_back(s1[i]-'0');div(a,b);return 0;
}

五、前缀和

1. 前缀和 (2分钟)

原题链接

#include<iostream>using namespace std;const int N = 1e5+10;int a[N],s[N];int main()
{int n,m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];s[i] = a[i] + s[i-1];}while(m--){int l,r;cin >> l >> r;cout << s[r] - s[l-1] << endl;}return 0;
}

2. 子矩阵的和(7分钟)

原题链接

#include<iostream>using namespace std;const int N = 1010;int a[N][N],s[N][N];int main()
{int n,m,q;cin >> n >> m >> q;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){cin >> a[i][j];s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];}while(q--){int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << endl; }return 0;
}

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

相关文章

数据库实践LAB大纲 02 检索

文章目录单表查询&#xff08;基本查询、分组查询&#xff09;select子句LIMITwhere关系/逻辑/取值/空值表达式模糊查询分组查询聚集函数Group by多表查询表连接子查询子查询与数据更新联合查询 UNION[ALL]查询效率高级查询&#xff08;复杂子查询&#xff09;包含关系查询ROLL…

Lesson 6.3 正则化与 sklearn 逻辑回归参数详解

文章目录一、过拟合、正则化、特征衍生与特征重要性评估1. 正则化&#xff08;Regularization&#xff09;的基本概念2. 过拟合概念介绍3. 正则化进行特征筛选与缓解过拟合倾向二、sklearn 中逻辑回归的参数解释1. 说明文档中的内容解释2. sklearn 中逻辑回归评估器的参数解释在…

从一线运维中浅谈docker

目录 一、docker的架构 二、docker的组件 1.docker 2. dockerd 3. docker-init 4. docker-proxy 三、docker容器的生命周期 四、docker的核心概念 五、docker的常用命令 •镜像命令 •容器命令 一、docker的架构 docker 镜像(Images) docker 镜像是用于创建 Docker …

有道云笔记签到(java版)

这里的cookie过期时间还未测试是多久&#xff0c;如果过期了就重新抓取下 通过fiddler抓取有道云的签到接口 1&#xff09;打开fiddler 2&#xff09;打开有道云笔记进行签到 抓取到的签到接口 https://note.youdao.com/yws/mapi/user?methodcheckin 抓取cookie&#xff1…

ThinkPHP 6 视图:从零开始

框架6.0默认只能支持PHP原生模板&#xff0c;如果需要使用thinkTemplate模板引擎&#xff0c;需要安装think-view扩展&#xff08;该扩展会自动安装think-template依赖库&#xff09;。 PHP原生模板 1.配置文件 默认设置为Think&#xff0c;因为没有安装&#xff0c;直接使用会…

【数据结构】二叉搜索树BSTree

文章目录一、概念二、基础操作1.查找find2.插入Insert3.中序遍历InOrder4.删除erase三、递归写法1.递归查找2.递归插入3.递归删除四、应用五、题目练习一、概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: 若它的左子树不…

thinkphp关于模型一对多,多对多,多对一的使用

首先看看thinkphp5.0的模型介绍这里关联有一对一&#xff0c;多对多&#xff0c;一对多&#xff0c;多对一。还有预载入&#xff08;就是查询预写好&#xff0c;php界面调用时候才查询&#xff09;还有关联统计&#xff0c;聚合等。这里只讲解通过一对一的预载入&#xff0c;推…

Day19 C++STL入门基础知识十一——map、multimap容器 构造赋值、大小交换、插入删除、查找统计、排序【全面深度剖析+例题代码展示】

&#x1f483;&#x1f3fc; 本人简介&#xff1a;男 &#x1f476;&#x1f3fc; 年龄&#xff1a;18 ✍每日一句&#xff1a;【道固远&#xff0c;笃行可至&#xff1b;事虽巨&#xff0c;坚为必成】 文章目录1. 基本概念2. 构造赋值① 函数原型② 代码展示③ 测试结果3. 大小…

初次认识C++类

目录 前言&#xff1a; 面向过程和面向对象的区别&#xff1a; C语言&#xff1a; C&#xff1a; 类的引入&#xff1a; 类的定义&#xff1a; 类的权限&#xff1a; 类的作用域&#xff1a; 类的实例化&#xff1a; 类的大小计算&#xff1a; 空类或则只…

前端基础html css js

html&#xff1a;框架 css&#xff1a;美化 jp&#xff1a;交互 HTML 1.基础标签 <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>这是我的滴滴滴一个网页</title></head><body><h1>一号 标题&…

ROS2机器人编程简述humble-第四章-The TF Subsystem

这个是ROS2机器人的核心工具之一。概念&#xff1a;TF&#xff08;坐标系转换&#xff09;子系统是ROS2机器人框架中的一个重要组件&#xff0c;它的功能是提供坐标系转换服务&#xff0c;使得不同坐标系之间的数据可以转换。比如&#xff0c;机器人的传感器可以产生的数据是基…

【JavaEE】Java中复杂的Synchronized关键字

目录 一、synchronized的特性 &#xff08;1&#xff09;互斥 &#xff08;2&#xff09;刷新内存 &#xff08;3&#xff09;可重入 二、synchronized的使用 &#xff08;1&#xff09;修饰普通方法 &#xff08;2&#xff09;修饰静态方法 &#xff08;3&#xff09;修…

JDK8 新特性详解,2014-03-18 正式发布

简介&#xff1a;JDK8 的主要新特性六个&#xff1a;Lambda、Stream、Date、新注解、函数编程、并发&#xff0c;前两者主要用于集合中。 1、Lambda 演变过程 Data ToString NoArgsConstructor AllArgsConstructor public class Student { //名字 private String name; //性别…

OpenFST、WFST 小记

文章目录关于 OpenFST安装 openfst关于 WFST编译 WFST关于 OpenFST 官网&#xff1a;https://www.openfst.org/twiki/bin/view/FST/WebHome快速入门文档&#xff1a;https://www.openfst.org/twiki/bin/view/FST/FstQuickTour下载&#xff1a;https://www.openfst.org/twiki/b…

阿里为什么建议给MVC三层架构多加一层Manager层

我们在刚刚成为程序员的时候&#xff0c;就会被前辈们 “教育” 说系统的设计要遵循 MVC&#xff08;Model-View-Controller&#xff09;架构。它将整体的系统分成了 Model&#xff08;模型&#xff09;&#xff0c;View&#xff08;视图&#xff09;和 Controller&#xff08;…

java 线程池

线程池概念 线程池可以看做是一个池子&#xff0c;在这个池子中存储了很多线程&#xff0c;线程池也可以说是一个复用线程的技术。 线程池存在的意义 系统创建一个线程的成本是比较高的&#xff0c;因为它涉及到与操作系统交互&#xff0c;当程序中需要创建大量生存期很短暂的线…

【C语言】速刷日记

这里总结10道C语言经典题型问题&#xff0c;有兴趣可以刷刷看。1.递归问题12.递归问题23.短路求值问题4.字符数组定义问题5.二维数组元素访问问题6.指针问题7.二维数组地址问题8.前置与后置问题9.求1的个数问题10.求1的个数移位操作符1.递归问题1 给定 fun 函数如下&#xff0…

mysql数据同步到ES集群

视频地址&#xff1a; 刚哥技术讲堂之mysql与elasticsearch同步1-数据库binlog的设置及python读取刚哥技术讲堂之mysql与elasticsearch同步2-kafka生产者消费者模式消费binlog刚哥技术讲堂之mysql与elasticsearch同步3-elasticsearch的增删改同步数据库目录 P01-数据库binlog的…

Web3.0:互联网新阶段

Web3.0 定义&#xff1a;从后端生产关系革新开始。 Web3.0 是结合了去中心化和代币&#xff08;Token&#xff09;经济学等概念&#xff0c;基于区块链技术的全新的互联网迭代方向&#xff0c;意在解决 Web2.0 带来的生态不平衡、发展不透明等问题。与 AR/VR 等前端创新相比&am…

MySQL(十):索引的应用场景、用于排序、用于分组

目录一、索引用于排序二、索引用于分组一、索引用于排序 我们在编写查询语句时&#xff0c;经常需要使用order by子句对查询出来的记录按照某种规则进行排序&#xff0c;一般情况下&#xff0c;我们只能记录加载到内存中&#xff0c;然后再使用一些排序算法在内存中对这些记录…
最新文章