acm算法模板1.docx

1、acm算法模板1算法模板1基础算法 2进制转换 2最长XX序列 3并查集 4食物链 4银河英雄传说 5高精度 6一、正整数 6二、实数 10数论 17欧拉函数 17稳定婚姻 17Picks Theore 18图论 19Dij 堆优化 19一、STL 19二、数组 20BELLMAN-FOLD 22SPFA 23LCA (不完整) 25一、tongji 1068 25二、pku1330 26最小树形图 27利用Floyed算法求最小环 29欧拉回路 31字符串处理 32KMP 32Greatest Common Increasing Subsequence (TJU2707) 33字母树Trie

2、 34AC 自动机 35后缀数组 38Pku3415 堆栈扫描 38Pku2758 动态更新 41Bupt1302 hard 二分求解 45RMQ 49平衡树 50TREAP 50魔兽争霸 50郁闷的出纳员 52树状数组 54线段树 55pku3368,线段树的一个常用的用法，记录左右区间以及中间的合并 55pku 3468，记录delta变量 57zju1610 统计区间信息 58pku 1151面积扫描 59pku1177，周长扫描 61树套树 63矩形切割 65网络流 66最大流 66Pku 2289 66分数划分 69求最小割 73最优比率生成树 76最大密度子图 78最大权闭合图 8

3、1费用流 84pku3680 84Pku2516 86基础算法进制转换int s100;int main() int i,n,r; while(cinnr) i=0; coutn=; while (n!=0) i+; si=n%r; n=n/r; if (si=1;i-) if (si=10) coutchar(A+si-10); else coutsi; cout (base r)endl; return 0;最长XX序列结论：上升序列的最小个数=不降序列的最长长度struct node int l,w;node a20002;int b20002;bool cmp(const node&

4、a, const node& b) return a.lb.w); int dp(int n) int i,l,r,m,len; memset(b,0,sizeof(b); b0=130; b1=a1.w; len = 1; for(i=2;i=n;+i) l=0,r=len; while(l1; if(bm=ai.w) l=m+1; else r=m-1; bl=ai.w; if (llen) len+; return len;int main() int i,n,t; scanf(%d,&t); while(t-) scanf(%d,&n); for(i=1;i=n;i+) scanf(%

5、d%d,&ai.l,&ai.w); sort(a+1,a+1+n,cmp); printf(%dn,dp(n); return 0; 并查集食物链Const int maxn=50010;int rootmaxn,dmaxn;void calc(int i,int f) if (rooti=f) return ; calc(rooti,f); di=(di+drooti)%3; rooti=f;int find(int i) int f; f=i; while (rootf!=f) f=rootf; calc(i,f); return f;int main() int i,n,k,dxy,x,

6、y,fx,fy,num; num=0; scanf(%d%d,&n,&k); for (i=1;i=n;i+) rooti=i; memset(d,0,sizeof(d); while (k-) scanf(%d%d%d,&dxy,&x,&y); dxy-; if (x=y & dxy=1) | xn | yn) num+; continue; fx=find(x); fy=find(y); if (fx=fy) if (dy-dx+3)%3!=dxy) num+; else rootfy=fx; dfy=(dx+dxy-dy+3)%3; printf(%dn,num); return 0;银

7、河英雄传说const int maxn=30001;int rootmaxn,aheadmaxn,nummaxn;int f;inline int calc(int i) if (rooti!=f) aheadi+=calc(rooti); rooti=f; return aheadi;int find(int i) f=i; while (rootf!=f) f=rootf; calc(i); return f;int main() int i,n,x,y,fx,fy; char c; while(scanf(%d,&n)&n) for (i=1;imaxn;i+) rooti=i; num

8、i=1; memset(ahead,0,sizeof(ahead); for (i=1;i0;x/=base) datalen+=x%base; bigint& operator=(const bigint& x) len=x.len; memcpy(data, x.data, len * sizeof *data); return *this; int& operator(int i) return datai; int operator(int i) const return i b.len ? 1 : -1; for (i = a.len - 1; i = 0 & ai = bi; i-

9、); if (i bi ? 1 : -1; bool operator=(const bigint& a, const bigint& b) return compare(a,b)=0;bool operator!=(const bigint& a, const bigint& b) return compare(a,b)!=0;bigint operator+(const bigint& a, const bigint& b) bigint c; int i; int x = 0; for (i = 0; i a.len | i 0; i+) if (i a.len) x += ai; if

10、 (i b.len) x += bi; ci = x % base; x /= base; c.len = i; return c; bigint operator-(const bigint& a, const bigint& b) bigint c; int x = 0; c.len = a.len; int i; for (i = 0; i c.len; i+) ci = ai - x; if (i b.len) ci -= bi; if (ci 0 & cc.len - 1 = 0) c.len-; return c; bigint operator*(const bigint& a,

11、 const int b) int i; if (b = 0) return 0; bigint c; longint x = 0; for (i = 0; i 0; i+) if (i a.len) x += longint(ai) * b; ci = x % base; x /= base; c.len = i; return c; bigint operator*(const bigint& a, const bigint& b) int i; if (b.len = 0) return 0; bigint c; for (i = 0; i a.len; i+) longint x =

12、0; for (int j = 0; j 0; j+) if (j b.len) x+=longint(ai)*bj; if (i + j = c.len) cc.len+ = x % base; else ci + j = x % base; x /= base; return c; bigint operator/(const bigint& a, const int b) bigint c; int i; longint x = 0; for (i = a.len - 1; i = 0; i-) x = x * base + ai; ci = x / b; x %= b; c.len =

13、 a.len; while (c.len 0 & cc.len - 1 = 0) c.len-; return c; bigint operator/(const bigint& a, const bigint& b) int i; bigint c, x = 0; int l, r, mid; for (i = a.len - 1; i = 0; i-) x = x * base + ai; l = 0; r = base - 1; while (l 1; if (compare(b * mid, x) 0 & cc.len - 1 = 0) c.len-; return c; bigint

14、 operator%(const bigint& a, const bigint& b) bigint c,x; c=a/b; x=a-b*c; return x; istream& operator(istream& input, bigint& x) char c; for (x = 0; input c;) x = x * 10 + (c - 0); if (input.peek() = ) break; return input; ostream& operator(ostream& output, const bigint& x) int i,j; output = 0; i-) f

15、or (j = base / 10; j 0; j /= 10) output a b, a!=0 | b!=0) c = gcd(a, b); cout a * b / c endl; return 0;二、实数#include#includeusing namespace std;class BigDecimal;string addition( string A, string B );string subtraction( string A, string B );BigDecimal BD_add( BigDecimal a, BigDecimal b );BigDecimal BD

16、_sub( BigDecimal a, BigDecimal b );BigDecimal BD_multiply( BigDecimal a, BigDecimal b );BigDecimal BD_divide( BigDecimal a, BigDecimal b );void eraser( string &in ); /去除多余的0 ( 除法中使用 )long max_decimal=0; /求商时小数位最大长度，-1表示没有限制 class BigDecimal bool negative; /标记数的正负性 正数0 负数1 string BDstr; /记录标准化的大数字符串

17、long point; /记录小数点的位置public: BigDecimal() negative=0;BDstr=;point=0; BigDecimal( string s ) initBD( s ); void initBD( string s ) long i,lenI; string In=s; BDstr=; if(In0=-) negative=1;In.erase(In.begin(); else if(In0=+) negative=0;In.erase(In.begin(); else negative=0; lenI=In.size(); for(i=0;ilenI;i

18、+) if(Ini=.) i+;break; BDstr.insert(BDstr.end(),Ini); point=lenI-i; for(;ilenI;i+) BDstr.insert(BDstr.end(),Ini); standard();/标准化 void standard()/去BDstr前后多余的0 long i,mid=BDstr.size()-point; for(i=0;imid;i+) if(BDstr0=0) BDstr.erase(BDstr.begin(); else break; for(i=0;ipoint;i+) long lenBD=BDstr.size(

19、); if(BDstrlenBD-1=0) BDstr.erase(BDstr.begin()+lenBD-1); else break; point-=i; if(BDstr=) negative=0;point=0; void print() standard(); long i,lenBD=BDstr.size(),mid=lenBD-point; if(BDstr=) putchar(0);return; if(negative=1) putchar(-); if(point=lenBD) putchar(0); for(i=0;imid;i+) putchar(BDstri); if(ilenBD)putchar(.); for(;ib.point ) while( a.point!=b.point ) b.BDstr.append(0);b.point+; /对齐小数部分 if( a.pointb.point ) while( a.point!=b.point ) a.BDstr.append(0);a.point+; if( (a.negative=0&b.negative=0) | (a.negative=1&b.negative=1) )/同正或同负 Res.negative=a.