《ACM算法与程序设计》解题报告模板

三角形面积计算 (1)字典树模板 (2)求线段所在直线 (5)求外接圆 (5)求内接圆 (6)判断点是否在直线上 (8)简单多边形面积计算公式 (8)stein算法求最大共约数 (9)最长递增子序列模板——o(nlogn算法实现) (9)判断图中同一直线的点的最大数量 (10)公因数和公倍数 (12)已知先序中序求后序 (12)深度优先搜索模板 (13)匈牙利算法——二部图匹配BFS实现 (15)带输出路径的prime算法 (17)prime模板 (18)kruskal模板 (19)dijsktra (22)并查集模板 (23)高精度模板 (24)三角形面积计算//已知三条边和外接圆半径，公式为s = a*b*c/(4*R)double GetArea(double a, double b, double c, double R){return a*b*c/4/R;}//已知三条边和内接圆半径，公式为s = prdouble GetArea(double a, double b, double c, double r){return r*(a+b+c)/2;}//已知三角形三条边，求面积double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}//已知道三角形三个顶点的坐标struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};double GetArea(Point p1, Point p2, Point p3){double t =-p2.x*p1.y+p3.x*p1.y+p1.x*p2.y-p3.x*p2.y-p1.x*p3.y+p2.x*p3.y;if(t < 0) t = -t;return t/2;}字典树模板#include <stdio.h>#include <string.h>#include <memory.h>#define BASE_LETTER 'a'#define MAX_TREE 35000#define MAX_BRANCH 26struct{int next[MAX_BRANCH]; //记录分支的位置int c[MAX_BRANCH]; //查看分支的个数int flag; //是否存在以该结点为终止结点的东东，可以更改为任意的属性}trie[MAX_TREE];int now;void init(){now = 0;memset(&trie[now], 0, sizeof(trie[now]));now ++;}int add (){memset(&trie[now], 0, sizeof(trie[now]));return now++;}int insert( char *str){int pre = 0, addr;while( *str != 0 ){addr = *str - BASE_LETTER;if( !trie[pre].next[addr] )trie[pre].next[addr] = add();trie[pre].c[addr]++;pre = trie[pre].next[addr];str ++;}trie[pre].flag = 1;return pre;}int search( char *str ){int pre = 0, addr;while( *str != 0 ){addr = *str - BASE_LETTER;if ( !trie[pre].next[addr] )return 0;pre = trie[pre].next[addr];str ++;}if( !trie[pre].flag )return 0;return pre;}pku2001题，源代码：void check( char *str ){int pre = 0, addr;while(*str != 0){addr = *str - BASE_LETTER;if( trie[pre].c[addr] == 1) {printf("%c\n", *str);return;}printf("%c", *str);pre = trie[pre].next[addr];str ++;}printf("\n");}char input[1001][25];int main(){int i = 0,j;init();while(scanf("%s", input[i]) != EOF){getchar();insert(input[i]);i++;}for(j = 0; j < i; j ++){printf("%s ", input[j]);check(input[j]);}return 0;}求线段所在直线//*****************************线段所在的直线struct Line{double a, b, c;};struct Point{double x, y;}Line GetLine(Point p1, Point p2){//ax+by+c = 0返回直线的参数Line line;line.a = p2.y - p1.y;line.b = p1.x - p2.x;line.c = p2.x*p1.y - p1.x*p2.y;return line;}求外接圆//***************已知三角形三个顶点坐标，求外接圆的半径和坐标********************struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};struct TCircle{double r;Point p;}double distance(Point p1, Point p2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}TCircle GetTCircle(Point p1, Point p2, Point p3){double a, b, c;double xa,ya, xb, yb, xc, yc, c1, c2;TCircle tc;a = distance(p1, p2);b = distance(p2, p3);c = distance(p3, p1);//求半径tc.r = a*b*c/4/GetArea(a, b, c);//求坐标xa = p1.x; ya = p1.b;xb = p2.x; yb = p2.b;xc = p3.x; yc = p3.b;c1 = (xa*xa + ya*ya - xb*xb - yb*yb)/2;c2 = (xa*xa + ya*ya - xc*xc - yc*yc)/2;tc.p.x = (c1*(ya-yc) - c2*(ya-yb))/((xa-xb)*(ya-yc) - (xa-xc)*(ya-yb)); tc.p.y = (c1*(xa-xc) - c2*(xa-xb))/((ya-yb)*(xa-xc) - (ya-yc)*(xa-xb));return tc;}求内接圆struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};struct TCircle{double r;Point p;}double distance(Point p1, Point p2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}TCircle GetTCircle(Point p1, Point p2, Point p3){double a, b, c;double xa,ya, xb, yb, xc, yc, c1, c2, f1, f2;double A,B,C;TCircle tc;a = distance(p1, p2);b = distance(p3, p2);c = distance(p3, p1);//求半径tc.r = 2*GetArea(a, b, c)/(a+b+c);//求坐标A = acos((b*b+c*c-a*a)/(2*b*c));B = acos((a*a+c*c-b*b)/(2*a*c));C = acos((a*a+b*b-c*c)/(2*a*b));p = sin(A/2); p2 = sin(B/2); p3 = sin(C/2);xb = p1.x; yb = p1.b;xc = p2.x; yc = p2.b;xa = p3.x; ya = p3.b;f1 = ( (tc.r/p2)*(tc.r/p2) - (tc.r/p)*(tc.r/p) + xa*xa - xb*xb + ya*ya - yb*yb)/2;f2 = ( (tc.r/p3)*(tc.r/p3) - (tc.r/p)*(tc.r/p) + xa*xa - xc*xc + ya*ya - yc*yc)/2;tc.p.x = (f1*(ya-yc) - f2*(ya-yb))/((xa-xb)*(ya-yc)-(xa-xc)*(ya-yb)); tc.p.y = (f1*(xa-xc) - f2*(xa-xb))/((ya-yb)*(xa-xc)-(ya-yc)*(xa-xb));return tc;}判断点是否在直线上//**************判断点是否在直线上********************* //判断点p是否在直线[p1,p2]struct Point{double x,y;};bool isPointOnSegment(Point p1, Point p2, Point p0){//叉积是否为0，判断是否在同一直线上if((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) != 0)return false;//判断是否在线段上if((p0.x > p1.x && p0.x > p2.x) || (p0.x < p1.x && p0.x < p2.x)) return false;if((p0.y > p1.y && p0.y > p1.y) || (p0.y < p1.y && p0.y < p2.y)) return false;return true;}简单多边形面积计算公式struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};Point pp[10];double GetArea(Point *pp, int n){//n为点的个数，pp中记录的是点的坐标int i = 1;double t = 0;for(; i <= n-1; i++)t += pp[i-1].x*pp[i].y - pp[i].x*pp[i-1].y;t += pp[n-1].x*pp[0].y - pp[0].x*pp[n-1].y;if(t < 0) t = -t;return t/2;}stein算法求最大共约数int gcd(int a,int b){if (a == 0) return b;if (b == 0) return a;if (a % 2 == 0 && b % 2 == 0) return 2 * gcd(a/2,b/2); else if (a % 2 == 0) return gcd(a/2,b);else if (b % 2 == 0) return gcd(a,b/2);else return gcd(abs(a-b),min(a,b));}最长递增子序列模板——o(nlogn算法实现)#include <stdio.h>#define MAX 40000int array[MAX], B[MAX];int main(){int count,i,n,left,mid,right,Blen=0,num;scanf("%d",&count); //case的个数while(count--){scanf("%d",&n); //每组成员的数量Blen = 0;for(i=1;i<=n;i++)scanf("%d",&array[i]); //读入每个成员for(i=1;i<=n;i++){num = array[i];left = 1;right = Blen;while(left<=right){mid = (left+right)/2;if(B[mid]<num)left = mid+1;elseright = mid-1;}B[left] = num;if(Blen<left)Blen++;}printf("%d\n",Blen);//输出结果}return 1;}判断图中同一直线的点的最大数量#include <iostream>#include <cstdio>#include <memory>using namespace std;#define MAX 1010 //最大点的个数struct point{int x,y;}num[MAX];int used[MAX][MAX*2]; //条件中点的左边不会大于1000,just equal MAX int countN[MAX][MAX*2];#define abs(a) (a>0?a:(-a))int GCD(int x, int y){int temp;if(x < y){temp = x; x = y; y = temp;}while(y != 0){temp = y;y = x % y;x = temp;}return x;}int main(){int n,i,j;int a,b,d,ans;while(scanf("%d", &n)==1){//initeans = 1;memset(used, 0, sizeof(used));memset(countN, 0, sizeof(countN));//readfor(i = 0; i < n; i++)scanf("%d%d", &num[i].x, &num[i].y);for(i = 0; i < n-1; i++){for(j = i+1; j < n; j++){b = num[j].y-num[i].y;a = num[j].x-num[i].x;if(a < 0) //这样可以让（2，3）（－2，－3）等价{a = -a; b = -b;}d = GCD(a,abs(b));a /= d;b /= d; b += 1000;//条件中点的左边不会大于1000if(used[a][b] != i+1){used[a][b] = i+1;countN[a][b] = 1;}else{countN[a][b]++;if(ans < countN[a][b])ans = countN[a][b];}}//for}//forprintf("%d\n", ans+1);}return 0;}公因数和公倍数int GCD(int x, int y){int temp;if(x < y){temp = x; x = y; y = temp;}while(y != 0){temp = y;y = x % y;x = temp;}return x;}int beishu(int x, int y){return x * y / GCD(x,y);}已知先序中序求后序#include <iostream>#include <string>using namespace std;string post;void fun(string pre, string mid){if(pre == "" || mid == "") return;int i = mid.find(pre[0]);fun(pre.substr(1,i), mid.substr(0,i));fun(pre.substr(i+1, (int)pre.length()-i-1), mid.substr(i+1, (int)mid.length()-i-1));post += pre[0];}int main(){string pre, mid;while(cin >> pre){cin >> mid;post.erase();fun(pre, mid);cout << post << endl;}return 0;}深度优先搜索模板int t; //t用来标识要搜索的元素int count; //count用来标识搜索元素的个数int data[m][n]; //data用来存储数据的数组//注意，数组默认是按照1……n存储，即没有第0行//下面是4个方向的搜索,void search(int x, int y){data[x][y] = *; //搜索过进行标记if(x-1 >= 1 && data[x-1][y] == t){count++;search(x-1,y);}if(x+1 <= n && data[x+1][y] == t){count++;search(x+1,y);}if(y-1 >= 1 && data[x][y-1] == t){count++;search(x,y-1);}if(y+1 <= n && data[x][y+1] == t){count++;search(x,y+1);}}//下面是8个方向的搜索void search(int x, int y){data[x][y] = *; //搜索过进行标记if(x-1 >= 1){if(data[x-1][y] == t){count++;search(x-1,y);}if(y-1 >= 1 && data[x-1][y-1] == t) {count++;search(x-1,y-1);}if(y+1 <= n && data[x-1][y+1] == t) {count++;search(x-1,y+1);}}if(x+1 <= n){if(data[x+1][y] == t){count++;search(x+1,y);}if(y-1 >= 1 && data[x+1][y-1] == t) {count++;search(x+1,y-1);}if(y+1 <= n && data[x+1][y+1] == t) {count++;search(x+1,y+1);}}if(y-1 >= 1 && data[x][y-1] == t){count++;search(x,y-1);}if(y+1 <= n && data[x][y+1] == t){count++;search(x,y+1);}}匈牙利算法——二部图匹配BFS实现//匈牙利算法实现#define MAX 310 //二部图一侧顶点的最大个数int n,m; //二分图的两个集合分别含有n和m个元素。

目录一、图论 (2)1.1.最小生成树类prim算法 (2)1.2.拓扑排序 (4)1.3.最短源路径Folyd实现 (5)1.4.关键路径实现算法 (6)1.5.二分图最大匹配的匈牙利算法 (8)1.6.并查集 (9)二、动规 (11)2.1.求最长子序列 (11)2.2.求解最长升序列长度及子序列 (12)2.3.完全背包问题 (13)2.4.0-1背包问题 (14)2.5.母函数DP算法求组合数 (15)2.6.滚动数组求回文串问题 (17)三、贪心 (18)3.1.时间安排问题 (18)3.2.求最大子段和 (19)3.3.贪心求最少非递减序列数 (20)四、数论 (21)4.1.简单求Cnk问题 (21)4.2.巧求阶乘位数 (21)4.3.线性算法求素数 (22)五、其他 (22)5.1.采用位操作递归求解示例 (22)5.2.Stack和Queue用法 (23)5.3.map使用详解 (24)5.4.字典树建立与查找 (25)5.5.KMP匹配算法 (26)5.6.后缀数组求最长连续公共子序列长度 (28)5.7.循环字符串最小位置表示及同构判断 (30)5.8.求哈夫曼树编码长度 (32)5.9.堆排序算法 (34)5.10.线段树着色问题 (35)六、附： (39)6.1.C++最值常量 (39)6.2.类型转换 (39)6.3.String常用函数举例 (39)6.4.C++常用头文件 (40)一、图论1.1.最小生成树类prim算法1.1.1下标从1开始#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define SIZE 101#define MAXSIZE 10201int n,nline;/*n 个点,nline行关系*/int in[SIZE];struct Point{int x,y;/*编号从1开始*/int v;/*根据实际情况更改类型*/}p[MAXSIZE];/*n*(n-1)/2*/int cmp(Point a,Point b){return a.v<b.v;}int prim(){int dis,count,i,j;memset(in,0,sizeof(in));in[p[1].x]=in[p[1].y]=1;dis=p[1].v;count=n-1;while(count--){/*做n-1次*/for(j=2;j<nline;j++){if((in[p[j].x]&&!in[p[j].y])||(!in[p[j].x]&&in[p[j].y])){in[p[j].x]=1;in[p[j].y]=1;dis+=p[j].v;break;}}}return dis;}int main(){int x,y,v,i;while(scanf("%d",&n)&&n){if(n==1){/*有可能输入的为1个点*/printf("0\n");continue;}nline=n*(n-1)/2+1;for(i=1;i<nline;i++){scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v);}sort(p+1,p+nline,cmp);printf("%d\n",prim());}return 0;}1.1.2下标从0开始#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define SIZE 101#define MAXSIZE 10201int n,nline;/*n 个点,nline行关系*/int in[SIZE];struct Point{int x,y;/*编号从1开始*/int v;/*根据实际情况更改类型*/}p[MAXSIZE];/*n*(n-1)/2*/int cmp(Point a,Point b){return a.v<b.v;}int prim(){int dis,count,i,j;memset(in,0,sizeof(in));in[p[0].x]=in[p[0].y]=1;dis=p[0].v;count=n-1;while(count--){/*做n-1次*/for(j=1;j<nline;j++){if((in[p[j].x]&&!in[p[j].y])||(!in[p[j].x]&&in[p[j].y])){in[p[j].x]=1;in[p[j].y]=1;dis+=p[j].v;break;}}}return dis;}int main(){int x,y,v,i;while(scanf("%d",&n)&&n){if(n==1){/*有可能输入的为1个点*/printf("0\n");continue;}nline=n*(n-1)/2;for(i=0;i<nline;i++){scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v);}sort(p,p+nline,cmp);printf("%d\n",prim());}return 0;}1.2.拓扑排序#include<iostream>#include<cstdio>#include<cstring>#define M 501using namespace std;int map[M][M],degree[M];int ne;/*个数*/void topo(){int i,j,k;for(i=0;i<ne;i++){j=1;while(j<=ne&&degree[j])j++;//直到一个度为零的顶点,这里不检查有多个度为零的情况//if(j>ne){break;}不是拓扑结构if(i)printf(" ");printf("%d",j);degree[j]=-1;for(k=1;k<=ne;k++){degree[k]-=map[j][k];}}printf("\n");}int main(){int a,b,i,j,nline;/*nline行*/while(scanf("%d%d",&ne,&nline)!=EOF){memset(map,0,sizeof(map));memset(degree,0,sizeof(degree));while(nline--){scanf("%d%d",&a,&b);map[a][b]=1;/*a to b*/}for(i=1;i<=ne;i++){for(j=1;j<=ne;j++){if(map[i][j])degree[j]++;}}topo();/*拓扑*/}return 0;}1.3.最短源路径Folyd实现#include<iostream>#include<cstdio>#include<cstring>#define M 201using namespace std;int n,map[M][M],start,end;void folyd(){int i,j,k;for(i=0;i<n;i++){for(j=0;j<n;j++){for(k=0;k<n;k++){if(map[j][i]==-1||map[i][k]==-1)continue;if(map[j][k]==-1||map[j][i]+map[i][k]<map[j][k]){map[j][k]=map[j][i]+map[i][k];}}}}}int main(){int nline,i,j,a,b,v;while(scanf("%d%d",&n,&nline)!=EOF){memset(map,-1,sizeof(map));for(i=0;i<n;i++){map[i][i]=0;}for(i=0;i<nline;i++){scanf("%d%d%d",&a,&b,&v);/*编号从0开始*/if(map[a][b]==-1||map[a][b]>v){//一个点到另一个有多条路map[b][a]=map[a][b]=v;}}scanf("%d%d",&start,&end);folyd();if(map[start][end]!=-1){printf("%d\n",map[start][end]);}else printf("-1\n");}return 0;}1.4.关键路径实现算法#include<iostream>#include<cstdio>#include<cstring>#define M 501using namespace std;int map[M][M],degree[M],dp[M];int ne;/*个数*/int topoplus(){int i,j,k,maxnum;for(i=0;i<ne;i++){j=1;while(j<=ne&&degree[j])j++;//直到一个度为零的顶点,这里不检查有多个度为零的情况//if(j>ne){break;}不是拓扑结构degree[j]=-1;for(k=1;k<=ne;k++){if(map[j][k]){if(map[j][k]+dp[j]>dp[k]){dp[k]=map[j][k]+dp[j];}degree[k]--;}}}for(i=0;i<=ne;i++){if(dp[i]>maxnum){maxnum=dp[i];}}return maxnum;}int main(){int a,b,v,i,j,nline;/*nline行*/while(scanf("%d%d",&ne,&nline)!=EOF){memset(map,0,sizeof(map));memset(degree,0,sizeof(degree));memset(dp,0,sizeof(dp));while(nline--){scanf("%d%d%d",&a,&b,&v);map[a][b]=v;/*a to b，v>0*/}for(i=1;i<=ne;i++){for(j=1;j<=ne;j++){if(map[i][j])degree[j]++;}}printf("%d\n",topoplus());/*拓扑改进*/}return 0;}1.5.二分图最大匹配的匈牙利算法#include<iostream>#include<cstdio>#define N 301using namespace std;int isuse[N]; //记录y中节点是否使用int lk[N]; //记录当前与y节点相连的x的节点int mat[N][N];//记录连接x和y的边，如果i和j之间有边则为1，否则为0 int gn,gm; //二分图中x和y中点的数目int can(int t){int i;for(i=1;i<=gm;i++){//下标从1开始if(isuse[i]==0 && mat[t][i]){isuse[i]=1;if(lk[i]==-1 || can(lk[i])){lk[i]=t;return 1;}}}return 0;}int MaxMatch(){int i,num=0;memset(lk,-1,sizeof(lk));for(i=1;i<=gn;i++){memset(isuse,0,sizeof(isuse));if(can(i))num++;}return num;}int main(){int t,i,j,k,tmp;scanf("%d",&t);while(t--){scanf("%d%d",&gn,&gm);memset(mat,0,sizeof(mat));//主要得到mat这个数组for(i=1;i<=gn;i++){scanf("%d",&k);for(j=1;j<=k;j++){scanf("%d",&tmp);mat[i][tmp]=1;//注意从1开始}}if(MaxMatch()==gn){printf("YES\n");}else printf("NO\n");}return 0;}/*In:23 33 1 2 32 1 21 13 32 1 32 1 31 1Out:YESNO*/1.6.并查集#include<iostream>#include<cstdio>using namespace std;const int N=1010;int pre[N];void Merge(int x,int y){int i,t,rx=x,ry=y;while(pre[rx]!=-1)//搜索x的树根rx=pre[rx];while(pre[ry]!=-1)//搜索y的树根ry=pre[ry];i=x;//压缩xwhile(pre[i]!=-1){t=pre[i];pre[i]=rx;i=t;}i=y;//压缩ywhile(pre[i]!=-1){t=pre[i];pre[i]=rx;i=t;}if(ry!=rx)//合并pre[ry]=rx;return;}int main(){int x,y,i,ans,n,m;while(scanf("%d",&n)&&n){scanf("%d",&m);memset(pre,-1,sizeof(pre));for(i=0;i<m;i++){//x与y连通scanf("%d %d",&x,&y);Merge(x,y);}ans=0;for(i=1;i<=n;i++)if(pre[i]==-1)ans++;printf("%d\n",ans-1);}}/*/showproblem.php?pid=1232 in:4 21 34 3999 0out:1998*/二、动规2.1.求最长子序列#include<iostream>#include<cstdio>#define M 1001using namespace std;char a[M],b[M];int dp[M+1][M+1],lena,lenb;void init(){int i,j;for(i=0;i<=lena;i++){for(j=0;j<=lenb;j++){dp[i][j]=0;}}}int cmax(int x,int y){return x>y?x:y;}int main(){int i,j,len;while(scanf("%s",a)!=EOF){scanf("%s",b);init();//下面这步很重要，否则会超时lena=strlen(a);lenb=strlen(b);for(i=0;i<lena;i++){for(j=0;j<lenb;j++){if(a[i]==b[j]){dp[i+1][j+1]=dp[i][j]+1;}else{dp[i+1][j+1]=cmax(dp[i][j+1],dp[i+1][j]);}}}//子序列长度printf("%d\n",dp[i][j]);/*打印出子序列*/len=1;for(i=1;i<=lena;i++){for(j=1;j<=lenb;j++){if(len==dp[i][j]){printf("%c",a[i-1]);len++;break;}}}printf("\n");}return 0;}2.2.求解最长升序列长度及子序列#include<iostream>#include<cstdio>#define M 1001using namespace std;int a[M],dp[M];void init(int n){int i;for(i=0;i<n;i++){dp[i]=1;}}int lis(int n){int i,j,maxlen=1;//初始长度为1for(i=n-2;i>=0;i--){for(j=n-1;j>i;j--){if(a[i]<a[j]){if(dp[j]+1>dp[i]){dp[i]=dp[j]+1;}if(dp[i]>maxlen)maxlen=dp[i];}}}return maxlen;}void showlis(int n,int maxlen){int i;for(i=0;i<n;i++){if(dp[i]==maxlen){printf("%d ",a[i]);maxlen--;}}printf("\n");}int main(){int t,n,i,maxlen;scanf("%d",&t);while(t--){/*1<=n<=1000*/scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);}init(n);maxlen=lis(n);printf("%d\n",maxlen);//显示最长升序列showlis(n,maxlen);}return 0;}2.3.完全背包问题#include<iostream>#include<cstring>#include<cstdio>using namespace std;int type[]={150,200,350};//种类int dp[10001];int max(int a,int b){return a>b?a:b;}int main(){int t,n,i,j;scanf("%d",&t);while(t--){scanf("%d",&n);memset(dp,0,sizeof(dp));for(i=0;i<3;i++){for(j=type[i];j<=n;j++){//剩余容量为j时装的东西量最大dp[j]=max(dp[j],dp[j-type[i]]+type[i]);}}printf("%d\n",n-dp[n]);}return 0;}2.4.0-1背包问题#include<iostream>#include<cstdio>#include<cstring>#define M 1002using namespace std;int val[M],wei[M],dp[M][M];int cmax(int a,int b){return a>b?a:b;}int main(){int t,n,w,i,j;scanf("%d",&t);while(t--){scanf("%d%d",&n,&w);for(i=1;i<=n;i++){scanf("%d",&val[i]);}for(i=1;i<=n;i++){scanf("%d",&wei[i]);}memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){for(j=0;j<=w;j++){if(j>=wei[i])dp[i][j]=cmax(dp[i-1][j-wei[i]]+val[i],dp[i-1][j]);else dp[i][j]=dp[i-1][j];}}printf("%d\n",dp[n][w]);}return 0;}2.5.母函数DP算法求组合数2.5.1.求母函数各系数值DP#include <iostream>#define M 17#define MAX 305using namespace std;int c1[MAX],c2[MAX],add[M+1];//add[]保存M种类void init(){int i;for(i=1;i<=M;i++){add[i]=i*i;}}int solve(int n){int i,j,k;//c1[k],c2[k]表示展开式中x^k的系数memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));c1[0]=c2[0]=1;//使用前i种币时的情况，也即母函数展开前i个多项式的乘积 for(i=1;i<=M;i++){//求新的多项式中的系数for(j=0;j<n;j++){for(k=1;j+k*add[i]<=n;k++){c2[j+k*add[i]]+=c1[j];}}for(k=0;k<=n;k++){//滚动数组c1[k]=c2[k];}}return c1[n];}int main(){int n;init();while(scanf("%d",&n)&&n){printf("%d\n",solve(n));}return 0;}2.5.2.状态继承类DP求某个和是否存在#include<cstdio>#include<iostream>#include<cstring>using namespace std;bool dp[250002];int val[101],num[101];//对应的值和数量int main(){int n,i,j,sum,k;while(scanf("%d",&n)&&n>0){sum=0;for(i=0;i<n;i++){scanf("%d%d",&val[i],&num[i]);sum+=val[i]*num[i];}//dp中保存所有可能的组合memset(dp,0,sizeof(dp));dp[0]=1;//遍历n种物品for(i=0;i<n;i++){//对区间求for(j=sum/2;j>=0;j--){if(!dp[j]){for(k=1;k<=num[i]&&k*val[i]<=j;k++){dp[j]|=dp[j-k*val[i]];}}}}for(i=sum/2;i>=0;i--){if(dp[i]){printf("%d %d\n",sum-i,i);break;}}}return 0;}/*in:210 120 1320 230 1-1out:20 1040 40*/2.6.滚动数组求回文串问题#include<cstdio>#include<iostream>#include<cstring>#define M 5001using namespace std;char str[M],rstr[M];int dp[2][M];//滚动DPint cmax(int x,int y){return x>y?x:y;}int main(){int n,i,j,s1,s2;while(scanf("%d",&n)!=EOF){scanf(" %s",str);//反转字符数组for(i=0;i<n;i++){rstr[n-i-1]=str[i];}rstr[n]='\0';memset(dp,0,sizeof(dp));for(i=0;i<n;i++){for(j=0;j<n;j++){s1=i%2;s2=(i+1)%2;if(str[i]==rstr[j]){dp[s1][j+1]=dp[s2][j]+1;}else{dp[s1][j+1]=cmax(dp[s2][j+1],dp[s1][j]);}}}printf("%d\n",n-dp[(n-1)%2][n]);return 0;}/*/showproblem.php?pid=1513 in:5Ab3bdout:2*/三、贪心3.1.时间安排问题#include<iostream>#include<cstdio>#include<algorithm>#define M 101using namespace std;int n;struct Point{int s,e;}p[M];int cmp(Point a,Point b){if(a.s==b.s)return a.e<b.e;else return a.s<b.s;}int arrange(){int start,end,i,count=1;start=p[0].s;end=p[0].e;for(i=1;i<n;i++){if(p[i].s>=start&&p[i].e<=end){start=p[i].s;end=p[i].e;}else if(p[i].s>=end){count++;end=p[i].e;}}return count;}int main(){int i;while(scanf("%d",&n)&&n){for(i=0;i<n;i++){scanf("%d%d",&p[i].s,&p[i].e);}sort(p,p+n,cmp);printf("%d\n",arrange());}return 0;}3.2.求最大子段和#include<iostream>using namespace std;int main(){int t,n,i,a[100002];int beg,end,x,y,cursum,maxsum;cin>>t;while(t--){cin>>n;for(i=0;i<n;i++){cin>>a[i];}beg=end=1;cursum=maxsum=a[0];x=y=1;for(i=1;i<n;i++){if(a[i]+cursum<a[i]){cursum=a[i];x=i+1;}else{cursum+=a[i];}if(cursum>maxsum){maxsum=cursum;beg=x;end=i+1;}}cout<<maxsum<<" "<<beg<<" "<<end<<endl;}return 0;}/*in:25 6 -1 5 4 -77 0 6 -1 1 -6 7 -5out:14 1 47 1 6*/3.3.贪心求最少非递减序列数#include<iostream>#include<cstdio>#include<cstring>using namespace std;int a[1001];int main(){int n,i,j,len,count,high;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++){scanf("%d",&a[i]);}count=0;len=n;while(len){count++;high=30005;//最高值for(i=0;i<n;i++){if(a[i]&&a[i]<high){high=a[i];a[i]=0;//标记已用值len--;}}}printf("%d\n",count);}return 0;}/*in:8 389 207 155 300 299 170 158 65out:2*/四、数论4.1.简单求Cnk问题#include<iostream>using namespace std;int main(){int n,k,i;double sum;while(cin>>n>>k){if(n==0&&k==0)break;if(k>n-k)k=n-k;sum=1;for(i=1;i<=k;i++){sum*=(double)(n-k+i)/i*1.000000000001;//必需要乘 }cout<<(int)sum<<endl;}return 0;}4.2.巧求阶乘位数#include<iostream>#include<cmath>using namespace std;const double pi=acos(-1.0);//NOTES:piconst double e=2.71828182845904523536028747135266249775724709369995957; int main(){long long n,tt;cin>>tt;while (tt--){cin>>n;long long ans=(long long)((double)log10(sqrt(2*pi*n))+n*log10(n/e))+1;cout<<ans<<endl;}return 0;}4.3.线性算法求素数const int MAX=10000000;//求[2,MAX]间的素数bool isprime[MAX+1];int prime[MAX];//保存素数//返回素数表元素总数int getprime(){int i,j,pnum=0;//memset(isprime,0,sizeof(isprime));for(i=2;i<=MAX;i++){if(!isprime[i])prime[pnum++]=i;for(j=0;j<pnum&&prime[j]*i<=MAX;j++){isprime[prime[j]*i]=1;if(i%prime[j]==0)break;}}return pnum;}五、其他5.1.采用位操作递归求解示例#include<iostream>#include<cstdio>using namespace std;unsigned short in[50001],ste;/*用16位的ste保存16种状态*/ unsigned short power[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768}; int n,m,maxnum,i,j;void dfs(int s,int count){if(count>maxnum)maxnum=count;for(i=s;i<m;i++){if(!(ste&in[i])){/*如果相与为0，说明材料未被使用*/ ste=ste|in[i];dfs(i+1,count+1);ste=ste&(~in[i]);}}}int main(){int tn,t;while(scanf("%d%d",&n,&m)!=EOF){if(n==0||m==0){printf("0\n");continue;}for(i=0;i<m;i++){scanf("%d",&tn);in[i]=0;for(j=1;j<=tn;j++){scanf("%d",&t);/*材料编号降为从0开始，防止益处*/in[i]=in[i]|power[t-1];}}ste=0;maxnum=0;dfs(0,0);printf("%d\n",maxnum);}return 0;}5.2.Stack和Queue用法#include<iostream>#include<stack>#include<queue>using namespace std;int main(){stack<int> s;queue<int> q;int a[]={1,2,3,4};/*加入*/for(int i=0;i<4;i++){s.push(a[i]);q.push(a[i]);}/*读取stack*/cout<<"stack-size:"<<s.size()<<endl;for(int i=0;i<4;i++){cout<<s.top()<<" ";s.pop();}cout<<endl<<"queue-size:"<<q.size()<<endl;/*读取queue*/cout<<"front:"<<q.front()<<"back:"<<q.back()<<endl;for(int i=0;i<4;i++){cout<<q.front()<<" ";q.pop();}cout<<endl;return 0;}5.3.map使用详解#include<iostream>#include<map>#include<string>#include<iterator>using namespace std;int main(){map<string,int>m;map<string,int>::iterator p;map<string,int>::reverse_iterator q;m["bd"]=2;m["ba"]=1;m["aa"]=3;m["bd"]=4;//按从小到大遍历for(p=m.begin();p!=m.end();p++){//注意不能使用p<m.end() cout<<p->first<<" "<<p->second<<endl;}//按从大到小遍历for(q=m.rbegin();q!=m.rend();q++){cout<<q->first<<" "<<q->second<<endl;}m.erase(m.begin());cout<<m.size()<<endl;//清楚全部m.clear();cout<<m.empty()<<endl;return 0;}5.4.字典树建立与查找#include<iostream>#include<cstring>#include<cstdio>#define M 26using namespace std;int ii;//只在Tree中使用struct Tree{Tree* next[M];int val;Tree(){for(ii=0;ii<M;ii++){next[ii]=0;}val=0;}~Tree(){for(ii=0;ii<M;ii++){delete(next[ii]);}}};int main(){char word[20];int len,i,j,count;Tree* root=new Tree;Tree* p;//建立字典树过程while(gets(word)){if(strcmp(word,"")==0)break;len=strlen(word);p=root;for(i=0;i<len;i++){j=word[i]-'a';if(p->next[j]==0){p->next[j]=new Tree;}p=p->next[j];(p->val)++;}word[0]='\0';}while(scanf("%s",word)!=EOF){len=strlen(word);p=root;for(i=0;i<len;i++){j=word[i]-'a';if(p->next[j]!=0){p=p->next[j];}else break;}if(i==len)printf("%d\n",p->val);else printf("0\n");}return 0;}/*In:bananabandbeeabsoluteacmbabbandabcout:231*/5.5.KMP匹配算法#include<iostream>#include<cstdio>#include<cstring>#define M 10001using namespace std;int s[M*100],t[M],next[M];//得到next数组，下标均从1开始void getnext(int m){int i=1,j=0;next[1]=0;while(i<=m){if(j==0||t[i]==t[j]){++i;++j;next[i]=j;}else j=next[j];}}//找不到则返回-1int kmp(int n,int m){int i=0,j=1;getnext(m);while(i<=n&&j<=m){if(!j||s[i]==t[j]){++i;++j;}elsej=next[j];}if(j>m)return i-m;else return -1;}int main(){int test,m,n,i;scanf("%d",&test);while(test--){scanf("%d %d",&n,&m);//主串s,长度为nfor(i=1;i<=n;i++)scanf("%d",&s[i]);//横式串t,长度为mfor(i=1;i<=m;i++)scanf("%d",&t[i]);printf("%d\n",kmp(n,m));}return 0;}5.6.后缀数组求最长连续公共子序列长度#include<iostream>#include<cstdio>#include<algorithm>#define M 100001using namespace std;char message[M*2];/*后缀数组*/int height[M*2];int _array[2][M*2];int _rank[2][M*2];int cnt[M*2];int *array, *rank, *narray, *nrank;/*得到最长连续公共子序列长度*/int suffix(int len1,int len2,int len){int i,k;memset(cnt,0,1024);for(i=0;i<len;++i){++cnt[message[i]];}for(i=1;i<= 'z';++i){cnt[i]+=cnt[i-1];}array = _array[0];rank = _rank[0];for(i=len-1;i>=0;--i){array[--cnt[message[i]]]=i;}rank[array[0]] = 0;for(i=1;i<len;i++){rank[array[i]]=rank[array[i-1]];if(message[array[i]]!=message[array[i-1]]){ rank[array[i]]++;}}narray = _array[1];nrank = _rank[1];for(k=1;k<len&&rank[array[len-1]]<len-1;k<<=1){for(i=0;i<len;++i){cnt[rank[array[i]]]=i+1;}for(i=len-1;i>=0;--i){if(array[i] >= k){// array[i]是当前的最大值，所以array[i] - k//是其相同前缀中（rank相同）的最大值narray[--cnt[rank[array[i]-k]]]=array[i]-k;}}for(i=len-k;i<len;++i){//这些没有k后缀，所以他们是最后面的k个，他的位置已经比较出来narray[--cnt[rank[i]]]=i;}nrank[narray[0]] = 0;for (i=1;i<len;++i){nrank[narray[i]]=nrank[narray[i-1]];if(rank[narray[i]]!= rank[narray[i-1]] ||rank[narray[i]+k]!=rank[narray[i-1]+k]){//如果前缀的排名不同，则++；如果前缀相同，但是后缀不同，也++ nrank[narray[i]]++;}}swap(nrank, rank);swap(narray, array);}int ret=0,hei;for(i=1;i<len;++i){if(((array[i]<len1&&array[i-1]>=len1) ||(array[i]>=len1&&array[i-1]<len1))){hei = 0;while(message[array[i]+ hei]==message[array[i-1]+hei]){hei++;}ret = max(ret, hei);}}return ret;}int main(){int len,len1,len2;while(gets(message)!=NULL){len1 = strlen(message);gets(message + len1);len2 = strlen(message+len1);len = len1 + len2;printf("%d\n",suffix(len1,len2,len));}return 0;}5.7.循环字符串最小位置表示及同构判断#include<cstdio>#include<iostream>#include<cstring>#include<string>using namespace std;//返回两个字符串是否同构//len为s1或S2的长度，s1与s2等长//pos1与pos2为字符循环最小表示位置，从0开始bool CircularMatch(string s1, string s2, int len, int& pos1, int& pos2) {int p1 = 0, p2 = 0, k, t1, t2;pos1 = pos2 = -1;while (1) {k = 0;while (1) {t1 = (p1+k)%len; t2 = (p2+k)%len;if(s1[t1] > s2[t2]) {p1 = p1+k+1;if (p1 >= len) return false;break;}else if (s1[t1] < s2[t2]) {p2 = p2+k+1;if (p2 >= len) return false;break;}else k++;if (k == len) {pos1 = p1; pos2 = p2;return true;}}}}//返回字符串循环最小表示的位置,从0开始int MinCircularDenote(string s, int len) {int p1 = 0, p2 = 1, k, t1, t2;while (1) {k = 0;while (1) {t1 = (p1+k)%len; t2 = (p2+k)%len;if(s[t1] > s[t2]) {if (p1+k+1 <= p2) p1 = p2+1;else p1 = p1+k+1;if (p1 >= len) return p2;break;}else if (s[t1] < s[t2]) {if (p2+k+1 <= p1) p2 = p1+1;else p2 = p2+k+1;if (p2 >= len) return p1;break;}else k++;if (k == len)return (p1<p2 ? p1 : p2);}}}//返回字符串循环最大表示的位置,从0开始int MaxCircularDenote(string str,int len) {int p1 = 0, p2 = 1, k, t1, t2;while (1) {k = 0;while (1) {t1 = (p1+k)%len; t2 = (p2+k)%len;if(str[t1] < str[t2]) {if (p1+k+1 <= p2) p1 = p2+1; else p1 = p1+k+1;if (p1 >= len) return p2;break;}else if (str[t1] > str[t2]) {if (p2+k+1 <= p1) p2 = p1+1;else p2 = p2+k+1;if (p2 >= len) return p1;break;}else k++;if (k == len)return (p1<p2 ? p1 : p2);}}}int main(){string s1,s2;int pos1,pos2,len;while(cin>>s1>>s2){len=s1.length();cout<<MinCircularDenote(s1,len)<<endl;cout<<MaxCircularDenote(s1,len)<<endl;s1+=s1;//字符串加倍s2+=s2;cout<<CircularMatch(s1,s2,len, pos1,pos2)<<endl;cout<<pos1<<endl<<pos2<<endl;}return 0;}5.8.求哈夫曼树编码长度#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define M 27using namespace std;char line[100001];int tree[M],tmp[M];//保存权值int cmp(int a,int b){return a>b;}//对序号为index统计长度int huffman(int n,int index){if(n==1)return 1;//一个点时返回1int i,j,count,max,len,t;for(i=0;i<n;i++){tmp[i]=tree[i];}count=max=n-1;len=0;while(count--){if(index==max||index==max-1){len++;index=max-1;}tmp[max-1]+=tmp[max];j=--max;while(j>0&&tmp[j]>tmp[j-1]){t=tmp[j];tmp[j]=tmp[j-1];tmp[j-1]=t;if(index==j){index--;}else if(index==j-1){index++;}j--;}}return len;}int main(){int i,j,len,sum,n;int ch[M];while(gets(line)!=NULL){if(strcmp(line,"END")==0)break;len=strlen(line);memset(ch,0,sizeof(ch));for(i=0;i<len;i++){if(line[i]=='_'){ch[0]++;}else ch[line[i]-'A'+1]++;}//权值压缩到tree[]数组中for(j=0,i=0;i<M;i++){if(ch[i]){tree[j++]=ch[i];}}n=j;sort(tree,tree+n,cmp);for(sum=0,i=0;i<n;i++){sum+=tree[i]*huffman(n,i);}printf("%d %d %.1lf\n",len*8,sum,len*8.0/(sum*1.0));}return 0;}/*/showproblem.php?pid=1053in:AAAAABCDTHE_CAT_IN_THE_HATENDout:64 13 4.9144 51 2.8*/5.9.堆排序算法#include<cstdio>#include<cstdlib>using namespace std;void adjust(int a[],int s,int len){int t,i;t=a[s];for(i=s*2;i<len;i*=2){if(i<(len-1)&&a[i]<a[i+1])i++;if(t>=a[i])break;a[s]=a[i];s=i;}a[s]=t;}void sort(int a[],int len){int i,t;for(i=(len-1)/2;i>=0;i--){adjust(a,i,len);}for(i=len-1;i>1;i--){a[i]=a[0];a[0]=t;adjust(a,0,i-1);}if(a[0]>a[1]){t=a[0];a[0]=a[1];a[1]=t;}}int main(){int a[1000],i,n;scanf("%d",&n);//for(i=0;i<n;i++)// scanf("%d",a+i);for(i=0;i<n;i++)a[i]=rand()%10000;sort(a,n);for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");return 0;}//2 38 4 99 10 2 22 1 -43 22 33 91 78 335.10.线段树着色问题#include <iostream>#define N 8003#define NoCol -1#define MulCol -2using namespace std;struct SegTree{int l,r,c;}st[N*4];//一般大小开成节点数的4倍，不需要担心空间问题int seg[N],col[N];int n,sat,end;//创建线段树void segTreeCre(int l,int r,int i=1){int mid;st[i].l=l;。

问题重述:给出n种邮票，每种邮票有自己的面值（面值可能重复）指定m种“总面值”，对每种“总面值”，求解满足如下条件的组合以达到该“总面值”（1）所用邮票在n种中可以重复选取（2）所用邮票张数〈＝4（3）尽量多的适应那个不同总类的邮票Max (Stamp Types)（4）若有多种方案满足（3），则选取张数最小的一种方案Min (Stamp Num)（5）若有多种方案满足(3)(4),则选取“最大面额”最高的一种方案。

Max(Heightest Value) （6）若有多种方案满足（3）（4）（5）则输出“tie”题目分析:(1)算法定位:从题目的条件可知,此题必须遍求所有方案以求解,因此采用搜索的方法是非常合理的,因为题目带由一定的递推性,也可以尝试动态规划的方法.(2)问题优化与简化对于搜索型题目,关键的优化就是减少重复计算,本题可由3方面的简化,避免重复性计算.(1)对于面额相等的邮票,可以限制在1~5张,多余的可以不处理,例如这样的输入:1 1 1 1 1 1 1 1 0 8个14 0可以简化成为:1 1 1 1 1 0 5个14 0他们的解是相同的(2)搜索求解时约定, 后一张邮票面额>=前面张邮票的面额,即如下的6种情况:1 2 3 2 3 1 3 12 1 3 2 3 2 1 2 1 3只需搜索判断一种,即 1 2 3 的情况(3)对于给定的n种邮票,遍历4张邮票的所有可达“总面额”的解，当m种指定面额给出，只需插标输出即可，不需要重复m次类似的搜索。

（因为m次的搜索中，很多是重复计算的）（3）算法介绍（1）搜索方法一：（base on 史诗’s program）主要思路：4重循环，枚举所有可能，依据题目条件保留最优解。

For(i=1;i<=total_stamps;i++)For(j=i;j<=total_stamps;j++)For(k=j;k<=total_stamps;k++)For(l=k;l<=total_stamps;l++){更新最优解}优化：使用优化方案（1）（2），修改后可以加上优化方案（3）评价：编程复杂度低，代码少，运行时空效率高，比赛时候推荐使用但是扩展性受限制，若题目给的是任一k张而不是4,则必须大量修改代码（2）搜索方法二：（base on hawking’s program）主要思路：递归深度搜索，遍历所有k张邮票的可达面额的解，保留每种面额的最优解，查表输出指定面额的解，并给定k=4,即为题目要求的情况。

题目一：DescriptionSome positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive primenumbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.Your mission is to write a program that reports the number of representations for the given positive integer.InputThe input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero. OutputThe output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.Sample Input231741206661253Sample Output1123121.算法通过筛法找出10000以内所有的素数，存到数组里。

/*计算几何目录㈠点的基本运算1. 平面上两点之间距离12. 判断两点是否重合13. 矢量叉乘14. 矢量点乘25. 判断点是否在线段上26. 求一点饶某点旋转后的坐标27. 求矢量夹角2㈡线段及直线的基本运算1. 点与线段的关系32. 求点到线段所在直线垂线的垂足43. 点到线段的最近点44. 点到线段所在直线的距离45. 点到折线集的最近距离46. 判断圆是否在多边形内57. 求矢量夹角余弦58. 求线段之间的夹角59. 判断线段是否相交610.判断线段是否相交但不交在端点处611.求线段所在直线的方程612.求直线的斜率713.求直线的倾斜角714.求点关于某直线的对称点715.判断两条直线是否相交及求直线交点716.判断线段是否相交，如果相交返回交点7㈢多边形常用算法模块1. 判断多边形是否简单多边形82. 检查多边形顶点的凸凹性93. 判断多边形是否凸多边形94. 求多边形面积95. 判断多边形顶点的排列方向，方法一106. 判断多边形顶点的排列方向，方法二107. 射线法判断点是否在多边形内108. 判断点是否在凸多边形内119. 寻找点集的graham算法1210.寻找点集凸包的卷包裹法1311.判断线段是否在多边形内1412.求简单多边形的重心1513.求凸多边形的重心1714.求肯定在给定多边形内的一个点1715.求从多边形外一点出发到该多边形的切线1816.判断多边形的核是否存在19㈣圆的基本运算1 .点是否在圆内202 .求不共线的三点所确定的圆21㈤矩形的基本运算1.已知矩形三点坐标，求第4点坐标22㈥常用算法的描述22㈦补充1．两圆关系：242．判断圆是否在矩形内：243．点到平面的距离：254．点是否在直线同侧：255．镜面反射线：256．矩形包含：267．两圆交点：278．两圆公共面积：289. 圆和直线关系：2910. 内切圆：3011. 求切点：3112. 线段的左右旋：3113．公式：32*//* 需要包含的头文件*/#include <cmath >/* 常用的常量定义*/const double INF = 1E200const double EP = 1E-10const int MAXV = 300const double PI = 3.14159265/* 基本几何结构*/struct POINT{double x;double y;POINT(double a=0, double b=0) { x=a; y=b;} //constructor};struct LINESEG{POINT s;POINT e;LINESEG(POINT a, POINT b) { s=a; e=b;}LINESEG() { }};struct LINE // 直线的解析方程a*x+b*y+c=0 为统一表示，约定a >= 0{double a;double b;double c;LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;}};/*********************** ** 点的基本运算** ***********************/double dist(POINT p1,POINT p2) // 返回两点之间欧氏距离{return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );}bool equal_point(POINT p1,POINT p2) // 判断两个点是否重合{return ( (abs(p1.x-p2.x)<EP)&&(abs(p1.y-p2.y)<EP) );}/****************************************************************************** r=multiply(sp,ep,op),得到(sp-op)和(ep-op)的叉积r>0：ep在矢量opsp的逆时针方向；r=0：opspep三点共线；r<0：ep在矢量opsp的顺时针方向******************************************************************************* /double multiply(POINT sp,POINT ep,POINT op){return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));}/*r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的点积，如果两个矢量都非零矢量r<0：两矢量夹角为锐角；r=0：两矢量夹角为直角；r>0：两矢量夹角为钝角******************************************************************************* /double dotmultiply(POINT p1,POINT p2,POINT p0){return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y));}/****************************************************************************** 判断点p是否在线段l上条件：(p在线段l所在的直线上) && (点p在以线段l为对角线的矩形内)******************************************************************************* /bool online(LINESEG l,POINT p){return( (multiply(l.e,p,l.s)==0) &&( ( (p.x-l.s.x)*(p.x-l.e.x)<=0 )&&( (p.y-l.s.y)*(p.y-l.e.y)<=0 ) ) ); }// 返回点p以点o为圆心逆时针旋转alpha(单位：弧度)后所在的位置POINT rotate(POINT o,double alpha,POINT p){POINT tp;p.x-=o.x;p.y-=o.y;tp.x=p.x*cos(alpha)-p.y*sin(alpha)+o.x;tp.y=p.y*cos(alpha)+p.x*sin(alpha)+o.y;return tp;}/* 返回顶角在o点，起始边为os，终止边为oe的夹角(单位：弧度)角度小于pi，返回正值角度大于pi，返回负值可以用于求线段之间的夹角原理：r = dotmultiply(s,e,o) / (dist(o,s)*dist(o,e))r'= multiply(s,e,o)r >= 1 angle = 0;r <= -1 angle = -PI-1<r<1 && r'>0 angle = arccos(r)-1<r<1 && r'<=0 angle = -arccos(r)*/double angle(POINT o,POINT s,POINT e){double cosfi,fi,norm;double dsx = s.x - o.x;double dsy = s.y - o.y;double dex = e.x - o.x;double dey = e.y - o.y;cosfi=dsx*dex+dsy*dey;norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey);cosfi /= sqrt( norm );if (cosfi >= 1.0 ) return 0;if (cosfi <= -1.0 ) return -3.1415926;fi=acos(cosfi);if (dsx*dey-dsy*dex>0) return fi; // 说明矢量os 在矢量oe的顺时针方向return -fi;}/*****************************\* ** 线段及直线的基本运算** *\*****************************//* 判断点与线段的关系,用途很广泛本函数是根据下面的公式写的，P是点C到线段AB所在直线的垂足AC dot ABr = ---------||AB||^2(Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)= -------------------------------L^2r has the following meaning:r=0 P = Ar=1 P = Br<0 P is on the backward extension of ABr>1 P is on the forward extension of AB0<r<1 P is interior to AB*/double relation(POINT p,LINESEG l){LINESEG tl;tl.s=l.s;tl.e=p;return dotmultiply(tl.e,l.e,l.s)/(dist(l.s,l.e)*dist(l.s,l.e));}// 求点C到线段AB所在直线的垂足PPOINT perpendicular(POINT p,LINESEG l){double r=relation(p,l);POINT tp;tp.x=l.s.x+r*(l.e.x-l.s.x);tp.y=l.s.y+r*(l.e.y-l.s.y);return tp;}/* 求点p到线段l的最短距离,并返回线段上距该点最近的点np注意：np是线段l上到点p最近的点，不一定是垂足*/double ptolinesegdist(POINT p,LINESEG l,POINT &np){double r=relation(p,l);if(r<0){np=l.s;return dist(p,l.s);}if(r>1){np=l.e;return dist(p,l.e);}np=perpendicular(p,l);return dist(p,np);}// 求点p到线段l所在直线的距离,请注意本函数与上个函数的区别double ptoldist(POINT p,LINESEG l){return abs(multiply(p,l.e,l.s))/dist(l.s,l.e);}/* 计算点到折线集的最近距离,并返回最近点.注意：调用的是ptolineseg()函数*/double ptopointset(int vcount,POINT pointset[],POINT p,POINT &q) {int i;double cd=double(INF),td;LINESEG l;POINT tq,cq;for(i=0;i<vcount-1;i++)l.s=pointset[i];l.e=pointset[i+1];td=ptolinesegdist(p,l,tq);if(td<cd){cd=td;cq=tq;}}q=cq;return cd;}/* 判断圆是否在多边形内.ptolineseg()函数的应用2 */bool CircleInsidePolygon(int vcount,POINT center,double radius,POINT polygon[]){POINT q;double d;q.x=0;q.y=0;d=ptopointset(vcount,polygon,center,q);if(d<radius||fabs(d-radius)<EP)return true;elsereturn false;}/* 返回两个矢量l1和l2的夹角的余弦(-1 --- 1)注意：如果想从余弦求夹角的话，注意反余弦函数的定义域是从0到pi */double cosine(LINESEG l1,LINESEG l2){return (((l1.e.x-l1.s.x)*(l2.e.x-l2.s.x) +(l1.e.y-l1.s.y)*(l2.e.y-l2.s.y))/(dist(l1.e,l1.s)*dist(l2.e,l2.s))) );}// 返回线段l1与l2之间的夹角单位：弧度范围(-pi，pi)double lsangle(LINESEG l1,LINESEG l2){POINT o,s,e;o.x=o.y=0;s.x=l1.e.x-l1.s.x;s.y=l1.e.y-l1.s.y;e.x=l2.e.x-l2.s.x;e.y=l2.e.y-l2.s.y;return angle(o,s,e);// 如果线段u和v相交(包括相交在端点处)时，返回true////判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) ×( Q2 - Q1 ) * ( Q2 - Q1 ) ×( P2 - Q1 ) >= 0。

目录目录 (1)Graph 图论 (3)|DAG的深度优先搜索标记 (3)|无向图找桥 (3)|无向图连通度(割) (3)|最大团问题DP+DFS (3)|欧拉路径O(E) (3)|D IJKSTRA数组实现O（N^2） (3)|D IJKSTRA O(E* LOG E) (4)|B ELLMAN F ORD单源最短路O(VE) (4)|SPFA(S HORTEST P ATH F ASTER A LGORITHM) (4)|第K短路（D IJKSTRA） (5)|第K短路（A*） (5)|P RIM求MST (6)|次小生成树O(V^2) (6)|最小生成森林问题(K颗树)O(MLOGM) (6)|有向图最小树形图 (6)|M INIMAL S TEINER T REE (6)|T ARJAN强连通分量 (7)|弦图判断 (7)|弦图的PERFECT ELIMINATION点排列 (7)|稳定婚姻问题O(N^2) (7)|拓扑排序 (8)|无向图连通分支(DFS/BFS邻接阵) (8)|有向图强连通分支(DFS/BFS邻接阵)O(N^2) (8)|有向图最小点基(邻接阵)O(N^2) (9)|F LOYD求最小环 (9)|2-SAT问题 (9)Network 网络流 (11)|二分图匹配（匈牙利算法DFS实现） (11)|二分图匹配（匈牙利算法BFS实现） (11)|二分图匹配（H OPCROFT－C ARP的算法） (11)|二分图最佳匹配（KUHN MUNKRAS算法O(M*M*N)）..11 |无向图最小割O(N^3) (12)|有上下界的最小(最大)流 (12)|D INIC最大流O(V^2*E) (12)|HLPP最大流O(V^3) (13)|最小费用流O(V*E* F).......................................13|最小费用流O(V^2* F). (14)|最佳边割集 (15)|最佳点割集 (15)|最小边割集 (15)|最小点割集（点连通度） (16)|最小路径覆盖O(N^3) (16)|最小点集覆盖 (16)Structure 数据结构 (17)|求某天是星期几 (17)|左偏树合并复杂度O(LOG N) (17)|树状数组 (17)|二维树状数组 (17)|T RIE树(K叉) (17)|T RIE树(左儿子又兄弟) (18)|后缀数组O(N* LOG N) (18)|后缀数组O(N) (18)|RMQ离线算法O(N*LOG N)+O(1) (19)|RMQ(R ANGE M INIMUM/M AXIMUM Q UERY)-ST算法(O(NLOGN +Q)) (19)|RMQ离线算法O(N*LOG N)+O(1)求解LCA (19)|LCA离线算法O(E)+O(1) (20)|带权值的并查集 (20)|快速排序 (20)|2台机器工作调度 (20)|比较高效的大数 (20)|普通的大数运算 (21)|最长公共递增子序列O(N^2) (22)|0-1分数规划 (22)|最长有序子序列（递增/递减/非递增/非递减） (22)|最长公共子序列 (23)|最少找硬币问题（贪心策略-深搜实现） (23)|棋盘分割 (23)|汉诺塔 (23)|STL中的PRIORITY_QUEUE (24)|堆栈 (24)|区间最大频率 (24)|取第K个元素 (25)|归并排序求逆序数 (25)|逆序数推排列数 (25)|二分查找 (25)|二分查找（大于等于V的第一个值） (25)|所有数位相加 (25)Number 数论 (26)|递推求欧拉函数PHI(I) (26)|单独求欧拉函数PHI(X) (26)|GCD最大公约数 (26)|快速GCD (26)|扩展GCD (26)|模线性方程 A * X = B (% N) (26)|模线性方程组 (26)|筛素数[1..N] (26)|高效求小范围素数[1..N] (26)|随机素数测试(伪素数原理) (26)|组合数学相关 (26)|P OLYA计数 (27)|组合数C(N, R) (27)|最大1矩阵 (27)|约瑟夫环问题（数学方法） (27)|约瑟夫环问题（数组模拟） (27)|取石子游戏1 (27)|集合划分问题 (27)|大数平方根（字符串数组表示） (28)|大数取模的二进制方法 (28)|线性方程组A[][]X[]=B[] (28)|追赶法解周期性方程 (28)|阶乘最后非零位,复杂度O(NLOGN) (29)递归方法求解排列组合问题 (30)|类循环排列 (30)|全排列 (30)|不重复排列 (30)|全组合 (31)|不重复组合 (31)|应用 (31)模式串匹配问题总结 (32)|字符串H ASH (32)|KMP匹配算法O(M+N) (32)|K ARP-R ABIN字符串匹配 (32)|基于K ARP-R ABIN的字符块匹配 (32)|函数名: STRSTR (32)|BM算法的改进的算法S UNDAY A LGORITHM (32)|最短公共祖先（两个长字符串） (33)|最短公共祖先（多个短字符串）...............................33Geometry 计算几何.. (34)|G RAHAM求凸包O(N* LOG N) (34)|判断线段相交 (34)|求多边形重心 (34)|三角形几个重要的点 (34)|平面最近点对O(N* LOG N) (34)|L IUCTIC的计算几何库 (35)|求平面上两点之间的距离 (35)|(P1-P0)*(P2-P0)的叉积 (35)|确定两条线段是否相交 (35)|判断点P是否在线段L上 (35)|判断两个点是否相等 (35)|线段相交判断函数 (35)|判断点Q是否在多边形内 (35)|计算多边形的面积 (35)|解二次方程A X^2+B X+C=0 (36)|计算直线的一般式A X+B Y+C=0 (36)|点到直线距离 (36)|直线与圆的交点，已知直线与圆相交 (36)|点是否在射线的正向 (36)|射线与圆的第一个交点 (36)|求点P1关于直线LN的对称点P2 (36)|两直线夹角（弧度） (36)ACM/ICPC竞赛之STL (37)ACM/ICPC竞赛之STL简介 (37)ACM/ICPC竞赛之STL--PAIR (37)ACM/ICPC竞赛之STL--VECTOR (37)ACM/ICPC竞赛之STL--ITERATOR简介 (38)ACM/ICPC竞赛之STL--STRING (38)ACM/ICPC竞赛之STL--STACK/QUEUE (38)ACM/ICPC竞赛之STL--MAP (40)ACM/ICPC竞赛之STL--ALGORITHM (40)STL IN ACM (41)头文件 (42)线段树 (43)求矩形并的面积（线段树+离散化+扫描线） (43)求矩形并的周长（线段树+离散化+扫描线） (44)Graph 图论/*==================================================*\| DAG的深度优先搜索标记| INIT: edge[][]邻接矩阵; pre[], post[], tag全置0;| CALL: dfstag(i, n); pre/post:开始/结束时间\*==================================================*/int edge[V][V], pre[V], post[V], tag;void dfstag(int cur, int n){ // vertex: 0 ~ n-1pre[cur] = ++tag;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (0 == pre[i]) {printf("Tree Edge!\n");dfstag(i,n);} else {if (0 == post[i]) printf("Back Edge!\n");else if (pre[i] > pre[cur])printf("Down Edge!\n");else printf("Cross Edge!\n");}}post[cur] = ++tag;}/*==================================================*\| 无向图找桥| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],bridge 置0;| CALL: dfs(0, -1, 1, n);\*==================================================*/int bridge, edge[V][V], anc[V], pre[V], vis[V];void dfs(int cur, int father, int dep, int n){ // vertex: 0 ~ n-1if (bridge) return;vis[cur] = 1; pre[cur] = anc[cur] = dep;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (i != father && 1 == vis[i]) {if (pre[i] < anc[cur])anc[cur] = pre[i];//back edge}if (0 == vis[i]) { //tree edgedfs(i,cur,dep+1,n);if (bridge) return;if (anc[i] < anc[cur]) anc[cur] = anc[i];if (anc[i] > pre[cur]) { bridge = 1; return; } }}vis[cur] = 2;}/*==================================================*\| 无向图连通度(割)| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],deg[]置为0;| CALL: dfs(0, -1, 1, n);| k=deg[0], deg[i]+1(i=1…n-1)为删除该节点后得到的连通图个数| 注意:0作为根比较特殊!\*==================================================*/int edge[V][V], anc[V], pre[V], vis[V], deg[V];void dfs(int cur, int father, int dep, int n){// vertex: 0 ~ n-1int cnt = 0;vis[cur] = 1; pre[cur] = anc[cur] = dep;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (i != father && 1 == vis[i]) {if (pre[i] < anc[cur])anc[cur] = pre[i];//back edge}if (0 == vis[i]) { //tree edgedfs(i,cur,dep+1,n);++cnt; // 分支个数if (anc[i] < anc[cur]) anc[cur] = anc[i];if ((cur==0 && cnt>1) ||(cnt!=0 && anc[i]>=pre[cur]))++deg[cur];// link degree of a vertex }}vis[cur] = 2;} /*==================================================*\| 最大团问题 DP + DFS| INIT: g[][]邻接矩阵;| CALL: res = clique(n);\*==================================================*/int g[V][V], dp[V], stk[V][V], mx;int dfs(int n, int ns, int dep){if (0 == ns) {if (dep > mx) mx = dep;return 1;}int i, j, k, p, cnt;for (i = 0; i < ns; i++) {k = stk[dep][i]; cnt = 0;if (dep + n - k <= mx) return 0;if (dep + dp[k] <= mx) return 0;for (j = i + 1; j < ns; j++) {p=stk[dep][j];if (g[k][p]) stk[dep + 1][cnt++] = p;}dfs(n, cnt, dep + 1);}return 1;}int clique(int n){int i, j, ns;for (mx = 0, i = n - 1; i >= 0; i--) {// vertex: 0 ~ n-1for (ns = 0, j = i + 1; j < n; j++)if (g[i][j]) stk[1][ ns++ ] = j;dfs(n, ns, 1); dp[i] = mx;}return mx;}/*==================================================*\| 欧拉路径O(E)| INIT: adj[][]置为图的邻接表; cnt[a]为a点的邻接点个数;| CALL: elpath(0); 注意:不要有自向边\*==================================================*/int adj[V][V], idx[V][V], cnt[V], stk[V], top;int path(int v){for (int w ; cnt[v] > 0; v = w) {stk[ top++ ] = v;w = adj[v][ --cnt[v] ];adj[w][ idx[w][v] ] = adj[w][ --cnt[w] ];// 处理的是无向图—-边是双向的，删除v->w后，还要处理删除w->v}return v;}void elpath (int b, int n){ // begin from b int i, j;for (i = 0; i < n; ++i) // vertex: 0 ~ n-1 for (j = 0; j < cnt[i]; ++j)idx[i][ adj[i][j] ] = j;printf("%d", b);for (top = 0; path(b) == b && top != 0; ) {b = stk[ --top ];printf("-%d", b);}printf("\n");}/*==================================================*\| Dijkstra数组实现O（N^2）| Dijkstra --- 数组实现(在此基础上可直接改为STL的Queue实现)| lowcost[] --- beg到其他点的最近距离| path[] -- beg为根展开的树，记录父亲结点\*==================================================*/#define INF 0x03F3F3F3Fconst int N;int path[N], vis[N];void Dijkstra(int cost[][N], int lowcost[N], int n, int beg){ int i, j, min;memset(vis, 0, sizeof(vis));vis[beg] = 1;for (i=0; i<n; i++){lowcost[i] = cost[beg][i]; path[i] = beg;}lowcost[beg] = 0;path[beg] = -1; // 树根的标记int pre = beg;for (i=1; i<n; i++){min = INF;dist[v] = dist[u] + c;for (j=0; j<n; j++)// 下面的加法可能导致溢出,INF 不能取太大if (vis[j]==0 &&lowcost[pre]+cost[pre][j]<lowcost[j]){lowcost[j] =lowcost[pre] + cost[pre][j]; path[j] = pre; } for (j=0; j<n; j++) if (vis[j] == 0 && lowcost[j] < min){ min = lowcost[j]; pre = j; } vis[pre] = 1; } } /*==================================================*\ | Dijkstra O(E * log E) | INIT: 调用init(nv, ne)读入边并初始化; | CALL: dijkstra(n, src); dist[i]为src 到i 的最短距离 \*==================================================*/ #define typec int // type of cost const typec inf = 0x3f3f3f3f; // max of cost typec cost[E], dist[V]; int e, pnt[E], nxt[E], head[V], prev[V], vis[V]; struct qnode { int v; typec c; qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {} bool operator < (const qnode& r) const { return c>r.c; } }; void dijkstra(int n, const int src){ qnode mv; int i, j, k, pre; priority_queue<qnode> que; vis[src] = 1; dist[src] = 0; que.push(qnode(src, 0)); for (pre = src, i=1; i<n; i++) { for (j = head[pre]; j != -1; j = nxt[j]) { k = pnt[j]; if (vis[k] == 0 && dist[pre] + cost[j] < dist[k]){ dist[k] =dist[pre] + cost[j]; que.push(qnode(pnt[j], dist[k])); prev[k] = pre; } } while (!que.empty() && vis[que.top().v] == 1) que.pop(); if (que.empty()) break ; mv = que.top(); que.pop(); vis[pre = mv.v] = 1; } } inline void addedge(int u, int v, typec c){ pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++; } void init(int nv, int ne){ int i, u, v; typec c; e = 0;memset(head, -1, sizeof (head));memset(vis, 0, sizeof (vis));memset(prev, -1, sizeof (prev));for (i = 0; i < nv; i++) dist[i] = inf;for (i = 0; i < ne; ++i) {scanf("%d%d%d", &u, &v, &c);// %d: type of cost addedge(u, v, c); // vertex: 0 ~ n-1, 单向边 }}/*==================================================*\| BellmanFord 单源最短路O(VE)| 能在一般情况下，包括存在负权边的情况下，解决单源最短路径问题| INIT: edge[E][3]为边表| CALL: bellman(src);有负环返回0;dist[i]为src 到i 的最短距| 可以解决差分约束系统: 需要首先构造约束图，构造不等式时>=表示求最小值, 作为最长路，<=表示求最大值, 作为最短路 （v-u <= c:a[u][v] = c ）\*==================================================*/#define typec int // type of costconst typec inf=0x3f3f3f3f; // max of costint n, m, pre[V], edge[E][3];typec dist[V];int relax (int u, int v, typec c){if (dist[v] > dist[u] + c) {pre[v] = u; return 1; } return 0; } int bellman (int src){ int i, j;for (i=0; i<n; ++i) { dist[i] = inf; pre[i] = -1; } dist[src] = 0; bool flag; for (i=1; i<n; ++i){ flag = false; // 优化 for (j=0; j<m; ++j) { if( 1 == relax(edge[j][0], edge[j][1], edge[j][2]) ) flag = true; } if( !flag ) break; } for (j=0; j<m; ++j) { if (1 == relax(edge[j][0], edge[j][1], edge[j][2])) return 0; // 有负圈 } return 1; } /*==================================================*\ | SPFA(Shortest Path Faster Algorithm) Bellman-Ford 算法的一种队列实现，减少了不必要的冗余计算。

报告范例 动态规划法解0-1
2011级2班
作者姓名
背包问题是一个经典问题……这部分描述问题，并给出分析过程用来引出下面的算
法。

二、算法设计（或算法步骤）
用动态规划法解0-1背包问题……这部分详细描述解题算法思想或者具体算法步骤。

三、算法实现
此部分要有完整的程序源代码和运行结果截图。

还要有适当的说明，比如数据结构的选择和存储、变量的作用等，源代码中要有适当的注释。

四、算法分析（与改进）
此部分要有两方面的分析，以时间复杂度为主，有分析过程和结果。

如果有改进算法的想法，可以加在这部分，给出改进算法的清晰描述。

第三个报告中，此部分还要有几种解题方法的比较。

报告成绩单。

acm模板总结字符串模板KMPEXKMPTrie可持久化Trie树+DFS序01TrieManacher字符串哈希 2019上海⽹络赛G题 17SA(后缀数组) 最⼤不重叠相似⼦串 求两个字符串长度不⼩于 k 的公共⼦串的个数SAM (后缀⾃动机) 洛⾕p3975 求字典序第K⼩串 动态求出现⾄少k次本质不同⼦串个数 线段树合并:求在串s的l,r区间的⼦串第k个出现位置 两个字符串的⼦串拼接成的不同字符串数量 SAM+线性基GSAM(⼴义后缀⾃动机) ⼀颗字典树每次查询⼀个给出字符串是字典树上多少串的后缀 线段树合并 长度<=m的⼦串的期望ACAM (AC⾃动机) HDU2222:查找模式串 树状数组维护fail树的dfs序 主席树维护fail树的dfs序 长度不超过m的串所得到的最⼤权值 DP+AC⾃动机+最短路PAM(回⽂⾃动机) 模板 ⼀个串⾥所有本质不同的回⽂⼦串满⾜⼀个串是另⼀个的⼦串的对数 求公共回⽂串个数 邻接表优化求相交回⽂串对个数序列⾃动机 求⼦序列个数 求两个串的公共⼦序列个数 求串回⽂⼦序列个数 求A,B的最长公共⼦序列S使得C是S的⼦序列数据结构模板带权并查集线性基单纯形线段树 历史最值线段树 位运算线段树主席树树状数组多维树状数组 树状数组区间加，区间询问RMQ树分治 最短路径树 动态树分治(重⼼树) 动态维护树的直径(19上海⽹络A题) 点分治+三进制加法 点分治+启发式合并(论⽂题) 输出点乘为K的字典序最⼩的路径 Query on a tree IV（边分）树链剖分 倍增法BZOJ3083换根操作 HDU3710 MST+树链剖分+倍增Splay tree (伸展树) BZOJ1500基本模板 BZOJ1208前驱后继 在线带修改插⼊的区间第K⼩LCT模板 基本模板 BZOJ 3091路径期望查询划分树左偏树图论模板⽀配树DFS靠谱找环强连通分量(Tarjan)双联通分量 边双联通 点双联通桥和割顶最⼩树形图 固定根 不定根 不定根路径输出最短路径树 求包含每条边的最⼩简单环最短路SPFAK短路差分约束分层图求最短路⼆分图 ⼆分图的判定以及最⼤匹配数(HDU2444) (KM算法(对匈⽛利算法的贪⼼拓展)⽹络流 最⼤流模板：(⽩书上的) ⽹络流最⼤流(优化的dinic)表⽰: 求最⼩点割集为例: 最⼩路径覆盖并输出路径： 矩阵解压为例（给出每⾏的和，每列的和，还原原矩阵 最⼩费⽤最⼤流。

ACM Steps1.3.1解题报告#include<iostream>#include<cstdio>using namespace std;int main(){float m,j[1001],f[1001],sum,temp,temp1;int n,i,t,k;while(cin>>m>>n){if(n==-1&&m==-1) break;for(i=0;i<n;i++)cin>>j[i]>>f[i];for(t=0;t<n-1;t++){for(k=0;k<n-t-1;k++)if((j[k]/f[k])<(j[k+1]/f[k+1])){temp=j[k];j[k]=j[k+1];j[k+1]=temp;temp1=f[k];f[k]=f[k+1];f[k+1]=temp1;}}sum=0;for(i=0;i<n;i++){if(m>f[i]){sum=sum+j[i];m=m-f[i];}else{sum=sum+m/f[i]*j[i];m=0;}if(m==0)break;}printf("%.3f\n",sum);}return 0;}这是一个求最优解的问题，要用到贪心算法的思维。

我的思路是：首先把它给的几组数按照j[i]/f[i]进行由大到小排序，然后把老鼠有的猫粮与仓库需要的猫粮进行比较，如果老鼠有的粮食有余，那就直接拿到这个仓库的所有的三明治，再又把老鼠剩余的粮食与下一个仓库所需的粮食进行比较,如果老鼠有的粮食还是有余，又直接拿到这个仓库的所有的三明治。

如此比较下去，如果老鼠有的粮食比仓库所需的粮食少，就按照比例得到这个仓库的三明治。

最后输出老鼠得到的所有的三明治，就可以得到本题的结果。

只要思维清晰，这样的题很快就以AC。

在这一章节的8道题中，基本全是涉及到贪心算法的题。

算法模板2矩阵乘法 (3)domino 多米诺骨牌取0 到0～n 的状态。

(3)pku3233 S = A + A2 + A3 + ... + Ak. (4)pku2778 不含疾病基因的长度为n 的的基因总数 (5)voj1049 (8)Voj1067 (9)高斯削元 (10)Ural 01 高斯消元 (10)01转换为mod 2 (12)pku3532 实数高斯消元 (14)Hdu2408整系数线性方程组的整数解（高斯消元） (16)hdu2449 分数高斯消元（高精度） (18)动态规划 (21)状态压缩 (21)pku1038 一个有限制的矩形用2*3 覆盖，最多能覆盖多少块。

（三进制） (21)pku2411 11*11 的格子用1*2铺满 (23)pku1185 炮兵阵地 (24)pku2430 两列n行一堆牛。

(25)pku2288 best triangular Hamilton (27)pku2285 放积木，要求放满 (29)hrb5085 放积木，积木不能旋转(注意长宽方向)，求最多铺的面积 (32)树型dp (34)题目类型总结 (34)pku1463 树的最小点覆盖 (34)pku3342 树的最大独立点集 (35)pku3398 树的节点只与一个server 相连。

(37)pku1947 删最少的边得到一个含p个节点的子树(dfs 降维) (39)pku3140 m 是骗人的。

树分成两半，节点权和差最小 (40)tsoi3_4 所有点间距离的平均值 (42)pku1155 在权值非负的情况下包括尽量多的叶子节点(dfs 降维) (43)pku1155 dfs 降维 (45)pku2486 apple tree 两种状态互相推导(go,back) (46)pku3345(hdu2415) 贿选。

(47)拓扑序dp (50)Hdu2437 Jerboas 有向无环图单起点多终点路线为K的倍数地最短的路线长度. 50Hdu2452 Navy maneuvers 有向无环图，两个船长轮流领航 (52)四边形不等式 (54)一般性结论 (54)石子合并 (54)pku1160 有n 个村子要建p 个邮局 (55)单调队列 (56)题目类型总结 (56)pku2823 求数列中定长区间的最大最小值 (57)hdu2430 预处理g[x]=i 表示s[i]%p==x 的第一个i (58)noi05_adv1900 (60)pku2373 f[i]=max(f[i-2*b]..f[i-2*a])+1 (62)zoj3031 邮件分发 (63)pku1821 n 个工人刷长为m 的墙 (64)平衡二叉树 (65)pku1765 算每个屋檐的降雨量，扫除线+treap (65)静态平衡二叉树hrb5086 (68)Pku2352 (71)pku3378 5维逆序对 (72)归并排序 (74)Hrb5085 树状数组 (78)pku3321 Apple Tree 欧拉序列+树状数组 (79)线段树 (81)题目类型总结 (81)线段树总结 (81)Pku3225 集合操作线段树翻转 (82)pku1769 线段树+dp (动态查询修改某一区间的信息) (85)Hdu2430 线段树dp 询问长度为k 的区间中的最小值。

ACM图论解题报告图论1 题意：输入cas n m 输入n个数输入m组每组表示一个范围内l r 中小于num 的数的个数注意从l是0开始的思路：区间内找数很容易联想到划分树划分树是用来求一个区间内的第k 大的数那我们可以找出第1第2第3.。

大数的值和num进行比较用二分法很容易找到第几大的数小于且等于num_include_lt;stdio.h_gt;_include_lt;algorithm_gt;using namespace std;_define M 100005int tree[40][M],sorted[M];int toLeft[40][M];void build(int level,int left,int right){if(left==right)return ;int mid=(left+right)_gt;_gt;1;int i;int suppose;//假设在中位数sorted[mid]左边的数都全部小于sorted[mid] suppose=mid-left+1;for(i=left;i_lt;=right;i++){if(tree[level][i]_lt;sorted[mid]){suppose--;}}//如果suppose==1，则说明数组中值为sorted[mid]只有一个数。

比如序列：1 3 4 5 6，sorted[mid]=4/_如果suppose_gt;1，则说明数组中左半边值为sorted[mid]的不止一个数,为mid-suppose。

比如序列：1 4 4 4 6，sorted[mid]=4_/int lpos=left,rpos=mid+1;for(i=left;i_lt;=right;i++){if(i==left){//这里是预处理，相当与初始化toLeft[level][i]=0;}else{toLeft[level][i]=toLeft[level][i-1];}if(tree[level][i]_lt;sorted[mid]){//划分到中位数左边 toLeft[level][i]++;tree[level+1][lpos++]=tree[level][i];。

第一期训练题解题报告（1013、1016、1017）曾志平解题报告，就是将自己AC了的题的算法用文字/公式描述出来，并附上代码。

养成撰写解题报告的习惯，有利于加深自己对所用算法的理解和记忆，并且可以帮助后来者更快的学习ACM。

以下是第一期训练题中的思考题的解题报告。

HDU1013解题报告：题意理解：将一个正整数的各数位上数字相加，直到和为个位数为止。

注意，题目没有指定正整数的取值范围，所以可能会很大，位数可达500.算法思路：1.用char number[N]字符数据保存整数，N取个足够大的值，比如500；2.将字符串数组按元素进行求和，ASCII码的计算公式为ans +=number[i] – 48；3.如果计算出来的ans大于10，则将ans转换为字符串，转到第二步；4.否则，输出ans。

代码：int main(){char a[1000];int i, ans;while(scanf("%s", a) && a[0]!='0'){i=ans=0;while(1){while(a[i]!='\0')ans += a[i++] - 48;if(ans>9){sprintf(a, "%d", ans);i = ans = 0;}else break;}printf("%d\n", ans);}return 0;}HDU1016解题报告：题意理解：给你一个有n个节点的圆环，将数字1~n分别填入n 个节点中，要求任意两个相邻节点中的数字的和为素数。

题目指定了n的范围为0<n<20；算法思路：使用回溯法的最基本形式1.将1放入第一个节点（题目要求），进入下一个节点；2.递归：按顺序将2~n中的可用数字m放入当前节点（用for循环），如m加前一个节点中的数字为素数，则进入下一个节点，递归重复本步；若所有可用数字和前一个节点中的数字的和都不为素数，则返回递归的上一层；3.若当前节点是最后一个节点，且最后剩下的数字m和前一个节点中的数字的和，以及m+1都为素数，则从1开始依次输出各节点中的数字；否则，返回上一层递归，回到步骤2；4.直到所有的可能性都测试过了，算法终止。

FAFU第一次ACM月赛解题报告赛前预计：参赛人数60，人均通过题数2.8题左右，较不易3道通过人次为3-4次。

第一名A7题。

赛后结果参赛人数52，人均通过题数 2.33题。

较不易通过4人次。

第一名A 6题5题3人。

总提交数461，每题都至少有1人通过，基本符合比赛目标。

Problem A:讨厌的数学复杂度：O（1）难度：★本题练手题。

Problem B:帮冬儿忙复杂度：O（log(n) ）难度：★★★★整除K就得整除K中的每个素数分子，这样就先把K化成素数相乘，然后对每一个素数进行判断C(n，m）中所含的个数，取最小值，便是结果。

但是，如何解决C（n，m）含有一素数的个数呢。

可以把C(n,m)化成 n!/(m!*(n-m)!) 从而转成n！中含有一素数的个数，这可以用O(log(n))解决，所以问题圆满解决。

本题代码较少，思路没什么陷阱和绕弯，但要求对素数比较深刻的理解，此题定为中下难度题。

Problem C:王子与公主复杂度：O（n*m*log(n*m) ）难度：★★★本题求的是点和点之间的最短路径，主要考察的是广度优先搜索和优先队列的结合使用。

本题用到的数据结构如下：struct node{int x,y,t,key;bool operator <( const node &b){//(重载运算符’<’,指示优先队列按t的大小把最小的排在队头)return t>b.t;}};广度优先用到的数据结构，其中x，y代表王子此时所在的位置，t是到达此位置所用的时间，key代表王子从原始位置到当前位置所得到的食物,用二进制表示，即如果(key&(1<<i))==1表示王子当前拥有第i中食物。

刚开始时:x=0,y=0,t=0,key=0(没有任何食物)。

然后将刚开始时的状态加入优先队列中。

广度优先时从队列头取出时间最小的状态进行扩展，扩展时是向4个方向进行，当扩展到的位置有魔兽时，如果此时手上有它喜欢的食物，就直接贿赂它，否则就打败它；还有一点是要判断当前位置有无食物，如果有食物就要取走食物，具体操作是：tmp.key=(cur.key|(1<<当前含有食物的种类))。

2008年5月17日，在浙江大学成功举行了浙江省第五届大学生程序设计竞赛。

本人的解题报告如下：A 简单题因为p的范围很小才99 所以从700-799就可以满足全部要求了。

可以打表出来，找出每个连续的一段满足要求的数，保存起来（并且要求新存的段长度比原先的要长），打出一张表，对每个要求的数，2分答案。

（把1-99的结果都保存好，直接输出）。

反正“转折点”很少，怎么搞都可以。

B 简单题直接bfs无向图mst。

C 中等偏难。

给定直线，对每条直线，传说解不等式组可以过，直接看是否存在一个点在直线之上。

（左端点取max,右端点取min，如果左>=右，直接break掉）。

有点ft...O(n^2) n=5000 rp好的可以过....我用的方法类似于凸包，先把所有直线按照斜率a由小到大排序，斜率相同取b较大的，扔掉b小的。

于是所有直线斜率不同。

准备一个栈，栈里面存放上一次能看到的“最上面”的直线以及这条直线能看到的范围x(x值右边的部分可以被看到）。

初始时，把斜率最小的直线入栈，并记录x值为-inf。

然后对第i条直线，所做的是用第i条直线和栈顶直线求交点x,如果这个x值不大于栈顶的x值，则把栈顶元素弹出，继续求交，否则退出。

这种判断操作直到栈为空，或者当前栈顶的x值大于栈顶的x值。

然后把第i条直线入栈，继续，看后面的直线。

最后栈中的直线数就是能看到的。

这种做法类似于凸包的方法，除去排序外，每条直线至多出入栈一次，复杂度O(n)。

总复杂度是O(nlogn)。

D 难题。

这题是比较有意思和有搞头的题。

应该可以算压轴题吧。

题目意思不难，但是很难做。

我想了好久，想出个方法，但是比vb的方法难一些。

其实可以贪心。

首先集合大小为1时，没法搞，直接判断掉。

我们把A集合和B集合里的数都由小到大排序。

要移动元素并且保证代价，那么可以选择的操作方法是A和B交换一些元素，然后A再给B(或者B再给A)若干个元素。

我们只讨论最后A再给B若干个数的情形，B给A的可以类似讨论。