问题标题: 关于c++的一些小板子

开！

1、判断素数

函数判断法：

bool zs(int a){
    if(a==1)//特判
        return false;
    for(int i=2;i<=sqrt(a);i++)//优化
        if(!(a%i))
            return false;
    return true;
}

埃氏筛：

a[1]=false;//相当于特判
for(int i=2;i<=sqrt(m);i++){//遍历因数，sqrt()是埃氏优化
    if(a[i])
        for(int j=i*2;j<=m;j+=i)
            f[j]=1;
}

最长不下降子序列：

for(int i=1;i<=n;i++){
    f[1]=1;//可能前面没有≥它的
    for(int j=1;j<i;j++)//暴力遍历
        if(f[i]>=f[j])
            f[i]=f[j]+1;
}

最大子数组和：

for(int i=1;i<=n;i++){
    f[i]=max(a[i],f[i-1]+a[i]);//选与不选
}

会更

有像是图论之类的也可以在下面给哦！

汪宇航在2022-10-16 19:47:40追加了内容

重载运算符(例)：

bool operator ==(const node &b)const{
    return b==b.b;
}

顺便说一声，纯手打，可能有误

01背包：

for(int i=1;i<=n;i++){
    for(int j=m;j>=v[i];j--){
        f[j]=max(f[j],f[j-v[i]+w[i]]);
    }
}

完全背包：

for(int i=1;i<=n;i++){
    for(int j=v[i];j<=m;j++){
        f[j]=max(f[j],f[j-v[i]+w[i]]);
    }
}

汪宇航在2022-10-16 19:52:03追加了内容

多重背包

for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
        for(int k=1;k<=min(j/v[i],p[i]);k++)//个数
            f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);

混合背包和稀泥和一下

汪宇航在2022-10-17 16:50:35追加了内容

Floyed:

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            diff[i][j]=min(diff[i][j],diff[i][k]+diff[j][k]);

注：dijkstra因为主体太长而且题目在有主体非常容易写，所以这里只发松弛操作

dijkstra：

for(int i=1;i<=n;i++)
    if(!found[i] && dis[u]+g[u][i]<dis[i])
        dis[i]=dis[u]+g[u][i];