ACM函数整理ACM模板

ACMACM函数整理函数整理ACMACM模板模板 I I I I目目录 一 数学问题1 精度计算 大数阶乘语法int result factorial int n 参数nn的阶乘返回值阶乘结果的位数注意本程序直接输出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 j0 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 精度计算 乘法 大数乘小数 语法mult char c char t int m 参数c 被乘数 用字符串表示 位数不限t 结果 用字符串表 示ACM ICPC函数实例华董圣华 752222m乘数 限定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 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 0 i ACM ICPC函数实例华董圣华 753333 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 jstrlen b l strlen a 2 else l strlen b 2 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 j9 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 ACM ICPC函数实例华董圣华 755555if s1 l1 s2 i 0 t l1 s1 l1 s2 i 0 else t l1 10 s1 l1 s2 i 0 s1 l1 1 s1 l1 1 1 k l1 while s1 k 0 t l1 s1 l1 l1 loop if t 0 0 l1 strlen s1 for i 0 i 0 t s i 0 else t s i A 10 ACM ICPC函数实例华董圣华 756666num 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 1 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 m1n1 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 intl int il 参数pr n 输入的实部pi n 数入的虚部n k满足n 2 kfr n 输 出的实部fi n 输出的虚部l逻辑开关 0FFT 1ifFTACM ICPC函数实 例华董圣华 758888il逻辑开关 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 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 ACM ICPC函数实例华董圣华 759999s 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 for i 0 i n 1 i fr i fr i 1 0 n fi i fi i 1 0 n if il 0 fo r i 0 i n 1 i pr i sqrt fr i fr i fi i fi i if fabs 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 5ACM ICPC函数实例华董圣华 7510源程序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 loop double s 0 0 double x a h 2 0 while x1e 5 r1 r2 c1 c2 k h 2 0 t1 t2 s1 s2 ACM ICPC函数实例华董 圣华 7511goto 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 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 求排列组合数ACM ICPC函数实例华董圣华 7512语法r esult P long n long m result long C long n long m 参数m排列组合的上系数n排列组合的下系数返回值排列组合数注 意符合数学规则m 3 n N else n N 1 c n 100 ACM ICPC函数实例华董圣华 7513y n 100 w int d floor 13 m 5 y floor y 4 floor c 4 2 c 7 while w 2 该递推关系的解为h n c 2n 2 n 1 n n 1 2 3 1 1 2 5 14 42 132 429 1430 4862 16796 5878 6 208012 742900 2674440 9694845 35357670 129644790 47763870 0 1767263190 6564120420 24466267020 91482563640 34305961365 0 1289904147324 4861946401452 1 括号化问题 矩阵链乘P a1 a2 a3 an 依据乘法结合律 不改变其顺 序 只用括号表示成对的乘积 试问有几种括号化的方案 h n 种 2 出栈次序问题 一个栈 无穷大 的进栈序列为1 2 3 n 有多少个不同的出栈序列 类似有2n个人排成一行进入剧场 入场费5元 其中只有n个人有一张5元钞票 另外n人只有10元钞票 剧院无其它 钞票 问有多少中方法使得只要有10元的人买票 售票处就有5元的 钞票找零 将持5元者到达视作将5元入栈 持10元者到达视作使栈 中某5元出栈 3 将多边行划分为三角形问题 将一个凸多边形区域分成三角形区域的方法数 类似一位大城市的律 师在她住所以北n个街区和以东n个街区处工作 每天她走2n个街区去上班 如果他从不穿越 但可以碰到 从家到办公室的对角线 那么有多 少条可能的道路 类似在圆上选择2n个点 将这些点成对连接起来使 得所得到的n条线段不相交的方法数 15 杨辉三角语法 void gen 预置 Const intMax 注意 Max一般不能超过22 否则要用高精度计算 int inta Max Max 结果 inta为杨辉三角序列 inta 1 1 1 inta 2 1 1 inta 2 2 1 void gen int i j for i 1 i Max i ACM ICPC函数实例华董圣华 7514int a i 1 1 inta i i 1 inta 2 2 1 for i 3 i Max i fo r j 2 jusing namespacestd const intMaxNum 20 static inta MaxNum void qp intArray intbegin intend int main int i for i 0 i end for i 0 i includeusing namespacestd int main int i int A 0 1 2 3 while next permutation A A 4 true prev pe rmutation A A 4 for i 0 i 4 i cout includebool g 201 201 为边之间的关系 如g 0 1 true表示为左边0点可 与右边1点相连 int n m ans n左边的点 m右边的点 ans为最大匹配的边数 ACM ICPC 函数实例华董圣华 7516bool b 201 b i 表示该点是否有左边的点连上int link 201 bool init int x y memset g 0 sizeof g 对二维数组也可以这 样初始化 memset link 0 sizeof link ans 0 if scanf d d for inti 1 i n i n左边的点 m右边的点 scanf d for intj 0 j x j scanf d g i y true r eturn true bool find inta for inti 1 i m i if g a i trueif link i 0 find link i link i a return true return false int main while init for inti 1 i1 Q pop if preturn true else xckd ymate u true Q push ymate u 1 else f or inti 0 iex slack i ex prev i u else yckd i true pr ev i u Q push i 1 1 return false void Graph agument intu while u 1 int pv xmate prev u ymate u prev u xmate prev u u u pv int Graph KMMatch int i j memset ly 0 sizeof ly for i 0 iedge i j lx i edge i j memset xmate 1 sizeof xmate memset ymate 1 sizeof ymate bool agu true for intmn 0 mn 二 字符串处理1 字符串替换语法replace char str char key char swap 参数str 在此源字符串进行替换操作key 被替换的字符 串 不能为空串swap 替换的字符串 可以为空串 为空串表示在 源字符中删除key 返回值null注意默认str 长度小于1000 如否 重新设定设定tmp大小需要string h源程序ACM ICPC函数实例华董 圣华 7520void replace char str char key char swap int l1 l2 l3 i j flag char tmp 1000 l1 strlen str l2 strlen key l3 strlen swap for i 0 i0 ACM ICPC函数实例华董圣华 7523 if c i j c i 1 j i else if c i j c i j 1 j else s k a i 1 i j return s 6 数字转换为字符语法cstr int k char o 参数k转换的数字o 存储转换结果的字符串返回值null注意需 要math h源程序void cstr int k char o int len i t len log10 k 1 for i len i 0 i t k 10 k t k 10 o i 1 0 t o len 0 ACM ICPC函数实例华董圣华 7524 三 计算几何1 叉乘法求任意多边形面积语法result polygonarea Point polygon int N 参数 polygon多变形顶点数组N多边形顶点数目返回值多边形面 积注意支持任意多边形 凹 凸皆可多边形顶点输入时按顺时针顺 序排列源程序typedef struct double x y Point double polygonarea Point polygon int N int i j double area 0 for i 0 iPI dtheta PI 2 while dtheta PI dtheta PI 2 return dtheta 4 两点距离 2D 3D 语法res ult distance 2d float x1 float x2 float y1 float y2 参数x y z1 2各点的x y z坐标ACM ICPC函数实例华董圣华 7526返回值两点之间的距离注意需要math h源程序float distance 2d float x1 float x2 float y1 float y2 return sqrt x1 x2 x1 x2 y1 y2 y1 y2 float distance 3d float x1 float x2 float y1 float y2 float z1 float z2 return sqrt x1 x2 x1 x2 y1 y2 y1 y2 z1 z2 z1 z2 5 射向法判断点是否在多边形内部语法result insidepolyg on Point polygon int N Point p 参数 polygon多边形顶点数组N多边形顶点个数p被判断点返回值 0点在多边形内部 1点在多边形外部注意若p点在多边形顶点或者边 上 返回值不确定 需另行判断需要math h源程序 define MIN x y xy x y typedef struct double x y Point int insidepolygon Point polygon intN Point p int counter 0 int i double xinters Point p1 p2 p1 polygon 0 for i 1 iMIN p1 y p2 y ACM ICPC函数实例华董圣华 7527if p y M AX p1 y p2 y if p x MAX p1 x p2 x if p1 y p2 y xinte rs p y p1 y p2 x p1 x p2 y p1 y p1 x if p1 x p2 x p x xinters counter p1 p2 if counter 2 0 return OUTSIDE elsereturn INSIDE 6 判断 点是否在线段上语法result Pointonline Point p1 Point p2 Point p 参数p 1 p2线段的两个端点p被判断点返回值0点在不在线段上 1点在线 段上注意若p线段端点上返回1需要math h源程序 define MIN x y xy x y typedef struct double x y Point int FC double x1 double x2 if x1 x2 0 000002 return1 else return0 int Pointonline Point p1 Point p2 Point p ACM ICPC函数实例华董圣华 7528double x1 y1 x2 y2 x1 p x p1 x x2 p2 x p1 x y1 p y p1 y y2 p2 y p1 y if FC x1 y2 x2 y1 0 0 return0 if MIN p1 x p2 x p x