C++算法及数据结构模板
本文章原为2016-09-28的文章冲刺NOIp2016算法模板(C++)，本人于2016-11-20日从OI退役，并于2017-09-09服役ACM，故将本篇文章更新。之后本文章将持续更新并囊括更多的不仅限于OI的算法与数据结构。
程序大部分没经过编译和测评，欢迎在评论区指出本文中的错误 另：点开右下角像WIFI一样的标志进入RSS模式(XML文件)即可避免索引目录鬼畜的问题(现该问题已经解决)（可能需要向下翻一会才能找到本篇文章）
OI比赛记得考前一定要练好DFS和记忆化DFS！！骗分必用！
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++改
单调队列
- 例题:Luogu P1823 音乐会的等待（我写了一篇此题的解题报告）
以下单调队列的标程就用的音乐会的等待的。
#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;
};
};
};
应用举例：
- 模板题 : Luogu P3383
验证素数
普通方法
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；
} //不理解建议背过
应用举例：
- 模板题 : NOIp2012TG day2 T1 / Luogu P1082
逆元
所谓逆元就是，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;
}
那么同时有个除法取模的问题
有a / c mod p
= a / c mod p * 1
= a / c mod p * c^(p-1) mod p
= a * c^(p-2) mod p
即可
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;
}
应用举例：
- 模板题 : NOIp2003 PJ / Luogu P1044
高精
读入、储存与输出
以下代码块均包含以下语句 :
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*。
- 当一个点第k次出队时，答案是它的优先级
- 当终点第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的最短路的长度。
考虑如何来得到一个合法的非树边序列。
- 找到一条起点在当前点p到根t的路径上的非树边
- 令p等于这条边的终点。
我们可以通过这样的方法来得到所有的非树边序列。但是我们并不需要所有的非树边序列，因此当找到第x短路后再进行拓展状态，然后用优先队列来维护。
但是这样每次拓展时间复杂度可达O(m)，总时间复杂度可以达到O(mklog(mk))。
令人无法接受。但是其中真正会被用到的状态十分少。
因此可以像UVa 11997那样进行优化。
当一个非树边序列出队时，代价和比它大的才可能有用。
因此，考虑一个非树边序列出队时通过下面的方法来进行得到新的序列:
- 追加操作：假如最后一条非树边的终点为v，找到一条起点在v到t的路径上代价最小的非树边追加在当前非树边序列后
- 替换操作：将最后一条非树边更换为代价比它大的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条边时，最小生成树就已经生成完了，剩下的边就不用再枚举了。
训练参考:
- 最小生成树: Slim Span(UVa1395)
- 最小生成树: Buy or Build(UVa1151)
图的遍历
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]);
例题：
- Luogu1048 菜药
完全背包
//条件和上面一样,只是每个物品可以取无数次
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。
- 练习题:luogu P1757
分治算法
二分
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模板以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;
}
博弈论
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;
}
感谢您的阅读
