poj题目总结1

//前5题是我从我总结的模版中拿出来的一：最短路径（dijkstra, floyd, SPFA）1,dijkstra(poj.1502)•#include <iostream>•#include<cstring>•using namespace std;•const int INF=9999;•const int MAX=105;•int n, map[MAX][MAX], d[MAX];•int input(char str[])•{•int res=0, k=1, len=strlen(str);•if(str[0]=='X')•return INF;•for(int i=len-1; i>=0; i--)• {• res+=(str[i]-'0')*k;• k*=10;• }•return res;•}•void dijkstra()•{•int i,j,k=1,min;•bool vis[MAX]={0};• vis[1]=1;• d[1]=0;•for(i=1;i<=n; i++)• d[i]=map[1][i];•for(i=1; i<n; i++)• {• min=INF;•for(j=1; j<=n; j++)•if(!vis[j] && d[j]<min)• {• min=d[j];• k=j;• }• vis[k]=true;•for(j=1; j<=n; j++)•if(!vis[j] && d[j]>min+map[k][j]) • d[j]=min+map[k][j];• }•}•int main()•{•int i,j,max_dis;•char str[15];•while(cin>>n)• {•for(i=2; i<=n; i++)•for(j=1; j<i; j++)• {• cin>>str;• map[i][j]=map[j][i]=input(str);• }• dijkstra();• max_dis=0;•for(i=2; i<=n; i++)• {•if(d[i]>max_dis)• max_dis=d[i];• }• cout<<max_dis<<endl;• }•return 0;•}2,Floydfor(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if( map[i][k] != maxint && map[k][j] != maxint )if( map[i][k] + map[k][j] < map[i][j] )map[i][j] = map[i][k] + map[k][j];}3,SPFA2，二，最小生成树1. int graph[MAX][MAX];2. int Prim(int graph[][MAX], int n)3. {4. /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */5. int lowcost[MAX];6. /* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */7. int mst[MAX];8. int i, j, min, minid, sum = 0;9. /* 默认选择1号节点加入生成树，从2号节点开始初始化 */10. for (i = 2; i <= n; i++)11. {12. /* 最短距离初始化为其他节点到1号节点的距离 */13. lowcost[i] = graph[1][i];14. mst[i] = 1; /* 标记所有节点的起点皆为默认的1号节点 */15. } /* 标记1号节点加入生成树 */16. mst[1] = 0;17. for (i = 2; i <= n; i++) /*n个节点至少需要n-1条边构成最小生成树 */18. {19. min = MAXCOST;20. minid = 0; /* 找满足条件的最小权值边的节点minid */21. for (j = 2; j <= n; j++)22. {23. if (lowcost[j] < min && lowcost[j] != 0) /* 边权值较小且不在生成树中 */24. {25. min = lowcost[j];26. minid = j;27. }28. } /* 输出生成树边的信息:起点，终点，权值 */29. printf("%c - %c : %d/n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);30. sum += min; /* 累加权值 */31. lowcost[minid] = 0; /* 标记节点minid加入生成树 */32. for (j = 2; j <= n; j++) 更新当前节点minid到其他节点的权值 */33. {34. if (graph[minid][j] < lowcost[j]) /* 发现更小的权值 */35. {36. lowcost[j] = graph[minid][j]; /* 更新权值信息 */37. mst[j] = minid; /* 更新最小权值边的起点 */38. }39. }40. }41. return sum; /* 返回最小权值和 */42. }43. int main()44. {45. int i, j, k, m, n;46. int x, y, cost;47. char chx, chy;48. scanf("%d%d", &m, &n); /* 读取节点和边的数目 */49. getchar();50. for (i = 1; i <= m; i++) /* 初始化图，所有节点间距离为无穷大 */51. for (j = 1; j <= m; j++)52. graph[i][j] = MAXCOST;53. for (k = 0; k < n; k++) /* 读取边信息 */54. {55. scanf("%c %c %d", &chx, &chy, &cost);56. getchar();57. i = chx - 'A' + 1;58. j = chy - 'A' + 1;59. graph[i][j] = graph[j][i] =cost;60. }61. cost = Prim(graph, m); /* 求解最小生成树 */62. printf("Total:%d/n", cost); /* 输出最小权值和 */63. return 0;64. }如果map中除了map[i][i] 外还有map[i][j] ( i!=j )为0，则用下面的方法（poj.3625，错了好多遍）• #include<iostream>• #include<cstring>• #include<cstdio>• #include<cmath>•using namespace std;•double map[1005][1005], lowcost[1005];•const double maxcost=1e30;•int n;•double prim()• {•int i, j, minid;•double min, sum=0;•bool vis[1005]={0};• vis[1]=true;• lowcost[1]=0;•for(i=2; i<=n; i++)• lowcost[i]=map[1][i];•for(i=2; i<=n; i++)• {• min=maxcost;•for(j=2; j<=n; j++)• {•if(lowcost[j]<min && !vis[j])• {• min=lowcost[j];• minid=j;• }• }• sum+=min;• vis[minid]=true;•for(j=2; j<=n; j++)• {•if(!vis[j] && map[minid][j]<lowcost[j])• {• lowcost[j]=map[minid][j];• }• }• }•return sum;• }•int main()• {•int i, j, m;•double cost;•int p, q;• cin>>n>>m;•int x[1001], y[1001];•for(i=1; i<=n; i++)• {• cin>>x[i]>>y[i];• }•for(i=1; i<=n; i++)• {•for(j=1; j<=n; j++)• {•if(i==j)• map[i][j]=0;•else•map[i][j]=map[j][i]=sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*( y[i]-y[j]));• }• }•for(j=1; j<=m; j++)• {• cin>>p>>q;• map[p][q]=map[q][p]=0;• }• cost=prim();• printf("%.2lf\n", cost);•return 0;•}三，二分匹配3，Poj.1274 最基本的“最大匹配”•#include<iostream>• #include<cstring>• #include<cstdio>•using namespace std;•int map[202][202], link[202], b[202], m;•bool find(int a)• {•int i;•for(i=1; i<=m; i++)• {•if(map[a][i] && b[i]==0)• {• b[i]=1;•if(link[i]==0 || find(link[i])) • {• link[i]=a;•return true;• }• }• }•return false;• }•int main()• {•int n, i, j, temp, stall;•while(cin>>n>>m)• {• memset(map, 0, sizeof(map));•for(i=1; i<=n; i++)• {• scanf("%d", &temp);•for(j=1; j<=temp; j++)• {• scanf("%d", &stall);• map[i][stall]=1;• }• }• memset(link, 0, sizeof(link));•int ans=0;•for(i=1; i<=n; i++)• {• memset(b, 0, sizeof(b));•if(find(i))• ans++;• }• cout<<ans<<endl;• }•}4，Poj.22264，4代表4x4的矩阵，题意就是最少用多少块木板可以覆盖’*’,但不可以覆盖’.’，就一种测试情形（构图比较困难）4 4*.*..******...*.•#include<iostream>• #include<cstring>• #include<cstdio>•using namespace std;•char s[52][52];•int tempx[52][52], tempy[52][52];•int map[2501][2501], link[2501], b[2501], nx, ny;•bool find(int a)• {•int i;•for(i=1; i<=ny; i++)• {•if(map[a][i] && b[i]==0)• {• b[i]=1;•if(link[i]==0 || find(link[i]))• {• link[i]=a;•return true;• }• }• }•return false;• }•int main()• {•int i, j, r, c;• scanf("%d%d", &r,&c);• getchar();• memset(map,0,sizeof(map));•for(i=1; i<=r; i++)• {•for(j=1; j<=c; j++)• {• scanf("%c", &s[i][j]); • }• getchar();• }• nx=0; ny=0;•for(i=1; i<=r; i++)• {• j=1;•while(j<=c)• {•if(s[i][j]=='*')• {• nx++;•while(s[i][j]=='*') • {• tempx[i][j]=nx; • j++;• }• }•else• j++;• }• }•for(j=1; j<=c; j++)• {• i=1;•while(i<=r)• {•if(s[i][j]=='*')• {• ny++;•while(s[i][j]=='*') • {• tempy[i][j]=ny; • i++;• }• }•else• i++;• }• }•for(i=1; i<=r; i++)•for(j=1; j<=c; j++)• {•if(s[i][j]=='*')• {• map[tempx[i][j]][tempy[i][j]]=1;• }• }• memset(link,0,sizeof(link));•int ans=0;•for(i=1; i<=nx; i++)• {• memset(b, 0, sizeof(b));•if(find(i))• ans++;• }• cout<<ans<<endl;•return 0;• }5，Poj.3020比较难的这题是相邻的’*’可以匹配，问总共有多少匹配数#include<iostream>#include<cstdio>#include<cstring>using namespace std;int mp[1601][1601];char charmp[41][41];int flag[1601];int link[1601];bool b[1601];int dir[4][2]={-1,0,0,1,1,0,0,-1};int left_num,right_num;bool can(int t){for(int i=0;i<right_num;i++){if(!b[i]&&mp[t][i]){b[i]=1;if(link[i]==-1||can(link[i])){link[i]=t;return 1;}}}return 0;}int main(){int t;scanf("%d",&t);while(t--){int x,y;scanf("%d%d",&x,&y);memset(flag,0,sizeof(flag));left_num=right_num=x*y;for(int i=0;i<x;i++){scanf("%s",&charmp[i]);}int ni,nj;memset(mp,0,sizeof(mp));int total=0;for(int i=0;i<x;i++){for(int j=0;j<y;j++){if(charmp[i][j]=='*'){total++;for(int k=0;k<4;k++){ni=i+dir[k][0];nj=j+dir[k][1];if(ni<0||ni>=x||nj<0||nj>=y) continue;if(charmp[ni][nj]=='*')mp[i*y+j][ni*y+nj]=1;}}}}memset(link,0xff,sizeof(link));int ans=0;for(int i=0;i<left_num;i++){memset(b,0,sizeof(b));if(can(i))ans++;}printf("%d\n",total-ans/2);}return 0;}//这以上是我从我之前总结的模版里拿出来的1，Poj.2954 Tringle（2011-7-20 15:47:45）题意：已知三角形三个顶点，求三角形内部的整点个数。

例1：求一维数组中连续数之和的最大值。

代码：#include<iostream>using namespace std;int a[100];//记录一维数组int res[100];//res[i]表示以第i个数为末尾的连续数之和的最大值int main(){int i,n,max;while(1){cin>>n;if(!n) break;memset(res,0,sizeof(a)),max=-1270000;for(i=0;i<n;i++){cin>>a[i];res[i]=a[i];if(i>0 && res[i-1]>0) res[i]+=res[i-1];//动态规划法if(res[i]>max) max=res[i];//打擂法}cout<<max<<endl;}return 0;}例2（poj1050）：求二维数组中子矩阵之和的最大值。

（例1的拓展）代码：#include<iostream>using namespace std;int a[101][101];//记录二维数组int sum[101][101];//sum[i][j]表示第j列前i行的数之和int res[101][101][101];//res[i1][i2][j]表示从第i1行到第i2行，以第j个数为末尾的连续数之和的最大值int main(){int i,i1,i2,j,n,temp,max;while(1){cin>>n;if(!n) break;memset(sum,0,sizeof(sum)),memset(res,0,sizeof(res));for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>a[i][j];//输入二维数组sum[i][j]=sum[i-1][j]+a[i][j];//求第j列前i行之和}max=-1270000;for(i1=1;i1<=n;i1++)//类似一维数组求最大和的方法，将一重循环改为三重循环for(i2=i1;i2<=n;i2++)for(j=1;j<=n;j++){res[i1][i2][j]=sum[i2][j]-sum[i1-1][j];//相当于一维数组中的第j 个数if(res[i1][i2][j-1]>0) res[i1][i2][j]+=res[i1][i2][j-1];if(res[i1][i2][j]>max) max=res[i1][i2][j];}cout<<max<<endl;}return 0;}例3（poj1458）：求最长公共子序列的长度。

poj搜索题总结——初期篇简单搜索(1)深度优先搜索(poj2488,poj3009,poj1321)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414,poj2251,poj3083)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)看到这些题是不是很眼熟。

没错，这就是某位大牛推荐初期要做的题。

而这文章就是为这些题加上解题报告以及一些总结。

深度优先搜索poj2488：A Knight's Journey如果没有按字典序输出这个要求的话，就是简单的DFS，但是加上的话，就是麻烦题。

这就要求求出全部的走法或在行走时，按照某种顺序走。

从时间上来说，当然是选择第二种了。

若存在可行路线，则每个格子必然都走过。

所以从A1开始，按照某种顺序走，若有解，则为所求，若无，则无解。

//W A了N次,才发现是倒在字典序的手下//虽然题目没说，但是这道题最后一组数据后是没有空行的...否则会PE...//若存在可行路线，则每个格子都走过。

所以从（0，0）开始即可，不需要遍历每一个起始点//注意行走的方法（即MOV数组元素的排列），可以在找到可行解时，就使得其字典序最小#include<iostream>#include<string>#include<fstream>using namespace std;bool flag;string answer[30];int chess[30][30];//这个的设置一定要与下面的转换相对应，之前就是不对应，错了N次int mov[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};string GetPosition(int x,int y) { //将X，Y坐标转换成题目要求的形式string stmp;stmp+=(char)(y+'A'); //由于先出现的是Y坐标（如B3），所以MOV数组中的Y 应从-2到2的顺序变化stmp+=(char)(x+'1');return stmp;}void SaveIt(int p,int q) { //保存下答案answer[chess[i][j]]=GetPosition(i,j);}}}void dfs(int p,int q,int num,int x,int y) {if( num==p*q ) {flag=true;SaveIt(p,q);return;}int xx,yy;for(int i=0;i<8;++i) {if( flag ) return ;xx=x+mov[i][0];yy=y+mov[i][1];if( (xx>=0 && xx<p) && (yy>=0 && yy<q) && chess[xx][yy]==0 ) {chess[xx][yy]=num+1;dfs(p,q,num+1,xx,yy);chess[xx][yy]=0;}}}int main() {ifstream cin("test.in");int cases,count(1),p,q,i;cin>>cases;while( cases-- ) {cin>>p>>q;flag=false;memset(chess,0,sizeof(chess));chess[0][0]=1;dfs(p,q,1,0,0);//outputcout<<"Scenario #"<<count++<<":"<<endl;if( flag ) {for(i=1;i<=p*q;++i) cout<<answer[i];cout<<endl;}}return 0;}poj1321：棋盘问题这题是简单的DFS，但题目有个地方说得不是很清楚，就是以“#”为标志的位置才能放棋子。

数组逆序重放using System;using System.Collections.Generic;using System.Linq;using System.Text;/*题目描述将一个数组中的值按逆序重新存放。

例如，原来的顺序为8,6,5,4,1。

要求改为1,4,5,6,8。

输入输入为两行：第一行数组中元素的个数n（1<n<100)，第二行是n个整数，每两个整数之间用空格分隔。

输出输出为一行：输出逆序后数组的整数，每两个整数之间用空格分隔。

*/namespace数组逆序重放{class Program{static void Main(string[] args){Console.Write("输入数字，以空格隔开：\n");string ar =Console.ReadLine();string[]array=ar.Split("".ToCharArray(),StringSplitOptions.RemoveEmptyEntries);//获取输入数组保存在array中int[] num =new int[array.Length];for (int i = 0; i < array.Length; i++){int.TryParse(array[i],out num[i]);//将输入保存在int型数组中}Console.Write("{0}\n",num.Length);Array.Reverse(num);foreach (int k in num)Console.Write("{0} ",k);Console.ReadKey();}}}化验诊断using System;using System.Collections.Generic;using System.Linq;using System.Text;/*题目描述下表是进行血常规检验的正常值参考范围，及化验值异常的临床意义：给定一张化验单，判断其所有指标是否正常，* 如果不正常，统计有几项不正常。

匹配问题学习小结(POJ)临行上海，决定把最近研究过的各种匹配题做个汇总，原因是这样既可以巩固自己对匹配问题的掌握，又可以借此复习一下匹配问题的各种外在表现形式。

我认为，如果比赛中出到匹配，出题者在问题的算法上大做文章的可能性不大，大多数出题者一定会挖空心思来设计一个让你眼花缭乱的背景，借此来隐藏匹配问题的实质！二分图最小覆盖的Konig定理及其证明二分图：顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。

最小覆盖：最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。

可以证明：最少的点（即覆盖数）＝最大匹配数Konig定理：二分图的最小顶点覆盖数等于最大匹配数。

证明：为主便叙述，假设G分为左边X和右边Y两个互不相交的点集。

假设G经过匈牙利算法后找到一个最大匹配M，则可知G中再也找不到一条增广路径。

标记右边未匹配边的顶点，并从右边未匹配边的顶点出发，按照边：未匹配->匹配->未匹配...，的原则标记途中经过的顶点，则最后一条经过的边必定为匹配边。

重复上述过程，直到右边不再含有未匹配边的点。

记得到的左边已标记的点和右边未标记的点为S，以下证明S即为所求的最小顶点集。

1。

| S | == M显然，左边标记的点全都为匹配边的顶点，右边未标记的点也为匹配边的顶点。

因此，我们得到的点与匹配边一一对应。

2。

S能覆盖G中所有的边。

上途S中点所得到的边有以下几种情况：（1）左右均标记；（2）左右均无标记；（3）左边标记，右边未标记；若存在一条边e不属于S所覆盖的边集，则e 左边未标记右边标记。

如果e不属于匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果e属于匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的左端点就应该有标记。

3。

S是最小的覆盖。

因为要覆盖这M条匹配边至少就需要M个点。

转自:/post.2801156.html#在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集．由上面可以得出：１.一个单独的顶点是一条路径；２．如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．最小路径覆盖就是找出最小的路径条数，使之成为Ｐ的一个路径覆盖．路径覆盖与二分图匹配的关系：最小路径覆盖＝｜Ｐ｜－最大匹配数；其中最大匹配数的求法是把Ｐ中的每个顶点pi分成两个顶点pi'与pi''，如果在p中存在一条pi到pj的边，那么在二分图Ｐ＇中就有一条连接pi'与pj''的无向边；这里pi' 就是p中pi 的出边，pj''就是p中pj 的一条入边；对于公式：最小路径覆盖＝｜Ｐ｜－最大匹配数；可以这么来理解；如果匹配数为零，那么Ｐ中不存在有向边，于是显然有：最小路径覆盖＝｜Ｐ｜－最大匹配数＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路径覆盖数为｜Ｐ｜；Ｐ＇中不在于匹配边时，路径覆盖数为｜Ｐ｜；如果在Ｐ＇中增加一条匹配边pi'－－＞pj''，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在一条路径上，于是路径覆盖数就可以减少一个；如此继续增加匹配边，每增加一条，路径覆盖数就减少一条；直到匹配边不能继续增加时，路径覆盖数也不能再减少了，此时就有了前面的公式；但是这里只是说话了每条匹配边对应于路径覆盖中的一条路径上的一条连接两个点之间的有向边；下面来说明一个路径覆盖中的每条连接两个顶点之间的有向边对应于一条匹配边；与前面类似，对于路径覆盖中的每条连接两个顶点之间的每条有向边pi--->pj，我们可以在匹配图中对应做一条连接pi'与pj''的边，显然这样做出来图的是一个匹配图（这一点用反证法很容易证明，如果得到的图不是一个匹配图，那么这个图中必定存在这样两条边 pi'---pj'' 及pi' ----pk''，（j!=k），那么在路径覆盖图中就存在了两条边pi-->pj, pi--->pk ，那边从pi出发的路径就不止一条了，这与路径覆盖图是矛盾的；还有另外一种情况就是存在pi'---pj'',pk'---pj''，这种情况也类似可证）；至此，就说明了匹配边与路径覆盖图中连接两顶点之间边的一一对应关系，那么也就说明了前面的公式成立！转自:/cjhh314/blog/item/ded8d31f15d7510c304e1591.htmlPOJ 1469 COURSES学生选课问题，基础匹配问题。

初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026)(4)拓扑排序 (poj1094)(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串 (poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书 page149):1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化 (poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等) (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题. (poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解) (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446) (3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的).(poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点). (poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.(poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划. (poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263) 以及补充Dp状态设计与方程总结1.不完全状态记录<1>青蛙过河问题<2>利用区间dp2.背包类问题<1> 0-1背包，经典问题<2>无限背包，经典问题<3>判定性背包问题<4>带附属关系的背包问题<5> + -1背包问题<6>双背包求最优值<7>构造三角形问题<8>带上下界限制的背包问题(012背包)3.线性的动态规划问题<1>积木游戏问题<2>决斗（判定性问题）<3>圆的最大多边形问题<4>统计单词个数问题<5>棋盘分割<6>日程安排问题<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)<8>方块消除游戏(某区间可以连续消去求最大效益)<9>资源分配问题<10>数字三角形问题<11>漂亮的打印<12>邮局问题与构造答案<13>最高积木问题<14>两段连续和最大<15>2次幂和问题<16>N个数的最大M段子段和<17>交叉最大数问题4.判定性问题的dp(如判定整除、判定可达性等)<1>模K问题的dp<2>特殊的模K问题，求最大(最小)模K的数<3>变换数问题5.单调性优化的动态规划<1>1-SUM问题<2>2-SUM问题<3>序列划分问题(单调队列优化)6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)<1>凸多边形的三角剖分问题<2>乘积最大问题<3>多边形游戏(多边形边上是操作符,顶点有权值)<4>石子合并(N^3/N^2/NLogN各种优化)7.贪心的动态规划<1>最优装载问题<2>部分背包问题<3>乘船问题<4>贪心策略<5>双机调度问题Johnson算法8.状态dp<1>牛仔射击问题(博弈类)<2>哈密顿路径的状态dp<3>两支点天平平衡问题<4>一个有向图的最接近二部图9.树型dp<1>完美服务器问题(每个节点有3种状态)<2>小胖守皇宫问题<3>网络收费问题<4>树中漫游问题<5>树上的博弈<6>树的最大独立集问题<7>树的最大平衡值问题<8>构造树的最小环转一个搞ACM需要的掌握的算法.要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红, 发挥自己的长处,这才是重要的.第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来.1.最短路(Floyd、Dijstra,BellmanFord)2.最小生成树(先写个prim,kruscal要用并查集，不好写)3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换第二阶段：练习复杂一点，但也较常用的算法。

一.1.第一季10题全（注：第五题问题已经解决,确认AC!)#include <stdio.h>int main(){int a,b,sum;scanf("%d%d",&a,&b);sum=a+b;printf("%d\n",sum);return 0;}2.#include <stdio.h>#define PI 3.1415926int main(){double r,h,l,s,sq,vq,vz;scanf("%lf%lf",&r,&h);l=2*PI*r;s=PI*r*r;sq=4*PI*r*r;vq=4*PI*r*r*r/3;vz=s*h;printf("%.2lf\n%.2lf\n%.2lf\n%.2l f\n%.2lf\n",l,s,sq,vq,vz);return 0; }3.#include <stdio.h>int main(){int a,b,c;double d,e;scanf("%d%d%d",&a,&b,&c);d=a+b+c;e=d/3;printf("%lf\n%lf\n",d,e);return 0;}4.#include <stdio.h>int main(){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a<b)a=b;if(a<c)a=c;printf("%d\n",a);return 0;}5.#include<stdio.h>int main(){int i=0,j=0,k=1;char a[6];while((a[i]=getchar())!='\n'){i++;}for(;i>0;i--){if(a[j]==a[i-1]){j++;continue;}else {k=0;break;}}if(k==1)printf("yes\n");elseprintf("no\n"); }6.#include<stdio.h>int main(){double a,c;scanf("%lf",&a);switch((int)a/10){case 0:c=a*0.1;break;case 1:c=(a-10)*0.075+10 *0.1;break;case 2:case 3:c=(a-20)*0.05+10* 0.075+10*0.1;break;case 4:case 5:c=(a-40)*0.03+20* 0.05+10*0.075+10*0.1;break;case 6:case 7:case 8:case 9:c=(a-60)*0.015+20 *0.03+20*0.05+10*0.075+10*0.1;break;default:c=(a-100)*0.01+40*0.015+20*0.03+20*0.05+10 *0.075+10*0.1;}printf("%lf\n",c);return 0;}7.#include<stdio.h>int main(){double a,b,c;scanf("%lf",&a);c=(int)a;if(a>c)a=c+1;if(a>15)b=(a-15)*2.1+7+13*1.5;else {if(a>2)b=(a-2)*1.5+7;else b=7;}printf("%lf\n",b);return 0;}8.#include <stdio.h>int main(){int a,b,c,e,f=30,g=31,n;scanf("%d-%d-%d",&a,&b,&c);if((a%400==0)||(a%100!=0&&a%4 ==0))e=29;elsee=28;switch (b){case 1:n=c;break;case 2:n=g+c;break;case 3:n=g+e+c;break;case 4:n=g+e+g+c;break;case 5:n=g+e+g+f+c;break;case 6:n=g+e+g+f+g+c;break;case 7:n=g+e+g+f+g+f+c;break;case 8:n=g+e+g+f+g+f+g+c;break;case 9:n=g+e+g+f+g+f+g+g+c;break;case 10:n=g+e+g+f+g+f+g+g+f+c;br eak;case 11:n=g+e+g+f+g+f+g+g+f+g+c; break;default: n=g+e+g+f+g+f+g+g+f+g+f +c;}printf("%d\n",n);return 0;}9.#include <stdio.h>int main(){int x;scanf("%d",&x);if(x>=90&&x<=100)printf("A\n");else if (x>=80)printf("B\n");else if (x>=70)printf("C\n");else if (x>=60)printf("D\n");elseprintf("E\n");return 0;}10.#include<stdio.h> int main(){double x,y,s;scanf("%lf,%lf",&x,&y);s=(x+2)*(x+2)+(y-2)*(y-2);if(s>1){s=(x+2)*(x+2)+(y+2)*(y+2);if(s>1){s=(x-2)*(x-2)+(y+2)*(y+2);if(s>1){s=(x-2)*(x-2)+(y-2)*( y-2);if(s>1){printf("0\n") ;return 1;}}}}printf("10\n");return 0;}二。