當前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

蓝桥杯常考算法 + 知识点

發布時間：2023/12/13 综合教程 21 生活家

生活随笔收集整理的這篇文章主要介紹了蓝桥杯常考算法 + 知识点小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

素數判斷/素數篩

埃氏篩：

const int N=10010;
int prime[N];
bool book[N]; // =1 表示不是素數

void w()
{
    book[0]=book[1]=1;
//    book[2]=1;
    int cnt=0;
    for(int i=1; i<=N; i++)
    {
        if(!book[i])
        {
            prime[cnt++]=i;
            for(int j=i+i; j<=N; j+=i);
            book[j]=1;
        }
    }
}

樸素判斷素數：

int w(int n)
{
    for(int i=2; i<=sqrt(n); i++)
        if(i%n==0) return 0; //不是素數
    return 1; //是素數
}

進制轉換

int main()
{
    printf("%03d
",'a'); // 保留3位高位補零

    int x=10;
    printf("%03d
",x); // 十進制輸出
    printf("%05o
",x);// 八進制輸出
    printf("%05x
",x); // 十六進制輸出
    
    cout << "35的8進制:" << std::oct << 35<< endl;
    cout << "35的10進制" << std::dec << 35 << endl;
    cout << "35的16進制:" << std::hex << 35 << endl;
    cout << "35的2進制: " << bitset<8>(35) << endl;      //<8>：表示保留8位輸出
    return 0;
}

參考博客：

https://www.cnblogs.com/zwjjj/p/9953718.html

https://blog.csdn.net/MOU_IT/article/details/89060249

Dijkstra

bool book[N];
int dis[N];

void dijkstra(int x)
{
    for(int i=1; i<=n; i++)
        dis[i]=e[1][i],book[i]=0;
    book[x]=1;
    for(int i=2; i<=n; i++)
    {
        int minn=inf,u;
        for(int j=1; j<=n; j++)
        {
            if(!book[j]&&dis[j]<minn)
                u=j,minn=dis[j];
        }
        book[u]=1;
        for(int k=1; k<=n; k++)
        {
            if(e[u][k]<inf&&dis[u]+e[u][k]<dis[k])
                dis[k]=dis[u]+e[u][k];
        }
    }
}

Floyd

SPFA

KMP

查找子串（模式串）在原串中出現了幾次。

char s[10020],t[1000020];
int lens,lent;
int nextt[10020];
void getnext()
{
    int i=0,j=-1;
    nextt[0]=-1;
    while(i<lens)
    {
        if(j<0||s[i]==s[j])
        {
            nextt[++i]=++j;
        }
        else
            j=nextt[j];
    }
}

int kmp()
{
    int i=0,j=0,ans=0;
    while(i<lent)
    {
        if(j<0||t[i]==s[j])
        {
            i++;
            j++;
        }
        else
            j=nextt[j];
        if(j==lens)
        {
            ans++;
            j=nextt[j];
        }
    }
    return ans;
}

背包

01背包：

for(int i=0; i<n; i++)
{
    for(int j=m; j>=w[i]; j--)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
cout<<dp[m]<<endl;

完全背包：

// n物品種數 m背包容量
for(int i=1; i<=n; i++)
{
    for(int j=w[i]; j<=m; j++)   // 枚舉物品重量
        dp[j]=max(dp[j], dp[j-w[i]]+v[i]);
}
cout<<dp[m]<<endl;

多重背包：

for(i=0; i<n; i++) //大米種類
{
    for(j=0; j<daishu[i]; j++)//每種大米的袋數
    {
        for(k=m; k>=p[i]; k--)//從總金額開始
            dp[k]=max(dp[k],dp[k-p[i]]+w[i]);
    }
}
printf("%d
",dp[m]);

全排列

int main()
{
    int a[5]={2,1,3};
    //sort(a,a+3);//輸出全部sort，輸出接下去的不用；
    do{
    cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    }while(next_permutation(a,a+3));
    // 與此對應的是：
    //prev_permutation：求上一個排列組合
    
    return 0;
}

快速冪

ll ksm(ll x,ll n,ll mod)
{
    ll w=1;
    while(n)
    {
        if(n&1) 
            w=w*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return w;
}

矩陣快速冪

一般并查集

帶權并查集

int f[N];

int getf(int x)
{
    if(f[x]==x)
        return x;
    int fu=f[x]; // 存f[x]的父節點
    f[x]=getf(f[x]); //f[x] = 其祖先 // 這個語句不要放到return那去寫，否則wa ，！？？為啥我不造
    d[x]+=d[fu];//更新x到根節點的距離 -> 它到它父節點的距離+父節點到根節點的距離
    return f[x];
//  return f[x]=getf(f[x]);
}

void merge(int x,int y)
{
    int t1=getf(x),t2=getf(y);
    if(t1!=t2) f[t2]=t1;
}

int main()
{
    for(int i=1; i<=N; i++)
        f[i]=i,d[i]=0;

    for(int i=0; i<m; i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        int t1=getf(x),t2=getf(y);
        if(t1==t2)
        {
            if(d[x]+z==d[y])
                ans++;
        }
        else if(t1!=t2)
        {
            merge(x,y);
            d[t2]=d[x]+z-d[y];
        }
    }
    
    return 0;
}

二分

手寫：

int L=1,R=n,x; // x是我們需要在給定序列a找的目標值
while(L<=R)
{
    int mid=(L+R)>>1;
    if(a[mid]>x)
        R=mid-1;
    else if(a[mid]>x)
        L=mid+1;
    else
    {
        cout<<mid<<end;
        break;
    }
}

調用：

#include <bits/stdc++.h>
using namespace std;

//upper_bound查找第一個大于某個元素的位置
//lower_bound查找第一個大于或等于某個元素的位置
// 返回下標位置

int main()
{
    int a[10] = {0, 1, 3, 5, 7, 6, 2, 4, 8, 9};
    sort(a,a+10); // 需要排序

    int w=upper_bound(a,a+9,4)-a; // 找數字4
    cout<<w<<endl; // 5

    w=upper_bound(a,a+9,90)-a; // 找數字90
    cout<<w<<endl;// 9

    w=lower_bound(a,a+9,4)-a;// 找數字4
    cout<<w<<endl; // 4

    w=lower_bound(a,a+9,90)-a; // 找數字90
    cout<<w<<endl; // 10

    return 0;
}

最大公約數

手寫：

int gcd(int x,int y)
{
    return x==0?y:gcd(y%x,x);
}
 
int mxin()
{
    int x,y;
    cin>>x>>y;
    cout<<gcd(x,y)<<endl;
    
    return 0;
}

調用：

#include<algorithm>

int x,y;
cout<<__gcd(x,y)<<endl;

最小公倍數

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f

int main()
{
    ll a,b;
    cin>>a>>b;
    ll x=a*b;
    cout<<x/__gcd(a,b)<<endl;
    return 0;
}

浮點數比較

if(fabs(x1*y1-x2*y2)<0.000001) 
//判斷浮點數是否相等用一個非常小的數即可
//如果用==可能得不到結果。fabs(float x)浮點數x的絕對值   
//比如：藍橋杯-雞蛋的數目

計算器

x年x月x日x時x分x秒 ~ x年x月x日x時x分x秒：里面有一個叫做日期時間的東西。

計算機當成普通轉換器就行。

JAVA大數

首先要會打開、運行、調試、必寫的頭文件、c++中的main()在JAVA怎么寫、導入包、包中有什么等。

會一些板子就行（BigInteger、BigDicimal、卡特蘭數等）

文件讀入讀出

會C/C++的就行，因為萬一碰到給了txt一堆數據的題目。

EXCEL

可視化打表

當成科學計算器用，需要記住一些函數。

數據較小的BFS。

畫圖。

find查找子串

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string a="abcd123456789";
    string b="123";
    cout<<a.find(b)<<endl; //a里面是否包含子串b 輸出4
    //有:返回首次出現位置
    //沒有:返回string::npos
    if(a.find("cba")==string::npos)
        cout<<-1<<endl;//輸出-1，但是是無法輸出string::npos的
    cout<<a.find(b,3);//從指定的位置3開始查找 輸出4
    return 0;
}

判斷閏年

if(y%4==0&&y%100!=0)||(y%400==0)

子集

前綴和

隊列和優先隊列

DFS

BFS

常用公式

鄰接表

二分圖

Prim

Kruskal

分解質因數

歐幾里得

（輾轉相除法）

可以調用 __gcd(a,b) ; 或者手寫一個函數，函數如下：

int gcd(int a,int b)
{
    if(b==0) return a;
    return(b,a%b);
}

擴展歐幾里得

求(ax+by=gcd(a,b))的整數解(x)、(y)，同時可以求出最大公因數。

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int yin=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-(a/b)*y;
    //x1=y2,
    //y1=x2-(a/b)*y2;
    return yin;
}

int main()
{
    int a,b,x,y;
    scanf("%d %d",&a,&b);
    int maxx=exgcd(a,b,x,y);//最大公因數
    return 0;
}

貪心

拓撲排序

https://www.cnblogs.com/OFSHK/p/11511010.html

計算組合數

https://blog.csdn.net/GD_ONE/article/details/104953289

大數加減乘除

位運算

排序

枚舉

https://www.cnblogs.com/OFSHK/p/13726381.html

DP

斐波那契

https://www.cnblogs.com/OFSHK/p/11258890.html

字符串匹配

字符串其他問題

總結

以上是生活随笔為你收集整理的蓝桥杯常考算法 + 知识点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：关于数字证书理解的简单整理以及12306
下一篇：几道比较有意思的js面试题