ACM算法记录 2.docx - 冰点文库

资源描述

ACM算法记录 2.docx

《ACM算法记录 2.docx》由会员分享，可在线阅读，更多相关《ACM算法记录 2.docx（78页珍藏版）》请在冰点文库上搜索。

ACM算法记录 2.docx

ACM算法记录2

1.优先队列1

2.线段树+map1

3.快速幂4

4.欧拉定理5

5.求n^m的最高位5

6．三个重要的同余式——威尔逊定理、费马小定理、欧拉定理+求幂大法的证明6

7．Lucas定理：

8．求C（n,m）7

9．最短路7

Bellman-Ford算法（VE）7

迪杰斯特拉算法（（v+E）*log（v））9

SPFA算法10

10.最小生成树13

1．Prim算法（ElogV）13

2.Kruskal（ElogE）14

11．二分图匹配15

1．匈牙利算法15

2．KM算法16

12．STL17

1.sort（）17

2.qsort（）;17

3.stack/queue19

4.vector20

5.set21

6．list22

13．卡特兰数23

14．RMQ-ST算法24

15．背包问题25

1．0-1背包25

2．完全背包25

3．多重背包25

16．中国剩余定理26

17.扩展欧几里得算法27

18．大数乘法27

Java大数34

19．方差的一种处理35

20．海伦公式36

21．两圆面积交36

22．矩阵快速幂37

23.树状数组37

24．二维图形的几何变换38

1、基本几何变换及变换矩阵38

1.1平移变换39

1.2缩放变换40

1.3旋转变换41

1.4对称变换42

1.5错切变换44

2、复合变换44

3、二维图形几何变换的计算46

4、复合变换的矩阵点乘的先后问题47

25．KMP48

26．二分图判定49

1.优先队列

typedefstructdata

{

intstart,i;

data（）:

start（0）,i（0）{}

data（inta,intb）:

start（a）,i（b）{}

}way;

structcmp

{

booloperator（）（constdata&x,constdata&y）

{

returnx.start+a[x.i]>y.start+a[y.i];

}

};

priority_queue,cmp>

priority_queue, greater >qi2;

2.线段树+map

/************************************************

Author:

kuangbin

CreatedTime:

2013-9-1721:

15:

FileName:

\2013ACM练习\2013网络赛\2013杭州网络赛\1010.cpp

*************************************************/

#pragmacomment（linker,"/STACK:

1024000000,1024000000"）

#include

usingnamespacestd;

constintMAXN=200010;

structNode

{

intl,r;

longlongsum;//区间和

intmx;//最大值

intlazy;//懒惰标记，表示赋值为相同的

}segTree[MAXN*3];

voidpush_up（inti）

{

if（segTree[i].l==segTree[i].r）return;

segTree[i].sum=segTree[i<<1].sum+segTree[（i<<1）|1].sum;

segTree[i].mx=max（segTree[i<<1].mx,segTree[（i<<1）|1].mx）;

}

voidUpdate_Same（inti,intv）

{

segTree[i].sum=（longlong）v*（segTree[i].r-segTree[i].l+1）;

segTree[i].mx=v;

segTree[i].lazy=1;

}

voidpush_down（inti）

{

if（segTree[i].l==segTree[i].r）return;

if（segTree[i].lazy）

{

Update_Same（i<<1,segTree[i].mx）;

Update_Same（（i<<1）|1,segTree[i].mx）;

segTree[i].lazy=0;

}

intmex[MAXN];

voidBuild（inti,intl,intr）

{

segTree[i].l=l;

segTree[i].r=r;

segTree[i].lazy=0;

if（l==r）

{

segTree[i].mx=mex[l];

segTree[i].sum=mex[l];

return;

}

intmid=（l+r）>>1;

Build（i<<1,l,mid）;

Build（（i<<1）|1,mid+1,r）;

push_up（i）;

}

//将区间[l,r]的数都修改为v

voidUpdate（inti,intl,intr,intv）

{

if（segTree[i].l==l&&segTree[i].r==r）

{

Update_Same（i,v）;

return;

}

push_down（i）;

intmid=（segTree[i].l+segTree[i].r）>>1;

if（r<=mid）

{

Update（i<<1,l,r,v）;

}

elseif（l>mid）

{

Update（（i<<1）|1,l,r,v）;

}

else

{

Update（i<<1,l,mid,v）;

Update（（i<<1）|1,mid+1,r,v）;

}

push_up（i）;

}

//得到值>=v的最左边位置

intGet（inti,intv）

{

if（segTree[i].l==segTree[i].r）

returnsegTree[i].l;

push_down（i）;

if（segTree[i<<1].mx>v）

returnGet（i<<1,v）;

elsereturnGet（（i<<1）|1,v）;

}

inta[MAXN];

mapmp;

intnext[MAXN];

intmain（）

{

//freopen（"in.txt","r",stdin）;

//freopen（"out.txt","w",stdout）;

intn;

while（scanf（"%d",&n）&&n）

{

for（inti=1;i<=n;i++）

scanf（"%d",&a[i]）;

mp.clear（）;

inttmp=0;

for（inti=1;i<=n;i++）

{

mp[a[i]]=1;

while（mp.find（tmp）!

=mp.end（））tmp++;

mex[i]=tmp;

}

mp.clear（）;

for（inti=n;i>=1;i--）

{

if（mp.find（a[i]）==mp.end（））next[i]=n+1;

elsenext[i]=mp[a[i]];

mp[a[i]]=i;

}

Build（1,1,n）;

longlongsum=0;

for（inti=1;i<=n;i++）

{

sum+=segTree[1].sum;

if（segTree[1].mx>a[i]）

{

intl=Get（1,a[i]）;

intr=next[i];

if（l

Update（1,l,r-1,a[i]）;

}

Update（1,i,i,0）;

}

printf（"%I64d\n",sum）;

}

return0;

}

3.快速幂

intpow4（inta,intb）

{

intr=1,base=a;

while（b!

=0）

{

if（b&1）

r*=base;

base*=base;

b>>=1;

}

returnr;

}

llpow4（lla1,llb1,llmod1）

{

llr1=1,base1=a1%mod1;

while（b1!

=0）

{

if（b1&1）

r1=r1*base1%mod1;

base1=base1*base1%mod1;

b1>>=1;

}

returnr1;

}

4.欧拉定理

假如p是质数，且（a,p）=1，那么a^（p-1）≡1（modp）

5.求n^m的最高位

longlongintx＝n^m;

式子两边同时取lglg（x）=m＊lg（n）；

x＝10^（m＊lg（n））；

10的整数次方的最高位一定是1，所以x的最高位取决于m＊lg（n）的小数部分

k＝m＊lg（n）的小数部分＝m＊lg（n）－floor（m＊lg（n））；

floor函数的用法请自行XX

x的最高位＝floor（10^k）；

6．三个重要的同余式——威尔逊定理、费马小定理、欧拉定理+求幂大法的证明

一、威尔逊定理

若p为质数，则

p|（p-1）!

亦：

（p-1）!

≡ p-1 ≡ -1（mod p）

二、费马小定理

假如p是质数，且gcd（a,p）=1，那么

a^（p-1） ≡1（mod p）

我们可以利用费马小定理来简化幂模运算：

由于a^（p-1）≡a^0≡1（mod p），所以a^x（mod p）有循环节，长度为p-1，所以a^x≡a^（x%（p-1））（mod p）

例题：

三、欧拉定理

若a,m为正整数，且gcd（a,m） = 1，则

a^φ（m）≡1（modm）

我们亦可以利用欧拉定理来简化幂模运算：

a^x≡a^（x%φ（m））（mod m）

为下一节做铺垫，我们将a^x≡a^（x%φ（m））（mod m）变下形：

由于a^φ（m）≡1（modm）

a^x≡a^（x%φ（m））≡a^（x%φ（m）+φ（m））（modm）

四、求幂大法（广义欧拉定理）及其证明

对于同余式a^b≡x（mod m），如何求出x？

（1<=a,m<=1000000000，1<=b<=10^1000000）

注意到b很大，我们可以先采取一些方法降幂。

若gcd（a,m）=1，那么使用欧拉定理即可：

a^b≡a^（b%φ（m））（mod m）

若gcd（a,m）>1，且b>φ（m），则有“求幂大法”——a^b≡a^（b%φ（m）+φ（m））（mod m）

（当b<=φ（m）时直接用快速幂即可）

7．Lucas定理：

A、B是非负整数，p是质数。

AB写成p进制：

A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。

则组合数C（A,B）与C（a[n],b[n]）*C（a[n-1],b[n-1]）*...*C（a[0],b[0]） modp同余

即：

Lucas（n,m,p）=c（n%p,m%p）*Lucas（n/p,m/p,p）

llLucas（lln1,llm1,llp1,ll*f1）

{

if（m1==0）

return1;

returnC（n1%p1,m1%p1,p1,f1）*Lucas（n1/p1,m1/p1,p1,f1）%p1;

}

8．求C（n,m）

llpow4（lla1,llb1,llmod1）

{

llr1=1,base1=a1%mod1;

while（b1!

=0）

{

if（b1&1）

r1=r1*base1%mod1;

base1=base1*base1%mod1;

b1>>=1;

}

returnr1;

}

voidF（ll*f1,llmod1）

{

f1[0]=1;

f1[1]=1;

for（inti=2;i<100000;i++）

f1[i]=f1[i-1]*i%mod1;

}

llC（lln1,llm1,llmod1,ll*f1）

{

if（n1

return0;

returnf1[n1]*pow4（f1[n1-m1]*f1[m1]%mod1,mod1-2,mod1）%mod1;

}

9．最短路

Bellman-Ford算法（VE）

#include

usingnamespacestd;

#defineMAX0x3f3f3f3f

#defineN1010

intnodenum,edgenum,original;//点，边，起点

typedefstructEdge//边

{

intu,v;

intcost;

}Edge;

Edgeedge[N];

intdis[N],pre[N];

boolBellman_Ford（）

{

for（inti=1;i<=nodenum;++i）//初始化

dis[i]=（i==original?

MAX）;

for（inti=1;i<=nodenum-1;++i）

for（intj=1;j<=edgenum;++j）

if（dis[edge[j].v]>dis[edge[j].u]+edge[j].cost）//松弛（顺序一定不能反~）

{

dis[edge[j].v]=dis[edge[j].u]+edge[j].cost;

pre[edge[j].v]=edge[j].u;

}

boolflag=1;//判断是否含有负权回路

for（inti=1;i<=edgenum;++i）

if（dis[edge[i].v]>dis[edge[i].u]+edge[i].cost）

{

flag=0;

break;

}

returnflag;

}

voidprint_path（introot）//打印最短路的路径（反向）

{

while（root!

=pre[root]）//前驱

{

printf（"%d-->",root）;

root=pre[root];

}

if（root==pre[root]）

printf（"%d\n",root）;

}

intmain（）

{

scanf（"%d%d%d",&nodenum,&edgenum,&original）;

pre[original]=original;

for（inti=1;i<=edgenum;++i）

{

scanf（"%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost）;

}

if（Bellman_Ford（））

for（inti=1;i<=nodenum;++i）//每个点最短路

{

printf（"%d\n",dis[i]）;

printf（"Path:

"）;

print_path（i）;

}

else

printf（"havenegativecircle\n"）;

return0;

}

迪杰斯特拉算法（（v+E）*log（v））

typedefstructnode

{

intv,w;

}E;

intb[505];

structcmp

{

booloperator（）（constE&p1,constE&p2）

{

returnp1.w>p2.w;

}

};

vectoredge[505];

priority_queue,cmp>pq;

voidDijkstra（）

{

Ex,y;

while（!

pq.empty（））

{

x=pq.top（）;

pq.pop（）;

intl=edge[x.v].size（）;

for（inti=0;i

{

if（b[edge[x.v][i].v]>x.w+edge[x.v][i].w）

{

b[edge[x.v][i].v]=x.w+edge[x.v][i].w;

y.v=edge[x.v][i].v;

y.w=b[edge[x.v][i].v];

pq.push（y）;

}

SPFA算法

SPFA（ShortestPathFasterAlgorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

求单源最短路的SPFA算法的全称是：

ShortestPathFasterAlgorithm，是西南交通大学段凡丁于1994年发表的。

从名字我们就可以看出，这种算法在效率上一定有过人之处。

很多时候，给定的图存在负权边，这时类似Dijkstra算法等便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。

简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。

如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。

当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。

我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。

我们采取的方法是动态逼近法：

设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。

这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

定理：

只要最短路径存在，上述SPFA算法必定能求出最小值。

证明：

每次将点放入队尾，都是经过松弛操作达到的。

换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。

所以算法的执行会使d越来越小。

由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。

因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。

期望时间复杂度：

O（me），其中m为所有顶点进队的平均次数，可以证明m一般小于等于2：

“算法编程后实际运算情况表明m一般没有超过2n.事实上顶点入队次数m是一个不容易事先分析出来的数,但它确是一个随图的不同而略有不同的常数.所谓常数,就是与e无关,与n也无关,仅与边的权值分布有关.一旦图确定,权值确定,原点确定,m就是一个确定的常数.所以SPFA算法复杂度为O（e）.证毕."（SPFA的论文）不过，这个证明是非常不严谨甚至错误的，事实上在bellman算法的论文中已有这方面的内容，所以国际上一般不承认SPFA算法。

对SPFA的一个很直观的理解就是由无权图的BFS转化而来。

在无权图中，BFS首先到达的顶点所经历的路径一定是最短路（也就是经过的最少顶点数），所以此时利用数组记录节点访问可以使每个顶点只进队一次，但在带权图中，最先到达的顶点所计算出来的路径不一定是最短路。

一个解决方法是放弃数组，此时所需时间自然就是指数级的，所以我们不能放弃数组，而是在处理一个已经在队列中且当前所得的路径比原来更好的顶点时，直接更新最优解。

SPFA算法有两个优化策略SLF和LLL——SLF：

SmallLabelFirst策略，设要加入的节点是j，队首元素为i，若dist（j）

LargeLabelLast策略，设队首元素为i，队列中所有dist值的平均值为x，若dist（i）>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist（i）<=x，则将i出队进行松弛操作。

SLF可使速度提高15~20%；SLF+LLL可提高约50%。

在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。

#include

usingnamespacestd;

structEdge

{

intto,length;

};

boolspfa（constint&beg,//出发点

constvector>&adjlist,//邻接表，通过传引用避免拷贝

vector&dist,//出发点到各点的最短路径长度

vector&path）//路径上到达该点的前一个点

//C++习惯上函数异常返回非零值，未异常才返回0（想想main函数），因此出现负权回路返回1！

//福利：

这个函数没有调用任何全局变量，可以直接复制！

{

constint&INF=0x7FFFFFFF,&NODE=adjlist.size（）;//用邻接表的大小传递顶点个数，减少参数传递

dist.assign（NODE,INF）;//初始化距离为无穷大

path.assign（NODE,-1）;//初始化路径为未知

dequeque（1,beg）;//处理队列

vectorflag（NODE,0）;//标志数组，判断是否在队列中

vectorcnt（NODE,0）;//记录各点入队次数，用于判断负权回路

dist[beg]=0;//出发点到自身路径长度为0

++cnt[beg];//开始计数

flag[beg]=1;//入队

while（!

que.empty（））

展开阅读全文