【蓝桥杯】蓝桥杯算法复习（五）

😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！💪💪💪

在这里插入图片描述

文章目录

前言
蓝桥杯复习（五）
总结

前言

本文适合有一定算法基础，但是由于各种原因已经很久没有敲代码的同学。本文以复习+练习为主，旨在通过练习算法题快速复习已经遗忘的算法。即使不是参加蓝桥杯的同学，如果符合上面的条件，依然可以参考本文进行复习。

如果你是新手，可以参考白晨的算法专栏进行学习。

如果你想系统性进行复习，可关注白晨的蓝桥杯专栏进行学习。

本期是本系列的最后一期，因为在写文章的明天就要蓝桥杯比赛了，祝愿各位都能取得自己满意的成绩🤩。

蓝桥杯复习（五）

一、数学期望

复习

数学期望是描述随机变量平均取值的概念，具有以下性质：

线性性质：设X和Y是两个随机变量，a和b是常数，则有：
$E (a X + bY) = a E (X) + b E (Y)$

非负性质：对于任何随机变量X，有：
$\geq 0$

单调性质：如果随机变量X和Y满足X ≤ Y，则有：
$\leq E(Y)$

常数性质：对于任何常数c，有：
$E (c) = c$

加法性质：如果随机变量X和Y独立，则有：
$E (X + Y) = E (X) + E (Y)$

常数倍性质：如果随机变量X和Y独立，并且a和b是常数，则有：
$E (a X + bY) = a E (X) + b E (Y)$

凸性质：对于任何随机变量X和Y，以及任意两个常数a和b，有：
$\geq aE(X) + bE(Y)$
当且仅当a和b非负，并且a + b = 1时取等号。

Jensen不等式：设f(x)是凸函数，则对于任何随机变量X，有：
$\geq f(E[X])$
当且仅当f(x)是线性函数时取等号。

练习：收集卡牌

🍬题目链接：收集卡牌

🍎算法思想：

本题是状态压缩DP+数学期望+记忆化搜索的结合，本身题目比较难。

首先说一下状态压缩DP：

状态表示：f(st, coins)

st：表示当前已经获得的卡牌的集合状态，使用二进制位表示，其中第 i 位为 1 表示已经获得第 i 种卡牌，为 0 表示尚未获得。
coins：表示当前已经获得的硬币数量。
f(st, coins)：从st，coins状态转移到11...111，0状态步数的数学期望。

状态划分：

按照下一次抽到的卡来划分，可以分为n种状态，此时的步数+1，状态根据下一个所抽卡片进行变化。

下面是状态为01011，2状态的状态划分：（这里st表示从右到左为第一种卡到最后一种卡）

状态转移：

首先进行一下本状态的数学推导：

可以得到状态转移方程：
$f(st,cions) = p_1*(f(st_1, cions_1) + 1)+...+p_n*(f(st_n, cions_n) + 1)$
使用记忆化搜索和剪枝可以大大加快效率，比如一共有10种卡，5个硬币可以换一种卡，已经抽到8种卡了，现在coins最多为9个，不能再多了，10个硬币及以上的状态为非法状态，因为小林是绝对聪明的，满足上面的条件就会自动结束。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 16, M = 1 << N;

int n, m;
double p[N], f[M][N * 5 + 1];

// st--二进制状态，表示当前有的卡牌种类
// coins--当前硬币数
// r--未获得的卡牌种类数
double dp(int st, int coins, int r)
{
    double& v = f[st][coins];
    if (f[st][coins] > 0) return v; // 记忆化搜索
    if (coins >= r * m) return v = 0; // coins大于等于购买未获得卡牌的的硬币，进行剪枝
    
    v = 0;
    for (int i = 0; i < n; ++i) { // 遍历下次抽卡的情况
        if (st >> i & 1) v += p[i] * (dp(st, coins + 1, r) + 1); // 已经有这个卡了，coins数+1
        else v += p[i] * (dp(st | (1 << i), coins, r - 1) + 1); // 没有这个卡，更新st，并且没有的卡r-1
    }
    
    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < n; ++i) scanf("%lf", &p[i]);
    
    memset(f, -1, sizeof(f));
    printf("%.10lf", dp(0, 0, n));
    return 0;
}

二、欧拉函数

复习

最大公约数——辗转相除法

// 辗转相除法
#include <iostream>

using namespace std;

// 辗转相除法：证明见百度

int get_comdiv(int a, int b)
{
    // 迭代 (a, b) = (b, a % b) ，直到 b 为 0，此时a为最大公约数
    return b ? get_comdiv(b, a % b) : a;
}

int main()
{
    int n;
    scanf("%d", &n);

    while (n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        printf("%d\n", get_comdiv(a, b));
    }
    return 0;
}

欧拉函数

欧拉函数（Euler’s totient function）通常表示为φ(n)，它是小于或等于n的正整数中与n互质的数的个数。直接用公式求解的话，可以通过分解n为质因数的乘积来计算。如果n的质因数分解为 $p_1^{a_1} * p_2^{a_2} * ... * p_k^{a_k}$ ，那么 $φ(n) = n * (1 - 1/p_1) * (1 - 1/p_2) * ... * (1 - 1/p_k)$ 。

举个例子，如果要计算φ(10)：
10 = 2 * 5
φ(10) = 10 * (1 - 1/2) * (1 - 1/5) = 10 * (1/2) * (4/5) = 4

因此，10以内与10互质的数的个数为4个。

如果你有一个特定的数n想要求互质数的个数，你可以分解n为质因数的乘积，然后应用上述公式即可求得互质数的个数。

两数互质定义：两个或多个整数的公因数只有1的非零自然数。

欧拉函数的推导思路就是去掉1~N中，N的质因数的倍数，如一个质因数为 2，N * 1/2 就是质因数2的数，结果一定为整数，因为N的质因数才会被计算。由于质因数间也有重复，比如 6 会被 2，3都减一遍，所以最后还要加上 N * 1/(2 * 3)。

同理，加上的数中，也有重复比如 30，被2，3，5各减了1遍，被23，25，3*5加了一遍，但是应该是要减去这个数的，所以要再减去 N 1/(2*3*5)。

上面的过程不断迭代。

所以
$cnt = N - N/p_1 - N/p_2 -...- N/p_k + N / (p_1*p_2) + N / (p_1* p_3) +....+ N / (p_{k-1}*p_k) - N / (p_1*p_2*p_3) - ... - N/(p_{k-2}*p_{k-1}*p_k) + ......$
整合得欧拉公式： $cnt = N(1-1/p_1)(1-1/p_2)...(1-1/p_k)$

int eluer(int x)
{
    int cnt = x;
    for (int i = 2; i <= x / i; ++i)
    {
        if (x % i == 0)
        {
            while (x % i == 0) x /= i;
            cnt = cnt / i * (i - 1);
        }
    }

    if (x > 1) cnt = cnt / x * (x - 1);
    return cnt;
}

线性筛欧拉

这个本题用不到，不够顺便复习一下

// 筛法求欧拉：当x为质数时，eluer[x] = x - 1
// 当 x % primes[j] == 0时，primes[j] 为 x * primes[j] 和 x 的最小质因数，所以由eluer公式得 eluers[x * primes[j]] = eluers[x] * primes[j]
// 当 x % primes[j] != 0时，primes[j] 为 x * primes[j] 的最小质因数，所以由eluer公式得 eluers[x * primes[j]] = eluers[x] * primes[j] * (1 - 1/primes[j])

int n;

int primes[N], eluers[N];
bool book[N];
int cnt;
long long res;

void get_eluers()
{
    eluers[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!book[i])
        {
            primes[cnt++] = i;
            eluers[i] = i - 1;
        }

        for (int j = 0; primes[j] <= n / i; ++j)
        {
            book[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                eluers[i * primes[j]] = eluers[i] * primes[j];
                break;
            }
            eluers[i * primes[j]] = eluers[i] * (primes[j] - 1);
        }
    }

    for (int i = 1; i <= n; ++i) res += eluers[i];
}

练习：最大公约数

🍬题目链接：最大公约数

🍎算法思想：

设d=gcd(a, m)=gcd(a + x, m)，d可以整除a、m、a+x，则d可以整除x。

再设a'=a/d、m'=m/d、x'=x/d，可得gcd(a' + x', m') = 1，如果gcd(a' + x', m') != 1说明还有最公倍数，与题目相违。

现在题目就转换为了求a' + x'与m'互质，a'是一定的，则要求满足上面条件的x'。

换句话说，求a'到a'+m'-1中共有多少个数与m'互质。

由辗转相除法可得gcd(k, m') = gcd(k + m', m')，说明同模m'的情况下，k和k+m'与m'的最大公约数是相同的，所以a'~a'+m'-1可以转化为0~m'中共有多少个数与m'互质，见下图。

所以，题目就转化为了m'与0~m'中多少个数互质，直接使用欧拉公式求解即可。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

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

LL eluer(LL m)
{
    LL res = m;
    
    for (int i = 2; i <= m / i; ++i) {
        if (m % i == 0) {
            res = res / i * (i - 1);
            while (m % i == 0) m /= i;
        }
    }
    
    if (m > 1) res = res / m * (m - 1);
    return res;
}

int main()
{
    int T;
    cin >> T;
    
    while (T--) {
        LL a, m;
        cin >> a >> m;
        
        m /= gcd(a, m); // 求m'
        cout << eluer(m) << endl;
    }
    return 0;
}

三、最短路

复习

朴素Dijkstra算法

朴素Dijkstra算法为单源最短路算法，适合稠密图，时间复杂度为 $O(N^2)$ （N为节点个数），对于边的存储结构为 邻接矩阵。

算法思路：

1、初始化 dist数组（初始化为无限大）以及 dist[1] = 0（一号节点到自己的距离为0）；

2、遍历所有节点的dist，选出其中距离最短的节点，选中此节点加入已确定最短距离的节点；

3、根据上面确定节点的最短距离更新到达其他节点的最短距离；

4、重复2、3过程 N 次，N次迭代后，全部点的最短距离已经被确定。

const int N = 510, INF = 0x3f3f3f3f;

int n, m;

int g[N][N]; // 邻接矩阵
int dist[N]; // 存储最短距离
bool book[N]; // 是否已确定最短路

int Dijkstra() // 求1号节点到n号节点的最短距离
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    // 循环n次
    for (int i = 0; i < n; ++i)
    {
        // 选出其中距离最短的节点
        int u = -1;
        for (int j = 1; j <= n; ++j)
            if (!book[j] && (u == -1 || dist[u] > dist[j])) u = j;
        book[u] = true;

        // 更新边
        for (int i = 1; i <= n; ++i)
            if (!book[i] && dist[u] + g[u][i] < dist[i]) dist[i] = dist[u] + g[u][i];
    }

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

堆优化Dijkstra算法

堆优化Dijkstra算法为单源最短路算法，适用于稀疏图，时间复杂度为 $O (m l o g n)$ （m为边数，n为节点数），边的存储结构为邻接表。

相比于朴素版，本算法对于寻找路径最短的节点的过程进行了优化，改为了用小根堆堆存储最短路径，根据小根堆的特性，最短的路径就是堆顶元素，这样就省去了寻找最短路径的过程。

堆优化Dijkstra算法：

1、初始化dist以及g数组，dist[1] = 0，将其入堆；

2、出堆顶元素，根据新确定最短路径更新其他路径；

3、重复2过程，直到堆为空。

typedef pair<int, int> PII;

const int N = 150010, INF = 0x3f3f3f3f;

int n, m;

int g[N], e[N], ne[N], val[N], idx;// g为邻接表，e，ne，val为单链表，e存放节点序号，ne存放子节点下标，val存储权值
bool book[N]; // 此节点是否已经确定最短路径
int dist[N]; // 存储到1号节点的最短路径大小

void add(int a, int b, int w)
{
    e[idx] = b, val[idx] = w, ne[idx] = g[a], g[a] = idx++;
}

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq; // 小根堆
    pq.push({0, 1});
    
    while (pq.size())
    {
        auto t = pq.top();
        pq.pop();
        int st = t.first, node = t.second;
        // 由于题目有重边，所以可能会把一个节点更新多次，由于堆是距离小的先出，所以小边会先出确定最短路径，后面出的直接忽略即可
        if (book[node]) continue; 
        book[node] = true;
        
        for (int i = g[node]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[node] + val[i] < dist[j])
            {
                dist[j] = dist[node] + val[i];
                pq.push({dist[j], j});
            }
        }
    }
    
    if (dist[n] == INF) return -1;
    else return dist[n];
}

SPFA

SPFA算法，带负权单源最短路算法，时间复杂度一般为 $O (m)$ ，最坏为 $O (nm)$ ，本算法优化了BF算法每次遍历全部边的过程，边的存储结构为邻接矩阵。

只有 dist[a] 更新了，a->b 边才会被使用，否则不会使用a->b这条边，所以本算法存储更新过的最短路，很像Dijkstra堆优化版本

算法思路：

初始化dist数组，dist[1] = 0，将1号节点其入队
广度优先搜素，出队节点元素，遍历每个节点的出边，更新，直到队列为空

int n, m;
int g[N], e[N], ne[N], val[N], idx;
int dist[N];
bool book[N];

int SPFA()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    book[1] = true;
    
    while (q.size())
    {
        int u = q.front();
        q.pop();
        
        // 出队列以后记得更新状态
        book[u] = false;
        
        for (int i = g[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[u] + val[i] < dist[j])
            {
                dist[j] = dist[u] + val[i];
                // 防止重复添加
                if (!book[j])
                {
                    q.push(j);
                    book[j] = true;
                }
            }
        }
    }
    
    return dist[n];
}

Floyd

Floyd算法，多源最短路算法，时间复杂度为 $O(n^3)$ ，本质上是动态规划，核心代码只有四行。

状态：f[i, j, k]表示从i走到j的路径上除了i和j以外，只经过1~k号节点的所有路径的最短距离

存储：邻接矩阵

eg.

f[5, 6, 3]表示从5号节点走到6号节点只经过 1，2，3 这三个节点的最短距离

状态转移方程： $f [i, j, k] = min (f [i, j, k], f [i, k, k - 1] + f [k, j, k - 1])$

解释：i节点到j节点只经过1~k号节点的最短距离等于本身原值和 i节点到k节点只经过1~k-1号节点最短距离和k节点到j节点只经过1~k-1号节点最短距离之和的最小值。

int n, m, q;
int g[N][N];

void Floyd()
{
    // 在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

练习：奶牛回家

🍬题目链接：奶牛回家

🍎算法思想：

本题数据较小，用朴素Dijkstra或者堆优化Dijkstra算法都可以，这里我们使用朴素Dijkstra。

🍊具体实现：

// 最短路：奶牛回家
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 60;

int p;
int g[N][N], dist[N];
bool st[N];

int get(char c)
{
    if (c <= 'Z') return c - 'A' + 1;
    else return c - 'a' + 27;
}

void dijkstra()  
{
    memset(dist, 0x3f, sizeof(dist));
    dist[26] = 0;
    
    for (int i = 0; i < 51; ++i) 
    {
        int t = -1;
        
        for (int j = 1; j <= 52; ++j)
            if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        
        st[t] = true;
        
        for (int j = 1; j <= 52; ++j)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}


int main()
{
    cin >> p;
    memset(g, 0x3f, sizeof(g));
    
    while(p--) 
    {
        char a, b;
        int z;
        cin >> a >> b >> z;
        int x = get(a), y = get(b);
        g[x][y] = g[y][x] = min(g[x][y], z);
    }
    
    dijkstra();
    
    int k = 1;
    for (int i = 1; i <= 25; i ++ )
        if (dist[k] > dist[i])
            k = i;

    cout << (char)(k - 1 + 'A') << ' ' << dist[k] << endl;
    return 0;
}

四、贪心

复习

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即贪心）的选择，从而希望最终能够达到全局最优解的算法策略。它通常用于解决一些最优化问题，比如最小生成树、最短路径、任务调度等。

贪心算法的核心思想是通过局部最优解的选择来构建全局最优解。它并不保证能够获得全局最优解，但在某些情况下能够快速地找到一个较好的解决方案。贪心算法通常具有高效性，因为它们通常只需做出局部的、不可回退的选择。

然而，贪心算法并不适用于所有问题，有些问题需要更复杂的算法来找到最优解。贪心算法适用的问题通常具有贪心选择性质和最优子结构性质，即问题的最优解可以通过一系列局部最优解的组合得到。

贪心非常难想，而且证明比较困难，并且没有固定模板。

练习：修理牛棚

🍬题目链接：修理牛棚

🍎算法思想：

这道题正着比较难想，但是倒着很好想，什么叫倒着想呢？

先拿一块长度足够长的木板，把有牛的牛棚全封住，再根据最大木板个数，在原来的木板上打洞（就是找最多连续没有牛的牛棚），将其长度减去。

最后，删到满足最大木板数即可。

实现见代码：

🍊具体实现：

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

int m, s, c;
int a[N];

int main()
{
    cin >> m >> s >> c;
    for (int i = 0; i < c; ++i) cin >> a[i];
    // 将有牛的牛棚按序号从小到达排列
    sort(a, a + c);
    
    // 第一块木板的长度就是 最后一个有牛的牛棚序号-第一个有牛的牛棚序号-1
    int res = a[c - 1] - a[0] + 1;
    priority_queue<int> pq; // 存放连续没有牛的牛棚长度
    
    // 计算连续没有牛的牛棚长度
    for (int i = 0; i + 1 < c; ++i) pq.push(a[i + 1] - a[i] - 1);
    
    // 共要打m-1个洞，这样就有m个木板了，每次选连续没有牛的牛棚长度最长的减
    m--;
    while (pq.size() && m--) 
    {
        res -= pq.top();
        pq.pop();
    }
    
    cout << res << endl;
    return 0;
}