蓝桥杯——算法篇

你的名字 2023-09-26 16:03 34阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~*

## 一、大概情况 ##

1排序是学的思想，比赛的时候都是用sort，但是你学的快排和归并会在一些题目中用到这些思想，比如快排学的是分治思想，归并学的是两个数组分治思想

2高精度我也不想背，但是蓝桥杯考过，不过到时候你写ll骗分也能拿省一

3省一暴力就可以，暴力也不是纯暴力，要有些优化的暴力，求稳的话要学习dp（01背包，线性dp，区间dp，数位，状态机，树形，三角形模型），数论（分解质因数，筛素数），图论（最短路），数据结构（单调栈，单调队列，trie，线段树），基础算法那一章都要学，还有贪心那章，掌握这些省一稳了，甚至国赛也能拿b组国一，加油吧，一年够了

## 二、2021年题目（了解有哪些题型）    ##

1.  卡片（填空题）
2.  直线（填空题）
3.  货物摆放（填空题）
4.  路径（填空题）
5.  [回路计数][Link 1]（填空题）
6.  砝码称重（编程题）
7.  [异或数列][Link 2]（编程题）
8.  左孩子右兄弟（编程题）
9.  括号序列（编程题）
10. 分果果（编程题）

## 三、必备算法（欧几里得算法） ##

> [欧几里得算法][Link 3]又称辗转相除法，是指用于计算两个[非负整数][Link 4]a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
> 
>     int gcd(int a,int b)
>     {
>         return b == 0 ? a : gcd(b,a%b);
>     }

## 四、真题 ##

**题目描述：**  
如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。  
例如，4/3 ， 5/2 ，1/8 ，7/1都是既约分数。  
请问，有多少个既约分数，分子和分母都是1到2020之间的整数(包括1 和2020)?

普通暴力算法解题：

#include <bits/stdc++.h>
    using namespace std;
    int gong(int a,int b)
    {
        int c;
        c= min(a,b);
        while(c)
        {
            if(a%c==0&&b%c==0)
            {
                break;
    
            }
            else
                c--;
        }
        return c;
    }
    
    int main()
    {
        int sum=0;
        for (int i=1;i<=2020;i++)
        {
            for(int j=1;j<=2020;j++)
            {
                int a;
                a=gong(i,j);
                if(a==1)
                {
                    sum++;
                }
            }
        }
        cout<<sum;
    }

欧几里得算法解题：

#include <bits/stdc++.h>
    using namespace std;
    int gcd(int a,int b)
    {
        return b == 0 ? a : gcd(b,a%b);
    }
    
    int main()
    {
        int sum=0;
        for (int i=1;i<=2020;i++)
        {
            for(int j=1;j<=2020;j++)
            {
                int a;
                a=gcd(i,j);
                if(a==1)
                {
                    sum++;
                }
            }
        }
        cout<<sum;
    }

答案：

2481215

### **心得总结：** ###

我们如果用第一种普通解法的话，时间复杂度很大，会运行很长时间，如果采用欧几里得算法，时间复杂度会减少很多。但这是一道填空题最后算出答案就好，使用对于这道题，俩种方法都可，欧几里得算法是一道技巧，用来算最大公约数。

对于我的普通方法，则是把i，j传入函数，计算出两个数的最小公倍数，再判断是否为一，为一的话，sum就会加一。输出sum的值即可。

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[Link 1]: https://www.zhihu.com/search?q=%E5%9B%9E%E8%B7%AF%E8%AE%A1%E6%95%B0&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A2388988914%7D
[Link 2]: https://www.zhihu.com/search?q=%E5%BC%82%E6%88%96%E6%95%B0%E5%88%97&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A2388988914%7D
[Link 3]: https://www.zhihu.com/search?q=%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A2389668612%7D
[Link 4]: https://www.zhihu.com/search?q=%E9%9D%9E%E8%B4%9F%E6%95%B4%E6%95%B0&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A2389668612%7D