跳转至

其他算法

  • 注意：
  • typedef 需要定义在using下面
  • #define 需要定义在头文件哪里
  • 能使用全局变量，就使用全局变量

快速幂

 long long fastPower(long long base, long long power) {
    long long result = 1;
     while (power 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            result = result * base % 1000;
        }
        power>= 1;//此处等价于power=power/2
        base = (base * base) % 1000;
     }
    return result;
 }

线性筛

  • p是bool数组，如果是0表示是质数
  • q用来存放质数
void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!p[i]) q[++tot] = i;
        for (int j = 1; q[j] <= n / i; j ++ )
        {
            p[i * q[j]] = true;
            if (i % q[j] == 0) break;
        }
    }
}

欧拉筛

int cnt;
int primes[N];
bool st[N];
//分解质数
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}

欧几里得算法

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

KMP算法

 for (int i = 2, j = 0; i <= m; i ++ )
 {
     while (j && str[i] != str[j + 1]) j = nxt[j];
     if (str[i] == str[j + 1]) j ++ ;
     nxt[i] = j;
 }

safa 算法模板

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

using namespace std;
const int N = 2510,M=6200*2+10;//点数 边数

int n,m,S,T;
//邻接表存储树  存储元素 存储列表的next值 单链表指针
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];//循环队列 距离
bool st[N];//判重数组

void add(int a,int b,int c){//a 指向 b 权重是 c

    //被指的边   权重   多少条出口    边数
    //h[a]=idx++ 代表当前第idx个节点是被a指向的
    //ne[idx]=h[a]  代表 当a指向新节点时，上一个节点是h[a]，然后再更新一下h[a]
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;

}

void spfa(){
    memset(dist, 0x3f, sizeof dist);//初始化正无穷
    dist[S]=0;//起点处长度是0

    int hh=0,tt=1;//循环队列下标

    //记录起点   标记
    q[0]=S,st[S]=true;

    while(hh!=tt){//循环队列  头部跟尾部不相等即可

        int t=q[hh++];//取出来一个
        if(hh==N)hh=0;//如果到末尾了 则置为0

        st[t]=false;//取出来了 咱就标记一下

        //~i 的意思是i!=-1 
        //i=t的出口数
        for(int i=h[t];~i;i=ne[i]){

            int j=e[i];//得到i指向的边
            if(dist[j]>dist[t]+w[i]){//边权判断
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N)tt=0;
                    st[j]=true;
                }
            }
        }
    }

}

int main(){

    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    spfa();

    cout<<dist[T]<<endl;

    return 0;
}

prim算法模板

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

using namespace std;
const int N = 110;
int w[N][N];
bool st[N];
int dist[N];
int n;
//T. 1140
//连接光纤
int prim(){
    int res=0;
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;

    for (int i = 0; i < n; i ++ ){
        int t=-1;
        //挨个找最小值
        for (int j = 1; j <= n; j ++ )
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;

        st[t]=true;
        res+=dist[t];

        //把t->j这条路全部改为最小值
        for(int j=1;j<=n;j++)    dist[j]=min(dist[j],w[t][j]);

    }
    return res;
}

int main(){
    cin>>n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin>>w[i][j];

    cout<<prim()<<endl;

    return 0;
}

线段树

 int lowbit(int x){
     return x&-x;//求最低位
 }
 //第a个数加b
 void add(int a,int b){
     for(int i=a;i<=n;i+=lowbit(i))
        tr[i]+=b;
 }
//0~x区间和
int query(int x){
     int res=0;
     for(int i=x;i;i-=lowbit(i))res+=tr[i];
     return res;
 }

快速排序算法模板

void quick_sort(int q[], int l, int r){
 if (l= r) return;

    int i = l - 1, j = r + 1, x = q[l + r> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

图论

 void add(int a,int b,int c){
 //a 指向b价值是w
    w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
 }

// 遍历邻接表
for(int i=h[u];i!=-1;i=ne[i])

单调队列

# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
    int n, k;
    cin> n> k;
    for (int i = 0; i < n; ++ i)
    {
        scanf("%d", &a[i]);
        if (i - k + 1 q[hh]) ++ hh;                  // 若队首出窗口，hh加1
        while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若队尾不单调，tt减1
        q[++ tt] = i;                                  // 下标加到队尾
        if (i + 1= k) printf("%d ", a[q[hh]]);       // 输出结果
    }
    cout << endl;
    hh = 0; tt = -1;                                   // 重置！
    for (int i = 0; i < n; ++ i)
    {
        if (i - k + 1 q[hh]) ++ hh;
        while (hh <= tt && a[i]= a[q[tt]]) -- tt;
        q[++ tt] = i;
        if (i + 1= k) printf("%d ", a[q[hh]]);
    }
    return 0;
}

二分

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

using namespace std;
const int N = 1e5+10;
int a[N];
int n,q,tar;

int main(){
    cin>>n>>q;
    for (int i = 0; i < n; i ++ )
        cin>>a[i];

    for(int i=0;i<q;i++){
        cin>>tar;
        int l=0,r=n-1,mid=0;
        //左边二分
        while(l<r){
            mid=(r+l)>>1;
            if(a[mid]>=tar)r=mid;//r不动  l往右边来
            else l=mid+1;
        }
        if(a[l]!=tar){
            printf("-1 -1\n");
            continue;
        }
        int c=l;
        r=n-1;
        mid=0;
        //右边二分
        while(l<r){
            mid=(r+l+1)>>1;
            if(a[mid]<=tar)l=mid;//l不动,r往左边来
            else r=mid-1;
        }
        cout<<c<<' '<<l<<endl;
    }
    return 0;
}

求组合数

LL C(int a,int b){
    LL res=1;
    for(int j=1,i=a;j<=b;i--,j++){
        res=res*i/j;
        if(res>n)return res;
    }
    return res;
}

拓扑排序

void topo_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.push(i);

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        L.push_back(t);

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (!--in[j]) q.push(j);
        }
    }
}

完全背包问题 每种物品无限使用

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10,MOD=1e9;
int f[N];
int n,V;
int main(){
    cin>>n>>V;     //背包容量是V
    f[0]=0;
    while(n--){
        int v,w;
        cin>>v>>w;
        //for(int i=1;i<=n;i*=2)
            for(int j=v;j<=V;j++)
                f[j]=max(f[j],f[j-v]+w);
    }
    cout<<f[V]<<endl;
    return 0;
}

01背包

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

using namespace std;
const int N = 1010;
int f[N];
int n,V;
int v,w;

int main(){
    cin>>n>>V;
    for(int i=0;i<n;i++){
        cin>>v>>w;
        for(int j=V;j>=v;j--){
            f[j]=max(f[j],f[j-v]+w);
        }
    }

    cout<<f[V]<<endl;
    return 0;
}

例题1模板 - while循环下就是对应着它的性质

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

const int N = 4e5+10;

int primes[N];

int main(){
    int n;
    cin> n;
    for(int i = 2; i <= n; i++){
        int t = i, j = 2;
        while(t 1)
            if(t % j == 0) t /= j, primes[j]++;
            else j++;
    }
    for(int i = 1; i <= 1e4; i++)
        if(primes[i]) cout << i << " " << primes[i] << endl;
    return 0;
}

欧拉线性筛质数

#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 1e5+10;
int n, cnt;
int nums[N], primes[M];
bool st[M*N];

int main(){
    cin> n;
    for(int i = 1; i <= n; i++) cin> nums[i];

    for(int i = 2; i <= M; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= M/i; j++){  // 从小到大枚举所有质数
            st[primes[j] * i] = true;           // 只用最小质因子去筛掉合数
            // 说明primes[j]一定是i的最小质因子，则primes[j]页一定是primes[j]*i的最小质因子
            // 如果i%primes[j] != 0 的话，说明primes[j]一定小于i的所有质因子
            if(i % primes[j] == 0) break;
        }
    }

    for(int i = 1; i <= n; i++)
        if(!st[nums[i]] && nums[i] != 1) 
            cout << nums[i]<< " ";

    return 0;
}

读取一行

getline(cin,s);

拓扑排序

题目介绍：有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。 给出每个人的孩子的信息。 输出一个序列，使得每个人的孩子都比那个人后列出。

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

using namespace std;
const int N = 110,M=N*N/2;
int in[N];
int a[N];
int n;
vector<int>L;

//e 表示的是边  ne表示的是下一个指针    idx表示的是边个数
int h[N],e[M],ne[M],idx;
//使用邻接表存储图
void add(int a,int b){//无权图
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void top_sort(){
    queue<int>q;//使用队列
    //先进行一次遍历，把所有父辈塞进队列
    for (int i = 1; i <= n; i ++ )
        if(!in[i])
            q.push(i);
    //普通的入队出队
    while(q.size()){
        int t=q.front();
        q.pop();
        L.push_back(t);
        //访问邻接表即可
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!--in[j])q.push(j);
        }
    }
}

int main(){
    cin>>n;
    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i ++ ){
        int x;
        while(cin>>x,x){
            add(i,x);//i与x之间进行连边
            in[x]++;//使用in数组记录x节点的父亲个数
        }
    }

    top_sort();//拓扑排序

    for(int &i:L)// L数组用于记录结果
        cout<<i<<" ";

    return 0;
}

单源最短路 spfa算法

  • 需要注意的：如果起点是任意一个，那么这个点的dist[Start]=0; 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2510,M=6200*2+10;//点数 边数

int n,m,S,T;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];//循环队列 距离
bool st[N];//判重数组

void add(int a,int b,int c){//a 指向 b 权重是 c
    //边      权重       多少条出口    出口+1
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void spfa(){
    memset(dist, 0x3f, sizeof dist);//初始化正无穷
    dist[S]=0;//起点处长度是0
    int hh=0,tt=1;//循环队列下标
    //记录起点   标记
    q[0]=S,st[S]=true;
    while(hh!=tt){//循环队列  头部跟尾部不相等即可
        int t=q[hh++];//取出来一个
        if(hh==N)hh=0;//如果到末尾了 则置为0
        st[t]=false;//标记一下
        //~i 的意思是i!=-1 
        //i=t的出口数    
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];//得到i指向的边
            if(dist[j]>dist[t]+w[i]){//边权判断
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N)tt=0;
                    st[j]=true;
                }
            }
        }
    }
}

int main(){

    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    spfa();

    cout<<dist[T]<<endl;

    return 0;
}

评论