算法模板

忘是亡心i 2022-02-02 10:49 174阅读 0赞

### 文章目录 ###

*  常用头文件
 *  DP部分
 *   *   *  01背包
         *  完全背包
         *  多重背包
         *  LIS
         *  LCS
 *  图论
 *   *  最短路
     *   *  DIjkstra
 *  数据结构
 *   *  主席树
 *  其它
 *   *  大数
     *   *  N!的位数
         *  N！
         *  Fib

# 常用头文件 #

/**
     *　　　　　　　　┏┓　　　┏┓+ +
     *　　　　　　　┏┛┻━━━┛┻┓ + +
     *　　　　　　　┃　　　　　　　┃
     *　　　　　　　┃　　　━　　　┃ ++ + + +
     *　　　　　　 ████━████ ┃+
     *　　　　　　　┃　　　　　　　┃ +
     *　　　　　　　┃　　　┻　　　┃
     *　　　　　　　┃　　　　　　　┃ + +
     *　　　　　　　┗━┓　　　┏━┛
     *　　　　　　　　　┃　　　┃
     *　　　　　　　　　┃　　　┃ + + + +
     *　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting
     *　　　　　　　　　┃　　　┃ + 　　　　神兽保佑,代码无bug
     *　　　　　　　　　┃　　　┃
     *　　　　　　　　　┃　　　┃　　+
     *　　　　　　　　　┃　 　　┗━━━┓ + +
     *　　　　　　　　　┃ 　　　　　　　┣┓
     *　　　　　　　　　┃ 　　　　　　　┏┛
     *　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +
     *　　　　　　　　　　┃┫┫　┃┫┫
     *　　　　　　　　　　┗┻┛　┗┻┛+ + + +
     */

/*--------- Hongjie ----------*/
    // #include<bits/stdc++.h>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<string>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e5+7;
    
    
    int main(){
        
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
    
    
    
            return 0;
    }

# DP部分 #

### 01背包 ###

int dp[MAXN];
    for(int i=0;i<n;i++)
        for(int j=W;j>=w[i];j--)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    printf("%d\n",dp[W]);

### 完全背包 ###

int dp[MAXN];
    for(int i=0;i<n;i++)
        for(int j=w[i];j<=W;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    printf("%d\n",dp[W]);

### 多重背包 ###

（第i种背包最多可以选择m\[i\]种）

for(int i=0;i<n;i++){
        
        int num=m[i];//用来找a 
        for(int k=1;num>0;k<<=1){
        
            int mul=min(k,num);
            for(int j=W;j>=w[i]*mul;j--){
        
                dp[j]=max(dp[j],dp[j-w[i]*mul]+v[i]*mul); 
            }
            num-=mul;
        }
    }
    printf("%d\n",dp[W]);

### LIS ###

最长递增子序列（长度+打印路径）

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=105;
    int a[MAXN];
    int dp[MAXN];
    int n;
    int vis[MAXN];
    void dfs(int pos)//打印路径 
    {
        
    	if(pos==-1)	return  ;
    	dfs(vis[pos]);
    	printf(" %d",pos+1);//这里是正序输出编号(从1开始的) 
    }
    int main()
    {
        
    	while(~scanf("%d",&n)&&n)
    	{
        
    		for(int i=0;i<n;i++)
    			scanf("%d",&a[i]);
    		memset(dp,0,sizeof(dp));
    		memset(vis,-1,sizeof(vis));
    		int res=0;
    		int pos=-1;		
    		for(int i=0;i<n;i++)
    		{
        
    			dp[i]=1;
    			for(int j=0;j<i;j++)
    				if(a[i]>a[j])
    				{
        
    					if(dp[i]<dp[j]+1)
    					{
        
    						dp[i]=dp[j]+1;
    						vis[i]=j;//vis[i]=j 表示以a[i]为结尾的LIS的上一个元素是a[j]		
    					}
    				}	
    			if(res<dp[i])
    			{
        
    				res=dp[i];
    				pos=i;//找到LIS的最后一个结点 
    			}
    		}
    		printf("The number is %d:",res);//输出LIS的长度 
    		dfs(pos);
    		printf("\n");
    	}
    	return 0;
    }

### LCS ###

最长公共子序列（长度+打印路径）

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int  maxn=1009;
    char a[maxn],b[maxn];
    int path[maxn][maxn],dp[maxn][maxn];//path 记录路径 
     
    void lcs(int i,int j)//打印路径 
    {
        
    	if(i==0||j==0)	return ;//结束标志，a或者b只要有一个找完了，就不在找了 
    	if(path[i][j]==1)//path是1的时候输出这个字符 
    	{
        
    		lcs(i-1,j-1);//因为是从后往前找的 
    		printf("%c",a[i-1]);//所以这句得写到递归函数下边 
    	 } 
    	else if(path[i][j]==2)
    		lcs(i-1,j);
    	else 
    		lcs(i,j-1);
    	return ;
    }
     
    int main()
    {
        
    	while(~scanf("%s %s",a,b))
    	{
        
    		memset(dp,0,sizeof(dp));
    		int m=strlen(a);
    		int n=strlen(b);
    		for(int i=1;i<=m;i++)
    			for(int j=1;j<=n;j++)
    				if(a[i-1]==b[j-1])
    				{
        
    					dp[i][j]=dp[i-1][j-1]+1;
    					path[i][j]=1;
    				}
    				else if(dp[i-1][j]>dp[i][j-1])
    				{
        
    					dp[i][j]=dp[i-1][j];
    					path[i][j]=2;
    				}
    				else
    				{
        
    					dp[i][j]=dp[i][j-1];	
    					path[i][j]=3;
    				}
    		
    		lcs(m,n);		
    		printf("\n"); 
    //		printf("\n%d\n",dp[m][n]);//输出最长子序列的长度 
    	}
    	return 0;

# 图论 #

## 最短路 ##

### DIjkstra ###

/*
    	邻接链表写法 
    	
    */
     
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    typedef pair<int,int> P;
    const int maxn=1e3+5;
    const int INF=0x3f3f3f3f;
     
    struct edge
    {
        
    	int to,cost;
    	edge(){
        }
    	edge(int _to,int _cost)
    	{
        
    		to=_to;
    		cost=_cost;
    	}
    };
     
    vector<edge> G[maxn];
    int d[maxn];
     
    void dijkstra(int s)
    {
        
    	memset(d,0x3f,sizeof(d));
    	d[s]=0;
    	priority_queue<P,vector<P>,greater<P> >que;
    	que.push(P(0,s));
    	while(que.size())
    	{
        
    		P p=que.top();que.pop();
    		int v=p.second;
    		if(d[v]<p.first)	continue;
    		for(int i=0;i<G[v].size();i++)
    		{
        
    			edge e=G[v][i];
    			if(d[e.to]>d[v]+e.cost)
    			{
        
    				d[e.to]=d[v]+e.cost;
    				que.push(P(d[e.to],e.to));
    			}
    			
    		}
    	}
    }
     
    int main()
    {
        
    	int n,m;
    	while(~scanf("%d %d",&n,&m)&&(n|m))//n is number of  vertex  ,  m is number of edge
    	{
        
    		for(int i=0;i<maxn;i++)	G[i].clear();//一定要记得初始化邻接链表，不然会错 
    		for(int i=0;i<m;i++)//
    		{
        
    			int x,y,z;
    			scanf("%d %d %d",&x,&y,&z);
    			G[x].push_back(edge(y,z));
    			G[y].push_back(edge(x,z));
    		}
    		dijkstra(1);
    		printf("%d\n",d[n]); 
    	}
    	return 0;
    }

# 数据结构 #

## 主席树 ##

#include<cstdio>
    #include<vector>
    #include<iostream>
    #include<algorithm>
    
    using namespace std;
    /*
    求区间第k大
    poj - 2104
    */
    
    const int MAXN = 1e5+7;
    int n, m, cnt, root[MAXN], a[MAXN], x, y, k;
    struct node{
        int l, r, sum;} T[MAXN*40];
    vector<int> v;
    int getid(int x) {
         return lower_bound(v.begin(), v.end(), x)-v.begin() + 1;}
    
    void update(int l, int r, int &x, int y, int pos) {
        // T[y] 是上一版本的， T[x] 是这一版本的
            T[++cnt] = T[y]; T[cnt].sum++; x = cnt;
            if(l == r) return ;
            int mid = (l+r)>>1;
            if(mid >= pos)  update(l, mid, T[x].l, T[y].l, pos);
            else            update(mid+1, r, T[x].r, T[y].r, pos);
    }
    int query(int l, int r, int x, int y, int k) {
        
            if(l == r)      return l;
            int mid = (l+r)>>1;
            int sum = T[T[y].l].sum - T[T[x].l].sum;
            if(sum>=k)      return query(l, mid, T[x].l, T[y].l, k);
            else            return query(mid+1, r, T[x].r, T[y].r, k - sum);
    }
    
    int main() {
        
            scanf("%d %d",&n, &m);
            for(int i=1;i<=n;++i)   scanf("%d",&a[i]), v.push_back(a[i]);
            sort(v.begin(),v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
            for(int i=1;i<=n;++i)   update(1,n,root[i],root[i-1],getid(a[i]));
            for(int i=1;i<=m;++i) {
        
                    scanf("%d %d %d",&x,&y,&k);
                    printf("%d\n",v[query(1, n, root[x-1], root[y], k) - 1]);
            }
            return 0;
    }

# 其它 #

## 大数 ##

### N!的位数 ###

首先要计算阶乘的位数，以便知道开多大的数组

#include<cstdio>
    #include<cmath>
    int main()
    {
        
    	double sum=0;
    	for(int i=1;i<=10000;i++)	// n是10000的情况下 
    		sum+=log10(i);
    	printf("%d\n",(int)sum+1);
    	return 0;
    }

第二种求法：运用斯特林公式来计算 n! 的位数

n ! ≈ 2 π n ( n e ) n \\LARGE n!\\approx \\sqrt\{2\\pi n\}(\\frac\{n\}\{e\})^n n!≈2πn(en)n

#include<cstdio>
    #include<cmath>
    #define PI 3.141592654
    #define E 2.71828182846 	
    int main()
    {
        
    	int n,sum=1;
    	scanf("%d",&n);
    	if(n>3)
    		sum=log10(2*PI*n)/2+n*log10(n/E)+1;
    	printf("%d\n",sum);
    	return 0;
    }

### N！ ###

#include<cstdio>  
    #include<cstring>  
    #include<algorithm>  
    using namespace std;  
    #define ll long long    
    const ll c=1e14;  
    ll a[10000000];  
    int main()  
    {
          
        ll n;  
        while(~scanf("%lld",&n))   
        {
          
            ll temp;  
            ll dight=1;  
            a[0]=1;  
            for(ll i=1;i<=n;i++)  
            {
          
                ll num=0;  
                for(ll j=0;j<dight;j++)  
                {
          
                    temp=a[j]*i+num;  
                    a[j]=temp%c;  
                    num=temp/c;  
                }  
                if(num!=0)  
                {
          
                    a[dight++]=num;  
                }  
            }  
            printf("%lld",a[dight-1]);  
            for(ll i=dight-2;i>=0;i--)  
                printf("%014lld",a[i]);//这样也可以   
    //            printf("%0.14lld",a[i]);//这里想不明白为什么要加个.   
            printf("\n");  
        }  
        return 0;  
    }  
    //这个代码可以计算1e4以内的数，超过这个范围的话数据会溢出，需要在修改一下a[i]的最大储存位数 
    //就这段代码而言，a[i]最多储存1e14大小的数，要是在乘个1e5的数，结果是1e19大小，肯定会溢出
    //所以测试99999!的时候前边出现了负号。。。

### Fib ###

/*
      大斐波那契数 
    */
     
    //这段代码让每一个a[i][j]的值都是9位 
    #include<cstdio>
    #include<cstring>
    #define ll long long
    const int MAXN=1e4+3;
    const int c=1e9;
    ll a[MAXN][MAXN];
    int main()
    {
        
    	int n;
    	while(~scanf("%d",&n))
    	{
        
    		a[1][0]=1;a[2][0]=1;
    		int temp=0;
    		int d=0;
    		for(int i=3;i<=n;i++)
    		{
        
    			temp=0;
    			for(int j=0;j<=d;j++)
    			{
        
    				a[i][j]=a[i-1][j]+a[i-2][j]+temp;
    				temp=a[i][j]/c;
    				a[i][j]%=c;
    			}
    			if(temp)
    			{
        
    				d++;
    				a[i][d]=temp;
    			}	
    		}	
    		printf("%lld",a[n][d]);
    		for(int i=d-1;i>=0;i--)
    			printf("%010lld",a[n][i]);
    		printf("\n");
    	}
    	return 0;
    }