img

王熠弘

Reign in Hell

Dark`Kris

Private blog

I'm spark , hope you fire

C++算法及数据结构模板

| Have been read： times

Top

C++算法及数据结构模板

本文章原为2016-09-28的文章冲刺NOIp2016算法模板(C++)，本人于2016-11-20日从OI退役，并于2017-09-09服役ACM，故将本篇文章更新。之后本文章将持续更新并囊括更多的不仅限于OI的算法与数据结构。

程序大部分没经过编译和测评，欢迎在评论区指出本文中的错误 另：点开右下角像WIFI一样的标志进入RSS模式(XML文件)即可避免索引目录鬼畜的问题(现该问题已经解决)（可能需要向下翻一会才能找到本篇文章）

OI比赛记得考前一定要练好DFS和记忆化DFS！！骗分必用！

C++

Catalogue:

(众所周知GFM没办法自动生成目录，于是博主自己用Python撸了一个目录生成工具，之后会发博客贴代码)

栈与队列

栈

int strack[maxn];
int head;
bool b[maxn];

void push(int x)
{
	strack[++head]=x;
	b[x]=true;
};

int pop()
{
	int ret;
	ret=strack[head--];
	b[ret]=false;
	return ret;
};

bool empty()
{
	return head>0;
}

队列

int queue[2*maxn];
int tail,head;
bool b[maxn];

void push(int x)
{
	queue[++tail]=x;
	bool[x]=true;
};

int pop()
{
	int ret;
	ret=queue[++head];
	b[ret]=false;
	return ret;
};

bool empty()
{
	return head>=tail;
};

当然有的时候你手写的数据结构需要比较大的空间，这样队列就会造成很多损失，所以相应的就有两种解决方法：一：STL；二：循环队列，只需改两个地方（代码如下）；

head=(head+1)%n;//把head++改(从0开始用数组)
tail=(tail+1)%n;//把tail++改

单调队列

以下单调队列的标程就用的音乐会的等待的。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=500005;
int n,l,ans;
long long q[maxn],bef[maxn];
int main()
{
    cin>>n;
    q[0]=-1;
    long long a;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        while(l>0&&a>q[l])
        {
            l--;
            ans++;
        };
        if(l!=0)
        {
            if(a!=q[l])ans++;else
            {
                ans+=bef[l];
                if(bef[l]<l)ans++;
            };
        };
        l++;q[l]=a;
        if(q[l-1]==a)bef[l]=bef[l-1]+1;else bef[l]=1;   
    };
    cout<<ans;
    return 0;
}

STL

关于每个STL我只会写一下是什么，怎么用（举例子的形式），不会说的太细

向大家推荐C++库及函数等查询网站:cplusplus

可迭代容器的遍历方法

要用到迭代器，以vector举例，代码如下:

for (vector<int>::iterator iter=ivec.begin();iter!=ivec.end();iter++)  
    {  
        i++;  
        cout<< *iter <<endl;  
        *iter=(*iter)+i;  
    }

Vector

不定长度数组

#include <vector>
vector<int> first;	//第一种定义方法

int myints[]={16,2,77,29};
vector<int> second(myints,myints+4);//第二种定义方法

sort(second.begin(),second.end());//对vector排序

a=second[i];//可以这么使用

//以下是对vector的操作

Vector<int> opt;

opt.begin();	//返回起始地址
opt.end();	//返回结束地址
opt.size();	//返回大小
opt.empty();	//返回是否vector为空
opt.back();	//返回最后一个push进的数
opt.pop_back();	//把最后一个数弹出（不返回）
opt.push_back(int x);//把x从后面push进去

opt.erase(opt.begin(),opt.begin()+3);//删掉前三个元素
opt.erase(opt.begin()+5);//删掉第6个元素

Queue

队列，操作与Stack一样。

Priority_queue

相当于堆

#include <queue>
#include <functional>//在某些IDE下用greater的时候需要本语句

priority_queue<int> Bigheap;//定义一个大根堆
priority_queue<int,vector<int>,greater<int> > Smallheap;//定义一个小根对（注意两个尖括号间有空格）

//以下是操作

priority_queue<int> opt;
opt.top();//返回堆顶元素的值（不弹出）
opt.pop();//弹出堆顶元素（无返回值）
opt.push(x);

Stack

stack<int> opt;
opt.front();//返回
opt.size();
opt.empty();
opt.push();
opt.pop();//弹出

Deque

双向队，操作与Stack一样

Bitset

压位神器，只普及一下，不会用。

Set

set<int> first;
int myints[]= {10,20,30,40,50};
set<int> second (myints,myints+5);
set<int> third (second);
set<int> fourth (second.begin(), second.end());
third.rbegin(); third.rend();//rend相当于begin，rbegin相当于end
third.size();//返回大小
third.insert(60);
third.erase(it);
third.erase(50);//删除元素'50'
third.find(10);//找元素'10'
third.lower_bound(30); third.upper_bound(30);//'30'出现的第一个位置/最后一个位置
third.clear();//清除

Multiset

与Set用法一样，只是允许重复元素。

Map

map<char,int> first;
first[‘a’] = 10;
first.insert(make_pair(‘b’,20));
it++; ++it; it--; --it;
first.erase(1);//删除元素
firstt.count(1);//看有没有关系
it->first//键
it->second//值

Algorithm里其他好用的函数

Next_permutation

int a[]={1,2,3,4};

next_permutation(a,a+3);//下一个全排列

//现在a数组变成了:1 2 4 3

Lower_bound与Upper_bound

lower_bound(first,last,val);//有返回值
upper_bound(first,last,val);

Merge

merge (first,first+5,second,second+5,v.begin(),compare);

sort

bool compare(int a,int b)
{
	return a<b;
};//compare函数的例子

sort(起始地址,结束地址,compare函数);

Reverse

Reverse(myvector.begin(),myvector.end());

Unique

bool myfunction (int i, int j)
{
  return (i==j);
}

unique(起始地址,结束地址,去重条件函数);//按照函数里面编写的规则去重，当然也可以没有第三个参数

Random_shuffle

留一个概念，不会用，生成数据的时候用。

数论

快速幂

普通快速幂

#define ull unsigned long long
ull qpow(ull x,ull y,ull p) // x^y mod p
{
	ull ret=1;
	while(y)
	{
		if(y&1)ret = ret * x % p;
		x=x*x%p;
		y>>=1;
	};
	return ret;
}

矩阵快速幂

matrix operator *(matrix m1,matrix m2)//重载运算符
{
	assert(m1.m==m2.n);
	matrix res;
	res.n=m1.n; res.m=m2.m;
	for(int i=0;i<m1.n;i++)
		for(int j=0;j<m2.m;j++)
			for(int k=0;k<m1.m;k++)
				res.mat[i][j]+=m1.mat[i][k]*m2.mat[k][j];
	return res;
}

matrix matrix_pow(matrix x,int y)
{
	matrix res;
	res.n=res.m=2;
	res.mat[0][0]=res.mat[1][1]=1;
	while(y)
	{
		if(y&1)res=res*x;
		x=x*X;
		y>>=1;
	}
	return res;
}

筛法求素数

欧拉筛法

int tot=0;
void euler(int n)
{
	memset(check,0,sizeof(check));
	for(int i=2;i<=n;i++)
	{
		if(!check[i])prime[++tot]=i;
		for(int k=1;k<=tot;k++)
		{
			if(i*prime[k]>n)break;
			check[i*prime[k]]=1;
			if(i%prime[k]==0)break;
		};
	};
};

应用举例：

验证素数

普通方法

bool flag=true;
for(int i=1;i<=trunc(sqrt(prime));i++)
    if(prime%i==0)flag=false;//置不是素数标志

Miller-Rabin

时间复杂度： k是次数(见下文) 难度：★★★

这里只说明一下原理，关于代码，自行百度吧。

  • 根据费马小定理，随机选一个数，若(mod p)则很有可能是素数。多次尝试（尝试k次）若都成立若都成立则判定为素数。
  • 但是合数也有可能能通过这一测试：Carmichael数
  • Carmichael概念： 　　卡迈克尔数是一种合数，使得对于所有跟n互质的整数a：(mod n)
  • 这种数用此方法测试时，除非random出其因子，不然都无法判断为合数。例如：6。
  • 二次探测定理：若n为素数，方程(mod n)小于n的正整数解只有和。
  • 先计算出m、j，使得且j尽可能大。
  • 随机选一个数
  • 计算x=mod n

  • 然后将x不断平方j次，重复如下步骤： 　　1. 计算y=mod n 　　2. 如果y=1并且，此时一定不是素数，退出测试 　　3. x=y； 　　4. 如果y=1，暂时认为是素数，回到2.继续下一轮 若上述计算中没有满足2.和4.而正常退出，即不满足(mod n)，一定不是质数

    其次：这个博客写的很好（点击进入）；

分解质因数——唯一分解定理

void divide_prime(int n)
{
	int p=2;
	int t(trunc(sqrt(n)));
	while(n!=1&&p<=t)
	{
		int i=0;
		if(n%p==0)
		{
			while(n%p==0){n/=p;i++;};
			cout<<p<<'^'<<i<<' ';
		};
		p++;
	};
	if(n!=1)cout<<n<<'^'<<1;
}

最大公约数和最小公倍数

gcd为最大公约数，lcm为最小公倍数 ;

int gcd(int a,int b)//注意此处a要大于b
{
	return b==0?a:gcd(b,a%b);
};
int lcm(int a,int b)
{
	return a*b/gcd(a,b);
};

扩展欧几里德

解决 当a,b互质： 解为： 或 

int x,y;
int gcd(int a,int b)
{
	int ret,t;
	
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	};
	
	ret=gcd(b,a%b);
	t=y; y=x-(a%b)*y; x=t;
	return ret；
} //不理解建议背过

应用举例：

逆元

所谓逆元就是，a和b就在模p的意义下逆元。

利用同余的性质： 故可以用扩展欧几里德求解

//其实就是NOIp2012TG D2T1/Luogu P1082
#include <iostream>
#include <cstdio>
using namespace std;
long long x,y,a,b,ans;
long long gcd(long long a,long long b)
{
	long long t,ret;
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ret=gcd(b,a%b);
	t=y;
	y=x-(a/b)*y;
	x=t;
	return ret;
}
int main()
{
	cin>>a>>b;
	ans=gcd(a,b);
	while(x>b)x-=b;
	while(x<0)x+=b;
	cout<<x<<endl;
	return 0;
}

Catalan数

原理理解：(两个应用模板)

括号化 矩阵连乘： ，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n-1)种)

出栈次序 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?

详情请参照百度百科

int main() // 求第n个卡特兰数
{
	cin>>n;
	h[0]=1;h[1]=1;
	for(int i=2;i<=n;i++)
		for(int j=0;j<=i-1;j++)
			h[i]=h[i]+h[j]*h[i-j-1];
	cout<<h[n];
	return 0;
}

应用举例：

高精

读入、储存与输出

以下代码块均包含以下语句 :

int s[255];//255位的数

读入与储存 :

void read()
{
	char ss[255];
	 
	scanf("%s",ss);
	for(int i=0;i<strlen(ss);i++)
   		s[i+1]=ss[strlen(ss)-1-i]-'0';
	s[0]=strlen(ss);//存长度
};

输出 :

void print()
{
	for(int i=s[0];i>=1;i--)
		cout<<s[i];
};

高精度加法

高精加单精

void add(int *s,int x)//s存高精度数，x是要加的单精度
{
	int k=1;
	s[k]+=x;
	while(s[k]>=10)
	{
		s[k+1]+=s[k]/10;
		s[k++]%=10;
	};
	s[0]=max(k,s[0]);
};

高精加高精

void add(int *s1,int *s2,int *ans)
{
	int len;
	len=max(s1[0],s2[0]);
	for(int i=1;i<=len;i++)
	{
		ans[i]+=s1[i]+s2[i];
		if(ans[i]>=10)
		{
			ans[i+1]+=ans[i]/10;
			ans[i]%=10;
		};
	};
	if(ans[len+1]!=0)len++;
	ans[0]=len;
};

高精度乘法

高精乘单精

void multiply(int *s,int x)
{
	for(int i=1;i<=n;i++)
	{
		c[i]+=s[i]*x;
		c[i+1]+=(s[i]*x)/10;
		c[i]%=10;
	};
	c[0]=s[0]+1;
	while(c[c[0]]>=10)
	{
		c[c[0]+1]+=c[c[0]]/10;
		c[c[0]]%=10;
		c[0]++;
	};
	while(c[0]>1&&c[c[0]]==0)
	{
		c[0]--;
	};
};

高精乘高精

void multiply(int *s1,int *s2,int *ans)
{
	for(int i=1;i<=s1[0];i++)
		for(int j=1;j<=s2[0];j++)
		{
			ans[i+j-1]+=s1[i]*s2[j];
			ans[i+j]+=ans[i+j-1]/10;
			ans[i+j-1]%=10;
		};
	ans[0]=s1[0]+s2[0]+1;
	while(ans[0]>1&&ans[ans[0]]==0)
	{
		ans[0]--;
	};

高精度除法

高精度除以单精度

此处略微借鉴了一下铭哥的标程

//divide
const int opt=10000;

struct node
{
	int a[1005];
	int len;
}

node divide(node a;int p)
{
	node c;
	int i,d;
	
	d=0;
	c.len=a.len;
	for(int i=a.len;i>=1;i--)
	{
		d=d*opt+a.a[i];
		c.a[i]=d/p;
		d=d%p;
	};
	while(c.len>1&&c.a[c.len]==0)
	{
		c.len--;
	};
	return c;
}

高精度模

高精模单精

int mod(char* s,int p)
{
	int res=0;
	for(int i=0;i<strlen(s);i++)
		res = (res*10 + s[i]-'0')%p;
	return res;
}

压位

const int opt=100000000;

void multiply(int *num,int x)
{
    for(int i=1;i<=num[0];i++)num[i]*=x;
    for(int i=1;i<=num[0];i++)
    {
        if(num[i]>=opt)
        {
            num[i+1]+=num[i]/opt;
            num[i]%=opt;
        };
        while(num[num[0]]!=0)
        {
            num[0]++;
        };
    }
}

void print(int *a)
{
    for(int i=a[0];i>=1;i--)
    {
        if(i==a[0])
        {
            cout<<a[i];
        }else
        {
            if(a[i]<10000000)cout<<0;
            if(a[i]<1000000)cout<<0;
            if(a[i]<100000)cout<<0;
            if(a[i]<10000)cout<<0;
            if(a[i]<1000)cout<<0;
            if(a[i]<100)cout<<0;
            if(a[i]<10)cout<<0;
            cout<<a[i];
        };
    };
}

注意⚠:使用压位的时候的读入不要读错 比如不要把99存到数组的两个位置里面，而应该是一个；

树

建树

具体思路：对于一个节点来说，其他的任意一个节点，不是他的父节点，就是他的子节点。

传递闭包

详见上面图论部分Floyd算法。

并查集

int find(int x)//非路径压缩
{
	return p[x]==x?x:find(p[x]);
};

int find(int x)//并查集+路径压缩
{
	return p[x]==x?x:p[x]=find(p[x]);
}；

树状数组

int lowbit(int x)
{
	return x&-x;
};

int getsum(int n) //求1～n见的和
{
	int ret=0;
	while(n)
	{
		ret+=c[n];
		n-=lowbit(n);
	};
	return ret;
};

void add(int n,int x) //给a[n]加上x
{
	a[n]+=x;
	while(n<=maxn)
	{
		c[n]+=x;
		n+=lowbit(n);
	}
}

应用模型：

  • 树状数组求逆序对：
void update(int n)
{
	while(n<=maxn)
	{
		c[n]+=1;
		n+=lowbit(n);
	};
};

for(int i = 1; i <= n; ++i)  //主程序里面加上这个
{  
	update(reflect[i]);  
	ans += i - getsum(reflect[i]);//reflect是离散化后的数组
}

线段树

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const int maxnode = 1e5+5;
const int INF = 0xffffff;
struct IntervalTree{//L,R是需要更新的区间，l,r是当前节点的区间
	int sum[maxnode<<2];//rt==1为根结点
	int Add[maxnode<<2];//懒人标记(为降低时间复杂度)

	void pushdown (int rt,int ln,int rn)//向下更新一个深度的Add标记
	{
		if(Add[rt])
		{
			Add[rt<<1]+=Add[rt];
			Add[rt<<1|1]+=Add[rt];
			sum[rt<<1]+=Add[rt]*ln;
			sum[rt<<1|1]+=Add[rt]*rn;
			Add[rt]=0;
		}
	}

	void pushup(int rt)
	{
		sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	}

	void update(int L,int R,int C,int l,int r,int rt)//区间修改
	{
		if(L<=l&&R>=r)
		{
			sum[rt]+=C*(r-l+1);
			Add[rt]+=C;
			return;
		}
		int m=(l+r)>>1;
		pushdown(rt,m-l+1,r-m);
		if(L<=m)update(L,R,C,l,m,rt<<1);
		if(R>m)update(L,R,C,m+1,r,rt<<1|1);
		pushup(rt);
	}

	void update(int L,int C,int l,int r,int rt)//单点修改
	{
		if(l==r)
		{
			sum[rt]+=C;
			return;
		}
		int m=(l+r)>>1;
		if(L<=m)update(L,C,l,m,rt<<1);
		else update(L,C,m+1,r,rt<<1|1);
		pushup(rt);
	}

	int query(int L,int R,int l,int r,int rt)//区间查询
	{
		if(L<=l&&R>=r)
		{
			return sum[rt];
		}
		int m=(l+r)>>1;
		pushdown(rt,m-l+1,r-m);

		int ans=0;
		if(L<=m)ans+=query(L,R,l,m,rt<<1);
		if(R>m)ans+=query(L,R,m+1,r,rt<<1|1);
		return ans;
	}
};

IntervalTree tree;

int main()
{
	int n,m;
	while(~scanf("%d %d",&n,&m))
	{
		int x,y,k,opt;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			tree.update(i,x,1,n,1);
		}

		for(int i=1;i<=m;i++)
		{
			scanf("%d",&opt);
			if(opt==1)
			{
				scanf("%d %d %d",&x,&y,&k);
				tree.update(x,y,k,1,n,1);
			}else{
				scanf("%d %d",&x,&y);
				printf("%d\n",tree.query(x,y,1,n,1));
			}
		}
	}
	return 0;
}

LCA

倍增版LCA

思路如下

// 把树存起来（前向星，无向边）
// 把每个点的深度求出来（dfs）
// 把i向上2^j个深度的祖宗求出来（倍增）(先搜j在搜i)
// 读入两个点
// 把较深的一个点向上移动至与另一个点相同
// 如果祖宗一样就返回这个祖宗
// 两个点一起向上移（从远到近）（条件里不要忘了＝）
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,s;//n is node,m is qustion,s is root
int anc[500005][50];
int fa[500005];
int deep[500005];
int h[500005],v[1000010],nt[1000010];

void dfs(int u)//u代表起点
{
    int p=h[u];
    while(p)
    {
        if(deep[v[p]]==-1)//如果没处理过
        {
            deep[v[p]]=deep[u]+1;
            anc[v[p]][0]=u;//v[i]上面2^0个深度的祖先是u
            dfs(v[p]);//接下来处理一下v[i]
        }
        p=nt[p];
    }
}

void init()
{
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            anc[i][j]=anc[anc[i][j-1]][j-1];//倍增核心
}

int LCA(int a,int b)
{
    if(deep[a]<deep[b])swap(a,b);
    
    int i;for(i=0;(1<<i)<=deep[a];i++);i--;
    
    if(deep[a]!=deep[b])
        for(int j=i;j>=0;j--)
            if(deep[a]-(1<<j)>=deep[b])
                a=anc[a][j];
    
    if(a==b)return a;
    
    for(int j=i;j>=0;j--)
    {
        if(anc[a][j]&&(anc[a][j]!=anc[b][j]))
        {
            a=anc[a][j];
            b=anc[b][j];
        };
    };
    return anc[a][0];
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    
    for(int i=1;i<=n;i++)deep[i]=-1;//表示deep还没有处理过
    
    for(int i=1;i<2*n-1;i+=2)//i个点的树有2*(n-1)条边
    {
        int a;
        scanf("%d%d",&a,&v[i]);
        nt[i]=h[a]; h[a]=i;
        v[i+1]=a; nt[i+1]=h[v[i]]; h[v[i]]=i+1;
    }//前向星存边
        
    deep[s]=0;//根的深度是0
    
    dfs(s);//深搜求每个点的深度
    init();
    
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d",LCA(a,b));
    }
    return 0;
}

图论

最短路

dijkstra

经过了heap优化,前向星存边。在ACM类型赛事中，卡SPFA的题目比较多，建议直接掌握此类型最短路算法

struct node{
	long long u,dis;

	node(long long _u, long long _dis):u(_u),dis(_dis){};

	bool operator < (const node &b) const{
		return dis > b.dis;
	}
};
priority_queue<node> que;
void dijkstra()
{
	dist[1]=0;
	que.push(node(1,0));
	while(!que.empty())
	{
		long long u=que.top().u; que.pop();
		long long nowp=h[u];
		if(b[u])continue;
		b[u]=true;
		while(nowp)
		{
			long long v = ed[nowp];
			if(!b[v])
			{
				if(dist[v]>dist[u]+w[nowp])
				{
					dist[v]=dist[u]+w[nowp];
					que.push(node(v,dist[v]));
				}
			}
			nowp=nt[nowp];
		}
	}
}

SPFA

以下代码中包括邻接表(前向星)存图

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=5005,maxm=100005;
const int INF=0xffffff;

int n,m; //n个点，m条边
int queue[2*maxn],head,tail;
int dist[maxn];
int firstEdge[maxn],weight[maxm],nextEdge[maxm],endPoint[maxm];
int p;
bool b[maxn];
void add(int x,int y,int z)//前向星
{
    weight[++p]=z;
    endPoint[p]=y;
    nextEdge[p]=firstEdge[x];
    firstEdge[x]=p;
};

void push(int x)  //队列的操作，详见上面
{
    b[x]=true;
    queue[++tail]=x;
}

int pop() //队列的操作，详见上面
{
    int ret;
    ret=queue[++head];
    b[ret]=false;
    return ret;
}

void SPFA()
{
    int u;
    int nowP;
    
    for(int i=2;i<=n;i++)dist[i]=INF;
    
    push(1);
    while(tail>head)
    {
        u=pop();
        nowP=firstEdge[u];
        while(nowP)
        {
            if(dist[endPoint[nowP]]>dist[u]+weight[nowP])
            {
                dist[endPoint[nowP]]=dist[u]+weight[nowP];
	            if(b[endPoint[nowP]])push(endPoint[nowP]);
	        }；
            nowP=nextEdge[nowP];
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z); //无向图加上这句，有向图不用加（具体看题描述）
    };
    SPFA();
    cout<<dist[n]<<endl;
    return 0;
}

次短路

代码比较麻烦，不写了，说一下思路吧。

先用SPFA跑一遍，找出来最短路。把最短路记下来。 接下来，每次删掉最短路上的一条边，再跑一边SPFA。 运行一遍以后，路径长度最小的即次短路。

K短路

部分内容引自阿波罗2003的博客

Dijkstra+A*

时间复杂度：

首先建反图，跑一次最短路算法，得到每个点到t的最短路的距离。
然后用当前走的距离加上到终点的最短路的长度作为优先级进行A*。

  1. 当一个点第k次出队时，答案是它的优先级
  2. 当终点第k次出队时，答案是它已经走的路程
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn=1005, maxm=10005;
const int MAXINF = 0xfffffff;
int n,m;
int s,e,k,t;
int dist[maxn];
bool b[maxn];

struct node{
    int v,w;
    node (int _v=0, int _w=0):v(_v),w(_w){}
    bool operator < (const node &res) const{
        return w+dist[v]>res.w+dist[res.v];
    }
};

struct edge{
    int v,w;
    edge (int _v=0,int _w=0):v(_v),w(_w){}
};

vector<edge> E[maxn],revE[maxn];

void dijkstra(int s)
{
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)dist[i]=MAXINF;
    dist[s]=0;
    priority_queue<node> que;
    que.push(node(s,0));
    while(!que.empty())
    {
        node tmp = que.top();que.pop();
        int u = tmp.v;
        if(b[u])continue;
        b[u]=true;
        for(int i=0;i<(int)E[u].size();i++)
        {
            int v=E[u][i].v;
            int cst=E[u][i].w;
            if(!b[v] && dist[v]>dist[u]+cst){
                dist[v]=dist[u]+cst;
                que.push(node(v,dist[v]));
            }
        }
    }
}

int _a(int s){
    priority_queue<node> que;
    que.push(node(s,0));k--;
    while(!que.empty())
    {
        node pre = que.top();que.pop();
        int u=pre.v;
        if(u==e)
        {
            if(k)k--;
            else return pre.w;
        }
        for(int i=0;i<(int)revE[u].size();i++){
            int v=revE[u][i].v;
            int cst=revE[u][i].w;
            que.push(node(v,pre.w+cst));
        }
    }
    return -1;
};

void init()
{
    for(int i=0;i<=n;i++)
    {
        E[i].clear();
        revE[i].clear();
    }
}
void add(int x,int y,int z)
{
    revE[x].push_back(edge(y,z));
    E[y].push_back(edge(x,z));
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        init();
        scanf("%d %d %d %d",&s,&e,&k);
        for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            add(x,y,z);
        }
        dijkstra(e);
        if(dist[s]==MAXINF)
        {
            printf("-1\n");
            continue;
        }
        if(s==e)k++;
        printf("%d\n",_a(s));
    }
    return 0;
}

最短路+可持久化堆

时间复杂度：

考虑建立反图，然后跑最短路算法得到以t为根的最短路径生成树。
当走了一条非树边(u,v,w)意味着什么？
最终的路径长度就会因此增加f[v]−f[u]+w。
对于一条路径，我们依次将它经过的非树边记下来，约定得到的序列是这条路径的非树边序列。
考虑对于一个合法的非树边序列，我们可以找到唯一的一条s到t的路径与之对应。
因此，k短路的长度就等于第k小的代价和加上s到t的最短路的长度。
考虑如何来得到一个合法的非树边序列。

  1. 找到一条起点在当前点p到根t的路径上的非树边
  2. 令p等于这条边的终点。

我们可以通过这样的方法来得到所有的非树边序列。但是我们并不需要所有的非树边序列，因此当找到第x短路后再进行拓展状态，然后用优先队列来维护。
但是这样每次拓展时间复杂度可达O(m)，总时间复杂度可以达到O(mklog(mk))。
令人无法接受。但是其中真正会被用到的状态十分少。
因此可以像UVa 11997那样进行优化。
当一个非树边序列出队时，代价和比它大的才可能有用。
因此，考虑一个非树边序列出队时通过下面的方法来进行得到新的序列:

  1. 追加操作：假如最后一条非树边的终点为v，找到一条起点在v到t的路径上代价最小的非树边追加在当前非树边序列后
  2. 替换操作：将最后一条非树边更换为代价比它大的1条非树边。

例如图中橙色虚线是被替换掉的非树边，紫色是新加入的非树边

考虑用一些可持久化数据结构（如可持久化斜堆，可持久化线段树，可持久化Treap）来维护起点在点u到根的路径上的非树边的代价。

对于替换操作，

  • 如果用的可持久化堆，那么把最后一条非树边替换为它所在的堆（你从哪个堆把它拿出来的）中它的左右子节点代表的边。
  • 如果用的可持久化平衡树，那么把最后一条非树边直接替换为它的后继
  • ……

这是一个很稳定的算法，时间复杂度O(n+mlogm+klogk)。就是常数有点大，sad…..
注意一些细节

  • 计算代价时需要考虑终点是否可以到达t
  • 考虑s=t时，要求的k短路包不包含0
  • k短路不存在，队首为空
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef bool boolean;

#define pii pair<int, int>
#define fi first
#define sc second

typedef class Node {
    public:
        int val, ed;
        Node *l, *r;
        
        Node()    {        }
        Node(int val, int ed, Node *l, Node *r):val(val), ed(ed), l(l), r(r) {        }
}Node;

#define Limit 1000000

Node pool[Limit];
Node* top = pool;

Node* newnode(int val, int ed) {
    if(top >= pool + Limit)
        return new Node(val, ed, NULL, NULL);
    top->val = val, top->ed = ed, top->l = top->r = NULL;
    return top++;
}

Node* merge(Node* a, Node* b) {
    if (!a)    return b;
    if (!b)    return a;
    if (a->val > b->val)    swap(a, b);
    Node* p = newnode(a->val, a->ed);
    p->l = a->l, p->r = a->r;
    p->r = merge(p->r, b);
    swap(p->l, p->r);
    return p;
}

typedef class Status {
    public:
        int dist;
        Node* p;
        
        Status(int dist = 0, Node* p = NULL):dist(dist), p(p) {        }

        boolean operator < (Status b) const {
            return dist > b.dist;
        }
}Status;

typedef class Edge {
    public:
        int end, next, w;
        
        Edge(int end = 0, int next = 0, int w = 0):end(end), next(next), w(w) {        }
}Edge;

typedef class MapManager {
    public:
        int ce;
        int* h;
        Edge* es;
        
        MapManager() {            }
        MapManager(int n, int m):ce(0) {
            h = new int[(n + 1)];
            es = new Edge[(m + 5)];
            memset(h, 0, sizeof(int) * (n + 1));
        }
        
        void addEdge(int u, int v, int w) {
            es[++ce] = Edge(v, h[u], w);
            h[u] = ce;
        }
        
        Edge& operator [] (int pos) {
            return es[pos];
        }
}MapManager;

int n, m;
int s, t, k;
MapManager g;
MapManager rg;
boolean *vis;
int* f, *lase;

inline void init() {
    scanf("%d%d", &n, &m);
    g = MapManager(n, m);
    rg = MapManager(n, m);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        g.addEdge(u, v, w);
        rg.addEdge(v, u, w);
    }
    scanf("%d%d%d", &s, &t, &k);
}

queue<int> que;
void spfa(MapManager& g, int s) {
    vis = new boolean[(n + 1)];
    f = new int[(n + 1)];
    lase = new int[(n + 1)];
    memset(f, 0x7f, sizeof(int) * (n + 1));
    memset(vis, false, sizeof(boolean) * (n + 1));
    que.push(s);
    f[s] = 0, lase[s] = 0;
    while (!que.empty()) {
        int e = que.front();
        que.pop();
        vis[e] = false;
        for (int i = g.h[e]; i; i = g[i].next) {
            int eu = g[i].end, w = g[i].w;
            if (f[e] + w < f[eu]) {
                f[eu] = f[e] + w, lase[eu] = i;
                if (!vis[eu]) {
                    vis[eu] = true;
                    que.push(eu); 
                } 
            }
        }
    }
 }

Node** hs;
inline void rebuild() {
    for (int i = 1; i <= n; i++)
        for (int j = g.h[i]; j; j = g[j].next) {
            int e = g[j].end;
            if (lase[i] != j)
                g[j].w += f[e] - f[i];
        }
    
    hs = new Node*[(n + 1)];
    que.push(t);
    hs[t] = NULL;
    while (!que.empty()) {
        int e = que.front();
        que.pop();
        if (lase[e])
            hs[e] = hs[g[lase[e]].end];
        for (int i = g.h[e]; i; i = g[i].next)
            if (lase[e] != i && f[g[i].end] != 0x7f7f7f7f)
                hs[e] = merge(hs[e], new Node(g[i].w, g[i].end, NULL, NULL));
        for (int i = rg.h[e]; i; i = rg[i].next) {
            int eu = rg[i].end;
            if (lase[eu] == i)
                que.push(eu);
        }
    }
}

inline int kthpath(int k) {
    if (s == t)
        k++;
    if (f[s] == 0x7f7f7f7f)
        return -1;
    if (k == 1)
        return f[s];
    
    priority_queue<Status> q;
    if (!hs[s])
        return -1;
        
    q.push(Status(hs[s]->val, hs[s]));
    while (--k && !q.empty()) {
        Status e = q.top();
        q.pop();
        
        if(k == 1)
            return e.dist + f[s];
        
        int eu = e.p->ed;
        if (hs[eu])
            q.push(Status(e.dist + hs[eu]->val, hs[eu]));
        if (e.p->l)
            q.push(Status(e.dist - e.p->val + e.p->l->val, e.p->l));
        if (e.p->r)
            q.push(Status(e.dist - e.p->val + e.p->r->val, e.p->r));
    }
    return -1;
}

inline void solve() {
    printf("%d\n", kthpath(k));
}

int main() {
    init();
    spfa(rg, t);
    rebuild();
    solve();
    return 0;
}

最小生成树(MST)

最小生成树即一个无向连通不含圈图中，连接G中所有点，且边集是E的子集，且边权和最小的生成树。（我解释的有点拗口）

最小生成树算法一共有两个：Prim和Kruskal算法，由于经并查集优化的Kruskal算法比Prim算法优秀得多，且Prim算法较容易理解，这里只给出Kruscal算法的模板。

Kruskal

下面展现两种做法，一种是普通的暴力枚举做法，另一种是并查集优化过的。并查集优化过的算法比较快，但是要忽略生成树的形状。就是说如果你需要用到新生成树的形状，那么不能使用此种方法。

  • 普通方法：//类似Prim算法
struct node{int u,v,w;}e[maxe];//u是起点,v是终点,w是权
node MST[maxe];
bool com(node a,node b){return a.w<b.w;};

void Kruskal()
{
	sort(e+1,e+m+1,com);//按边权从小到大排序
	for(int i=1;i<=m;i++)
	{
		if(condition)//判断是否在同一个集合里
			MST[++tot]=e[i];//如果不是，加入这条边
	};
}

以上版本是自己写的，感觉不对（上面的已经改成伪代码了），于是抄下来了粉书上的伪代码和讲解：

把所有边排序，记第i小的边为e[i](1<=i<m)
初始化MST为空
初始化连通分量，让每个点自成一个独立的连通分量
for(int i=1;i<=m;i++)
	if(e[i].u和e[i].v不在同一个连通分量)
	{
		把边e[i]加入MST
		合并e[i].u和e[i].v所在的连通分量
	}

在上面的伪代码中，最关键的地方在于”连通分量的查询与合并”:需要知道任意两个点是否在同一个连通分量中，还需要合并两个连通分量。 最容易想到的方法是”暴力”——每次”合并”时只在MST中加入一条边（如果使用邻接矩阵，只需G[e[i].u][e[i].v]=1），而”查询”时直接在MST中进行图遍历(DFS和BFS都可以判断连通性)。

  • 并查集优化
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}//并查集的find和路径压缩
int Kruskal()//返回的最小生成树的边权和
{
	int ans=0;
	for(int i=1;i<=n;i++)p[i]=i;//初始化并查集
	sort(edge+1,edge+m+1,com);//给边从小到大排序
	for(int i=1;i<=m;i++)
	{
		int x=find(edge[i].u);
		int y=find(edge[i].v);
		
		if(x!=y)
		{
			ans+=edge[i].w;//求和
			p[x]=y;
		};//如果在不同的集合，合并
	}
	return ans;
};

其实此处还有一个优化，虽然不会节省很长时间，但是，优势都是一点点积累出来的！就是循环枚举边的时候不用for而用while，当当前得到的最小生成树一共有n-1条边时，最小生成树就已经生成完了，剩下的边就不用再枚举了。

训练参考:

图的遍历

Floyed

for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
		d[i][j]=INF;//INF是比最大权和大一点的数，不能超2*10^9
for(int i=1;i<=n;i++)
	d[i][i]=0;		//以上为使用前的初始化

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

还有一点相关的东西就是传递闭包（Transitive Closure）

即在有向图中，有时不必关心路径长度，而只关心每两点间是否有通路，则可以用1和0分别表示”连通”和”不连通”。得到的结果称为有向图的传递闭包。

只需将程序中的

d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

改成

d[i][j]=d[i][j]||(d[i][k]&&d[k][j]));

例题:

  • 传递闭包：电话圈(Calling Circles,ACM/ICPC World Finals 1996,UVa247)(Floyd，连通分量)
  • Floyd：噪音恐惧症(Audiophobia,UVa10048)(Floyd，最大值最小路)

二分图染色

基本思路就是用DFS，对于每个点，将与其连接的下一个点染上不同的颜色。

下面的程序是“双栈排序“里二分图染色的子程序：

void dfs(int p,int colour)
 {
     if(!color[p])color[p]=colour;
     else if(color[p]!=colour)
      {
          printf("0");
          exit(0);
      }
          else return;

    for(int i=last[p];i>0;i=next[i])dfs(goal[i],3-colour);
     
 }

附上几篇不错的博客：（感谢喵头鹰、暗金色、LOI_summer） 喵头鹰的博客 暗金色的博客 LOI_summer的博客

二分图匹配

匈牙利算法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 205,maxm =205;
int n,m;
bool line[maxn][maxm];
bool used[maxn];
int belong[maxm];
bool find(int x)
{
    for(int i=1;i<=m;i++)
    {
        if(line[x][i] && !used[i])
        {
            used[i]=true;
            if(belong[i]==0 || find(belong[i]))
            {
                belong[i]=x;
                return true;
            }
            
        }
    }
    return false;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        for(int j=1;j<=x;j++)
        {
            int res;
            scanf("%d",&res);
            line[i][res]=true;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(used,0,sizeof(used));
        if(find(i))ans++;
    }
    printf("%d",ans);
    return 0;
}

可以参考该篇博客：匈牙利算法简单易懂

最大连通子图

Tarjan

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=1005,maxm=2005;//n is node,m is edge
int n,m;
int h[maxn],v[maxm],nt[maxm],p;//forward-star
int stk[maxn],head;//stack
bool b[maxn];//visit
int dfn[maxn],low[maxn],timestamp;//tarjan
void add(int x,int y)
{
    v[++p]=y;
    nt[p]=h[x];
    h[x]=p;
}
void push(int x)
{
    stk[++head]=x;
    b[x]=true;
}
int pop()
{
    int ret=stk[head--];
    b[ret]=false;
    return ret;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++timestamp;
    push(x);
    int nowp=h[x];
    while(nowp)
    {
        if(!dfn[v[nowp]])//node wasn't visited
        {
            tarjan(v[nowp]);
            low[x]=min(low[x],low[v[nowp]]);
        }else if(b[v[nowp]]){
            low[x]=min(low[x],dfn[v[nowp]]);
        }
        nowp=nt[nowp];
    }
    if(low[x]==dfn[x])//the condition of tarjan's end
    {
        do{
            printf("%d ",pop());
        }while(x!=stk[head+1]);
        printf("\n");
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    return 0;
}

键盘里的青春的博客中对tarjan算法的讲解比较详细，学习tarjan算法请看这篇文章。同时在此感谢此文章对我学习tarjan算法的帮助。

缩点

void tarjan(int x)
{
    dfn[x]=low[x]=++timestamp;
    push(x);
    int nowp=h[x];
    while(nowp)
    {
        if(!dfn[v[nowp]])//node wasn't visited
        {
            tarjan(v[nowp]);
            low[x]=min(low[x],low[v[nowp]]);
        }else if(b[v[nowp]]){
            low[x]=min(low[x],dfn[v[nowp]]);
        }
        nowp=nt[nowp];
    }
    if(low[x]==dfn[x])//the condition of tarjan's end
    {
        bel[x]=++sum;
        do{
            int node=pop();
            bel[node]=sum;
        }while(x!=stk[head+1]);
    }
}
//未完成

割点

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

也就是说，这个点维持着双联通的继续，去掉这个点，这个连通分量就无法再维持下去，分成好几个连通分量。

仅需在以上Tarjan算法中稍加改动，即可得到割点算法。

void tarjan(int x,int fa)
{
    int child=0;
    dfn[x]=low[x]=++timestamp;
    push(x);
    int nowp=h[x];
    while(nowp)
    {
        if(!dfn[v[nowp]])//node wasn't visited
        {
            child++;
            tarjan(v[nowp],x);
            low[x]=min(low[x],low[v[nowp]]);
            if(low[v[nowp]]>dfn[x])
            {
                iscut[x]=true;//node x is cutNode
            }
        }else if(v[nowp]!=fa && b[v[nowp]]){//&& dfn[v[nowp]]<dfn[x]
            low[x]=min(low[x],dfn[v[nowp]]);
        }
        nowp=nt[nowp];
    }
    if(fa<0&&child==1)//根节点如果有两个及以上的儿子，那么他也是割点(初始调用时fa=-1)
    {
        iscut[x]=false;
    }
}

缩点、割点、桥的内容感谢Styx-ferryman的博客

网络流

最大流

EdmondsKarp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int maxn=1e5+5,INF=0xffffff;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){};
};
struct EK{
    int n,m;
    vector<Edge> edges;
    vector<int> G[maxn];
    int a[maxn];
    int p[maxn];
    
    void init(int n){
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    
    void AddEdge(int from,int to,int cap){
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));//反向弧
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    
    int Maxflow(int s,int t){
        int flow=0;
        while(true)
        {
            memset(a,0,sizeof(a));
            queue<int> Q;
            Q.push(s);
            a[s]=INF;
            while(!Q.empty())
            {
                int x = Q.front(); Q.pop();
                for(int i=0;i<G[x].size();i++){
                    Edge& e = edges[G[x][i]];
                    if(!a[e.to] && e.cap > e.flow){
                        p[e.to] = G[x][i];//记录增广路
                        a[e.to] = min(a[x],e.cap-e.flow);
                        Q.push(e.to);
                    }
                }
                if(a[t])break;
            }
            if(!a[t])break;//如果t点找不到增广路，说明已经没有增广路了，已经到汇点了
            for(int u=t;u!=s;u=edges[p[u]].from)//不断调整流量大小
            {
                edges[p[u]].flow += a[t];
                edges[p[u]^1].flow -= a[t];
            }
            flow += a[t];
        }
        return flow;
    }
}algo;
int main()
{
    int n,m,s,t;
    scanf("%d %d %d %d",&n,&m,&s,&t);
    algo.n=n; algo.m=m; algo.init(n);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        algo.AddEdge(u, v, w);
    }
    printf("%d",algo.Maxflow(s, t));
    return 0;
}

分层图

例如bzoj1579这种选择k条免费边的题目，可以建k+1层图，每一层图之间建立免费边，跑一边最短路，即可得出答案.（以下代码为有向边）

#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5+5, maxm = 2e5+5, maxk = 15;
const long long max_edge = maxm*(maxk+1)*2+(maxk+1), max_point = maxn*(maxk+1);
const long long MAXDIST = 1e18;
priority_queue<long long,vector<long long>,greater<long long>> que;
bool b[max_polong long];
long long h[max_point],nt[max_edge],ed[max_edge],n,m,k;
long long p,w[max_edge],dist[max_point];
inline void add(long long x,long long y,long long z)
{
	p++;
	ed[p]=y;
	w[p]=z;
	nt[p]=h[x];
	h[x]=p;
}
void spfa()
{
	que.push(1);
	while(!que.empty())
	{
		long long u=que.top();que.pop();
		long long nowp=h[u];
		if(b[u])continue;
		b[u]=true;
		while(nowp)
		{
			long long v = ed[nowp];
	        if(!b[v])
	        {
    			if(dist[v]>dist[u]+w[nowp])
    			{
    				dist[v]=dist[u]+w[nowp];
    			    que.push(v);
    			}
			}
			nowp=nt[nowp];
		}
	}
}
void clear()
{
    while(que.size())que.pop();
}
int main()
{
	long long t;
	scanf("%d",&t);
	dist[1]=0;
	while(t--)
	{
		memset(b,0,sizeof(b));
		memset(h,0,sizeof(h));
		p=0;
		clear();

		scanf("%d %d %d",&n,&m,&k);
		for(long long i=1;i<=m;i++)
		{
		    long long x,y;
		    long long z;
			scanf("%d %d %lld",&x,&y,&z);
			for(long long j=0;j<k;j++)
			{
				add(x+n*j,y+n*j,z);
				add(x+n*j,y+n*(j+1),0);
			}
			add(x+n*k,y+n*k,z);
		}
		long long lim = n*(k+1);
		for(long long i=2;i<=lim;i++)dist[i]=MAXDIST;
		spfa();
		long long ans=MAXDIST;
		for(long long i=0;i<=k;i++)ans=min(ans,dist[n+n*i]);
		printf("%lld\n",ans);
	}
	return 0;
}

动态规划

钟长者说：有几个未知量，DP数组就有几维，若求个数能再省掉最后一维。 然而这只是一般情况，例如有个例外：HAOI2012 音量调节/Luogu P1877，这道题就不能省掉最后一维。

铭哥说：重推所有的DP方程是复习DP的最佳方法

线性DP

最大递增子序列和

int ans=0,f[maxn]={-1};
for(int i=1;i<=n;i++)
	for(int j=0;j<=i-1;j++)
	{
		f[i]=max(f[i],f[j]+a[i]);
		ans=max(ans,f[i]);
	};

最大连续子序列和

f[1]=a[1];
for(int i=2;i<=n;i++)
{
	f[i]=max(f[i-1]+a[i],a[i]);
	ans=max(ans,f[i]);
}

最长公共子序列和

for(int i=1;i<=strlen(s1);i++)
	for(int j=1;j<=strlen(s2);j++)
		if(s1[i]==s2[j])f[i][j]=f[i-1][j-1]+1;
			else f[i][j]=max(f[i-1][j],f[i][j-1]);

字符串转换问题

给定A串和B串，有删除一个字符、插入一个字符、改变一个字符三种操作，求A变到B的最少操作次数。 f[i][j]表示A的前i个字符变成B的前j个字符所用的最少步数。

for(int i=0;i<=strlen(A);i++)f[i][0]=i;
for(int i=0;i<=strlen(B);i++)f[0][i]=i;
for(int i=1;i<=strlen(A);i++)
	for(int j=1;j<=strlen(B);j++)
		if(A[i]==B[j])f[i][j]=f[i-1][j-1];
			else f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1,j-1])+1;

最长公共子序列

LCS

c[i][j] = LCS(a[1…i],b[1…j]) 
for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
		if(a[i]==b[j]) c[i][j]=c[i-1][j-1]+1;
		else c[i][j]=max(c[i-1][j],c[i][j-1]);

最长不下降子序列

//据说可以用二分进行优化
for(int i=2;i<=n;i++)
	for(int j=1;j<=i-1;j++)
		if(a[j]<=a[i])f[i]=max(f[i],f[j]+1);
for(int i=1;i<=n;i++)ans=max(ans,f[i]);

背包DP

01背包

for(int i=1;i<=m;i++)//m个物品
	for(int j=1;j<=w;j++)//背包容量为w
		if(a[i]<=j)
		{
			dp[i][j]=max(dp[i-1,j-a[i]]+val[i],dp[i-1,j]);//a数组是占用的容量，val是价值
		}else
		{
			dp[i][j]=dp[i-1][j];
		};
//此时dp[m][w]即为最大权值

优化：

//条件和上面一样
for(int i=1;i<=n;i++)
	for(int j=w;j>=a[i];j--)
		dp[j]=(dp[j],dp[j-a[i]]+val[i]);

例题：

完全背包

//条件和上面一样,只是每个物品可以取无数次
for(int i=1;i<=n;i++)
	for(int j=a[i];j<=w;j++)//注意这里的改动
		dp[j]=(dp[j],dp[j-a[i]]+val[i]);

混合背包

即有好几种背包的条件，分别写dp满足条件就可以了（比如NOIp2014TG的飞扬的小鸟）

for(int k=1;k<=组数;k++)
	for(int j=c;j>=0;j++)
		for(int i=1;i<=n;i++)
			if(j>=v[i])f[j]=maxn(f[j],f[j-v[i]]+w[i]);

例题：

  • NOIp2014TG 飞扬的小鸟

分组背包

这里有一篇分组背包博客写的不错，参考这篇博客吧。感谢博客的作者nywsp。

分治算法

二分

void binary(int l,int r)	//找最小
{
	while(r>l)
	{
		mid=(l+r)/2;
		if(check(mid))r=mid;
			else l=mid+1;
	};
	ans=l;
}

void binary(int l,int r)	//找最大
{
	while(r>l)
	{
		mid=(r+l)/2+1;	//特别注意
		if(check(mid))l=mid+1;
			else r=mid;
	};
	ans=l;
};

三分

三分法常用来找凸点或凹点。

三分法

图片和思路取自黑码的博客

先取 [L,R] 的中点 mid，再取 [mid,R] 的中点 mmid，通过比较 f(mid) 与 f(mmid) 的大小来缩小范围。

int SanFen(int l,int r) //找凸点  
{  
    while(l < r-1)  
    {  
        int mid  = (l+r)/2;  
        int mmid = (mid+r)/2;  
        if( f(mid) > f(mmid) )  
            r = mmid;  
        else  
            l = mid;  
    }  
    return f(l) > f(r) ? l : r;  
} 

int SanFen(int l,int r) //找凸点  
{  
    while(l < r-1)  
    {  
        int mid  = (l+r)/2;  
        int mmid = (mid+r)/2;  
        if( f(mid) > f(mmid) )  
            l = mid;  
        else  
            r = mmid;  
    }  
    return f(l) > f(r) ? l : r;  
}

排序算法

插入排序/希尔排序

因希尔排序是插入排序的升级版，故将两个算法放在了一起

具体分析请参考文章：插入排序与希尔排序

插入排序(1.0)

时间复杂度: 

//a[0]中存的是a数组的长度
void insertsort(int *a)
{
	n = a[0];
	for(int i=2;i<=n;i++)
	{
		int t = a[i];
		int j = i;
		while(j>0&&t<a[j-1])
		{
			a[j]=a[j-1];
			j--;
		}
		a[j]=t;
	}
}

插入排序(2.0)

//x是待插入元素的值
void binaryq(int *a,int l,int r,int x)
{
	int mid;
	while(l<=r)
	{
		mid = (l+r)/2;
		if(x>a[mid])
		{
			l = mid+1;
		}else{
			r = mid-1;
		}
	}
	return l;
}

void insertsearch2(int *a)
{
	int n = a[0];
	for(int i=2;i<=n;i++)
	{
		int t = a[i];
		int l = binaryq(a,0,i-1,a[i]);
		for(int j=i;j>l;j--)
		{
			a[j]=a[j-1];
		}
		a[l]=t;
	}
}

希尔排序

时间复杂度: 

void shellsort(int *a)
{
	int n = a[0];
	int h = 1;
	while(h<n/3)h=3*h+1;//选择步长
	while(h>=1)
	{
		for(int i=h;i<=n;i++)
			for(int j=i;j>=h;j-=h)
				if(a[j]<a[j-h])
				{
					int t=a[j];
					a[j]=a[j-h];
					a[j-h]=t;
				}
		h/=3;
	}
}

归并排序

void mergesort(int l,int r)
{
	if(l==r)return;
	int ret[maxn];
	int mid;
	
	mid=(l+r)/2;
	mergesort(l,mid); mergesort(mid+1,r);
	
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<a[j])
		{
			ret[k++]=a[i++];
		}else
		{
			ret[k++]=a[j++];
			ans+=mid-i+1;//求逆序对时加上这一句
		};
	};
	while(i<=mid)ret[k++]=a[i++];
	while(j<=r)ret[k++]=a[j++];
	
	for(int i=l;i<=r;i++)a[i]=ret[i];
}

字符串算法

Hash

哈希大法好

#define ull unsigned long long
ull hash(char *s)
{
	int l=strlen(S);
	ull ans=0;
	int seed=27;
	for(int a=0;a<l;a++)
		ans=ans*seed+a[i]-'a'+1;
	return ans;
};

Trie树

Trie数又叫字典树，比如由字符串”abc”,”ab”,”bd”,”dda”创建的Trie树如下图

Trie

以下Trie模板以HDU 1251为题目而写

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
struct trieNode{
    int count;
    trieNode* next[26];
    bool isend;
    
    trieNode():count(0),isend(false)
    {
        for(int i=0;i<26;i++)
            next[i] = NULL;
    }
};

void insert(trieNode* root,string word)
{
    trieNode* node = root;
    int id;
    int len = word.length();
    int i=0;
    while(i<len)
    {
        id = word[i]-'a';
        if(node->next[id] == NULL)
        {
            node->next[id]=new trieNode;
        }
        
        node = node->next[id];
        node->count+=1;
        
        i++;
    }
    node->isend=true;
}

int search(trieNode* root,string word)
{
    trieNode* node = root;
    int len=word.length();
    int i=0;
    while(i<len)
    {
        int id = word[i]-'a';
        if(node->next[id] != NULL)
        {
            node = node->next[id];
            i++;
        }else{
            return 0;
        }
    }
    
    return node->count;
}
int main()
{
    trieNode* root = new trieNode();
    string word;
    int flag=false;
    
    while(getline(cin,word))
    {
        if(flag)
        {
            cout<<search(root,word)<<endl;
        }else{
            if(!word.empty())
            {
                insert(root, word);
            }else{
                flag=true;
            }
        }
    }
    return 0;
}

KMP

const int maxn = 1e6+5;
int nt[maxn];
int len1,len2;
inline void getNext(char p[])//获得next数组
{
    int k=0;
    for(int i=1;i<len2;i++)
    {
        while(k && p[i]!=p[k])k=nt[k];
        nt[i+1] = p[i]==p[k]?++k:0;
    }
}
int main()
{
    char a[maxn],b[maxn];
    scanf("%s",a);
    scanf("%s",b);
    len1 = strlen(a);
    len2 = strlen(b);
    getNext(b);
    int k=0;
    for(int i=0;i<len1;i++)//与主串匹配
    {
        while(k && a[i]!=b[k])k=nt[k];
        k+= a[i]==b[k]?1:0;
        if(k==len2)printf("%d\n",i-len2+2);
    }
    return 0;
}

博弈论

Kuangbin的ACM博弈论教程

Nim博弈

题目：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可将一堆全取走，但不可不取，最后取完者为胜，求先手必胜或者必输。

解法：求每堆的异或值，若为0则必输，否则必赢

SG函数

int s[101],sg[10001],k;//sg-array init to -1 ; k is the up-limit of s-array ; s-array is opt
int getsg(int m)
{
	bool b[101]={0};
	for(int i=0;i<k;i++)
	{
		if(m-s[i]<0)break;
		if(sg[m-s[i]]==-1)
			sg[m-s[i]]=getsg(m-s[i]);
		b[sg[m-s[i]]]=1;
	}
	for(int i=0;;i++)
		if(!b[i])
			return i;
}

暴力算法

分块

推荐学习视频：UESTCACM

时间复杂度：

#include <cmath>
using namespace std;
const int max = 1e5+5;
int block,num,r[maxn],l[maxn],n,belong[maxn];
void build()
{
	block=sqrt(n);
	num=n/block;if(num%block)num++;
	for(int i=1;i<=n;i++)
		l[i]=(i-1)*block+1,r[i]=i*block;
	r[num]=n;
	for(int i=1;i<n;i++)
		belong[i]=(i-1)/block+1;
}

感谢您的阅读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute，Loading