ACM模板1

目录目录 (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 算法的一种队列实现，减少了不必要的冗余计算。

acm模板整理和使用方法[acm模板整理和使用方法]ACM模板指的是计算机科学中常用的算法模板，是计算机专业的学生在学习算法和数据结构时必需掌握的内容。

ACM模板整理和使用方法主要包括以下问题：一、为什么要使用ACM模板？ACM模板能使算法实现变得更简单、更方便、更快捷。

尤其在ACM竞赛中，使用优秀的模板可以节省编程时间，避免出现冗余代码，使得编程效率大幅提升。

二、哪些算法需要掌握？许多常见的算法，如快速排序、线段树、并查集、Kruskal算法、Dijkstra算法、最小生成树问题等，都需要掌握。

因此，算法学习和掌握是使用ACM模板的前提。

三、如何整理和使用ACM模板？1.整理ACM模板将常用的算法的代码整理，以函数或者类的形式存放在一个文件中。

注意代码要有良好的注释，易于阅读和理解。

2.旧的代码调试如果有其他ACM竞赛选手或者教练的旧代码，需要先将其调试通过。

因为在ACM比赛中，时间十分宝贵。

如果没有调试好的代码可以使用，建议可以使用OJ网站上的代码进行练习。

3.在比赛中使用和修改模板在ACM比赛中，选手需要快速编写正确的程序并提交到OJ网站。

使用模板可以节省时间和精力，但有时候需要针对具体的问题进行修改。

在修改时需要小心，一定要保证修改后的代码与原始模板的代码所实现的算法是等效的。

4.维护和更新模板ACM模板需要不断地维护和更新，特别是在涉及到新的算法或者数据结构时。

保证ACM模板的有效性和及时性非常重要，这需要持续的学习和探索。

四、如何学习和掌握ACM模板？1.选择学习和观察别人的代码一个好的方式是看国内和国际大佬们的代码，学习他们的代码风格和思考方式。

了解其他人的ACM模板如何实现，可以帮助你提高代码风格和技术水平。

2.探索自己不熟悉的算法和数据结构ACM竞赛中考察的算法不限于常见的算法，还包括各种数论、图论、动态规划等。

掌握这些算法和数据结构可以提高解题的速度和质量。

在掌握新算法之前，阅读相关论文或文章，掌握其基本原理和实现方法。

免费模板~~~ACM Standard Code LibraryHuang WeiSoftware EngineeringComputer and Software CollegeHangzhou Dianzi UniversityOctober,2008ACM算法模板集Contents一.常用函数与STL二.重要公式与定理1.Fibonacci Number2.Lucas Number3.Catalan Number4.Stirling Number(Second Kind)5.Bell Number6.Stirling's Approximation7.Sum of Reciprocal Approximation8.Young Tableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式三.大数模板，字符读入四.数论算法1.Greatest Common Divisor最大公约数2.Prime素数判断3.Sieve Prime素数筛法4.Module Inverse模逆元5.Extended Euclid扩展欧几里德算法6.Modular Linear Equation模线性方程(同余方程)7.Chinese Remainder Theorem中国余数定理(互素与非互素)8.Euler Function欧拉函数9.Farey总数9.Farey序列构造ler_Rabbin素数测试，Pollard_rho因式分解五.图论算法1.最小生成树(Kruscal算法)2.最小生成树(Prim算法)3.单源最短路径(Bellman-ford算法)4.单源最短路径(Dijkstra算法)5.全源最短路径(Folyd算法)6.拓扑排序7.网络预流和最大流8.网络最小费用最大流9.网络最大流(高度标号预流推进)10.最大团11.最大匹配(Hungary，HopcroftKarp算法)12.带权二分图最优匹配(KM算法)13.强连通分量(Kosaraju算法)14.强连通分量(Gabow算法)15.无向图割边割点和双连通分量16.最小树形图O(N^3)17.最小树形图O(VE)六.几何算法1.几何模板2.球面上两点最短距离3.三点求圆心坐标4.三角形几个重要的点七.专题讨论1.树状数组2.字典树3.后缀树4.线段树5.并查集6.二叉堆7.逆序数(归并排序)8.树状DP9.欧拉路10.八数码11.高斯消元法12.字符串匹配(KMP算法)13.全排列,全组合14.二维线段树15.稳定婚姻匹配16.后缀数组17.左偏树18.标准RMQ-ST19.度限制最小生成树20.最优比率生成树(0/1分数规划)21.最小花费置换22.区间K大数23.LCA-RMQ-ST24.LCA–Tarjan25.指数型母函数26.指数型母函数(大数据)27.AC自动机(字典树+KMP)28.FFT(大数乘法)29.二分图网络最大流最小割30.混合图欧拉回路31.无源汇上下界网络流32.二分图最小点权覆盖33.带约束的轨道计数(Burnside引理)34.三分法求函数波峰35.单词计数，DFA自动机，Trie图(完全AC自动机)36.字符串和数值hash37.滚动队列，前向星表示法38.最小点基，最小权点基39.LCSubsequence O(N^2/logN)40.伸展树41.Treap42.0/1分数规划K约束43.表达式求值44.乘除法博弈,Wythoff博弈45.状态压缩的积木型DP46.解一般线性方程组(消元法)47.块状链表48.Factor Oracle第一章常用函数和STL一.常用函数#include<stdio.h>int getchar(void);//读取一个字符,一般用来去掉无用字符char*gets(char*str);//读取一行字符串#include<stdlib.h>void*malloc(size_t size);//动态内存分配,开辟大小为size的空间void qsort(void*buf,size_t num,size_t size,int(*compare)(const void*,const void*));//快速排序Sample:int compare_ints(const void*a,const void*b){int*arg1=(int*)a;int*arg2=(int*)b;if(*arg1<*arg2)return-1;else if(*arg1==*arg2)return0;else return1;}int array[]={-2,99,0,-743,2,3,4};int array_size=7;qsort(array,array_size,sizeof(int),compare_ints);#include<math.h>//求反正弦,arg∈[-1,1],返回值∈[-pi/2,+pi/2]double asin(double arg);//求正弦,arg为弧度,弧度=角度*Pi/180.0,返回值∈[-1,1]double sin(double arg);//求e的arg次方double exp(double arg);//求num的对数,基数为edouble log(double num);//求num的根double sqrt(double num);//求base的exp次方double pow(double base,double exp);#include<string.h>//初始化内存,常用来初始化数组void*memset(void*buffer,int ch,size_t count);memset(the_array,0,sizeof(the_array));//printf是它的变形,常用来将数据格式化为字符串int sprintf(char*buffer,const char*format,...);sprintf(s,"%d%d",123,4567);//s="1234567"//scanf是它的变形,常用来从字符串中提取数据int sscanf(const char*buffer,const char*format,...);Sample:char result[100]="24hello",str[100];int num;sprintf(result,"%d%s",num,str);//num=24;str="hello";//字符串比较,返回值<0代表str1<str2,=0代表str1=str2,>0代表str1>str2 int strcmp(const char*str1,const char*str2);二.常用STL[标准container概要]vector<T>大小可变的向量,类似数组的用法,容易实现删除list<T>双向链表queue<T>队列,empty(),front(),pop(),push()stack<T>栈,empty(),top(),pop(),push()priority_queue<T>优先队列,empty(),top(),pop(),push()set<T>集合map<key,val>关联数组,常用来作hash映射[标准algorithm摘录]for_each()对每一个元素都唤起（调用）一个函数find()查找第一个能与引数匹配的元素replace()用新的值替换元素,O(N)copy()复制（拷贝）元素,O(N)remove()移除元素reverse()倒置元素sort()排序,O(N log(N))partial_sort()部分排序binary_search()二分查找merge()合并有序的序列,O(N)[C++String摘录]copy()从别的字符串拷贝empty()判断字符串是否为空erase()从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace()替换元素substr()取子字符串swap()交换字符串第二章重要公式与定理1.Fibonacci Number0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610…Formula:011211i i i n n F F F F F F −−===+⎡⎤⎥==⎥⎠⎦2.Lucas Number1,3,4,7,11,18,29,47,76,123...Formula:n nn L =+⎝⎠⎝⎠3.Catalan Number1,2,5,14,42,132,429,1430,4862,16796,58786,208012…Formula:110(2,)1*n n n i n ii C n n Cat n Cat Cat Cat −−−==+=∑Application:1)将n +2边形沿弦切割成n 个三角形的不同切割数Sample:n =2;n =3;2)n +1个数相乘,给每两个元素加上括号的不同方法数Sample:n =2;(1(23)),((12)3)n =3;(1(2(34))),(1((23)4)),((12)(34)),((1(23))4),(((12)3)4)3)n 个节点的不同形状的二叉树数(严《数据结构》P .155)4)从n *n 方格的左上角移动到右下角不升路径数Sample:n =2;n =3;4.Stirling Number(Second Kind)S(n,m)表示含n 个元素的集合划分为m 个集合的情况数或者是n 个有标号的球放到m 个无标号的盒子中,要求无一为空,其不同的方案数Formula:,1,11,0 (0 || ) (1)n m n m n m m n m S S m S n m −−−=<⎧⎨+×>≥⎩,01(1)(,)()!m i n n m i S C m i m i m ==−××−∑Special Cases:,0,11,2,3,1,01211(3323)6(,2)1n n n n n n n n n n n S S S S S C n S −−===−=−×+==5.Bell Numbern 个元素集合所有的划分数Formula:,0nn n ii B S ==∑6.Stirling's Approximation!nn n e ⎞=⎟⎠7.Sum of Reciprocal ApproximationEulerGamma =0.57721566490153286060651209;11ln() ()n i n EulerGamma n i==+→∞∑8.Young TableauYoung Tableau(杨式图表)是一个矩阵,它满足条件:如果格子[i,j]没有元素,则[i+1,j]也一定没有元素如果格子[i,j]有元素a[i,j],则[i+1,j]要么没有元素,要么a[i+1,j]>a[i,j]Y[n]代表n 个数所组成的杨式图表的个数Formula:121212(1) (2)n n n Y Y Y Y n Y n −−===+−×>Sample:n =3;9.整数划分将整数n 分成k 份,且每份不能为空,任意两种分法不能相同1)不考虑顺序for (int p=1;p<=n ;p++)for (int i=p;i<=n ;i++)for (int j=k;j>=1;j--)dp[i][j]+=dp[i-p][j-1];cout<<dp[n][k]<<endl;2)考虑顺序dp[i][j]=dp[i-k][j-1];(k=1..i)3)若分解出来的每个数均有一个上限mdp[i][j]=dp[i-k][j-1];(k=1..m)10.错排公式121201(1)()n n n D D D n D D −−===−×+11.三角形内切圆半径公式22a b cp s sr a b c++===++12.三角形外接圆半径公式4abcR s=13.圆內接四边形面积公式2a b c dp s +++==14.基础数论公式1)模取幂%((((%)*)%))%n a b a b a b b=…2)n 的约数的个数若n 满足1212m n n n m n p p p =+++…,则n 的约数的个数为12(1)(1)(1)m n n n +++…第三章大数模板typedef int hugeint;//应不大于,以防乘法时溢出const int Base=1000;const int Capacity=1000;struct xnum{int Len;int Data[Capacity];xnum():Len(0){}xnum(const xnum&V):Len(V.Len){memcpy(Data,V.Data,Len*sizeof*Data);}xnum(int V):Len(0){for(;V>0;V/=Base)Data[Len++]=V%Base;}xnum(char S[]);xnum&operator=(const xnum&V){Len=V.Len;memcpy(Data,V.Data,Len*sizeof*Data);return*this;}int&operator[](int Index){return Data[Index];}int operator[](int Index)const{return Data[Index];}void print(){printf("%d",Len==0?0:Data[Len-1]);for(int i=Len-2;i>=0;i--)for(int j=Base/10;j>0;j/=10)printf("%d",Data[i]/j%10);}};xnum::xnum(char S[]){int I,J;Data[Len=0]=0;J=1;for(I=strlen(S)-1;I>=0;I--){Data[Len]+=(S[I]-'0')*J;J*=10;if(J>=Base)J=1,Data[++Len]=0;}if(Data[Len]>0)Len++;}int compare(const xnum&A,const xnum&B){int I;if(A.Len!=B.Len)return A.Len>B.Len?1:-1;for(I=A.Len-1;I>=0&&A[I]==B[I];I--);if(I<0)return0;return A[I]>B[I]?1:-1;}xnum operator+(const xnum&A,const xnum&B){xnum R;int I;int Carry=0;for(I=0;I<A.Len||I<B.Len||Carry>0;I++) {if(I<A.Len)Carry+=A[I];if(I<B.Len)Carry+=B[I];R[I]=Carry%Base;Carry/=Base;}R.Len=I;return R;}xnum operator-(const xnum&A,const xnum&B){xnum R;int Carry=0;R.Len=A.Len;int I;for(I=0;I<R.Len;I++){R[I]=A[I]-Carry;if(I<B.Len)R[I]-=B[I];if(R[I]<0)Carry=1,R[I]+=Base;else Carry=0;}while(R.Len>0&&R[R.Len-1]==0)R.Len--;return R;}xnum operator*(const xnum&A,const int B){int I;if(B==0)return0;xnum R;hugeint Carry=0;for(I=0;I<A.Len||Carry>0;I++){if(I<A.Len)Carry+=hugeint(A[I])*B;R[I]=Carry%Base;Carry/=Base;}R.Len=I;return R;}xnum operator*(const xnum&A,const xnum&B){int I;if(B.Len==0)return0;xnum R;for(I=0;I<A.Len;I++){hugeint Carry=0;for(int J=0;J<B.Len||Carry>0;J++){if(J<B.Len)Carry+=hugeint(A[I])*B[J];if(I+J<R.Len)Carry+=R[I+J];if(I+J>=R.Len)R[R.Len++]=Carry%Base;else R[I+J]=Carry%Base;Carry/=Base;}}return R;}xnum operator/(const xnum&A,const int B){xnum R;int I;hugeint C=0;for(I=A.Len-1;I>=0;I--){C=C*Base+A[I];R[I]=C/B;C%=B;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len--;return R;}//divxnum operator/(const xnum&A,const xnum&B){int I;xnum R,Carry=0;int Left,Right,Mid;for(I=A.Len-1;I>=0;I--){Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left<Right){Mid=(Left+Right+1)/2;if(compare(B*Mid,Carry)<=0)Left=Mid;else Right=Mid-1;}R[I]=Left;Carry=Carry-B*Left;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len--;return R;}//modxnum operator%(const xnum&A,const xnum&B){int I;xnum R,Carry=0;int Left,Right,Mid;for(I=A.Len-1;I>=0;I--){Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left<Right){Mid=(Left+Right+1)/2;if(compare(B*Mid,Carry)<=0)Left=Mid;else Right=Mid-1;}R[I]=Left;Carry=Carry-B*Left;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len--;return Carry;}istream&operator>>(istream&In,xnum&V){char Ch;for(V=0;In>>Ch;){V=V*10+(Ch-'0');if(cin.peek()<='')break;}return In;}ostream&operator<<(ostream&Out,const xnum&V){int I;Out<<(V.Len==0?0:V[V.Len-1]);for(I=V.Len-2;I>=0;I--)for(int J=Base/10;J>0;J/=10)Out<<V[I]/J%10;return Out;}xnum gcd(xnum a,xnum b){if(compare(b,0)==0)return a;else return gcd(b,a%b);}int div(char*A,int B){int I;int C=0;int Alen=strlen(A);for(I=0;I<Alen;I++){C=C*Base+A[I]-'0';C%=B;}return C;}xnum C(int n,int m){int i;xnum sum=1;for(i=n;i>=n-m+1;i--)sum=sum*i;for(i=1;i<=m;i++)sum=sum/i;return sum;}#define MAXN9999#define DLEN4class BigNum{private:int a[1000];//可以控制大数的位数int len;//大数长度public:BigNum(){len=1;memset(a,0,sizeof(a));} BigNum(const int);BigNum(const char*);BigNum(const BigNum&);BigNum&operator=(const BigNum&);BigNum operator+(const BigNum&)const;BigNum operator-(const BigNum&)const;BigNum operator*(const BigNum&)const;BigNum operator/(const int&)const;BigNum operator^(const int&)const;int operator%(const int&)const;bool operator>(const BigNum&T)const;void print();};BigNum::BigNum(const int b){int c,d=b;len=0;memset(a,0,sizeof(a));while(d>MAXN){c=d-(d/(MAXN+1))*(MAXN+1);d=d/(MAXN+1);a[len++]=c;}a[len++]=d;}BigNum::BigNum(const char*s){int t,k,index,l,i;memset(a,0,sizeof(a));l=strlen(s);len=l/DLEN;if(l%DLEN)len++;index=0;for(i=l-1;i>=0;i-=DLEN){t=0;k=i-DLEN+1;if(k<0)k=0;for(int j=k;j<=i;j++)t=t*10+s[j]-'0';a[index++]=t;}}BigNum::BigNum(const BigNum&T):len(T.len){ int i;memset(a,0,sizeof(a));for(i=0;i<len;i++)a[i]=T.a[i];}BigNum&BigNum::operator=(const BigNum&n){ len=n.len;memset(a,0,sizeof(a));int i;for(i=0;i<len;i++)a[i]=n.a[i];return*this;}BigNum BigNum::operator+(const BigNum&T)const{ BigNum t(*this);int i,big;//位数big=T.len>len?T.len:len;for(i=0;i<big;i++){t.a[i]+=T.a[i];if(t.a[i]>MAXN){t.a[i+1]++;t.a[i]-=MAXN+1;}}if(t.a[big]!=0)t.len=big+1;else t.len=big;return t;}BigNum BigNum::operator-(const BigNum&T)const{ int i,j,big;bool flag;BigNum t1,t2;if(*this>T){t1=*this;t2=T;flag=0;}else{t1=T;t2=*this;flag=1;}big=t1.len;for(i=0;i<big;i++){if(t1.a[i]<t2.a[i]){j=i+1;while(t1.a[j]==0)j++;t1.a[j--]--;while(j>i)t1.a[j--]+=MAXN;t1.a[i]+=MAXN+1-t2.a[i];}else t1.a[i]-=t2.a[i];}t1.len=big;while(t1.a[len-1]==0&&t1.len>1){t1.len--;big--;}if(flag)t1.a[big-1]=0-t1.a[big-1];return t1;}BigNum BigNum::operator*(const BigNum&T)const{BigNum ret;int i,j,up;int temp,temp1;for(i=0;i<len;i++){up=0;for(j=0;j<T.len;j++){temp=a[i]*T.a[j]+ret.a[i+j]+up;if(temp>MAXN){temp1=temp-temp/(MAXN+1)*(MAXN+1);up=temp/(MAXN+1);ret.a[i+j]=temp1;}else{up=0;ret.a[i+j]=temp;}}if(up!=0)ret.a[i+j]=up;}ret.len=i+j;while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;return ret;}BigNum BigNum::operator/(const int&b)const{BigNum ret;int i,down=0;for(i=len-1;i>=0;i--){ret.a[i]=(a[i]+down*(MAXN+1))/b;down=a[i]+down*(MAXN+1)-ret.a[i]*b;}ret.len=len;while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;return ret;}int BigNum::operator%(const int&b)const{int i,d=0;for(i=len-1;i>=0;i--){d=((d*(MAXN+1))%b+a[i])%b;}return d;}BigNum BigNum::operator^(const int&n)const{BigNum t,ret(1);if(n<0)exit(-1);if(n==0)return1;if(n==1)return*this;int m=n;while(m>1){t=*this;int i;for(i=1;i<<1<=m;i<<=1){t=t*t;}m-=i;ret=ret*t;if(m==1)ret=ret*(*this);}return ret;}bool BigNum::operator>(const BigNum&T)const{ int ln;if(len>T.len)return true;else if(len==T.len){ln=len-1;while(a[ln]==T.a[ln]&&ln>=0)ln--;if(ln>=0&&a[ln]>T.a[ln])return true;else return false;}else return false;}void BigNum::print(){int i;cout<<a[len-1];for(i=len-2;i>=0;i--){cout.width(DLEN);cout.fill('0');cout<<a[i];}}//读取整数const int ok=1;int get_val(int&ret){ret=0;char ch;while((ch=getchar())>'9'||ch<'0');do{ret=ret*10+ch-'0';}while((ch=getchar())<='9'&&ch>='0');return ok;}//带负数int get_val(int&ret){ret=0;char ch;bool neg=false;while(((ch=getchar())>'9'||ch<'0')&&ch!='-');if(ch=='-'){neg=true;while((ch=getchar())>'9'||ch<'0');}do{ret=ret*10+ch-'0';}while((ch=getchar())<='9'&&ch>='0');ret=(neg?-ret:ret);return ok;}//读取整数,可判EOF和EOLconst int eof=-1;const int eol=-2;int get_val(int&ret){ret=0;char ch;while(((ch=getchar())>'9'||ch<'0')&&ch!=EOF);if(ch==EOF)return eof;do{ret=ret*10+ch-'0';}while((ch=getchar())<='9'&&ch>='0');if(ch=='\n')return eol;return ok;}//读取浮点数int get_val(double&ret){ret=0;double base=0.1;char ch;bool dot=false,neg=false;while(((ch=getchar())>'9'||ch<'0')&&ch!='.'&&ch!='-');if(ch=='-'){neg=true;while(((ch=getchar())>'9'||ch<'0')&&ch!='.'&&ch!='-');}do{if(ch=='.'){dot=true;continue;}if(dot){ret+=(ch-'0')*base;base*=0.1;}else ret=ret*10+(ch-'0');}while(((ch=getchar())<='9'&&ch>='0')||ch=='.');ret=(neg?-ret:ret);return ok;}typedef long long LL;//LL MultiMod(LL a,LL b,LL c){//if(b)//return(a*(b&1)%c+(MultiMod(a,b>>1,c)<<1))%c; //return0;//}LL MultiMod(LL a,LL b,LL c){LL ret=0,d=a;for(;b;b>>=1,d<<=1,d%=c)if((b&1))ret=(ret+d)%c;return ret;}//128-bits integer's power with mod in O(64*LogN)LL ModPower(LL base,LL exp,LL mod){LL ret=1;for(;exp;exp>>=1,base=MultiMod(base,base,mod)) if((exp&1))ret=MultiMod(ret,base,mod);return ret;}第四章数论算法1.Greatest Common Divisor最大公约数int GCD(int x,int y){int t;while(y>0){t=x%y;x=y;y=t;}return x;}2.Prime素数判断bool is_prime(int u){if(u==0||u==1)return false;if(u==2)return true;if(u%2==0)return false;for(int i=3;i<=sqrt(u);i+=2)if(u%i==0)return false;return true;}3.Sieve Prime素数筛法const int M=1000;//M:sizebool mark[M];//true:prime numbervoid sieve_prime(){memset(mark,true,sizeof(mark));mark[0]=mark[1]=false;for(int i=2;i<=sqrt(M);i++){if(mark[i]){for(int j=i*i;j<M;j+=i)mark[j]=false;}}}4.Module Inverse模逆元//ax≡1(mod n)int Inv(int a,int n){int d,x,y;d=extended_euclid(a,n,x,y);if(d==1)return(x%n+n)%n;else return-1;//no solution}5.Extended Euclid扩展欧几里德算法//如果GCD(a,b)=d,则存在x,y,使d=ax+by//extended_euclid(a,b)=ax+byint extended_euclid(int a,int b,int&x,int&y){int d;if(b==0){x=1;y=0;return a;}d=extended_euclid(b,a%b,y,x);y-=a/b*x;return d;}6.Modular Linear Equation模线性方程(同余方程) //如果GCD(a,b)不能整除c,则ax+by=c没有整数解//ax≡b(mod n)n>0//上式等价于二元一次方程ax–ny=bvoid modular_linear_equation(int a,int b,int n){int d,x,y,x0,gcd;//可以减少扩展欧几里德溢出的可能gcd=GCD(a,n);if(b%gcd!=0){cout<<"no solution"<<endl;return;}a/=gcd;b/=gcd;n/=gcd;d=extended_euclid(a,n,x,y);if(b%d==0){x0=(x*(b/d))%n;//x0:basic solutionint ans=n;//min x=(x0%(n/d)+(n/d))%(n/d)for(int i=0;i<d;i++){ans=(x0+i*(n/d))%n;cout<<ans<<endl;}}else cout<<"no solution"<<endl;}7.Chinese Remainder Theorem中国余数定理//x≡b[i](mod w[i]),i∈[1,len-1]//前提条件w[i]>0,且w[]中任意两个数互质int chinese_remainder(int b[],int w[],int len){int i,d,x,y,m,n,ret;ret=0;n=1;for(i=0;i<len;i++)n*=w[i];for(i=0;i<len;i++){m=n/w[i];d=extended_euclid(w[i],m,x,y);ret=(ret+y*m*b[i])%n;}return(n+ret%n)%n;}//m≡r[i](mod a[i])//a[i]可以不互素//-1表示无解/*Pku2891Strange Way to Express Integers假设C≡A1(mod B1)，C≡A2(mod B2)。

目录一、数学问题 (4)1.精度计算——大数阶乘 (4)2.精度计算——乘法（大数乘小数） (4)3.精度计算——乘法（大数乘大数） (5)4.精度计算——加法 (6)5.精度计算——减法 (7)6.任意进制转换 (8)7.最大公约数、最小公倍数 (9)8.组合序列 (9)9.快速傅立叶变换（FFT） (10)10.Ronberg算法计算积分 (12)11.行列式计算 (13)12.求排列组合数 (14)13.求某一天星期几 (15)14.卡特兰(Catalan) 数列原理 (15)15.杨辉三角 (16)16.全排列 (17)17.匈牙利算法----最大匹配问题. (18)18.最佳匹配KM算法 (19)二、字符串处理 (21)1.字符串替换 (21)2.字符串查找 (22)3.字符串截取 (23)4.LCS-最大公共子串长度 (23)5.LCS-最大公共子串长度 (24)6.数字转换为字符 (25)三、计算几何 (26)1.叉乘法求任意多边形面积 (26)5.射向法判断点是否在多边形内部 (28)6.判断点是否在线段上 (29)7.判断两线段是否相交 (30)8.判断线段与直线是否相交 (31)9.点到线段最短距离 (31)10.求两直线的交点 (32)11.判断一个封闭图形是凹集还是凸集 (33)12.Graham扫描法寻找凸包 (33)13.求两条线段的交点 (35)四、数论 (36)1.x的二进制长度 (36)2.返回x的二进制表示中从低到高的第i位 (36)3.模取幂运算 (36)4.求解模线性方程 (37)5.求解模线性方程组(中国余数定理) (38)6.筛法素数产生器 (38)7.判断一个数是否素数 (39)8.求距阵最大和 (40)8.求一个数每一位相加之和 (41)10.质因数分解 (41)11.高斯消元法解线性方程组 (42)五、图论 (43)1.Prim算法求最小生成树 (43)2.Dijkstra算法求单源最短路径 (44)3.Bellman-ford算法求单源最短路径 (45)4.Floyd-Warshall算法求每对节点间最短路径 (46)5.解欧拉图 (47)六、排序/查找 (48)1.快速排序 (48)4.二分查找 (50)七、数据结构 (51)1.顺序队列 (51)2.顺序栈 (54)3.链表 (56)4.链栈 (60)5.二叉树 (63)八、高精度运算专题 (65)1.专题函数说明 (65)2.高精度数比较 (66)3.高精度数加法 (66)4.高精度数减法 (67)5.高精度乘10 (67)6.高精度乘单精度 (68)7.高精度乘高精度 (68)8.高精度除单精度 (69)9.高精度除高精度 (70)九、标准模板库的使用 (70)1.计算求和 (70)2.求数组中的最大值 (72)3. sort和qsort (73)九、其他 (74)1.运行时间计算 (74)一、数学问题1.精度计算——大数阶乘语法：int result=factorial(int n);参数：n：n 的阶乘返回值：阶乘结果的位数注意：本程序直接输出n!的结果，需要返回结果请保留long a[]需要math.h源程序：int factorial(int n){long a[10000];int i,j,l,c,m=0,w;a[0]=1;for(i=1;i<=n;i++){c=0;for(j=0;j<=m;j++){a[j]=a[j]*i+c;c=a[j]/10000;a[j]=a[j]%10000;}if(c>0) {m++;a[m]=c;}}w=m*4+log10(a[m])+1;printf("\n%ld",a[m]);for(i=m-1;i>=0;i--) printf("%4.4ld",a[i]);return w;}2.精度计算——乘法（大数乘小数）参数：c[]：被乘数，用字符串表示，位数不限t[]：结果，用字符串表示m：乘数，限定10以内返回值：null注意：需要string.h源程序：void mult(char c[],char t[],int m){int i,l,k,flag,add=0;char s[100];l=strlen(c);for (i=0;i<l;i++)s[l-i-1]=c[i]-'0';for (i=0;i<l;i++){k=s[i]*m+add;if (k>=10) {s[i]=k%10;add=k/10;flag=1;} else{s[i]=k;flag=0;add=0;}}if (flag) {l=i+1;s[i]=add;} else l=i;for (i=0;i<l;i++)t[l-1-i]=s[i]+'0';t[l]='\0';}3.精度计算——乘法（大数乘大数）语法：mult(char a[],char b[],char s[]);参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：空间复杂度为o(n^2)需要string.h源程序：void mult(char a[],char b[],char s[]){int i,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0;char result[65];alen=strlen(a);blen=strlen(b);for (i=0;i<alen;i++)for (i=alen-1;i>=0;i--){for (j=blen-1;j>=0;j--) sum=sum+res[i+blen-j-1][j];result[k]=sum%10;k=k+1;sum=sum/10;}for (i=blen-2;i>=0;i--){for (j=0;j<=i;j++) sum=sum+res[i-j][j];result[k]=sum%10;k=k+1;sum=sum/10;}if (sum!=0) {result[k]=sum;k=k+1;}for (i=0;i<k;i++) result[i]+='0';for (i=k-1;i>=0;i--) s[i]=result[k-1-i];s[k]='\0';while(1){if (strlen(s)!=strlen(a)&&s[0]=='0')strcpy(s,s+1);elsebreak;}}4.精度计算——加法语法：add(char a[],char b[],char s[]);参数：a[]：被加数，用字符串表示，位数不限b[]：加数，用字符串表示，位数不限s[]：结果，用字符串表示返回值：null注意：空间复杂度为o(n^2)需要string.h源程序：void add(char a[],char b[],char back[]){int i,j,k,up,x,y,z,l;char *c;c=(char *) malloc(l*sizeof(char));i=strlen(a)-1;j=strlen(b)-1;k=0;up=0;while(i>=0||j>=0){if(i<0) x='0'; else x=a[i];if(j<0) y='0'; else y=b[j];z=x-'0'+y-'0';if(up) z+=1;if(z>9) {up=1;z%=10;} else up=0;c[k++]=z+'0';i--;j--;}if(up) c[k++]='1';i=0;c[k]='\0';for(k-=1;k>=0;k--)back[i++]=c[k];back[i]='\0';}5.精度计算——减法语法：sub(char s1[],char s2[],char t[]);参数：s1[]：被减数，用字符串表示，位数不限s2[]：减数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：默认s1>=s2，程序未处理负数情况需要string.h源程序：void sub(char s1[],char s2[],char t[]){int i,l2,l1,k;l2=strlen(s2);l1=strlen(s1);t[l1]='\0';l1--;for (i=l2-1;i>=0;i--,l1--){if (s1[l1]-s2[i]>=0)t[l1]=s1[l1]-s2[i]+'0';{t[l1]=10+s1[l1]-s2[i]+'0';s1[l1-1]=s1[l1-1]-1;}}k=l1;while(s1[k]<0) {s1[k]+=10;s1[k-1]-=1;k--;}while(l1>=0) {t[l1]=s1[l1];l1--;}loop:if (t[0]=='0'){l1=strlen(s1);for (i=0;i<l1-1;i++) t[i]=t[i+1];t[l1-1]='\0';goto loop;}if (strlen(t)==0) {t[0]='0';t[1]='\0';}}6.任意进制转换语法：conversion(char s1[],char s2[],char t[]);参数：s[]：转换前的数字s2[]：转换后的数字d1：原进制数d2：需要转换到的进制数返回值：null注意：高于9的位数用大写'A'～'Z'表示，2～16位进制通过验证源程序：void conversion(char s[],char s2[],long d1,long d2){long i,j,t,num;char c;num=0;for (i=0;s[i]!='\0';i++){if (s[i]<='9'&&s[i]>='0') t=s[i]-'0'; else t=s[i]-'A'+10;num=num*d1+t;}i=0;while(1)t=num%d2;if (t<=9) s2[i]=t+'0'; else s2[i]=t+'A'-10;num/=d2;if (num==0) break;i++;}for (j=0;j<i/2;j++){c=s2[j];s2[j]=s[i-j];s2[i-j]=c;}s2[i+1]='\0';}7.最大公约数、最小公倍数语法：resulet=hcf(int a,int b)、result=lcd(int a,int b)参数：a：int a，求最大公约数或最小公倍数b：int b，求最大公约数或最小公倍数返回值：返回最大公约数（hcf）或最小公倍数（lcd）注意：lcd 需要连同hcf 使用源程序：int hcf(int a,int b){int r=0;while(b!=0){r=a%b;a=b;b=r;}return(a);}lcd(int u,int v,int h){return(u*v/h);}8.组合序列语法：m_of_n(int m, int n1, int m1, int* a, int head)参数：n1：组合数C的下参数m1：组合数C的上参数，递归之用*a：1～n的整数序列数组head：头指针返回值：null注意：*a需要自行产生初始调用时，m=m1、head=0调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);源程序：void m_of_n(int m, int n1, int m1, int* a, int head){int i,t;if(m1<0 || m1>n1) return;if(m1==n1){return;}m_of_n(m,n1-1,m1,a,head); // 递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;m_of_n(m,n1-1,m1-1,a,head+1); // 再次递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;}9.快速傅立叶变换（FFT）语法：kkfft(double pr[],double pi[],int n,int k,double fr[],double fi[],int l,int il);参数：pr[n]：输入的实部pi[n]：数入的虚部n，k：满足n=2^kfr[n]：输出的实部fi[n]：输出的虚部l：逻辑开关，0 FFT，1 ifFTil：逻辑开关，0 输出按实部/虚部；1 输出按模/幅角返回值：null注意：需要math.h源程序：void kkfft(pr,pi,n,k,fr,fi,l,il)int n,k,l,il;double pr[],pi[],fr[],fi[];int it,m,is,i,j,nv,l0;double p,q,s,vr,vi,poddr,poddi;for (it=0; it<=n-1; it++){m=it; is=0;for (i=0; i<=k-1; i++){j=m/2; is=2*is+(m-2*j); m=j;} fr[it]=pr[is]; fi[it]=pi[is];}pr[0]=1.0; pi[0]=0.0;p=6.283185306/(1.0*n);pr[1]=cos(p); pi[1]=-sin(p);if (l!=0) pi[1]=-pi[1];for (i=2; i<=n-1; i++){p=pr[i-1]*pr[1];q=pi[i-1]*pi[1];s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]);pr[i]=p-q; pi[i]=s-p-q;}for (it=0; it<=n-2; it=it+2){vr=fr[it]; vi=fi[it];fr[it]=vr+fr[it+1]; fi[it]=vi+fi[it+1];fr[it+1]=vr-fr[it+1]; fi[it+1]=vi-fi[it+1];}m=n/2; nv=2;for (l0=k-2; l0>=0; l0--){m=m/2; nv=2*nv;for (it=0; it<=(m-1)*nv; it=it+nv)for (j=0; j<=(nv/2)-1; j++){p=pr[m*j]*fr[it+j+nv/2];q=pi[m*j]*fi[it+j+nv/2];s=pr[m*j]+pi[m*j];s=s*(fr[it+j+nv/2]+fi[it+j+nv/2]);poddr=p-q; poddi=s-p-q;fr[it+j+nv/2]=fr[it+j]-poddr;fi[it+j+nv/2]=fi[it+j]-poddi;fr[it+j]=fr[it+j]+poddr;fi[it+j]=fi[it+j]+poddi;}}if (l!=0){fr[i]=fr[i]/(1.0*n);fi[i]=fi[i]/(1.0*n);}if (il!=0)for (i=0; i<=n-1; i++){pr[i]=sqrt(fr[i]*fr[i]+fi[i]*fi[i]);if (fabs(fr[i])<0.000001*fabs(fi[i])){if ((fi[i]*fr[i])>0) pi[i]=90.0;else pi[i]=-90.0;}elsepi[i]=atan(fi[i]/fr[i])*360.0/6.283185306;}return;}10.Ronberg算法计算积分语法：result=integral(double a,double b);参数：a：积分上限b：积分下限function f：积分函数返回值：f在（a,b）之间的积分值注意：function f(x)需要自行修改，程序中用的是sina(x)/x需要math.h默认精度要求是1e-5源程序：double f(double x){return sin(x)/x; //在这里插入被积函数}double integral(double a,double b){double h=b-a;double t1=(1+f(b))*h/2.0;int k=1;double r1,r2,s1,s2,c1,c2,t2;double s=0.0;double x=a+h/2.0;while(x<b){s+=f(x);x+=h;}t2=(t1+h*s)/2.0;s2=t2+(t2-t1)/3.0;if(k==1){k++;h/=2.0;t1=t2;s1=s2;goto loop;}c2=s2+(s2-s1)/15.0;if(k==2){c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}r2=c2+(c2-c1)/63.0;if(k==3){r1=r2; c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}while(fabs(1-r1/r2)>1e-5){r1=r2;c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}return r2;}11.行列式计算语法：result=js(int s[][],int n)参数：s[][]：行列式存储数组n：行列式维数，递归用返回值：行列式值函数中常数N为行列式维度，需自行定义源程序：int js(s,n)int s[][N],n;{int z,j,k,r,total=0;int b[N][N];/*b[N][N]用于存放，在矩阵s[N][N]中元素s[0]的余子式*/ if(n>2){for(z=0;z<n;z++){for(j=0;j<n-1;j++)for(k=0;k<n-1;k++)if(k>=z) b[j][k]=s[j+1][k+1]; elseb[j][k]=s[j+1][k];if(z%2==0) r=s[0][z]*js(b,n-1); /*递归调用*/else r=(-1)*s[0][z]*js(b,n-1);total=total+r;}}else if(n==2)total=s[0][0]*s[1][1]-s[0][1]*s[1][0];return total;}12.求排列组合数语法：result=P(long n,long m); / result=long C(long n,long m);参数：m：排列组合的上系数n：排列组合的下系数返回值：排列组合数注意：符合数学规则：m<＝n源程序：long P(long n,long m){long p=1;while(m!=0){p*=n;n--;m--;}return p;}long C(long n,long m)long i,c=1;i=m;while(i!=0){c*=n;n--;i--;}while(m!=0){c/=m;m--;}return c;}13.求某一天星期几语法：result=weekday(int N,int M,int d)参数：N,M,d：年月日，例如：2003,11,4返回值：0：星期天，1星期一……注意：需要math.h适用于1582年10月15日之后, 因为罗马教皇格里高利十三世在这一天启用新历法.源程序：int weekday(int N,int M,int d){int m,n,c,y,w;m=(M-2)%12;if (M>=3) n=N;else n=N-1;c=n/100;y=n%100;w=(int)(d+floor(13*m/5)+y+floor(y/4)+floor(c/4)-2*c)%7;while(w<0) w+=7;return w;}14.卡特兰(Catalan) 数列原理令h(1)＝1，catalan数满足递归式：h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)该递推关系的解为：h(n)=c(2n-2,n-1)/n (n=1,2,3,...)1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,1.括号化问题。

0.头文件#define _CRT_SBCURE_NO_DEPRECATE #include <set>#include <cmath>#include <queue>#include <stack>#include <vector>#include <string>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#include <functional>using namespace std;const int maxn = 110;1.const int INF = 0x3f3f3f3f;经典1.埃拉托斯特尼筛法/*|埃式筛法||快速筛选素数||16/11/05ztx|*/int prime[maxn];bool is_prime[maxn];int sieve(int n){int p = 0;for(int i = 0; i <= n; ++i)is_prime[i] = true;is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i){ // 注意数组大小是nif(is_prime[i]){prime[p++] = i;for(int j = i + i; j <= n; j += i) // 轻剪枝，j必定是i的倍数is_prime[j] = false;}}return p; // 返回素数个数}2.快速幂/*|快速幂||16/11/05ztx|*/typedef long long LL; // 视数据大小的情况而定LL powerMod(LL x, LL n, LL m){LL res = 1;while (n > 0){if (n & 1) // 判断是否为奇数，若是则true res = (res * x) % m;x = (x * x) % m;n >>= 1; // 相当于n /= 2;}..return res;}3.大数模拟大数加法/*|大数模拟加法||用string模拟||16/11/05ztx, thanks to caojiji|*/string add1(string s1, string s2){if (s1 == "" && s2 == "") return"0";if (s1 == "") return s2;if (s2 == "") return s1;string maxx = s1, minn = s2;if (s1.length() < s2.length()){maxx = s2;minn = s1;}int a = maxx.length() - 1, b = minn.length() - 1;for (int i = b; i >= 0; --i){maxx[a--] += minn[i] - '0'; // a一直在减，额外还要减个'0'}for (int i = maxx.length()-1; i > 0;--i){ if (maxx[i] > '9'){maxx[i] -= 10;//注意这个是减10maxx[i - 1]++;}}if (maxx[0] > '9'){maxx[0] -= 10;maxx = '1' + maxx;}return maxx;}大数阶乘/*|大数模拟阶乘||用数组模拟||16/12/02ztx|*/#include <iostream>#include <cstdio>using namespace std;typedef long long LL;const int maxn = 100010;int num[maxn], len;/*在mult函数中，形参部分：len每次调用函数都会发生改变，n 表示每次要乘以的数，最终返回的是结果的长度tip: 阶乘都是先求之前的(n-1)!来求n!初始化Init函数很重要，不要落下*/void Init() {num[0] = 1;}int mult(int num[], int len, int n) {LL tmp = 0;for(LL i = 0; i < len; ++i) {tmp = tmp + num[i] * n; //从最低位开始，等号左边的tmp表示当前位，右边的tmp表示进位（之前进的位）num[i] = tmp % 10; // 保存在对应的数组位置，即去掉进位后的一位数tmp = tmp / 10; // 取整用于再次循环,与n和下一个位置的乘积相加}while(tmp) { // 之后的进位处理num[len++] = tmp % 10;tmp = tmp / 10;}return len;}int main() {int n;n = 1977; // 求的阶乘数for(int i = 2; i <= n; ++i) {len = mult(num, len, i);}for(int i = len - 1; i >= 0; --i)printf("%d",num[i]); // 从最高位依次输出,数据比较多采用printf输出printf("\n");return0;}4.GCD/*|辗转相除法||欧几里得算法||求最大公约数||16/11/05ztx|*/int gcd(int big, int small){if (small > big) swap(big, small);int temp;while (small != 0){ // 辗转相除法if (small > big) swap(big, small); temp = big % small;big = small;small = temp;}return(big);}5.LCM/*|辗转相除法||欧几里得算法||求最小公倍数||16/11/05ztx|*/int gcd(int big, int small){if (small > big) swap(big, small);int temp;while (small != 0){ // 辗转相除法if (small > big) swap(big, small);temp = big % small;big = small;small = temp;}return(big);}6.全排列/*|求1到n的全排列, 有条件||16/11/05ztx, thanks to wangqiqi|*/void Pern(int list[], int k, int n) { // k表示前k 个数不动仅移动后面n-k位数if (k == n - 1) {for (int i = 0; i < n; i++) {printf("%d", list[i]);}printf("\n");}else {for (int i = k; i < n; i++) { // 输出的是满足移动条件所有全排列swap(list[k], list[i]);Pern(list, k + 1, n);swap(list[k], list[i]);}}}7.二分搜索/*|二分搜索||要求：先排序||16/11/05ztx, thanks to wangxiaocai|*/// left为最开始元素, right是末尾元素的下一个数，x是要找的数int bsearch(int *A, int left, int right, int x){int m;while (left < right){m = left + (right - left) / 2;if (A[m] >= x) right = m; else left = m + 1;// 如果要替换为 upper_bound, 改为:if(A[m] <= v) x = m+1; else y = m;}return left;}/*最后left == right如果没有找到135577找6，返回7如果找有多少的x，可以用lower_bound查找一遍，upper_bound查找一遍，下标相减C++自带的lower_bound(a,a+n,x)返回数组中最后一个x的下一个数的地址upper_bound(a,a+n,x)返回数组中第一个x的地址如果a+n内没有找到x或x的下一个地址，返回a+n的地址lower_bound(a,a+n,x）-upper_bound(a,a+n,x)返回数组中x的个数*/数据结构并查集8.并查集/*|合并节点操作||16/11/05ztx, thanks to chaixiaojun|*/int father[maxn]; // 储存i的father父节点void makeSet() {for (int i = 0; i < maxn; i++)father[i] = i;}int findRoot(int x) { // 迭代找根节点int root = x; // 根节点while (root != father[root]) { // 寻找根节点root = father[root];}while (x != root) {int tmp = father[x];father[x] = root; // 根节点赋值x = tmp;}return root;}void Union(int x, int y) { // 将x所在的集合和y所在的集合整合起来形成一个集合。

ACM模板---liang一．高精度计算： ------------------------------------------------------------ 31.高精度加法：----------------------------------------------------------- 31）C++ string类实现：----------------------------------------------- 3 2）字符数组char实现：----------------------------------------------- 32.高精度减法：----------------------------------------------------------- 41）C++ string类实现:------------------------------------------------ 4 2）字符数组char实现:------------------------------------------------ 53.高精度乘法------------------------------------------------------------- 51）字符数组char实现:------------------------------------------------ 5 2）C++ string类实现:------------------------------------------------ 64.高精度阶乘（压缩五位）------------------------------------------------- 65.高精度小数加法--------------------------------------------------------- 7 二．计算几何： -------------------------------------------------------------- 81.线段相交：------------------------------------------------------------- 82.点关于直线的对称点：点：（a,b）,直线：Ax+By+C=0------------------------- 93.求凸包 ---------------------------------------------------------------- 94.多边形面积------------------------------------------------------------ 115.皮克定理：------------------------------------------------------------ 116.三角形： ------------------------------------------------------------- 121）点和三角形的关系------------------------------------------------- 12 2）三角形各种面积算法：--------------------------------------------- 137.两圆相交面积---------------------------------------------------------- 14 三．搜索: ------------------------------------------------------------------ 151.DFS(深度优先、回溯) -------------------------------------------------- 152.BFS(广度优先) -------------------------------------------------------- 16 四．数论： ----------------------------------------------------------------- 171.最大公约数，最小公倍数：---------------------------------------------- 172.欧几里德扩展：-------------------------------------------------------- 173.大数除法求余、快速幂取余：-------------------------------------------- 174.同余： --------------------------------------------------------------- 195.筛素数 --------------------------------------------------------------- 19 五．图论 ------------------------------------------------------------------- 201.并查集： ------------------------------------------------------------- 202.最小生成树：---------------------------------------------------------- 201） Prim算法------------------------------------------------------- 21 2）克鲁斯卡尔算法--------------------------------------------------- 223.最短路径: ------------------------------------------------------------ 231）最短路径dijkstra算法-------------------------------------------- 23 1）Floyd算法（最短路径）------------------------------------------- 284.最大匹配 ------------------------------------------------------------- 295.最大流 --------------------------------------------------------------- 31 六．数据结构 --------------------------------------------------------------- 331.RMQ ------------------------------------------------------------------ 332.树状数组 ------------------------------------------------------------- 351)一维树状数组------------------------------------------------------ 352)二维树状数组------------------------------------------------------ 37 七．各种处理函数 ----------------------------------------------------------- 381.字符串 --------------------------------------------------------------- 381）字符串分解函数strtok-------------------------------------------- 38 八．动态规划 --------------------------------------------------------------- 391.最长公共子序列-------------------------------------------------------- 392.单调递增（递减）最长子序列-------------------------------------------- 403.整数规划：------------------------------------------------------------ 42一．高精度计算：1.高精度加法：1）C++ string类实现：#include<string>void sum(string &a,string b) // a=a+b{ int i,j,k,c,s;while (a.length()>b.length()) b='0'+b;// a,b处理成一样长 while (b.length()>a.length()) a='0'+a;c=0;for (i=a.length()-1; i>=0; i--){ s=a[i]-48+b[i]-48+c;if ( s>9 ) { s=s%10; c=1;} else c=0;a[i]=48+s;}if ( c>0 ) a='1'+a;}2）字符数组char实现：#include<string.h>void add(char a[],char b[])//a=a+b{int i,j,k,sum=0;k=strlen(a)>strlen(b)?strlen(a):strlen(b);a[k+1]=0;for(i=strlen(a)-1,j=strlen(b)-1;i>=0||j>=0;i--,j--,k--){ if(i>=0) sum+=a[i]-'0'; if(j>=0) sum+=b[j]-'0';a[k]=sum%10+'0'; sum/=10;}if(sum) a[0]=sum+'0';else strcpy(a,&a[1]);}2.高精度减法：1）C++ string类实现:#include<string>void f(string &a,string b){int i,j,sum=0;for(i=a.length()-1,j=b.length()-1;i>=0||j>=0;i--,j--){sum+=a[i]-'0'; if(j>=0) sum-=b[j]-'0';if(sum<0) {a[i]=sum+10+'0';sum=-1;}else {a[i]=sum+'0';sum=0;}}if(a[0]=='0') a=&a[1];for(i=0;a[i]=='0'&&i<a.length();i++) ;if(i==a.length()) a="0";}2）字符数组char实现:#include <string.h>void jian(char a[],char b[])//a-=b{int i,j,sum=0;for(i=strlen(a)-1,j=strlen(b)-1;i>=0||j>=0;i--,j--){sum+=a[i]-'0'; if(j>=0) sum-=b[j]-'0';if(sum<0) {a[i]=sum+10+'0';sum=-1;}else {a[i]=sum+'0';sum=0;}}if(a[0]=='0') strcpy(a,&a[1]);for(i=0;a[i]=='0';i++) ;if(i==strlen(a)) strcpy(a,"0");}3.高精度乘法1）字符数组char实现:#include <string.h>void chen(char a[],char b[])//a=a*b{ int i,j,k,l,sum,c[410]={0};l=strlen(a)+strlen(b);for(i=strlen(b)-1;i>=0;i--)for(j=strlen(a)-1,k=i+j+1;j>=0;j--,k--){ sum=(b[i]-'0')*(a[j]-'0')+c[k];c[k]=sum%10;c[k-1]+=sum/10;}for(i=c[0]?0:1,j=0;i<l;i++)a[j++]=(c[i]+'0'); a[j]=0;}2）C++ string类实现:#include<string>void chenn(string &a,string b)//a=a*b{ int i,j,k,l,sum,c[410]={0};l=a.length()+b.length();for(i=b.length()-1;i>=0;i--)for(j=a.length()-1,k=i+j+1;j>=0;j--,k--){ sum=(b[i]-'0')*(a[j]-'0')+c[k];c[k]=sum%10;c[k-1]+=sum/10;}i=c[0]?0:1;while(a.length()<l-i) a=a+'0';for(j=0;i<l;i++)a[j++]=(c[i]+'0');}4.高精度阶乘（压缩五位）#include<iostream>#include<iomanip>using namespace std;int a[10000];int main(void){int i,n,w,up,j;while(cin>>n){for(w=a[0]=i=1;i<=n;i++){ for(j=0,up=0;j<w;j++){a[j]=i*a[j]+up;up=a[j]/100000;a[j]%=100000;}if(up) a[w++]=up;}cout<<a[w-1];for(i=w-2;i>=0;i--)cout<<setfill('0')<<setw(5)<<a[i]; cout<<endl;}}5.高精度小数加法#include<cstring>#include<algorithm>void quw0(char a[]) //去除尾部多余的零 eg: 3.5+3.5=7.0变成 7 { int i;for(i=0;i<strlen(a);i++) //判断有没有小数点if(a[i]=='.') break;if(i!=strlen(a)){i=strlen(a)-1;while(a[i]=='0') {a[i]=0;;i--;}if(a[i]=='.') a[i]=0;;}}void add(char *a,char *b)//a=a+b{int i=0,j=0,la=strlen(a),lb=strlen(b),sum=0;while((a[i]-'.')&&i<la) i++;while((b[j]-'.')&&j<lb) j++;if(i==la) {a[i]='.';la++;};if(j==lb) {b[j]='.';lb++;};while(la-i>lb-j) {b[lb]='0';lb++;}while(lb-j>la-i) {a[la]='0';la++;}if(la<lb) { swap(a,b); swap(la,lb); }a[la+1]=0;b[lb]=0;for(i=la-1,j=lb-1;i>=0;i--,j--){ if(a[i]=='.') {a[i+1]='.';continue;}sum+=a[i]-'0'; if(j>=0) sum+=b[j]-'0';a[i+1]=sum%10+'0'; sum/=10;}if(sum) a[0]=sum+'0';else strcpy(a,&a[1]);quw0(a);//根据题目需要是否保留尾0}二．计算几何：1.线段相交：int xj(point x1,point x2,point x3,point x4)//相交为1,不交为0{if(min(x1.x,x2.x)>max(x3.x,x4.x)||min(x1.y,x2.y)>max(x3.y,x4.y)||min(x3.x,x4.x)>max(x1.x,x2.x)||min(x3.y,x4.y)>max(x1.y,x2.y) )return 0;//不交：矩形排斥实验，最小的>最大的肯定不交int a,b,c,d;a=(x1.x-x2.x)*(x3.y-x1.y)-(x1.y-x2.y)*(x3.x-x1.x);//跨立实验 b=(x1.x-x2.x)*(x4.y-x1.y)-(x1.y-x2.y)*(x4.x-x1.x);c=(x3.x-x4.x)*(x1.y-x3.y)-(x3.y-x4.y)*(x1.x-x3.x);d=(x3.x-x4.x)*(x2.y-x3.y)-(x3.y-x4.y)*(x2.x-x3.x);return a*b<=0&&c*d<=0;}2.点关于直线的对称点：点：（a,b）,直线：Ax+By+C=0#include <stdio.h>int main(){int n;float a,b,A,B,C,a1,b1;scanf("%d\n",&n);while(n--){ scanf("%f %f %f %f %f",&a,&b,&A,&B,&C);int a1=int (a-2*A*(A*a+B*b+C)/(A*A+B*B));int b1=int (b-2*B*(A*a+B*b+C)/(A*A+B*B));printf("%d %d\n",a1,b1);}}3.求凸包//根据题目改动数据类型，数组大小，排序方式#include <algorithm>#define eps 1e-8struct point{int x,y;};point pnt[100003],res[100005];bool operator<( point A,point B )//按y排也可，具体看题目要求{ return A.x < B.x || (A.x == B.x && A.y < B.y); }double mult(point p0,point p1,point p2){ r eturn (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); }//数组下标从0开始，n是点的个数，选中的点在保存在res数组中，个数是topint graham(point pnt[], int n, point res[])//选中的点在保存在res数组中，个数是top{ int i, len, k = 0, top = 1;sort(pnt, pnt + n); //用cmp可能超时，原因未知if (n == 0) return 0; res[0] = pnt[0];if (n == 1) return 1; res[1] = pnt[1];if (n == 2) return 2; res[2] = pnt[2];for (i = 2; i < n; i++){ while (top && mult(pnt[i], res[top], res[top-1])<=eps) top--;res[++top] = pnt[i];}len = top; res[++top] = pnt[n - 2];for (i = n - 3; i >= 0; i--){ while (top!=len && mult(pnt[i], res[top], res[top-1])<=eps) top--;res[++top] = pnt[i];}return top; // 返回凸包中点的个数}4.多边形面积//点必须是顺时针给出或逆时针给出才可用此法//使用时注意数据类型，和数据大小struct point{int x,y;}a[105];int duo(point a[],int n) //点在数组 a[]中，个数是n{ int i,s=0;for(i=1;i<=n;i++)s+=(a[i-1].x*a[i%n].y-a[i-1].y*a[i%n].x);if(s<0) s=-s;return s;// if(s%2) cout<<s/2<<".5"<<endl; 若为longl long 类型，不要用double// else cout<<s/2<<".0"<<endl;}5.皮克定理：//S=a+b÷2-1//(其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积)#include<cmath>struct point{int x,y;};int gcd(int m,int n){if(n==0) return m;return gcd(n,m%n);}int bian(point a[],int n)//算出点A和点B组成的线段上的点{ int s=0,i;for(i=1;i<=n;i++)s+=gcd(abs(a[i-1].x-a[i%n].x),abs(a[i-1].y-a[i%n].y));return s;}int duo(point a[],int n)//求n边形的面积,注意ans未除2；{int i,s=0;for(i=1;i<=n;i++)s+=(a[i-1].x*a[i%n].y-a[i-1].y*a[i%n].x);if(s<0) s=-s;return s;}6.三角形：1）点和三角形的关系//注意数据类型#include <cmath>struct point{int x,y;};bool operator ==(point A,point B){return A.x==B.x&&A.y==B.y;} int area(point A,point B,point C)//三角形面积，未除2{int s=abs((B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x));return s;}int pan3(point a[],point p) //若点在三角形内（不含边界），返回1；{int sa,sb,sc,s;s=area(a[0],a[1],a[2]);sa=area(a[0],a[1],p);sb=area(a[0],a[2],p);sc=area(a[1],a[2],p);if(sa&&sb&&sc&&s==sa+sb+sc) return 1;if((!sa||!sb||!sc)&&s==sa+sb+sc){if(p==a[0]||p==a[1]||p==a[2]) return 4;//若点在三角形顶点上，返回4。

Zhejiang UniversityICPC TeamRoutine Libraryby WishingBone (Dec. 2002)1. 几何1.1. 注意1.2. 几何公式1.3. 多边形1.4. 多边形切割1.5. 浮点函数1.6. 面积1.7. 球面1.8. 三角形1.9. 三维几何1.10. 凸包1.11. 网格1.13. 整数函数2. 组合2.1 组合公式2.2 排列组合生成2.3 生成gray码2.4 置换(polya)2.5 字典序全排列2.6 字典序组合3. 结构3.1 并查集3.2 堆3.3 线段树3.4 子段和3.5 子阵和4. 数论4.1 阶乘最后非0位4.2 模线性方程组4.4 欧拉函数5. 数值计算5.1 定积分计算(Romberg)5.2 多项式求根(牛顿法)5.3 周期性方程(追赶法)6. 图论—NP搜索6.1 最大团6.2 最大团(n<64)(faster)7. 图论—连通性7.1 无向图关键点(dfs邻接阵)7.2 无向图关键边(dfs邻接阵)7.3 无向图的块(bfs邻接阵)7.4 无向图连通分支(dfs/bfs邻接阵)7.5 有向图强连通分支(dfs/bfs邻接阵)7.6 有向图最小点基(邻接阵)8. 图论—匹配8.1 二分图最大匹配(hungary邻接表)8.2 二分图最大匹配(hungary邻接阵)8.3 二分图最大匹配(hungary正向表)8.4二分图最佳匹配(kuhn_munkras邻接阵)8.5 一般图匹配(邻接表)8.6 一般图匹配(邻接阵)8.7 一般图匹配(正向表)9. 图论—网络流9.1 最大流(邻接阵)9.2 上下界最大流(邻接阵)9.3 上下界最小流(邻接阵)9.4 最大流无流量(邻接阵)9.5 最小费用最大流(邻接阵)10. 图论—应用10.1 欧拉回路(邻接阵)10.2 树的前序表转化10.3 树的优化算法10.4 拓扑排序(邻接阵)10.5 最佳边割集10.6 最佳点割集10.7 最小边割集10.8 最小点割集10.9 最小路径覆盖11. 图论—支撑树11.1 最小生成树(kruskal邻接表)11.2 最小生成树(kruskal正向表)11.3 最小生成树(prim+binary_heap邻接表)11.4 最小生成树(prim+binary_heap正向表)11.5 最小生成树(prim+mapped_heap邻接表)11.6 最小生成树(prim+mapped_heap正向表)11.7 最小生成树(prim邻接阵)11.8 最小树形图(邻接阵)12. 图论—最短路径12.1 最短路径(单源bellman_ford邻接阵)12.2 最短路径(单源dijkstra+bfs邻接表)12.3 最短路径(单源dijkstra+bfs正向表)12.4 最短路径(单源dijkstra+binary_heap邻接表)12.5 最短路径(单源dijkstra+binary_heap正向表)12.6 最短路径(单源dijkstra+mapped_heap邻接表)12.7 最短路径(单源dijkstra+mapped_heap正向表)12.8 最短路径(单源dijkstra邻接阵)12.9 最短路径(多源floyd_warshall邻接阵)13. 应用13.1 Joseph问题13.2 N皇后构造解13.3 布尔母函数13.4 第k元素13.5 幻方构造13.6 模式匹配(kmp)13.7 逆序对数13.8 字符串最小表示13.9 最长公共单调子序列13.10 最长子序列13.11 最大子串匹配13.12 最大子段和13.13 最大子阵和其它14.1 大数(只能处理正数)14.2 分数14.3 矩阵14.4 线性方程组14.5 线性相关14.6 日期1.几何1.1. 注意1. 注意舍入方式(0.5的舍入方向);防止输出-0.2. 几何题注意多测试不对称数据.3. 整数几何注意xmult和dmult是否会出界;符点几何注意eps的使用.4. 避免使用斜率;注意除数是否会为0.5. 公式一定要化简后再代入.6. 判断同一个2*PI域内两角度差应该是abs(a1-a2)<beta||abs(a1-a2)>pi+pi-beta;相等应该是abs(a1-a2)<eps||abs(a1-a2)>pi+pi-eps;7. 需要的话尽量使用atan2,注意:atan2(0,0)=0,atan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.8. cross product = |u|*|v|*sin(a)dot product = |u|*|v|*cos(a)9. (P1-P0)x(P2-P0)结果的意义:正: <P0,P1>在<P0,P2>顺时针(0,pi)内负: <P0,P1>在<P0,P2>逆时针(0,pi)内0 : <P0,P1>,<P0,P2>共线,夹角为0或pi10. 误差限缺省使用1e-8!1.2. 几何公式三角形:1. 半周长 P=(a+b+c)/22. 面积 S=aHa/2=absin(C)/2=sqrt(P(P-a)(P-b)(P-c))3. 中线 Ma=sqrt(2(b^2+c^2)-a^2)/2=sqrt(b^2+c^2+2bccos(A))/24. 角平分线 Ta=sqrt(bc((b+c)^2-a^2))/(b+c)=2bccos(A/2)/(b+c)5. 高线 Ha=bsin(C)=csin(B)=sqrt(b^2-((a^2+b^2-c^2)/(2a))^2)6. 内切圆半径 r=S/P=asin(B/2)sin(C/2)/sin((B+C)/2)=4Rsin(A/2)sin(B/2)sin(C/2)=sqrt((P-a)(P-b)(P-c)/P)=Ptan(A/2)tan(B/2)tan(C/2)7. 外接圆半径 R=abc/(4S)=a/(2sin(A))=b/(2sin(B))=c/(2sin(C))四边形:D1,D2为对角线,M对角线中点连线,A为对角线夹角1. a^2+b^2+c^2+d^2=D1^2+D2^2+4M^22. S=D1D2sin(A)/2(以下对圆的内接四边形)3. ac+bd=D1D24. S=sqrt((P-a)(P-b)(P-c)(P-d)),P为半周长正n边形:R为外接圆半径,r为内切圆半径1. 中心角 A=2PI/n2. 内角 C=(n-2)PI/n3. 边长 a=2sqrt(R^2-r^2)=2Rsin(A/2)=2rtan(A/2)4. 面积 S=nar/2=nr^2tan(A/2)=nR^2sin(A)/2=na^2/(4tan(A/2))圆:1. 弧长 l=rA2. 弦长 a=2sqrt(2hr-h^2)=2rsin(A/2)3. 弓形高 h=r-sqrt(r^2-a^2/4)=r(1-cos(A/2))=atan(A/4)/24. 扇形面积 S1=rl/2=r^2A/25. 弓形面积 S2=(rl-a(r-h))/2=r^2(A-sin(A))/2棱柱:1. 体积 V=Ah,A为底面积,h为高2. 侧面积 S=lp,l为棱长,p为直截面周长3. 全面积 T=S+2A棱锥:1. 体积 V=Ah/3,A为底面积,h为高(以下对正棱锥)2. 侧面积 S=lp/2,l为斜高,p为底面周长3. 全面积 T=S+A棱台:1. 体积 V=(A1+A2+sqrt(A1A2))h/3,A1.A2为上下底面积,h为高(以下为正棱台)2. 侧面积 S=(p1+p2)l/2,p1.p2为上下底面周长,l为斜高3. 全面积 T=S+A1+A2圆柱:1. 侧面积 S=2PIrh2. 全面积 T=2PIr(h+r)3. 体积 V=PIr^2h圆锥:1. 母线 l=sqrt(h^2+r^2)2. 侧面积 S=PIrl3. 全面积 T=PIr(l+r)4. 体积 V=PIr^2h/3圆台:1. 母线 l=sqrt(h^2+(r1-r2)^2)2. 侧面积 S=PI(r1+r2)l3. 全面积 T=PIr1(l+r1)+PIr2(l+r2)4. 体积 V=PI(r1^2+r2^2+r1r2)h/3球:1. 全面积 T=4PIr^22. 体积 V=4PIr^3/3球台:1. 侧面积 S=2PIrh2. 全面积 T=PI(2rh+r1^2+r2^2)3. 体积 V=PIh(3(r1^2+r2^2)+h^2)/6球扇形:1. 全面积 T=PIr(2h+r0),h为球冠高,r0为球冠底面半径2. 体积 V=2PIr^2h/31.3. 多边形#include <stdlib.h>#include <math.h>#define MAXN 1000#define offset 10000#define eps 1e-8#define zero(x) (((x)>0?(x):-(x))<eps)#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))struct point{double x,y;};struct line{point a,b;};double xmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); //判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线int is_convex(int n,point* p){int i,s[3]={1,1,1};for (i=0;i<n&&s[1]|s[2];i++)s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;return s[1]|s[2];//判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线int is_convex_v2(int n,point* p){int i,s[3]={1,1,1};for (i=0;i<n&&s[0]&&s[1]|s[2];i++)s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;return s[0]&&s[1]|s[2];//判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出int inside_convex(point q,int n,point* p){int i,s[3]={1,1,1};for (i=0;i<n&&s[1]|s[2];i++)s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;return s[1]|s[2];//判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0 int inside_convex_v2(point q,int n,point* p){int i,s[3]={1,1,1};for (i=0;i<n&&s[0]&&s[1]|s[2];i++)s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;return s[0]&&s[1]|s[2];//判点在任意多边形内,顶点按顺时针或逆时针给出//on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限int inside_polygon(point q,int n,point* p,int on_edge=1){ point q2;int i=0,count;while (i<n)for(count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i++) if(zero(xmult(q,p[i],p[(i+1)%n]))&&(p[i].x-q.x)*(p[(i+1)%n].x-q.x )<eps&&(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps)return on_edge;else if (zero(xmult(q,q2,p[i])))break;else if (xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&xmult(p[i],q,p[( i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps)count++;return count&1;inline int opposite_side(point p1,point p2,point l1,point l2){ return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;inline int dot_online_in(point p,point l1,point l2){ returnzero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2 .y-p.y)<eps;//判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1 int inside_polygon(point l1,point l2,int n,point* p){ point t[MAXN],tt;int i,j,k=0;if (!inside_polygon(l1,n,p)||!inside_polygon(l2,n,p)) return 0;for (i=0;i<n;i++)if(opposite_side(l1,l2,p[i],p[(i+1)%n])&&opposite_side(p[i],p[(i+ 1)%n],l1,l2))return 0;else if (dot_online_in(l1,p[i],p[(i+1)%n]))t[k++]=l1;else if (dot_online_in(l2,p[i],p[(i+1)%n]))t[k++]=l2;else if (dot_online_in(p[i],l1,l2))t[k++]=p[i];for (i=0;i<k;i++)for (j=i+1;j<k;j++){tt.x=(t[i].x+t[j].x)/2;tt.y=(t[i].y+t[j].y)/2;if (!inside_polygon(tt,n,p))return 0;return 1;point intersection(line u,line v){point ret=u.a;doublet=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));ret.x+=(u.b.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;return ret;point barycenter(point a,point b,point c){ line u,v;u.a.x=(a.x+b.x)/2;u.a.y=(a.y+b.y)/2;u.b=c;v.a.x=(a.x+c.x)/2;v.a.y=(a.y+c.y)/2;v.b=b;return intersection(u,v);//多边形重心point barycenter(int n,point* p){point ret,t;double t1=0,t2;int i;ret.x=ret.y=0;for (i=1;i<n-1;i++)if (fabs(t2=xmult(p[0],p[i],p[i+1]))>eps){ t=barycenter(p[0],p[i],p[i+1]);ret.x+=t.x*t2;ret.y+=t.y*t2;t1+=t2;if (fabs(t1)>eps)ret.x/=t1,ret.y/=t1;return ret;1.4. 多边形切割//多边形切割//可用于半平面交#define MAXN 100#define eps 1e-8#define zero(x) (((x)>0?(x):-(x))<eps)struct point{double x,y;};double xmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);int same_side(point p1,point p2,point l1,point l2){return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;point intersection(point u1,point u2,point v1,point v2){ point ret=u1;double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)) /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));ret.x+=(u2.x-u1.x)*t;ret.y+=(u2.y-u1.y)*t;return ret;//将多边形沿l1,l2确定的直线切割在side侧切割,保证l1,l2,side不共线void polygon_cut(int& n,point* p,point l1,point l2,point side){ point pp[100];int m=0,i;for (i=0;i<n;i++){if (same_side(p[i],side,l1,l2))pp[m++]=p[i];if(!same_side(p[i],p[(i+1)%n],l1,l2)&&!(zero(xmult(p[i],l1,l2))&& zero(xmult(p[(i+1)%n],l1,l2))))pp[m++]=intersection(p[i],p[(i+1)%n],l1,l2);for (n=i=0;i<m;i++)if(!i||!zero(pp[i].x-pp[i-1].x)||!zero(pp[i].y-pp[i-1].y))p[n++]=pp[i];if (zero(p[n-1].x-p[0].x)&&zero(p[n-1].y-p[0].y))n--;if (n<3)n=0;1.5. 浮点函数//浮点几何函数库#include <math.h>#define eps 1e-8#define zero(x) (((x)>0?(x):-(x))<eps)struct point{double x,y;};struct line{point a,b;};//计算cross product (P1-P0)x(P2-P0)double xmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); double xmult(double x1,double y1,double x2,double y2,double x0,double y0){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);//计算dot product (P1-P0).(P2-P0)double dmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y); double dmult(double x1,double y1,double x2,double y2,double x0,double y0){return (x1-x0)*(x2-x0)+(y1-y0)*(y2-y0);//两点距离double distance(point p1,point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); double distance(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//判三点共线int dots_inline(point p1,point p2,point p3){return zero(xmult(p1,p2,p3));int dots_inline(double x1,double y1,double x2,double y2,double x3,double y3){return zero(xmult(x1,y1,x2,y2,x3,y3));//判点是否在线段上,包括端点int dot_online_in(point p,line l){returnzero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y )*(l.b.y-p.y)<eps;int dot_online_in(point p,point l1,point l2){returnzero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2 .y-p.y)<eps;int dot_online_in(double x,double y,double x1,double y1,double x2,double y2){returnzero(xmult(x,y,x1,y1,x2,y2))&&(x1-x)*(x2-x)<eps&&(y1-y)*(y2-y)< eps;//判点是否在线段上,不包括端点int dot_online_ex(point p,line l){returndot_online_in(p,l)&&(!zero(p.x-l.a.x)||!zero(p.y-l.a.y))&&(!zer o(p.x-l.b.x)||!zero(p.y-l.b.y));int dot_online_ex(point p,point l1,point l2){returndot_online_in(p,l1,l2)&&(!zero(p.x-l1.x)||!zero(p.y-l1.y))&&(!z ero(p.x-l2.x)||!zero(p.y-l2.y));int dot_online_ex(double x,double y,double x1,double y1,double x2,double y2){returndot_online_in(x,y,x1,y1,x2,y2)&&(!zero(x-x1)||!zero(y-y1))&&(!z ero(x-x2)||!zero(y-y2));//判两点在线段同侧,点在线段上返回0int same_side(point p1,point p2,line l){return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;int same_side(point p1,point p2,point l1,point l2){return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;//判两点在线段异侧,点在线段上返回0int opposite_side(point p1,point p2,line l){return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)<-eps;int opposite_side(point p1,point p2,point l1,point l2){ return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;//判两直线平行int parallel(line u,line v){returnzero((u.a.x-u.b.x)*(v.a.y-v.b.y)-(v.a.x-v.b.x)*(u.a.y-u.b.y)); int parallel(point u1,point u2,point v1,point v2){return zero((u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y)); //判两直线垂直int perpendicular(line u,line v){returnzero((u.a.x-u.b.x)*(v.a.x-v.b.x)+(u.a.y-u.b.y)*(v.a.y-v.b.y)); int perpendicular(point u1,point u2,point v1,point v2){ return zero((u1.x-u2.x)*(v1.x-v2.x)+(u1.y-u2.y)*(v1.y-v2.y)); //判两线段相交,包括端点和部分重合int intersect_in(line u,line v){if (!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b)) return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);returndot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u )||dot_online_in(v.b,u);int intersect_in(point u1,point u2,point v1,point v2){ if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);returndot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in (v1,u1,u2)||dot_online_in(v2,u1,u2);//判两线段相交,不包括端点和部分重合int intersect_ex(line u,line v){return opposite_side(u.a,u.b,v)&&opposite_side(v.a,v.b,u); int intersect_ex(point u1,point u2,point v1,point v2){ returnopposite_side(u1,u2,v1,v2)&&opposite_side(v1,v2,u1,u2);//计算两直线交点,注意事先判断直线是否平行!//线段交点请另外判线段相交(同时还是要判断是否平行!)point intersection(line u,line v){point ret=u.a;doublet=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));ret.x+=(u.b.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;return ret;point intersection(point u1,point u2,point v1,point v2){ point ret=u1;double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)) /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));ret.x+=(u2.x-u1.x)*t;ret.y+=(u2.y-u1.y)*t;return ret;//点到直线上的最近点point ptoline(point p,line l){point t=p;t.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;return intersection(p,t,l.a,l.b);point ptoline(point p,point l1,point l2){point t=p;t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;return intersection(p,t,l1,l2);//点到直线距离double disptoline(point p,line l){return fabs(xmult(p,l.a,l.b))/distance(l.a,l.b);double disptoline(point p,point l1,point l2){return fabs(xmult(p,l1,l2))/distance(l1,l2);double disptoline(double x,double y,double x1,double y1,double x2,double y2){return fabs(xmult(x,y,x1,y1,x2,y2))/distance(x1,y1,x2,y2);//点到线段上的最近点point ptoseg(point p,line l){point t=p;t.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;if (xmult(l.a,t,p)*xmult(l.b,t,p)>eps)return distance(p,l.a)<distance(p,l.b)?l.a:l.b;return intersection(p,t,l.a,l.b);point ptoseg(point p,point l1,point l2){point t=p;t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;if (xmult(l1,t,p)*xmult(l2,t,p)>eps)return distance(p,l1)<distance(p,l2)?l1:l2;return intersection(p,t,l1,l2);//点到线段距离double disptoseg(point p,line l){point t=p;t.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;if (xmult(l.a,t,p)*xmult(l.b,t,p)>eps)returndistance(p,l.a)<distance(p,l.b)?distance(p,l.a):distance(p,l.b) ;return fabs(xmult(p,l.a,l.b))/distance(l.a,l.b);double disptoseg(point p,point l1,point l2){point t=p;t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;if (xmult(l1,t,p)*xmult(l2,t,p)>eps)returndistance(p,l1)<distance(p,l2)?distance(p,l1):distance(p,l2);return fabs(xmult(p,l1,l2))/distance(l1,l2);//矢量V以P为顶点逆时针旋转angle并放大scale倍point rotate(point v,point p,double angle,double scale){ point ret=p;v.x-=p.x,v.y-=p.y;p.x=scale*cos(angle);p.y=scale*sin(angle);ret.x+=v.x*p.x-v.y*p.y;ret.y+=v.x*p.y+v.y*p.x;return ret;1.6. 面积#include <math.h>struct point{double x,y;};//计算cross product (P1-P0)x(P2-P0)double xmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); double xmult(double x1,double y1,double x2,double y2,double x0,double y0){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);//计算三角形面积,输入三顶点double area_triangle(point p1,point p2,point p3){return fabs(xmult(p1,p2,p3))/2;double area_triangle(double x1,double y1,double x2,double y2,double x3,double y3){return fabs(xmult(x1,y1,x2,y2,x3,y3))/2;//计算三角形面积,输入三边长double area_triangle(double a,double b,double c){double s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c));//计算多边形面积,顶点按顺时针或逆时针给出double area_polygon(int n,point* p){double s1=0,s2=0;int i;for (i=0;i<n;i++)s1+=p[(i+1)%n].y*p[i].x,s2+=p[(i+1)%n].y*p[(i+2)%n].x;return fabs(s1-s2)/2;1.7. 球面#include <math.h>const double pi=acos(-1);//计算圆心角lat表示纬度,-90<=w<=90,lng表示经度//返回两点所在大圆劣弧对应圆心角,0<=angle<=pidouble angle(double lng1,double lat1,double lng2,double lat2){ double dlng=fabs(lng1-lng2)*pi/180;while (dlng>=pi+pi)dlng-=pi+pi;if (dlng>pi)dlng=pi+pi-dlng;lat1*=pi/180,lat2*=pi/180;returnacos(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2));//计算距离,r为球半径double line_dist(double r,double lng1,double lat1,double lng2,double lat2){double dlng=fabs(lng1-lng2)*pi/180;while (dlng>=pi+pi)dlng-=pi+pi;if (dlng>pi)dlng=pi+pi-dlng;lat1*=pi/180,lat2*=pi/180;returnr*sqrt(2-2*(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2))) ;//计算球面距离,r为球半径inline double sphere_dist(double r,double lng1,double lat1,double lng2,double lat2){return r*angle(lng1,lat1,lng2,lat2);1.8. 三角形#include <math.h>struct point{double x,y;};struct line{point a,b;};double distance(point p1,point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); point intersection(line u,line v){point ret=u.a;doublet=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));ret.x+=(u.b.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;return ret;//外心point circumcenter(point a,point b,point c){ line u,v;u.a.x=(a.x+b.x)/2;u.a.y=(a.y+b.y)/2;u.b.x=u.a.x-a.y+b.y;u.b.y=u.a.y+a.x-b.x;v.a.x=(a.x+c.x)/2;v.a.y=(a.y+c.y)/2;v.b.x=v.a.x-a.y+c.y;v.b.y=v.a.y+a.x-c.x;return intersection(u,v);//内心point incenter(point a,point b,point c){ line u,v;double m,n;u.a=a;m=atan2(b.y-a.y,b.x-a.x);n=atan2(c.y-a.y,c.x-a.x);u.b.x=u.a.x+cos((m+n)/2);u.b.y=u.a.y+sin((m+n)/2);v.a=b;m=atan2(a.y-b.y,a.x-b.x);n=atan2(c.y-b.y,c.x-b.x);v.b.x=v.a.x+cos((m+n)/2);v.b.y=v.a.y+sin((m+n)/2);return intersection(u,v);//垂心point perpencenter(point a,point b,point c){ line u,v;u.a=c;u.b.x=u.a.x-a.y+b.y;u.b.y=u.a.y+a.x-b.x;v.a=b;v.b.x=v.a.x-a.y+c.y;v.b.y=v.a.y+a.x-c.x;return intersection(u,v);//重心//到三角形三顶点距离的平方和最小的点//三角形内到三边距离之积最大的点point barycenter(point a,point b,point c){ line u,v;u.a.x=(a.x+b.x)/2;u.a.y=(a.y+b.y)/2;u.b=c;v.a.x=(a.x+c.x)/2;v.a.y=(a.y+c.y)/2;v.b=b;return intersection(u,v);//费马点//到三角形三顶点距离之和最小的点point fermentpoint(point a,point b,point c){point u,v;doublestep=fabs(a.x)+fabs(a.y)+fabs(b.x)+fabs(b.y)+fabs(c.x)+fabs(c.y );int i,j,k;u.x=(a.x+b.x+c.x)/3;u.y=(a.y+b.y+c.y)/3;while (step>1e-10)for (k=0;k<10;step/=2,k++)for (i=-1;i<=1;i++)for (j=-1;j<=1;j++){v.x=u.x+step*i;v.y=u.y+step*j;if(distance(u,a)+distance(u,b)+distance(u,c)>distance(v,a)+distan ce(v,b)+distance(v,c))u=v;return u;1.9. 三维几何//三维几何函数库#include <math.h>#define eps 1e-8#define zero(x) (((x)>0?(x):-(x))<eps)struct point3{double x,y,z;};struct line3{point3 a,b;};struct plane3{point3 a,b,c;};//计算cross product U x Vpoint3 xmult(point3 u,point3 v){point3 ret;ret.x=u.y*v.z-v.y*u.z;ret.y=u.z*v.x-u.x*v.z;ret.z=u.x*v.y-u.y*v.x;return ret;//计算dot product U . Vdouble dmult(point3 u,point3 v){return u.x*v.x+u.y*v.y+u.z*v.z;//矢量差 U - Vpoint3 subt(point3 u,point3 v){point3 ret;ret.x=u.x-v.x;ret.y=u.y-v.y;ret.z=u.z-v.z;return ret;//取平面法向量point3 pvec(plane3 s){return xmult(subt(s.a,s.b),subt(s.b,s.c));point3 pvec(point3 s1,point3 s2,point3 s3){return xmult(subt(s1,s2),subt(s2,s3));//两点距离,单参数取向量大小double distance(point3 p1,point3 p2){returnsqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z )*(p1.z-p2.z));//向量大小double vlen(point3 p){return sqrt(p.x*p.x+p.y*p.y+p.z*p.z);//判三点共线int dots_inline(point3 p1,point3 p2,point3 p3){return vlen(xmult(subt(p1,p2),subt(p2,p3)))<eps;//判四点共面int dots_onplane(point3 a,point3 b,point3 c,point3 d){ return zero(dmult(pvec(a,b,c),subt(d,a)));//判点是否在线段上,包括端点和共线int dot_online_in(point3 p,line3 l){returnzero(vlen(xmult(subt(p,l.a),subt(p,l.b))))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps&&(l.a.z-p.z)*(l.b.z-p.z)<eps; int dot_online_in(point3 p,point3 l1,point3 l2){returnzero(vlen(xmult(subt(p,l1),subt(p,l2))))&&(l1.x-p.x)*(l2.x-p.x) <eps&&(l1.y-p.y)*(l2.y-p.y)<eps&&(l1.z-p.z)*(l2.z-p.z)<eps;//判点是否在线段上,不包括端点int dot_online_ex(point3 p,line3 l){returndot_online_in(p,l)&&(!zero(p.x-l.a.x)||!zero(p.y-l.a.y)||!zero(p.z-l.a.z))&&(!zero(p.x-l.b.x)||!zero(p.y-l.b.y)||!zero(p.z-l.b.z)); int dot_online_ex(point3 p,point3 l1,point3 l2){returndot_online_in(p,l1,l2)&&(!zero(p.x-l1.x)||!zero(p.y-l1.y)||!zer o(p.z-l1.z))&&(!zero(p.x-l2.x)||!zero(p.y-l2.y)||!zero(p.z-l2.z));//判点是否在空间三角形上,包括边界,三点共线无意义int dot_inplane_in(point3 p,plane3 s){returnzero(vlen(xmult(subt(s.a,s.b),subt(s.a,s.c)))-vlen(xmult(subt(p ,s.a),subt(p,s.b)))-vlen(xmult(subt(p,s.b),subt(p,s.c)))-vlen(xmult(subt(p,s.c), subt(p,s.a))));int dot_inplane_in(point3 p,point3 s1,point3 s2,point3 s3){ returnzero(vlen(xmult(subt(s1,s2),subt(s1,s3)))-vlen(xmult(subt(p,s1) ,subt(p,s2)))-vlen(xmult(subt(p,s2),subt(p,s3)))-vlen(xmult(subt(p,s3),sub t(p,s1))));//判点是否在空间三角形上,不包括边界,三点共线无意义int dot_inplane_ex(point3 p,plane3 s){returndot_inplane_in(p,s)&&vlen(xmult(subt(p,s.a),subt(p,s.b)))>eps&&vlen(xmult(subt(p,s.b),subt(p,s.c)))>eps&&vlen(xmult(subt(p, s.c),subt(p,s.a)))>eps;int dot_inplane_ex(point3 p,point3 s1,point3 s2,point3 s3){ returndot_inplane_in(p,s1,s2,s3)&&vlen(xmult(subt(p,s1),subt(p,s2)))> eps&&vlen(xmult(subt(p,s2),subt(p,s3)))>eps&&vlen(xmult(subt(p,s3 ),subt(p,s1)))>eps;//判两点在线段同侧,点在线段上返回0,不共面无意义int same_side(point3 p1,point3 p2,line3 l){returndmult(xmult(subt(l.a,l.b),subt(p1,l.b)),xmult(subt(l.a,l.b),sub t(p2,l.b)))>eps;int same_side(point3 p1,point3 p2,point3 l1,point3 l2){ returndmult(xmult(subt(l1,l2),subt(p1,l2)),xmult(subt(l1,l2),subt(p2,l2)))>eps;//判两点在线段异侧,点在线段上返回0,不共面无意义int opposite_side(point3 p1,point3 p2,line3 l){returndmult(xmult(subt(l.a,l.b),subt(p1,l.b)),xmult(subt(l.a,l.b),sub t(p2,l.b)))<-eps;int opposite_side(point3 p1,point3 p2,point3 l1,point3 l2){ returndmult(xmult(subt(l1,l2),subt(p1,l2)),xmult(subt(l1,l2),subt(p2, l2)))<-eps;//判两点在平面同侧,点在平面上返回0int same_side(point3 p1,point3 p2,plane3 s){returndmult(pvec(s),subt(p1,s.a))*dmult(pvec(s),subt(p2,s.a))>eps;int same_side(point3 p1,point3 p2,point3 s1,point3 s2,point3 s3){ returndmult(pvec(s1,s2,s3),subt(p1,s1))*dmult(pvec(s1,s2,s3),subt(p2, s1))>eps;//判两点在平面异侧,点在平面上返回0int opposite_side(point3 p1,point3 p2,plane3 s){returndmult(pvec(s),subt(p1,s.a))*dmult(pvec(s),subt(p2,s.a))<-eps;int opposite_side(point3 p1,point3 p2,point3 s1,point3 s2,point3 s3){returndmult(pvec(s1,s2,s3),subt(p1,s1))*dmult(pvec(s1,s2,s3),subt(p2, s1))<-eps;//判两直线平行int parallel(line3 u,line3 v){return vlen(xmult(subt(u.a,u.b),subt(v.a,v.b)))<eps;int parallel(point3 u1,point3 u2,point3 v1,point3 v2){ return vlen(xmult(subt(u1,u2),subt(v1,v2)))<eps;//判两平面平行int parallel(plane3 u,plane3 v){return vlen(xmult(pvec(u),pvec(v)))<eps;int parallel(point3 u1,point3 u2,point3 u3,point3 v1,point3 v2,point3 v3){return vlen(xmult(pvec(u1,u2,u3),pvec(v1,v2,v3)))<eps;//判直线与平面平行int parallel(line3 l,plane3 s){return zero(dmult(subt(l.a,l.b),pvec(s)));int parallel(point3 l1,point3 l2,point3 s1,point3 s2,point3 s3){ return zero(dmult(subt(l1,l2),pvec(s1,s2,s3)));//判两直线垂直int perpendicular(line3 u,line3 v){return zero(dmult(subt(u.a,u.b),subt(v.a,v.b)));int perpendicular(point3 u1,point3 u2,point3 v1,point3 v2){ return zero(dmult(subt(u1,u2),subt(v1,v2)));//判两平面垂直int perpendicular(plane3 u,plane3 v){return zero(dmult(pvec(u),pvec(v)));int perpendicular(point3 u1,point3 u2,point3 u3,point3 v1,point3 v2,point3 v3){return zero(dmult(pvec(u1,u2,u3),pvec(v1,v2,v3)));//判直线与平面平行int perpendicular(line3 l,plane3 s){return vlen(xmult(subt(l.a,l.b),pvec(s)))<eps;int perpendicular(point3 l1,point3 l2,point3 s1,point3 s2,point3 s3){return vlen(xmult(subt(l1,l2),pvec(s1,s2,s3)))<eps;//判两线段相交,包括端点和部分重合int intersect_in(line3 u,line3 v){if (!dots_onplane(u.a,u.b,v.a,v.b))return 0;if (!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b)) return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);returndot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u )||dot_online_in(v.b,u);int intersect_in(point3 u1,point3 u2,point3 v1,point3 v2){ if (!dots_onplane(u1,u2,v1,v2))return 0;if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2)) return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);returndot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in (v1,u1,u2)||dot_online_in(v2,u1,u2);//判两线段相交,不包括端点和部分重合int intersect_ex(line3 u,line3 v){returndots_onplane(u.a,u.b,v.a,v.b)&&opposite_side(u.a,u.b,v)&&opposi te_side(v.a,v.b,u);int intersect_ex(point3 u1,point3 u2,point3 v1,point3 v2){ returndots_onplane(u1,u2,v1,v2)&&opposite_side(u1,u2,v1,v2)&&opposite _side(v1,v2,u1,u2);//判线段与空间三角形相交,包括交于边界和(部分)包含int intersect_in(line3 l,plane3 s){return !same_side(l.a,l.b,s)&&!same_side(s.a,s.b,l.a,l.b,s.c )&&!same_side(s.b,s.c,l.a,l.b,s.a)&&!same_side(s.c,s.a,l.a,l.b, s.b);int intersect_in(point3 l1,point3 l2,point3 s1,point3 s2,point3 s3){return !same_side(l1,l2,s1,s2,s3)&&!same_side(s1,s2,l1,l2,s3 )&&!same_side(s2,s3,l1,l2,s1)&&!same_side(s3,s1,l1,l2,s2);//判线段与空间三角形相交,不包括交于边界和(部分)包含int intersect_ex(line3 l,plane3 s){returnopposite_side(l.a,l.b,s)&&opposite_side(s.a,s.b,l.a,l.b,s.c)&&opposite_side(s.b,s.c,l.a,l.b,s.a)&&opposite_side(s.c,s.a,l. a,l.b,s.b);int intersect_ex(point3 l1,point3 l2,point3 s1,point3 s2,point3 s3){returnopposite_side(l1,l2,s1,s2,s3)&&opposite_side(s1,s2,l1,l2,s3)&&opposite_side(s2,s3,l1,l2,s1)&&opposite_side(s3,s1,l1,l2,s2) ;//计算两直线交点,注意事先判断直线是否共面和平行!//线段交点请另外判线段相交(同时还是要判断是否平行!)point3 intersection(line3 u,line3 v){point3 ret=u.a;doublet=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));ret.x+=(u.b.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;ret.z+=(u.b.z-u.a.z)*t;return ret;point3 intersection(point3 u1,point3 u2,point3 v1,point3 v2){ point3 ret=u1;double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)) /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));ret.x+=(u2.x-u1.x)*t;ret.y+=(u2.y-u1.y)*t;ret.z+=(u2.z-u1.z)*t;return ret;//计算直线与平面交点,注意事先判断是否平行,并保证三点不共线!//线段和空间三角形交点请另外判断point3 intersection(line3 l,plane3 s){point3 ret=pvec(s);doublet=(ret.x*(s.a.x-l.a.x)+ret.y*(s.a.y-l.a.y)+ret.z*(s.a.z-l.a.z)) /(ret.x*(l.b.x-l.a.x)+ret.y*(l.b.y-l.a.y)+ret.z*(l.b.z-l.a.z) );ret.x=l.a.x+(l.b.x-l.a.x)*t;ret.y=l.a.y+(l.b.y-l.a.y)*t;ret.z=l.a.z+(l.b.z-l.a.z)*t;return ret;point3 intersection(point3 l1,point3 l2,point3 s1,point3 s2,point3 s3){point3 ret=pvec(s1,s2,s3);doublet=(ret.x*(s1.x-l1.x)+ret.y*(s1.y-l1.y)+ret.z*(s1.z-l1.z))/ (ret.x*(l2.x-l1.x)+ret.y*(l2.y-l1.y)+ret.z*(l2.z-l1.z));ret.x=l1.x+(l2.x-l1.x)*t;ret.y=l1.y+(l2.y-l1.y)*t;。

ACM模板（Java）模板TrieHIHOCODER1014static final int N = (int)1e5+10;static final int SIGMA=(int)27;static int ch[][]=new int[N*10][SIGMA],sz;static int var[]=new int[N*10];static void insert(String x){int u=0;for(int i=0;i<x.length();i++){int c=x.charAt(i)-'a';if(ch[u][c]==0){for(int t=0;t<SIGMA;t++){ch[sz][t]=0;}ch[u][c]=sz;var[sz++]=0;}u=ch[u][c];var[u]++;}}static int search(String x){int u=0;for(int i=0;i<x.length();i++){int c=x.charAt(i)-'a';if(ch[u][c]!=0) u=ch[u][c];else return 0;}return var[u];}static void clear() {sz=1;var[0]=0;for(int i=0;i<SIGMA;i++) {ch[0][i]=0;}}KMPHIHOCODER 1015写法1static void getFail(char[] b) {int m=b.length,j=0;f[0]=f[1]=0;for(int i=1;i<m;i++) {while(j>0&&b[j]!=b[i]) j=f[j];if(b[j]==b[i]) j++;f[i+1]=j;}}static int kmp_count(char[] a,char[] b) {int n=a.length,m=b.length;int j=0,res=0;for(int i=0;i<n;i++) {while(j>0&&b[j]!=a[i]) j=f[j];if(b[j]==a[i]) j++;if(j==m) {j=0;res++;}}return res;写法2static void getFail(char[] b,int m) {int j=0;f[1]=0;for(int i=2;i<=m;i++) {while(j>0&&b[j+1]!=b[i]) j=f[j];if(b[j+1]==b[i]) j++;f[i]=j;}}static int kmp_count(char[] a,char[] b,int n,int m) { int j=0,res=0;for(int i=1;i<=n;i++) {while(j>0&&b[j+1]!=a[i]) j=f[j];if(b[j+1]==a[i]) j++;if(j==m) {j=0;res++;}}return res;}ManacherHIHOCODER1016static final int N=(int)1e6+10;static char a[]=new char[N],str[]=new char[2*N+5]; static int p[]=new int[2*N+5],len1,len2;static void Init(){len1=a.length;str[0]='(';str[1]='#';for(int i=0;i<len1;i++){str[i*2+2]=a[i];str[i*2+3]='#';}len2=len1*2+2;str[len2]=')';}static int Manacher(){for(int i=0;i<len2;i++) p[i]=0;int id=0,mx=0,ans=0;for(int i=1;i<len2;i++){if(mx>i) p[i]=Math.min(mx-i,p[2*id-i]);else p[i]=1;for(;str[i+p[i]]==str[i-p[i]];p[i]++);if(p[i]+i>mx){mx=p[i]+i;id=i;}if(p[i]-1>ans) ans=p[i]-1;}return ans;}Tire图HIHOCODER 1036static int sz;static final int N=1000005;static class Node{Node(){post = 0;for(int i = 0; i < 26; i++)next[i] = 0;end = false;int post;int next[]=new int[26];boolean end;};static Node nodes[]=new Node[N];//将str添加到trie图中static void insert(String str){int cur=0;for(int i=0;i<str.length();i++){if(nodes[cur].next[str.charAt(i)-'a'] == 0)nodes[cur].next[str.charAt(i)-'a'] = ++sz;cur = nodes[cur].next[str.charAt(i)-'a'];}nodes[cur].end = true;}//为trie图中的每个点添加它指向的后缀点位置static void addPost(){LinkedList<Integer> que = new LinkedList<Integer>();que.push(0);int cur;while(!que.isEmpty()){cur=que.pop();for(int i=0;i<26;i++){if(nodes[cur].next[i]!=0){que.push(nodes[cur].next[i]);if(cur != 0)//不是根结点，需要设置当前点的⼦节点的后缀=⽗结点的后缀经过i到达的点 nodes[nodes[cur].next[i]].post = nodes[nodes[cur].post].next[i];}else //nodes[current].next[i] == -1当前点经过i没有可达的nodes[cur].next[i] = nodes[nodes[cur].post].next[i];}}}//查找strstatic boolean search(String str){int cur = 0;for(int i=0;i<str.length();i++){if(nodes[nodes[cur].next[str.charAt(i)-'a']].end)return true;cur = nodes[cur].next[str.charAt(i)-'a'];}return false;}static void Init() {sz=0;for(int i=0;i<=1000000;i++) {nodes[i]=new Node();}}。