1
高精度.......................................................................................................................2
(1)高精函数........................................................................................................2
(2)高精开方........................................................................................................6
(3)高精类............................................................................................................9
计算几何.................................................................................................................13
(1)凸包..............................................................................................................13
(2)最远点对......................................................................................................14
(3)最近点对......................................................................................................16
(4)简单多边形的重心 ......................................................................................17
(5)直线问题......................................................................................................17
(6)计算多边形面积(凹凸都适用).....................................................................19
(7)判断点线在多边行内...................................................................................19
图论算法.................................................................................................................20
(1)生成树问题..................................................................................................20
(2)最短路问题..................................................................................................20
(3)网络流问题..................................................................................................20
//网络流(最大流程序,标号法)................................................................20
//网络流(最大流程序,前流推进).............................................................21
//网络流(最小费用最大流程序) by peipei..............................................22
(4)二分图问题..................................................................................................23
//最大基数匹配..........................................................................................23
//最大权匹配..............................................................................................24
(5)Euler 回路 ....................................................................................................25
(6)连通性问题..................................................................................................26
//无向图的割顶和桥(pku 1523 测试)........................................................26
//极大强连通分支(tested by uva 247)........................................................26
数据结构.................................................................................................................27
(1)堆 .................................................................................................................27
(2)线段树..........................................................................................................28
(3)树状数组......................................................................................................28
(4)哈希表..........................................................................................................30
(5)左偏树..........................................................................................................30
数论算法.................................................................................................................31
简单的数论算法(gcd,ext_euclid,中国剩余定义,Euler 函数).........................31
//最大公约数..............................................................................................31
//中国剩余定义,高精度 ..........................................................................32
//中国剩余定理,int 版本 ............................................................................34
(2)随机素数测试与大数分解...........................................................................35
字符串.....................................................................................................................37
(1)KMP.............................................................................................................37
(2)后缀数组......................................................................................................38
(3)LIS(nlogn)....................................................................................................38
(4)最小串表示法(O(N)算法)............................................................................38
(5)最大公共上升子列(平方算法).....................................................................38
模拟算法.................................................................................................................39
表达式求值 ......................................................................................................39
特殊问题.................................................................................................................41
(1)LCA+RMQ...................................................................................................41
(2)FFT...............................................................................................................42
//多项式乘法..............................................................................................44
(3)最大团..........................................................................................................46
排序.........................................................................................................................46
(1)快速排序(找第 n 大数)................................................................................46
(2)归并排序(逆序数)........................................................................................47
(3)希尔排序......................................................................................................48
(4)基数排序......................................................................................................48
(5)STL 的 sort 函数 ..........................................................................................49
2
高精度
(1)高精函数
//高精例程
/////////////////////////////////////////////////////////////
//常用函数 //
//(1)add(bint a, bint b, bint& c)大数加法 c=a+b //
//(2)add(bint a, type b, bint& c)高精加单精 c=a+b //
//(3)by(bint a, type b, bint& c)高精乘单精 c=a*b, //
// **注意:b 应小于 base** //
//(4)by(bint a, bint b, bint& c)大数乘法 c=a*b //
//(5)div(bint a, type b, bint& c, type& d)高精除单精 //
// c = a/b, d = a%b; //
//(6)input(bint& a)输入高精,无效输入返回 0,否则返回 1 //
//(7)output(bint& a)输出高精 //
/////////////////////////////////////////////////////////////
//少用函数 //
//(8)move(bint& a)二进制右移,即除 2 操作 //
//(9)sub(bint a, bint b, bint& c)大数减法 c=a-b,a>=b //
//(10)sub(bint a, type b, bint& c)高精减单精 c=a-b,a>=b //
//(11)cmp(bint a, bint b)比较 a 和 b,>,==,<分别返回 //
// 正数,0,负数. //
//(12)give(bint a, bint& b)赋值 b = a; //
//(13)give(type a, bint& b)赋值 b = a; //
//(14)shift(bint& a, type k)段移位函数,把 a 移动 k 段,变大 mod^k//
//(15)div(bint a, bint b, bint& c, bint& d)大数除法 //
// c=a/b,d=a%b,**注意:需要函数(1),(2),(4),(9),(11),(13), //
// (14)** //
/////////////////////////////////////////////////////////////
#include <stdio.h>
#include <string.h>
//////////////////////////////////////
#define MAX 100
#define mod 10000
#define baselen 4
#define in(a) scanf("%d",&a)
#define out1(a) printf("%d",a)
#define out2(a) printf("%04d",a)
typedef int type;
/////////////////////////////////////
struct bint{
type dig[MAX], len;
bint(){len = 0, dig[0] = 0;}
};
////////////////////////////////////////////
//常用函数
//(1)
void add(bint a, bint b, bint& c){
type i, carry ;
for( i = carry = 0; i <= a.len || i <= b.len || carry; i++){
if(i<=a.len)carry += a.dig[i];
if(i<=b.len)carry += b.dig[i];
c.dig[i] = carry%mod;
carry /= mod;
}
c.len = i - 1;
用 FinePrint 打印 - 可在 www.fineprint.com.cn 订购
PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn