ACM算法记录(2)

1、目录1.优先队列12.线段树+map13.快速幂44.欧拉定理55.求nm的最高位56三个重要的同余式威尔逊定理、费马小定理、欧拉定理 + 求幂大法的证明67Lucas定理：68求C（n,m）79最短路7Bellman-Ford算法（VE）7迪杰斯特拉算法（(v+E)*log(v)）9SPFA算法1010.最小生成树131Prim算法（ElogV）132.Kruskal(ElogE)1411二分图匹配151匈牙利算法152KM算法1612STL171.sort()172.qsort();173.stack/queue194.vector205.set216list2213卡特兰数2314RMQ

2、-ST算法2415背包问题2510-1背包252完全背包253多重背包2516中国剩余定理2617.扩展欧几里得算法2718大数乘法27Java 大数3419方差的一种处理3520海伦公式3621两圆面积交3622矩阵快速幂3723.树状数组3724二维图形的几何变换381、基本几何变换及变换矩阵381.1 平移变换391.2 缩放变换401.3 旋转变换411.4 对称变换421.5 错切变换442、 复合变换443、二维图形几何变换的计算464、复合变换的矩阵点乘的先后问题4725KMP4826二分图判定491.优先队列typedef struct data int start,i; da

3、ta():start(0),i(0) data(int a, int b):start(a),i(b) way; struct cmp bool operator()(const data &x, const data &y) return x.start+ax.i>y.start+ay.i; ; priority_queue< way, vector<way> , cmp >priority_queue<int, vector<int>, greater<int> >qi2;2.线

4、段树+map/* *Author :kuangbinCreated Time :2013-9-17 21:15:02File Name :G:2013ACM练习2013网络赛2013杭州网络赛1010.cpp* */#pragma comment(linker, "/STACK:1024000000,1024000000")#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#inc

5、lude <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>using namespace std;const int MAXN = 200010;struct Nodeint l,r;long long sum;/区间和 int mx;/最大值 int lazy;/懒惰标记，表示赋值为相同的segTreeMAXN*3;void push_up(int

6、i)if(segTreei.l = segTreei.r)return;segTreei.sum = segTreei<<1.sum + segTree(i<<1)|1.sum;segTreei.mx = max(segTreei<<1.mx,segTree(i<<1)|1.mx);void Update_Same(int i,int v)segTreei.sum = (long long)v*(segTreei.r - segTreei.l + 1);segTreei.mx = v;segTreei.lazy = 1;void push_dow

7、n(int i)if(segTreei.l = segTreei.r)return;if(segTreei.lazy) Update_Same(i<<1,segTreei.mx); Update_Same(i<<1)|1,segTreei.mx);segTreei.lazy = 0; int mexMAXN;void Build(int i,int l,int r)segTreei.l = l;segTreei.r = r;segTreei.lazy = 0;if(l = r) segTreei.mx = mexl;segTreei.sum = mexl;return;

8、 int mid = (l + r)>>1;Build(i<<1,l,mid);Build(i<<1)|1,mid+1,r); push_up(i);/将区间l,r的数都修改为vvoid Update(int i,int l,int r,int v)if(segTreei.l = l && segTreei.r = r) Update_Same(i,v);return; push_down(i);int mid = (segTreei.l + segTreei.r)>>1;if(r <= mid) Update(i<&

9、lt;1,l,r,v); else if(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的最左边位置int Get(int i,int v)if(segTreei.l = segTreei.r)return segTreei.l; push_down(i);if(segTreei<<1.mx > v)return Get(i<<1,v);else retur

10、n Get(i<<1)|1,v);int aMAXN;map<int,int>mp;int nextMAXN;int main() /freopen("in.txt","r",stdin); /freopen("out.txt","w",stdout);int n;while(scanf("%d",&n) && n) for(int i = 1;i <= n;i+)scanf("%d",&ai);mp.clear(

11、);int tmp = 0;for(int i = 1;i <= n;i+) mpai = 1;while(mp.find(tmp) != mp.end()tmp+;mexi = tmp; mp.clear();for(int i = n;i >= 1;i-) if(mp.find(ai) = mp.end()nexti = n+1;else nexti = mpai;mpai = i; Build(1,1,n);long long sum = 0;for(int i = 1;i <= n;i+) sum += segTree1.sum;if(segTree1.mx >

12、 ai) int l = Get(1,ai);int r = nexti;if(l < r)Update(1,l,r-1,ai); Update(1,i,i,0); printf("%I64dn",sum); return 0;3.快速幂int pow4(int a,int b)int r=1,base=a;while(b!=0) if(b&1)r*=base;base*=base; b>>=1; return r;ll pow4(ll a1,ll b1,ll mod1)ll r1=1,base1=a1%mod1;while(b1!=0) if(b

13、1&1) r1=r1*base1%mod1; base1=base1*base1%mod1; b1>>=1; return r1;4.欧拉定理假如p是质数，且(a,p)=1，那么 a(p-1)1（mod p）5.求nm的最高位long long int xnm;式子两边同时取lg lg(x)=mlg（n）；x10（mlg（n）；10的整数次方的最高位一定是1，所以x的最高位取决于mlg（n）的小数部分kmlg（n）的小数部分mlg（n）floor（mlg（n）；floor函数的用法请自行百度x的最高位floor（10k）；6三个重要的同余式威尔逊定理、费马小定理、欧拉定理

14、+ 求幂大法的证明一、威尔逊定理若p为质数，则p|(p-1)!+1亦：(p-1)!  p-1  -1(mod p)二、费马小定理假如p是质数，且gcd(a,p)=1，那么a(p-1) 1（mod p）我们可以利用费马小定理来简化幂模运算：由于a(p-1)a01(mod p)，所以ax(mod p)有循环节，长度为p-1，所以axa(x%(p-1)(mod p)例题：三、欧拉定理若a,m为正整数，且gcd(a,m) = 1，则a(m)1(mod m)我们亦可以利用欧拉定理来简化

15、幂模运算：axa(x%(m)(mod m)为下一节做铺垫，我们将axa(x%(m)(mod m)变下形：由于a(m)1(mod m)axa(x%(m)a(x%(m)+(m)(mod m)四、求幂大法（广义欧拉定理）及其证明对于同余式abx(mod m)，如何求出x？（1<=a,m<=1000000000，1<=b<=101000000）注意到b很大，我们可以先采取一些方法降幂。若gcd(a,m)=1，那么使用欧拉定理即可：aba(b%(m)(mod m)若gcd(a,m)>1，且b>(m)，则有“求幂大法”aba(b%

16、(m)+(m)(mod m)（当b<=(m)时直接用快速幂即可）7Lucas定理：A、B是非负整数，p是质数。AB写成p进制：A=anan-1.a0，B=bnbn-1.b0。则组合数C(A,B)与C(an,bn)*C(an-1,bn-1)*.*C(a0,b0)  modp同余即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p) ll Lucas(ll n1,ll m1,ll p1,ll *f1)if(m1=0)return 1;return C(n1%p1,m1%p1,p1,f1)*Lucas(n1/p1,m1/p1

17、,p1,f1)%p1;8求C（n,m）ll pow4(ll a1,ll b1,ll mod1)ll r1=1,base1=a1%mod1;while(b1!=0) if(b1&1) r1=r1*base1%mod1; base1=base1*base1%mod1; b1>>=1; return r1;void F(ll *f1,ll mod1)f10=1;f11=1;for(int i=2;i<100000;i+)f1i=f1i-1*i%mod1;ll C(ll n1,ll m1,ll mod1,ll *f1)if(n1<m1|n1<0|m1<0)r

18、eturn 0;return f1n1*pow4(f1n1-m1*f1m1%mod1,mod1-2,mod1)%mod1;9最短路Bellman-Ford算法（VE）#include<iostream>#include<cstdio>using namespace std; #define MAX 0x3f3f3f3f #define N 1010 int nodenum, edgenum, original; /点，边，起点typedef struct Edge /边 int u, v; int cost; Edge; Edge edgeN; int disN, pr

19、eN; bool Bellman_Ford() for(int i = 1; i <= nodenum; +i) /初始化disi = (i = original ? 0 : MAX); for(int i = 1; i <= nodenum - 1; +i) for(int j = 1; j <= edgenum; +j) if(disedgej.v > disedgej.u + edgej.cost) /松弛（顺序一定不能反） disedgej.v = disedgej.u + edgej.cost; preedgej.v = edgej.u; bool flag

20、= 1; /判断是否含有负权回路for(int i = 1; i <= edgenum; +i) if(disedgei.v > disedgei.u + edgei.cost) flag = 0; break; return flag; void print_path(int root) /打印最短路的路径（反向） while(root != preroot) /前驱 printf("%d->", root); root = preroot; if(root = preroot) printf("%dn", root); int ma

21、in() scanf("%d%d%d", &nodenum, &edgenum, &original); preoriginal = original; for(int i = 1; i <= edgenum; +i) scanf("%d%d%d", &edgei.u, &edgei.v, &edgei.cost); if(Bellman_Ford() for(int i = 1; i <= nodenum; +i) /每个点最短路 printf("%dn", disi);

22、printf("Path:"); print_path(i); elseprintf("have negative circlen"); return 0; 迪杰斯特拉算法（(v+E)*log(v)）typedef struct nodeint v,w;E;int b505;struct cmpbool operator()(const E &p1,const E &p2)return p1.w>p2.w;vector<E> edge505;priority_queue<E,vector<E>,cmp&

23、gt; pq;void Dijkstra()E x,y;while(!pq.empty()x=pq.top();pq.pop();int l=edgex.v.size();for(int i=0;i<l;i+)if(bedgex.vi.v>x.w+edgex.vi.w)bedgex.vi.v=x.w+edgex.vi.w;y.v=edgex.vi.v;y.w=bedgex.vi.v;pq.push(y); SPFA算法SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得

24、以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于1994年发表的。从名字我们就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra算法等便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。当然，

25、我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。定理：只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估

26、计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。期望时间复杂度：O(me)，其中m为所有顶点进队的平均次数，可以证明m一般小于等于2：“算法编程后实际运算情况表明m一般没有超过2n.事实上顶点入队次数m是一个不容易事先分析出来的数,但它确是一个随图的不同而略有不同的常数.所谓常数,就是与e无关,与n也无关,仅与边的权值分布有关.一旦图确定,权值确定,原点确定,m就是一个确定的常数.所以SPFA算法复杂度为O(e).

27、证毕."（SPFA的论文）不过，这个证明是非常不严谨甚至错误的，事实上在bellman算法的论文中已有这方面的内容，所以国际上一般不承认SPFA算法。对SPFA的一个很直观的理解就是由无权图的BFS转化而来。在无权图中，BFS首先到达的顶点所经历的路径一定是最短路(也就是经过的最少顶点数)，所以此时利用数组记录节点访问可以使每个顶点只进队一次，但在带权图中，最先到达的顶点所计算出来的路径不一定是最短路。一个解决方法是放弃数组，此时所需时间自然就是指数级的，所以我们不能放弃数组，而是在处理一个已经在队列中且当前所得的路径比原来更好的顶点时，直接更新最优解。SPFA算法有两个优化策略SL

28、F和LLLSLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾； LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出队进行松弛操作。 SLF 可使速度提高 15 20%；SLF + LLL 可提高约 50%。在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。#include

29、<iostream>#include<vector>#include<deque>using namespace std;struct Edgeint to,length;bool spfa(const int &beg,/出发点 const vector<vector<Edge>>&adjlist,/邻接表，通过传引用避免拷贝 vector<int>&dist,/出发点到各点的最短路径长度 vector<int>&path)/路径上到达该点的前一个点/C+习惯上函数异常返回非零

30、值，未异常才返回0（想想main函数），因此出现负权回路返回1！/福利：这个函数没有调用任何全局变量，可以直接复制！ const int &INF=0x7FFFFFFF,&NODE=adjlist.size();/用邻接表的大小传递顶点个数，减少参数传递 dist.assign(NODE,INF);/初始化距离为无穷大 path.assign(NODE,-1);/初始化路径为未知 deque<int> que(1,beg);/处理队列 vector<bool> flag(NODE,0);/标志数组，判断是否在队列中 vector<int> c

31、nt(NODE,0);/记录各点入队次数，用于判断负权回路 distbeg=0;/出发点到自身路径长度为0 +cntbeg;/开始计数 flagbeg=1;/入队while(!que.empty() const int now=que.front();/当前处理的点，由于后面被删除，不可定义成常量引用 que.pop_front(); flagnow=0;/将该点拿出队列for(int i=0; i!=adjlistnow.size(); +i)/遍历所有与当前点有路径的点 const int &next=adjlistnowi.to;/目标点，不妨定义成常量引用，稍稍快些 if(di

32、stnow<INF&&/若距离已知（否则下面右式计算结果必爆int），且 /注：与运算先判断左式是否成立，若不成立则右式不会被判断 distnext>distnow+adjlistnowi.length)/优于当前值 distnext=distnow+adjlistnowi.length;/更新 pathnext=now;/记录路径if(!flagnext)/若未在处理队列中 if(+cntnext=NODE)return 1;/计数后出现负权回路 if(que.empty()|/空队列，或（或运算实现原理类似与运算） distnext<distque.fro

33、nt()/优先级高于队首（SLF） que.push_front(next);/放在队首 else que.push_back(next);/否则放在队尾 flagnext=1;/入队 return 0;int main() int n_num,e_num,beg;/含义见下 cout<<"输入点数、边数、出发点："cin>>n_num>>e_num>>beg; vector<vector<Edge>> adjlist(n_num,vector<Edge>();/默认初始化邻接表for(in

34、t i=0,p; i!=e_num; +i) Edge tmp; cout<<"输入第"<<i+1<<"条边的起点、终点、长度："cin>>p>>tmp.to>>tmp.length;adjlistp.push_back(tmp); vector<int> dist,path;/用于接收最短路径长度及路径各点 if(spfa(beg,adjlist,dist,path)cout<<"图中存在负权回路n"else for(int i=0; i

35、!=n_num; +i) cout<<beg<<"到"<<i<<"的最短距离为"<<disti<<"，反向打印路径："for(int w=i; pathw>=0; w=pathw)cout<<w<<"<-"cout<<beg<<'n' 10.最小生成树1Prim算法（ElogV）typedef struct nodeint k,w;P;int dist1000010;v

36、ector<P> edge1000010;struct Cmp bool operator()(const P &x, const P &y) return x.w>y.w; ; priority_queue<P,vector<P>,Cmp> q;void Prim()while(!q.empty()q.pop();for(int i=0;i<1000010;i+)disti=1000000000;dist0=0;int l=edge0.size();for(int i=0;i<l;i+)q.push(edge0i);dis

37、tedge0i.k=edge0i.w;V-;P p;sum=0;while(V-)p=q.top();q.pop();distp.k=0;l=edgep.k.size();for(int i=0;i<l;i+)if(distedgep.ki.k>edgep.ki.w)distedgep.ki.k=edgep.ki.w;q.push(edgep.ki);2.Kruskal(ElogE)typedef struct nodeint w,l,r;P;P edge2000010;int f1000010,tot;bool Comp(const P &a1,const P &

38、a2)return a1.w<a2.w;int Find(int x)if(fx=x)return x;elsereturn fx=Find(fx);int Kruskal()int cnt=n*m,ans=0;sort(edge,edge+tot,Comp);for(int i=0;i<n*m;i+)fi=i;for(int i=0;i<tot;i+)int t1=Find(edgei.l);int t2=Find(edgei.r);if(t1!=t2)ft1=t2;ans+=edgei.w;cnt-;if(cnt=1)break;return ans;11二分图匹配1匈牙

39、利算法#include<iostream>#include<cstring>using namespace std;int map105105;int visit105,flag105;int n,m;bool dfs(int a)for(int i=1; i<=n; i+) if(mapai&&!visiti) visiti=1;if(flagi=0|dfs(flagi) flagi=a;return true; return false;int main()while(cin>>n1 >>n2 >>m) me

40、mset(map,0,sizeof(map);for(int i=1; i<=m; i+) int x,y;cin>>x>>y;mapxy=1; memset(flag,0,sizeof(flag);int result=0;for(int i=1; i<=n1; i+) memset(visit,0,sizeof(visit);if(dfs(i)result+; cout<<result<<endl; return 0;2KM算法const int maxn=20,INF=2147483647;int wmaxnmaxn;int l

41、xmaxn=0,lymaxn=0;/顶标intl inkymaxn;int visxmaxn,visymaxn;int lack;bool find(intx)visxx=true;for(inty=0;y<maxn;y+)if(visyy)continue;int t=lxx+lyy-wxy;if(t=0)visyy=true;if(linkyy=-1|find(linkyy)linkyy=x;return true;else if(lack>t)lack=t;return false;void KM()memset(linky,-1,sizeof(linky);for(inti

42、=0;i<maxn;i+)for(intj=0;j<maxn;j+)if(wij>lxi)lxi=wij;/初始化顶标for(intx=0;x<maxn;x+)for(;)memset(visx,0,sizeof(visx);memset(visy,0,sizeof(visy);lack=INF;if(find(x)break;for(inti=0;i<maxn;i+)if(visxi)lxi-=lack;if(visyi)lyi+=lack;12STL1.sort() sort(a,a+n);bool comp(constint&a,const

43、int&b)return a>b;bool Comp(const P &a1,const P &a2)return a1.w<a2.w;/从小到大2.qsort();qsort(a,1000,sizeof(int),comp);其中comp函数应写为：1234int comp(const void*a,const void*b)return *(int*)a-*(int*)b;上面是由小到大排序，return *(int *)b - *(int *)a; 为由大到小排序。对一个二维数组进行排序：int a10002;

44、其中按照a0的大小进行一个整体的排序，其中a1必须和a0一起移动交换。/即第一行和第二行（a0和a1分别代表第一行和第二行的首地址）。使用库函数排序的代码量并不比用冒泡排序法小，但速度却快很多。qsort(a,1000,sizeof(int)*2,comp);int comp(const void*a,const void*b)return(int*)a)0-(int*)b)0;对字符串进行排序int Comp(const void*p1,const void*p2)return strcmp(char*)p2,(char*)p1);int main()char aMAX1MAX2;initi

45、al(a);qsort(a,lenth,sizeof(a0),Comp);/lenth为数组a的长度按结构体中某个关键字排序（对结构体一级排序）：structNodedouble data;int other;s100;int Comp(constvoid*p1,constvoid*p2)return(*(Node*)p2).data>(*（Node*）p1).data?1:-1;qsort(s,100,sizeof(s0),Comp);按结构体中多个关键字排序（对结构体多级排序）以二级为例：struct Nodeint x;int y;s100;/按照x从小到大排序，当x相等时按y从大

46、到小排序int Comp(const void*p1,const void*p2)struct Node*c=(Node*)p1;struct Node*d=(Node*)p2;if(c->x!=d->x)returnc->x-d->x;else return d->y-c->y;对结构体中字符串进行排序：struct Nodeint data;char str100;s100;/按照结构体中字符串str的字典序排序int Comp(const void*p1,const void*p2)return strcmp(*(Node*)p1).str,(*(No

47、de*)p2).str);qsort(s,100,sizeof(s0),Comp);计算几何中求凸包的Compint Comp(const void*p1,const void*p2)/重点Comp函数，把除了1点外的所有的点旋转角度排序struct point*c=(point*)p1;struct point*d=(point*)p2;if(cacl(*c,*d,p1)<0) return1;elseif(!cacl(*c,*d,p1)&&dis(c->x,c->y,p1.x,p1.y)<dis(d->x,d->y,p1.x,p1.y)/

48、如果在一条直线上，则把远的放在前面return1;elsereturn-1;3.stack/queues.push();s.pop();s.top();s.empty();s.size();q.push();q.pop();q.front();q.back();q.empty();q.size();4.vector1 基本操作(1)头文件#include<vector>.(2)创建vector对象，vector<int> vec;(3)尾部插入数字：vec.push_back(a);(4)使用下标访问元素，cout<<vec0<<endl;记住下

49、标是从0开始的。(5)使用迭代器访问元素.vector<int>:iterator it;for(it=vec.begin();it!=vec.end();it+)cout<<*it<<endl;(6)插入元素： vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;(7)删除元素： vec.erase(vec.begin()+2);删除第3个元素vec.erase(vec.begin()+i,vec.end()+j);删除区间i,j-1;区间从0开始(8)向量大小:vec.size();(9)清空:vec.clear();3

50、算法(1) 使用reverse将元素翻转：需要头文件#include<algorithm>reverse(vec.begin(),vec.end();将元素翻转(在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含.)(2)使用sort排序：需要头文件#include<algorithm>，sort(vec.begin(),vec.end();(默认是按升序排列,即从小到大).可以通过重写排序比较函数按照降序比较，如下：定义排序比较函数：bool Comp(const int &a,const int &b)return a>b;调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。5.set1.元素插入：insert()2.中序遍历：类似vector遍历（用迭代器）3.反向遍历：利用反向迭代器reverse_iterator。例：set<int> s; .set<int>:reverse_iterator rit;for(rit=s.rbegin();rit!=s.rend();rit+)4.元素删除：与插入一样，可以高效的删除，并自动调整使红黑树平衡。set<int> s; s.erase(2);