蓝桥杯常考算法 + 知识点

素数判断/素数筛

埃氏筛：

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