蓝桥杯知识点整理

时间：2024-03-24 21:17:58 来源：网络cs 作者：纳雷武栏目：卖家故事阅读：

标签：整理知识

阅读本书更多章节>>>>

知识点：

1、基本输入输出语法：
(1)如cin速度比scanf慢两者遇到空格回车会停止读入
(2)若想读整行需要cin.getline()或gets函数
(3)读到文件尾用scanf()!=EOF等等
(4)占位符‘%’相关格式，如对齐方式，补0等。
2、C/C++库函数以及stl模板
(1)algorithm: sort next_permutation lower_bound/upper_bound
(2)queue(priority_queue) stack vector set map基本操作等
3、数据结构
(1)结构体：注意结构体用sort排序，可自定义cmp函数，也可在结构体内重载“<”运算符。
(2)字符串：string类的使用、字典树（用于求解前缀和后缀问题）。
(3)栈、队列：前缀、后缀表达式计算等。
(4)图：两种表示方法，邻接表和邻接矩阵，当n较大时只能采用邻接表。
(5)树：树是一种特殊的图。如按层输出节点等
(6)线段树：基本的单点修改、区间修改、区间查询等。
4、算法
(1)暴力：蓝桥杯又称暴力杯，n<=1e3(1000)，O(n^{2)的代码大概率能解，如果1e4<=n<=1e6，则要考虑O(n*logn)的算法，不过蓝桥按测试点得分，实在不会，可用O(n}2)骗分，骗到了就是赚到了。
(2)思维：不涉及算法，不涉及复杂数据结构，往往几行代码就可以解决，考验思维能力，多训练此类题目即可。
(3)模拟：模拟指根据题目描述，按部就班的写代码就可以AC，通常思路容易看出但是代码量较大，考验细节与心态。
①大数加减法
②进制转换
(4)数学问题：
①质数相关：埃式筛、欧拉筛、唯一分解定理等。
②求最大公因数：要自己会写gcd函数（欧几里得算法）
③快速幂模板，矩阵快速幂模板
④慢速乘模板（防止相乘的时候数太大爆掉long long）
(5)贪心
(6)动态规划：
①最长公共子序列
②最长上升/不下降子序列
③背包问题（01背包、多重背包、完全背包等）
④前缀和问题（一维/二维前缀和）
(7)搜索：搜索基本是必考的点，包括DFS/BFS，可分别用栈和队列模拟。记忆化搜索也是常考的点，用于避免重复搜索。
(8)图论：
①最短路：最基本要掌握两种求法，floyd算法和dijkstra算法。前者O(n^3)，适用于n不大于500的情况。后者dijkstra用的较多，数据结构实现有两种，邻接矩阵与邻接表，建议用邻接表（具体实现啊哈算法上有）。
②最小生成树：kruscal算法和prim算法
③拓扑排序
(9)字符串：回文、kmp算法（字符串匹配算法）
(10)其他：并查集、二分/三分算法等

头文件

万能头文件 #include <bits.stdc++.h>

实数函数及运算符

求幂次

pow(x,y);数据类型下x,y应为double型

移位运算符

x<<y == x*(2^y)
x>>y == x/(2^y)

STL排序sort函数

void sort(first,last);
void sort(first,last,comp);
复杂度为O(nlogn)，排序的范围为[first,last)，包括first不包括last。

STL全排列函数next_permutation()

string s=“bca”;
sort(s.begin(),s.end());//字符串内部排序,得到最小的排列"abc"
do{
cout<<s<<" ";
}while(next_permutation(s.begin(),s.end()));
//s.end()指向最后一个字符的下一个位置

初始化函数memset()

例如：memset(a,0,sizeof(a))

GCD(最大公约数)和LCM(最小公倍数)

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int a,int b){return a/gcb(a,b)*b;}

C++字符串函数

find()函数：查找
substr()函数：查子串

按字典序反序排序

bool cmp(string a,string b){  return a+b>b+a;}

素数判断

bool is_prime(long long n){  If(n<=1) return false;  For(long long i=2;i<=sqrt(n);i++){If(n%i==0) return false;}Return true;}

快速幂

采用倍增的原理

int fastpow(int a,int b)//计算a的n次方{  Int ans=1;  while(n){ If(n&1) ans*=a; a*=a;n>>=1;//n右移一位，把刚处理过的n的最后一位去掉 }return ans;}

幂运算的结果往往很大，一般题目会要求先取模再输出。根据取模的性质有:aⁿ mod m=(a mod m)ⁿ mod m。

Ll fastpow(ll a,ll b){  Ll ans=1;  A%=mod;  while(n){If(n&1) ans=(ans*a)%mod;A=a*a%modlN>>=1;}Return ans;}

整数二分

Int L=1，R=N;//第一种写法While(L<R){Int mid=(L+R+1)/2;If(check(mid)) L=mid;Else R=mid-1;}Cout<<L;//第二种写法While(L<R){Int mid=(L+R)/2;If(check(mid)) L=mid+1;Else R=mid;}Cout<<L-1;

前缀和

For(int i=1;i<n;i++){  Sum[i]=sum[i-1]+a[i];}For(int i=1;i<n;i++){S+=sum[i-1]*a[i];}Cout<<S;

素数：

题目-纯质数

bool isPrime(int a){// 判断是否为质数if(a == 2){return true;}if(a < 2 || a % 2 == 0){return false;}for(int i = 3;i * i <= a;i += 2){if(a % i == 0){return false;}}return true;}bool isRealPrime(int a){// 判断是否为纯质数if(!isPrime(a)){return false;}do{if(!isPrime(a % 10)){return false;}a /= 10;}while(a != 0);return true;}

日期闰年：

if((i%4==0&&i%100!=0)||(i%400==0)){//闰年2月29天}

进制转换:

九进制转十进制,111=199+19+11=;

前缀和：

题目-统计子矩阵！！！

#include <iostream>#define ll long long intusing namespace std;const int N=510;int a[N][N],b[N][N];int main(){    int n,m,k;    cin>>n>>m>>k;    ll sum,cnt=0;    for(int i=0;i<n;i++)        for(int j=0;j<m;j++){            cin>>a[i][j];            a[i][j]+=a[i][j-1];        }    for(int i=0;i<m;i++)//左边界        for(int j=i;j<m;j++)//有边界    {        sum=0;        for(int l=0,r=0;r<n;r++){            //这里的lr是上下            sum+=a[r][j]-a[r][i-1];//前缀和            while(sum>k&&l<=r){                sum-=a[l][j]-a[l][i-1];                l++;            }            if(sum<=k&&l<=r) cnt+=r-l+1;        }    }    cout<<cnt<<endl;    return 0;}

状态dp:

计数类型的递推或者递归:
整数拼接：dp优化

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5 + 5;ll a[N], num[15];bool vis[15];ll connect(ll a, ll b){ll bb = b;while (bb != 0) {a *= 10;bb /= 10;}a += b;return a;} int main(void){int n, k, res = 0;cin >> n >> k;for (int i = 0; i < n; i++)cin >> a[i];for (int i = 0; i <= 9; i++)vis[(i * k) % 10] = 1;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {ll x = a[i], y = a[j];if (vis[y % 10] && connect(x, y) % k == 0)res++;if (vis[x % 10] && connect(y, x) % k == 0)res++;}}cout << res << endl;return 0;}

Bitset用法：明码

#include <iostream>#include <bitset>#include <cmath>using namespace std;unsigned int ans;int main(){//    bitset<8> bt;//    for(int i=0;i<10;i++)//    {//        for(int j=0;j<16;j++)//        {//            int a,b;//            bitset<8> bt;//            cin>>a>>b;//            bt=a;//            cout<<bt;//            bt=b;//            cout<<bt;//            cout<<endl;//        }//    }    ans=pow(9,9);    cout<<ans<<endl;    return 0;}

分治思想的快速排序

填空题

#include <stdio.h>int quick_select(int a[], int l, int r, int k) {int p = rand() % (r - l + 1) + l;//产生r到l的随机数int x = a[p];{int t = a[p]; a[p] = a[r]; a[r] = t;}int i = l, j = r;while(i < j) {while(i < j && a[i] < x) i++;if(i < j) {a[j] = a[i];j--;}while(i < j && a[j] > x) j--;if(i < j) {a[i] = a[j];i++;}}a[i] = x;p = i;if(i - l + 1 == k) return a[i];if(i - l + 1 < k) return ***quick_select( a,i+1,r,k-i+l-1);*** //填空else return quick_select(a, l, i - 1, k);}int main(){int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};printf("%d\n", quick_select(a, 0, 14, 5));return 0;}