专栏首页用户6093955的专栏蓝桥杯突击复习准备——部分算法汇总

蓝桥杯突击复习准备——部分算法汇总

蓝桥杯突击复习准备——部分算法汇总

一、一些库函数

lower_bound(a,a+n,x)
//二分查找,查找大于或等于x的第一个位置,只能查找vector<>数组,返回值为vector<>::iterator指针
unique(vector1.begin(),vector1.end())
//重排元素,使得所有值提前,返回值为重排后最后一个非重复值的后面的值的迭代器,即从返回值到vector1.end()是无意义的值,也是重复值的总数量
reverse(vector1.begin(),vector1.end())
    //反转元素顺序
next_permutation(p,p+n)
//求下一个全排列,枚举用
#include <vector>   数组

定义示例:vector<int> b(5);或者vector<int> a;

赋值:b[0]=1;只有第一种定义可以这样赋值

函数:

int size(),获取大小

void resize(int num),改变大小

void push_back(int x),向尾部添加元素

void pop_back(),删除最后一个元素

void clear(),清空

bool empty(),检查是否为空

iterator insert(iterator x,y),向vector数组的x位置插入元素y,x可以为v.begin()+2

iterator erase(iterator x),删除vector数组的x位置元素

iterator begin(),返回头指针

iterator end(),返回尾指针

vector<>::iterator为一个可以指向其元素的指针
#include <set>         集合,其中不含重复元素,且其中元素已从小到大排序,从1开始

定义示例:set<int> a;

函数:

int size(),获取大小

iterator find(x),若找到x,返回该键值迭代器的位置,否则,返回最后一个元素后面一个位置,即s.end()

void clear(),清空

bool empty(),检查是否为空

iterator insert(y),向set集合插入元素y

iterator erase(iterator x),删除set集合的值为x的元素,返回值为下一个位置的迭代器

iterator begin(),返回头指针

iterator end(),返回尾指针

set<>::iterator为一个可以指向其元素的指针
#include <map>       映射,索引

         定义示例:map<string,int> month_name;

赋值:map[“July”]=7;

函数:

iterator find(y),寻找索引值为y的元素,返回指向其的指针

iterator insert(map<string,int>(“July”,7)),向map映射插入元素(“July”,7)

iterator erase(iterator x),删除map映射的迭代器x的元素

map< string,int>::iterator l_it;;

   l_it=m.find(“July”);

   if(l_it==m.end())

        cout<<"we do not find July"<<endl;

   else  m.erase(l_it);  //delete July;

iterator begin(),返回头指针

iterator end(),返回尾指针

map<>::iterator为一个可以指向其元素的指针
#include <string>

string substr(int pos = 0,int n = npos) const;  //返回pos开始的n个字符组成的字符串

void swap(string &s2);                                       //交换当前字符串与s2的值

string &insert(int p0, const char *s);                //在p0位置插入字符串

string &erase(int pos = 0, int n = npos);          //删除pos开始的n个字符,返回修改后的字符串

int find(char c, int pos = 0) const;                     //从pos开始查找字符c在当前字符串的位置

int find(const char *s,int pos = 0) const;         //从pos开始查找字符串s在当前串中的位置

二、算法

1.并查集

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合:
p[find(a)] = find(b);

练习:POJ-2236AC代码

2.二分查找

整数二分算法模板

// 检查x是否满足某种性质
bool check(int x) {
    /* ... */
}
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分算法模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

3.快速排序算法模板

void quick_sort(int a[], int l, int r)
{
    if(l >= r) return ;
    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]);
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

//a[]数组下标从1开始

4.归并排序算法模板

//a[]是待排序的数组,tmp[]在排序过程中起到暂时存储的作用
void merge_sort(int a[], int l, int r)
{
    if(l >= r) return ;
    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j])
            tmp[k++] = a[i++];
        else 
            tmp[k++] = a[j++];
    }
    while(i <= mid)
        tmp[k++] = a[i++];
    while(j <= r)
        tmp[k++] = a[j++];
        
    i = l, j = 0;
    while(i <= r)
        a[i++] = tmp[j++];
}

关于归并排序,可以用它去求逆序对数目,例如【POJ - 2299】(AC代码)

5.背包问题

01背包问题

//二维
int N, V;
int v[maxn], w[maxn];
int f[maxn][maxn];
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    cin >> N >> V;
    for(int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= N; i++)
        for(int j = 0; j <= V; j++)
        {
            f[i][j] = f[i-1][j];
            if(j >= v[i])
                f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    int maxx = 0;
    for(int i = 0; i <= V; i++)
        maxx = max(maxx, f[N][i]);

    cout << maxx << endl;
}
//一维
int N, V;
int v[maxn], w[maxn];
int f[maxn];
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    cin >> N >> V;
    for(int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    for(int i = 1; i <= N; i++)
    {
        for(int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j-v[i]] + w[i]);
    }
    cout << f[V] << endl;
}

完全背包问题(每种物品都有无限件可用)

//从小到大遍历
int N, V;
int f[maxn];
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    cin >> N >> V;
    for(int i = 0; i < N; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = v; j <= V; j++)			//从小到大遍历
            f[j] = max(f[j], f[j-v] + w);
    }
    cout << f[V] << endl;
}
int N, V;
int v[maxn], w[maxn];
int f[maxn];
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    cin >> N >> V;
    for(int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    for(int i = 1; i <= N; i++)
    {
        for(int j = V; j >= v[i]; j--)		//从大到小遍历
        {
            for(int k = 0; k * v[i] <= j; k++)
                f[j] = max(f[j], f[j-k*v[i]] + k*w[i]);
        }
    }
    cout << f[V] << endl;
}

练习:POJ - 1837题解 AC代码

6.LIS最长上升子序列

状态转移方程:

//用下面一行状态转移方程的解法的时间复杂度为O(n*n),n为a数组的长度
f[i]先初始化为1
f[i]=max(f[i],f[j]+1)    (j>=0&&j<i,a[j]<a[i])

当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 IIAC代码,思路在代码中)

7.LCS最长公共子序列

状态转移方程:

//f[i][j] 表示 a[1~i] 和 b[1~j] 的最长公共子序列
f[i][j]=max(max(f[i-1][j],f[i][j-1]),f[i-1][j-1]+1(a[i]=b[j]))

练习:

树与图的存储及遍历

树是一种特殊的图,与图的存储方式相同。 对于无向图中的边ab,存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。

(1) 邻接矩阵:

g[a][b]

存储边a->b

(2) 邻接表:

// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的遍历

(1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心

int dfs(int u)
{
    st[u] = true;		//st[u]表示点u已经被遍历过
    for(int i = h[u], i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
            dfs(j);
    }
}

(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次

queue<int> q;
st[1] = true;	//表示1号点已经被遍历过
q.push(1);
while(q.size())
{
    int t = q.front();
    q.pop();
    for(int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;	//表示点j已经被遍历过
            q.push(j);
        }
    }
}

8.Dijkstra最短路径算法(不适用于有负边权的图)

朴素dijkstra算法 — 模板题 AcWing 849. Dijkstra求最短路 I

时间复杂度

O({n^2} + m)

, n表示点数

该算法对于n比较大的时候就不适用了,可以考虑在下一个堆优化版dijkstra。

const int inf = 0x3f3f3f3f;
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中,寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == inf) return -1;
    return dist[n];
}

堆优化版dijkstra — 模板题 AcWing 850. Dijkstra求最短路 II

时间复杂度

O(mlogn)

,n表示点数,m表示边数

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边, e[]是权重
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离,second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (!st[j] && dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == inf) return -1;
    return dist[n];
}

9.Floyd算法

floyd算法模板题 AcWing 854. Floyd求最短路

时间复杂度是

O({n^3})

, n 表示点数

初始化:
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

10.最小生成树Prim算法

朴素版prim算法模板题 AcWing 858. Prim算法求最小生成树

时间复杂度是

O({n^2} + m)

, n表示点数,m表示边数。

int n;      // n表示点数
int g[N][N];        // 邻接矩阵,存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

11.最小生成树Krusal算法

Kruskal算法模板题 AcWing 859. Kruskal算法求最小生成树

时间复杂度是

O(mlogm)

, n表示点数,m表示边数。

int n, m;       // n是点数,m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通,则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

12.拓扑排序

拓扑排序 — 模板题 AcWing 848. 有向图的拓扑序列

时间复杂度为

O(n+m)

, n表示点数,m表示边数

bool topsort()
{
    int hh = 0, tt = 0;
    //d[i]存储点i的入度
    for(int i = 1; i <= n; i ++)
    {
        if(d[i] == 0)
            que[tt++] = i;
    }
    while(hh < tt)
    {
        int t = que[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j]--;     //上一个节点被删除,那么它下一个点入度就减1
            if(!d[j])
                que[tt++] = j;
        }
    }
    // 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
    if(tt == n)    
        return true;        
    return false;  
}

13.快速幂

求 m^k mod p,时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

14.线性筛法求素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;		//primes[j]一定是primes[j]*i的最小质因子
            if (i % primes[j] == 0) break;		//满足这个条件时说明primes[j]一定是i的最小质因子,也一定是primes[j]*i的最小质因子
        }
    }
}

15.KMP

KMP —— 模板题 Acwing 831.KMP字符串

// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度

//求模式串的Next数组:
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

三、比赛时注意规范(对于选择C或C++语言的选手)

1.long long的输入输出

//在蓝桥杯里面long long 的输入输出:
long long a;
scanf("%I64d",&a);
printf("%I64d",a);
//或者
cin >> a;
cout << a;

2.可以使用万能头文件

#include<bits/stdc++.h>

3.最后不要忘记return 0

4.蓝桥杯最大栈空间为256MB,也就是说你最大可以开1e7的数组空间

5.各种数据类型数据范围

unsigned int 0~4294967295 // 9及以下位数都可装
int -2147483648~2147483647 // 9及以下位数都可装
unsigned long 0~4294967295 // 9及以下位数都可装
long -2147483648~2147483647 // 9及以下位数都可装
long long的最大值:9223372036854775807 // 18及以下位数都可装 19位也差不多
long long的最小值:-9223372036854775808 // 18及以下位数都可装 19位也差不多
unsigned long long的最大值:18446744073709551615 //20位
// 下面用的可能没有接触过, 但存在, 有上面的就够了, 下面和上面的long long 是一样的。
__int64的最大值:9223372036854775807
__int64的最小值:-9223372036854775808
unsigned __int64的最大值:18446744073709551615

6.一些简单的时间优化

// 位运算符的应用
// 如:
int n = 30;
int i =  n * 2;
int c =  n / 16;
// 可以更改为
int i = n << 1; // 相信我会快。
int c =  n >> 4;

// 如:
int i = 100;
while(i % 2 == 1){// 对于for循环同样使用。
i--;
}
// 改为
while(i & 1){ // 用位运算代替
--i;// 前自减/增 比 后自减/增快。
}

// 如:
int i = 0;
int x = i--;
// 改为
int x = i;
--i;// 这样结果一样, 但编译后,会少一条汇编指令。

7.其他

对于填空题,如果有些不知道如何用代码实现,要尽可能的利用身边的一切资源,比如Excel,手算等等。

对于一些做不出来的题,比如有想法但不知道如何优化时间复杂度的题,暴力去解也要提交上。这样有可能得一定的分数。

还有就是,不要忘记带准考证、身份证、笔。~最重要的是脑子。

参考来源:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • Dungeon Master POJ - 2251(bfs)

    _DIY
  • CF: Long Number

    分析1:题目原文中有这么一句“You can perform the following operation no more than once: choose...

    _DIY
  • 一遍记住Java常用的八种排序算法与代码实现

    对Java技术,架构技术感兴趣的同学,欢迎加QQ群668041364,一起学习,相互讨论。 群内已经有小伙伴将知识体系整理好(源码,笔记,PPT,学习视频),欢...

    java爱好者
  • 一遍记住Java常用的八种排序算法

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    Java旅途
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • LeetCode 164. Maximum Gap (排序)

    题解:首先,当然我们可以用快排,排完序之后,遍历一遍数组,就能得到答案了。但是快速排序的效率是O(n* logn),不是题目要求的线性效率,也就是O(n)的效率...

    ShenduCC
  • 图论--拓扑排序--判断一个图能否被拓扑排序

    拓扑排序的实现条件,以及结合应用场景,我们都能得到拓扑排序适用于DAG图(Directed Acyclic Graph简称DAG)有向无环图, 根据关系我们能得...

    风骨散人Chiam
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768

扫码关注云+社区

领取腾讯云代金券