ACM模板我的第一份ACM模板

ACMACM模板我的第一份模板我的第一份ACMACM模板模板 求逆序数int solve int f int l int mid f l 2 j 0 h1 f h2 mid 1 int sum 0 if f l return0 sum solve f mid solve mid 1 l fo r h1 mid if str i h1 str i h2 tem j str i h1 h1 else tem j str i h2 h2 sum mid h1 1 while h1 mid tem j str i h1 while h2 l t em j str i h2 memcpy return sum 经典宽搜visited a x a y 0 while s eif c x b xfor i 0 i 0 ans f 1 t m printf d n ans 最长公共子序列 若给定序列X x1 x2 x m 则另一序列Z z1 z2 z k 是X的子序列是指存在一个严格递增下标序列 i1 i2 i k 使得对于所有j 1 2 k有z j x ij 例如 序列Z B C D B 是序列X A B C B D A B 的子序 列 相应的递增下标序列为 2 3 5 7 给定2个序列X和Y 当另一序列Z既是X的子序列又是Y的子序列时 称Z是序列X和Y的公共子序列 给定2个序列X x1 x2 x m 和Y y1 y2 y n 找出X和Y的最长公共子序列 设序列X x1 x2 x m 和Y y1 y2 y n 的最长公共子序列为Z z1 z2 z k 则 1 若x m y n 则z k x m y n 且z k 1是x m 1和y n 1的最长公共子序列 2 若x m yn且z k xm 则Z是x m 1和Y的最长公共子序列 3 若x m yn且z k yn 则Z是X和y n 1的最长公共子序列 由此可见 2个序列的最长公共子序列包含了这2个序列的前缀的最 长公共子序列 因此 最长公共子序列问题具有最优子结构性质 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归 关系 用c i j 记录序列和的最长公共子序列的长度 其中 X i x1 x2 x i Yj y1 y2 y j 当i 0或j 0时 空序列是X i和Y j的最长公共子序列 故此时C i j 0 其他情况下 由最优子结构性质可建立递归关系如下 Algorithm lcsLength x y b 1 m x length 1 2 n y length 1 3 c i 0 0 c 0 i 0 4 for int i 1 i m i 0 c i j c i 1 j 1 1 max c i j 1 c i 1 j i 0 j 0i j 0 x i yji j 0 x i yj 5 for int j 1 j c i j 1 10 c i j c i 1 j 11 b i j 2 12 else 13 c i j c i j 1 14 b i j 3 构造最长公共子序列Algorithm lcs int i int j char x int b if i 0 j 0 return if b i j 1 l cs i 1 j 1 x b System out print x i else if b i j 2 lcs i 1 j x b else lcs i j 1 x b 图论Floyd for k 1 k n k for i 1 i n i for j 1 jarr i k arr k j arr i j arr i k arr k j for i 1 i n i for j 1 jlenth for i 0 i for i 0 i if set edges i from set edges i to temp set edges i to for j 0 j include define N201 define M201int g N M g x y 表示x y两个点之间有边相连int y M x记录的是x中的i节点是否被访问过 int link M link x 记录的是当前与x节点相连的y节点int n m s t int find int v int i for i 1 i h2 return1 else if h1max max tem printf d n max 凸 包 include include include include define PI3 14159struct POINT int x y pts 1001 int n stack 1002 flag 1002 sp int cmp const void p1 const void p2 struct POINT n1 struct POINT p1 n2 struct POINT p2 if n1 y n2 y return n1 y n2 y else returnn1 x n2 x int test int a int b int c if pts c y pts b y pts b x pts a x pts b y pts a y pts c x pts b x 0 return1 else return0 int ConvexHull int i nsp memset flag 0 sizeof flag qsort pts n sizeof struct POINT cmp sp 0 stack sp 0 flag sp 1 stack sp 1 i 2 while i 0 if flag i i continue 用过的点就舍弃if sp 2 include define N201 define M201int n m arr M M path M s t queue M ans int find road int in out int c i int visit M memset path 0 sizeof path memset visit 0 sizeof visit visit s 1 queue 0 s in 1 out 0 while in out c qu eue out out if c t re