ACM经典试题集华师大

1目录一数论31阶乘最后非零位32模线性方程组43素数表54素数随机判定MILLER_RABIN65质因数分解66最大公约数欧拉函数8二图论_匹配91二分图最大匹配HUNGARY邻接表形式92二分图最大匹配HUNGARY邻接表形式,邻接阵接口93二分图最大匹配HUNGARY邻接阵形式104二分图最大匹配HUNGARY正向表形式105二分图最佳匹配KUHN_MUNKRAS邻接阵形式116一般图匹配邻接表形式127一般图匹配邻接表形式,邻接阵接口138一般图匹配邻接阵形式149一般图匹配正向表形式14三图论_生成树151最小生成树KRUSKAL邻接表形式152最小生成树KRUSKAL正向表形式173最小生成树PRIMBINARY_HEAP邻接表形式184最小生成树PRIMBINARY_HEAP正向表形式195最小生成树PRIMMAPPED_HEAP邻接表形式206最小生成树PRIMMAPPED_HEAP正向表形式217最小生成树PRIM邻接阵形式228最小树形图邻接阵形式23四图论_网络流241上下界最大流邻接表形式242上下界最大流邻接阵形式263上下界最小流邻接表形式274上下界最小流邻接阵形式285最大流邻接表形式296最大流邻接表形式,邻接阵接口307最大流邻接阵形式318最大流无流量邻接阵形式319最小费用最大流邻接阵形式32五图论_最短路径331最短路径单源BELLMAN_FORD邻接阵形式332最短路径单源DIJKSTRA_BFS邻接表形式343最短路径单源DIJKSTRA_BFS正向表形式344最短路径单源DIJKSTRABINARY_HEAP邻接表形式355最短路径单源DIJKSTRABINARY_HEAP正向表形式366最短路径单源DIJKSTRAMAPPED_HEAP邻接表形式3727最短路径单源DIJKSTRAMAPPED_HEAP正向表形式388最短路径单源DIJKSTRA邻接阵形式399最短路径多源FLOYD_WARSHALL邻接阵形式39六图论_连通性401无向图关键边DFS邻接阵形式402无向图关键点DFS邻接阵形式413无向图块BFS邻接阵形式424无向图连通分支BFS邻接阵形式425无向图连通分支DFS邻接阵形式436有向图强连通分支BFS邻接阵形式437有向图强连通分支DFS邻接阵形式448有向图最小点基邻接阵形式45七图论_应用451欧拉回路邻接阵形式452前序表转化463树的优化算法474拓扑排序邻接阵形式485最佳边割集496最佳顶点割集507最小边割集518最小顶点割集529最小路径覆盖53八图论_NP搜索541最大团N小于64FASTER542最大团56九组合571排列组合生成572生成GRAY码593置换POLYA594字典序全排列605字典序组合606组合公式61十数值计算611定积分计算ROMBERG612多项式求根牛顿法633周期性方程追赶法64十一几何651多边形652多边形切割683浮点函数694几何公式745面积766球面777三角形7738三维几何809凸包GRAHAM8710网格PICK9011圆9012整数函数9213注意95十二结构951并查集952并查集扩展FRIEND_ENEMY963堆BINARY964堆MAPPED975矩形切割986线段树987线段树扩展1008线段树应用1039子段和10310子阵和103十三其他1041分数1042矩阵1063日期1084线性方程组GAUSS1095线性相关111十四应用1121JOSEPH1122N皇后构造解1123布尔母函数1134第K元素1145幻方构造1146模式匹配KMP1157逆序对数1168字符串最小表示1169最长公共单调子序列11710最长子序列11811最大子串匹配11912最大子段和12013最大子阵和120一数论1阶乘最后非零位/求阶乘最后非零位,复杂度ONLOGN/返回该位,N以字符串方式传入INCLUDEDEFINEMAXN100004INTLASTDIGITCHARBUFCONSTINTMOD201,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2INTLENSTRLENBUF,AMAXN,I,C,RET1IFLEN1RETURNMODBUF00FORI0I0ICC10AI,AIC/5,C5RETURNRETRET252模线性方程组IFDEFWIN32TYPEDEF_INT64I64ELSETYPEDEFLONGLONGI64ENDIF/扩展EUCLID求解GCDA,BAXBYINTEXT_GCDINTA,INTB,INTIFBX1,Y0RETURNARETEXT_GCDB,AB,X,YTX,XY,YTA/BYRETURNRET/计算MA,OLOGA,本身没什么用,注意这个按位处理的方法PINTEXPONENTINTM,INTAINTRET1FORAA1,MMIFARETURNRET/计算幂取模ABMODN,OLOGBINTMODULAR_EXPONENTINTA,INTB,INTN/ABMODN5INTRET1FORBB1,AINTI64AANIFBRETURNRET/求解模线性方程AXBMODN/返回解的个数,解保存在SOL中/要求N0,解的范围0N1INTMODULAR_LINEARINTA,INTB,INTN,INTSOLINTD,E,X,Y,IDEXT_GCDA,N,X,YIFBDRETURN0EXB/DNNNFORI0I0,WI与WJ互质,解的范围1N,NW0W1WK1INTMODULAR_LINEAR_SYSTEMINTB,INTW,INTKINTD,X,Y,A0,M,N1,IFORI0I1VOIDINITPRIMEINTIFORPLISTPCOUNT2,I3IIFDEFWIN32TYPEDEF_INT64I64ELSETYPEDEFLONGLONGI64ENDIFINTMODULAR_EXPONENTINTA,INTB,INTN/ABMODNINTRETFORBB1,AINTI64AANIFBRETURNRET/CARMICHEALNUMBER561,41041,825265,321197185INTMILLER_RABININTN,INTTIME10IFN1|N2WHILETIMEIFMODULAR_EXPONENTRANDDEFINEMAXN2001000DEFINEPSIZE100000INTPLISTPSIZE,PCOUNT0INTPRIMEINTNINTIIFN2FORI0PLISTIPLISTI1VOIDINITPRIMEINTIFORPLISTPCOUNT2,I3I1RETURNCNT/产生MAXN以内的所有素数/NOTE2863311530就是10101010101010101010101010101010/给所有2的倍数赋初值8INCLUDEINCLUDEUSINGNAMESPACESTDDEFINEMAXN100000000UNSIGNEDINTPLIST6000000,PCOUNTUNSIGNEDINTISPRIMEMAXN51DEFINESETBITZEROAISPRIMEA5FORI0I1RETN1RETURNRET9二图论_匹配1二分图最大匹配HUNGARY邻接表形式/二分图最大匹配,HUNGARY算法,邻接表形式,复杂度OME/返回最大匹配数,传入二分图大小M,N和邻接表LIST只需一边/MATCH1,MATCH2返回一个最大匹配,未匹配顶点MATCH值为1INCLUDEDEFINEMAXN310DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTMAXNSTRUCTEDGE_TINTFROM,TOEDGE_TNEXTINTHUNGARYINTM,INTN,EDGE_TLIST,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,P,Q,RET0,I,J,KEDGE_TEFOR_CLRMATCH1,_CLRMATCH2,I0I0FOR_CLRT,SPQ0IPNEXTIFTJETO0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRET2二分图最大匹配HUNGARY邻接表形式,邻接阵接口/二分图最大匹配,HUNGARY算法,邻接表形式,邻接阵接口,复杂度OMES/返回最大匹配数,传入二分图大小M,N和邻接阵/MATCH1,MATCH2返回一个最大匹配,未匹配顶点MATCH值为1INCLUDEINCLUDEDEFINEMAXN310DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTMAXNINTHUNGARYINTM,INTN,INTMATMAXN,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,P,Q,RET0,I,J,K,RVECTOREMAXN/生成邻接表只需一边FORI0I010FOR_CLRT,SPQ0IP0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRET3二分图最大匹配HUNGARY邻接阵形式/二分图最大匹配,HUNGARY算法,邻接阵形式,复杂度OMMN/返回最大匹配数,传入二分图大小M,N和邻接阵MAT,非零元素表示有边/MATCH1,MATCH2返回一个最大匹配,未匹配顶点MATCH值为1INCLUDEDEFINEMAXN310DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTMAXNINTHUNGARYINTM,INTN,INTMATMAXN,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,P,Q,RET0,I,J,KFOR_CLRMATCH1,_CLRMATCH2,I0I0FOR_CLRT,SPQ0IP0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRET4二分图最大匹配HUNGARY正向表形式/二分图最大匹配,HUNGARY算法,正向表形式,复杂度OME/返回最大匹配数,传入二分图大小M,N和正向表LIST,BUF只需一边/MATCH1,MATCH2返回一个最大匹配,未匹配顶点MATCH值为1INCLUDEDEFINEMAXN310DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTMAXNINTHUNGARYINTM,INTN,INTLIST,INTBUF,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,P,Q,RET0,I,J,K,LFOR_CLRMATCH1,_CLRMATCH2,I0I0FOR_CLRT,SPQ0IP0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRET5二分图最佳匹配KUHN_MUNKRAS邻接阵形式/二分图最佳匹配,KUHNMUNKRAS算法,邻接阵形式,复杂度OMMN/返回最佳匹配值,传入二分图大小M,N和邻接阵MAT,表示权值/MATCH1,MATCH2返回一个最佳匹配,未匹配顶点MATCH值为1/一定注意MDEFINEMAXN310DEFINEINF1000000000DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTNINTKUHN_MUNKRASINTM,INTN,INTMATMAXN,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,L1MAXN,L2MAXN,P,Q,RET0,I,J,KFORI0IL1IMATIJL1IFORI0I0JPMATCH2JKTJ,PMATCH1K,MATCH1KJIFMATCH1INEXTIFVTETOIFMATCHT2IFMATCHI013RETURNJ/27一般图匹配邻接表形式,邻接阵接口/一般图最大匹配,邻接表形式,复杂度ONE/返回匹配顶点对数,MATCH返回匹配,未匹配顶点MATCH值为1/传入图的顶点数N和邻接表LISTINCLUDEDEFINEMAXN100INTAUGINTN,VECTORLIST,INTMATCH,INTV,INTNOWINTT,RET0,RVNOW1/FORELISTNOWEEENEXTFORR0RLISTMAXNFORI0I2IFMATCHI0RETURNJ/28一般图匹配邻接阵形式/一般图最大匹配,邻接阵形式,复杂度ON3/返回匹配顶点对数,MATCH返回匹配,未匹配顶点MATCH值为1/传入图的顶点数N和邻接阵MATDEFINEMAXN100INTAUGINTN,INTMATMAXN,INTMATCH,INTV,INTNOWINTI,RET0VNOW1FORI0I2IFMATCHI0RETURNJ/29一般图匹配正向表形式/一般图最大匹配,正向表形式,复杂度ONE15/返回匹配顶点对数,MATCH返回匹配,未匹配顶点MATCH值为1/传入图的顶点数N和正向表LIST,BUFDEFINEMAXN100INTAUGINTN,INTLIST,INTBUF,INTMATCH,INTV,INTNOWINTI,T,RET0VNOW1FORILISTNOWI2IFMATCHI0RETURNJ/2三图论_生成树1最小生成树KRUSKAL邻接表形式/无向图最小生成树,KRUSKAL算法,邻接表形式,复杂度OMLOGM/返回最小生成树的长度,传入图的大小N和邻接表LIST/可更改边权的类型,EDGE2返回树的构造,用边集表示/如果图不连通,则对各连通分支构造最小生成树,返回总长度INCLUDE16DEFINEMAXN200DEFINEINF1000000000TYPEDEFDOUBLEELEM_TSTRUCTEDGE_TINTFROM,TOELEM_TLENEDGE_TNEXTDEFINE_UFIND_RUNXFORPTXXPX,PTPXPXXDEFINE_RUN_BOTH_UFIND_RUNI_UFIND_RUNJSTRUCTUFINDINTPMAXN,TVOIDINITMEMSETP,0,SIZEOFPVOIDSET_FRIENDINTI,INTJ_RUN_BOTHPIIJ0JINTIS_FRIENDINTI,INTJ_RUN_BOTHRETURNIJDEFINE_CPA,BALEN1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2CNEXTIFITO17EAI,EBTTO,ELENTLEN,HINSEWHILEMDEFINEMAXN200DEFINEINF1000000000TYPEDEFDOUBLEELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_UFIND_RUNXFORPTXXPX,PTPXPXXDEFINE_RUN_BOTH_UFIND_RUNI_UFIND_RUNJSTRUCTUFINDINTPMAXN,TVOIDINITMEMSETP,0,SIZEOFPVOIDSET_FRIENDINTI,INTJ_RUN_BOTHPIIJ0JINTIS_FRIENDINTI,INTJ_RUN_BOTHRETURNIJDEFINE_CPA,BALEN1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2C1HPHP1,P1HPEINTDELHEAP_TFOR19EHP1,C2CNEXTIFVTTORETURNRET4最小生成树PRIMBINARY_HEAP正向表形式/无向图最小生成树,PRIM算法二分堆,正向表形式,复杂度OMLOGM/返回最小生成树的长度,传入图的大小N和正向表LIST,BUF/可更改边权的类型,PRE返回树的构造,用父结点表示,根节点第一个PRE值为1/必须保证图的连通的DEFINEMAXN200DEFINEINF1000000000TYPEDEFDOUBLEELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_CPA,BAD1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2C1HMAPINDPINDP1PHP1,P1HMAPINDPIPE21INTDELINTI,ELEM_TIFINRETURN0FOREHPIP1HMAPINDPINDP1PHP1,P1FORC2CNEXTIFVTTORETURNRET6最小生成树PRIMMAPPED_HEAP正向表形式/无向图最小生成树,PRIM算法映射二分堆,正向表形式,复杂度OMLOGN/返回最小生成树的长度,传入图的大小N和正向表LIST,BUF/可更改边权的类型,PRE返回树的构造,用父结点表示,根节点第一个PRE值为1/必须保证图的连通的DEFINEMAXN200DEFINEINF1000000000TYPEDEFDOUBLEELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_CPA,BA1HMAPINDPINDP1PHP1,P1HMAPINDPIPEINTDELINTI,ELEM_TIFINRETURN0FOREHPIP1HMAPINDPINDP1PHP1,P1FORC2CDEFINEMAXN120DEFINEINF1000000000TYPEDEFINTELEM_TELEM_TEDMONDSINTN,ELEM_TMATMAXN2,INTPREELEM_TRET0INTCMAXN2MAXN2,LMAXN2,PMAXN2,MN,T,I,J,KFORI0INPREKPREMFORI0IEMAXNFORI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1INTLIMIT_MAX_FLOWINTN,INTMATMAXN,INTBFMAXN,INTSOURCE,INTSINK,INTFLOWMAXNINTI,J,SK,KSIFSOURCESINKRETURNINFFORMATNN1MATN1NMATNNMATN1N1I0IEMAXNFORI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0I0FLOWPREI1IDSINK,IPREI1ELSE29FLOWIPREI1DSINK,IPREI1INTLIMIT_MIN_FLOWINTN,INTMATMAXN,INTBFMAXN,INTSOURCE,INTSINK,INTFLOWMAXNINTI,J,SK,KSIFSOURCESINKRETURNINFFORMATNN1MATN1NMATNNMATN1N1I0I存放所有以I相邻的点,包括反向边DEFINEMAXN100DEFINEINF1000000000INTMAX_FLOWINTN,INTMATMAXN,VECTORLIST,INTSOURCE,INTSINK,INTFLOWMAXNINTPREMAXN,QUEMAXN,DMAXN,P,Q,T,I,J,RIFSOURCESINKRETURNINFFORI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0IEMAXNIFSOURCESINKRETURNINFFORI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0ICJJIIFJCIELSEFLOWIPREI1DSINK,IPREI1FORJI0I03最短路径单源DIJKSTRA_BFS正向表形式/单源最短路径,用于路权相等的情况,DIJKSTRA优化为BFS,正向表形式,复杂度OM/求出源S到所有点的最短路经,传入图的大小N和正向表LIST,BUF,边权值LEN/返回到各点最短距离MIN和路径PRE,PREI记录S到I路径上I的父结点,PRES1/可更改路权类型,但必须非负且相等DEFINEMAXN200DEFINEINF1000000000TYPEDEFINTELEM_TVOIDDIJKSTRAINTN,INTLIST,INTBUF,ELEM_TLEN,INTS,ELEM_TMIN,INTPREINTI,QUEMAXN,F0,R0,P1,L1,TFORI0I1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2CNEXTIFVTTO5最短路径单源DIJKSTRABINARY_HEAP正向表形式/单源最短路径,DIJKSTRA算法二分堆,正向表形式,复杂度OMLOGM/求出源S到所有点的最短路经,传入图的大小N和正向表LIST,BUF/返回到各点最短距离MIN和路径PRE,PREI记录S到I路径上I的父结点,PRES1/可更改路权类型,但必须非负DEFINEMAXN200DEFINEINF1000000000TYPEDEFINTELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_CPA,BAD1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2C1HMAPINDPINDP1PHP1,P1HMAPINDPIPEINTDELINTI,ELEM_TIFINRETURN0FOREHPIP1HMAPINDPINDP1PHP1,P1FORC2CNEXTIFVTTO7最短路径单源DIJKSTRAMAPPED_HEAP正向表形式/单源最短路径,DIJKSTRA算法映射二分堆,正向表形式,复杂度OMLOGN/求出源S到所有点的最短路经,传入图的大小N和正向表LIST,BUF/返回到各点最短距离MIN和路径PRE,PREI记录S到I路径上I的父结点,PRES1/可更改路权类型,但必须非负DEFINEMAXN200DEFINEINF1000000000TYPEDEFINTELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_CPA,BA1HMAPINDPINDP1PHP1,P1HMAPINDPIPEINTDELINTI,ELEM_TIFINRETURN0FOREHPIP1HMAPINDPINDP1PHP1,P1FORC2CDFNNOWKEYCNT0I,KEYCNT1NOWIFLOWIDFNNOWIFNOWROOTELSEIFNOWROOTRDELSEIFDFNI1RETURNRET423无向图块BFS邻接阵形式/无向图的块,DFS邻接阵形式,ON2/每产生一个块调用DUMMY/传入图的大小N和邻接阵MAT,不相邻点边权0DEFINEMAXN100INCLUDEVOIDDUMMYINTN,INTAFORINTI0IDFNNOWFORSTSP1,A0NOW,M1STSPIAMSTSPDUMMYM,AELSEIFDFNI0IWHILEMATNOWIMATNOWI,MATINOWFIND_PATH_UN,MAT,I,STEP,PATHPATHSTEPNOWVOIDFIND_PATH_DINTN,INTMATMAXN,INTNOW,INTFORIN1I0IWHILEMATNOWIMATNOWIFIND_PATH_DN,MAT,I,STEP,PATHPATHSTEPNOWINTEUCLID_PATHINTN,INTMATMAXN,INTSTART,INTPATHINTRET0FIND_PATH_UN,MAT,START,RET,PATH/FIND_PATH_DN,MAT,START,RET,PATHRETURNRET2前序表转化/将用边表示的树转化为前序表示的树/传入节点数N和邻接表LIST,邻接表必须是双向的,会在函数中释放/PRE返回前序表,MAP返回前序表中的节点到原来节点的映射DEFINEMAXN10000STRUCTNODEINTTONODENEXTVOIDPRENODEINTN,NODELIST,INTPRE,INTMAP,INTV,INTNOW,INTLAST,INTINTPIDFORVMAPPNOW1,PREPLASTLISTNOWTLISTNOW,LISTNOWTNEXTIFVTTOPRENODEN,LIST,PRE,MAP,V,TTO,P,ID47VOIDMAKEPREINTN,NODELIST,INTPRE,INTMAPINTVMAXN,ID0,IFORI0I0IIFCISETI1IFPREI1CPREI1RETRETURNRET/最大边独立集INTMAX_EDGE_INDEPENDENTINTN,INTPRE,INTSETINTCMAXN,I,RET0FORI0I0IIFCICPREI1RETRETURNRET/最小顶点覆盖集INTMIN_NODE_COVERINTN,INTPRE,INTSETINTCMAXN,I,RET0FORI0I0IIFCI48CPREI1RETRETURNRET/最小顶点支配集INTMIN_NODE_DOMINANTINTN,INTPRE,INTSETINTCMAXN,I,RET0FORI0I0IIFCICPREI1IFPREPREI1CPREPREI1ELSESETI1RETRETURNRET4拓扑排序邻接阵形式/拓扑排序,邻接阵形式,复杂度ON2/如果无法完成排序,返回0,否则返回1,RET返回有序点列/传入图的大小N和邻接阵MAT,不相邻点边权0DEFINEMAXN100INTTOPOSORTINTN,INTMATMAXN,INTRETINTDMAXN,I,J,KFORI0ICJJIIFJCIIFJCIIFJCIIFJCIFOR_CLRMATCH1,_CLRMATCH2,I0I0FOR_CLRT,SPQ0IP0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRETINLINEINTPATH_COVERINTN,INTMATMAXN,INTPRE,INTNEXTRETURNNHUNGARYN,MAT,NEXT,PRE八图论_NP搜索1最大团N小于64FASTER/WISHINGBONESACM/ICPCROUTINELIBRARYMAXIMUMCLIQUESOLVER/INCLUDEUSINGSTDVECTOR/CLIQUESOLVERCALCULATESBOTHSIZEANDCONSITUTIONOFMAXIMUMCLIQUE/USESBITOPERATIONTOACCELERATESEARCHING/GRAPHSIZELIMITIS63,THEGRAPHSHOULDBEUNDIRECTED/CANOPTIMIZETOCALCULATEONEACHCOMPONENT,ANDSORTONVERTEXDEGREES/CANBEUSEDTOSOLVEMAXIMUMINDEPENDENTSETCLASSCLIQUEPUBLICSTATICCONSTLONGLONGONE1STATICCONSTLONGLONGMASK11ICLIQUEDELETEBITS/SEARCHROUTINEBOOLSEARCHINTSTEP,INTSIZE,LONGLONGMORE,LONGLONGCON/SOLVEMAXIMUMCLIQUEANDRETURNSIZEINTSIZECLIQUEVECTOR/SOLVEMAXIMUMCLIQUEANDRETURNCONSTITUTIONVECTORCONSCLIQUEVECTOR/SEARCHROUTINE/STEPISNODEID,SIZEISCURRENTSOLUTION,MOREISAVAILABLEMASK,CONSISCONSTITUTIONMASKBOOLCLIQUESEARCHINTSTEP,INTSIZE,LONGLONGMORE,LONGLONGCONSIFSTEPN/ANEWSOLUTIONREACHEDTHISSIZESIZETHISCONSCONSRETURNTRUELONGLONGNOWONE0LONGLONGNEXTMOREIFSIZEBITSNEXTLONGLONGNEXTMOREIFSIZEBITSNEXT56RETURNFALSE/SOLVEMAXIMUMCLIQUEANDRETURNSIZEINTCLIQUESIZECLIQUEVECTOR/GENERATEMASKVECTORSFORINTI0I0MASKI|ONE0ISEARCHI1,1,MASKI,ONECLIQUECONSCLIQUEVECTORVECTORRETFORINTI0I0RETPUSH_BACKIRETURNRET2最大团/最大团/返回最大团大小和一个方案,传入图的大小N和邻接阵MAT/MATIJ为布尔量DEFINEMAXN60VOIDCLIQUEINTN,INTU,INTMATMAXN,INTSIZE,INTIFNIFSIZECU0MAXMAXSIZEFORI0I0IFORVN0,JI1JVOIDDUMMYINTA,INTNINTICOUT0KNIFORJI1J0IPITNI,T/NIFORIN1IIFORJI1J0JIFPJKCOMBNJ,MI1TK,J6组合公式1CM,NCM,MN2CM,NCM1,NCM1,N1DERANGEMENTDNN11/11/21/31N/NN1DN2DN1QNDNDN1求和公式,K1N1SUMKNN1/22SUM2K1N23SUMK2NN12N1/64SUM2K12N4N21/35SUMK3NN1/226SUM2K13N22N217SUMK4NN12N13N23N1/308SUMK5N2N122N22N1/129SUMKK1NN1N2/310SUMKK1K2NN1N2N3/412SUMKK1K2K3NN1N2N3N4/5十数值计算1定积分计算ROMBERG/ROMBERG求定积分输入积分区间A,B，被积函数FX,Y,Z输出积分结果FX,Y,Z示例DOUBLEF0DOUBLEX,DOUBLEL,DOUBLETRETURNSQRT10LLTTCOSTXCOSTX/DOUBLEINTEGRALDOUBLEA,DOUBLEB,DOUBLEFDOUBLEX,DOUBLEY,DOUBLEZ,DOUBLEEPS,DOUBLEL,DOUBLETDOUBLEROMBERGDOUBLEA,DOUBLEB,DOUBLEFDOUBLEX,DOUBLEY,DOUBLEZ,DOUBLEEPS,DOUBLEL,DOUBLETDEFINEMAX_N100062INTI,J,TEMP2,MINDOUBLEH,R2MAX_N,TEMP4FORI0IMINRETURNR1I1H050TEMP22FORJ0J0IPPXCI1RETURNPINTNEWTONDOUBLEX0,DOUBLER,DOUBLEC,DOUBLECP,INTN,DOUBLEA,DOUBLEB,DOUBLEEPSINTMAX_ITERATION1000INTI1DOUBLEX1,X2,FP,EPS2EPS/100X1X0WHILEI10RETURN0X2X1X2/FPIFFABSX1X2BRETURN0RX2RETURN1X1X2IRETURN0DOUBLEPOLYNOMIAL_ROOTDOUBLEC,INTN,DOUBLEA,DOUBLEB,DOUBLEEPSDOUBLECPINTIDOUBLEROOTCPDOUBLECALLOCN,SIZEOFDOUBLEFORIN1I0ICPII1CI1IFABROOTAABBROOTIFNEWTONA,FREECPIFFABSROOT0IAIAICIAI1XICIXI1XN1CN1X0AN1XN2XN1/CN1A0AN1AN2BN1FORINTIN2I0IXIAIXN1十一几何1多边形INCLUDEINCLUDEDEFINEMAXN1000DEFINEOFFSET10000DEFINEEPS1E8DEFINEZEROXX0XXEPS1XEPSTBARYCENTERP0,PI,PI1RETXTXT2RETYTYT2T1T2IFFABST1EPSRETX/T1,RETY/T1RETURNRET2多边形切割/多边形切割/可用于半平面交DEFINEMAXN100DEFINEEPS1E8DEFINEZEROXX0XXEPS69POINTINTERSECTIONPOINTU1,POINTU2,POINTV1,POINTV2POINTRETU1DOUBLETU1XV1XV1YV2YU1YV1YV1XV2X/U1XU2XV1YV2YU1YU2YV1XV2XRETXU2XU1XTRETYU2YU1YTRETURNRET/将多边形沿L1,L2确定的直线切割在SIDE侧切割,保证L1,L2,SIDE不共线VOIDPOLYGON_CUTINTINTM0,IFORI0IDEFINEEPS1E8DEFINEZEROXX0XXEPSINTSAME_SIDEPOINTP1,POINTP2,POINTL1,POINTL2RETURNXMULTL1,P1,L2XMULTL1,P2,L2EPS/判两点在线段异侧,点在线段上返回0INTOPPOSITE_SIDEPOINTP1,POINTP2,LINELRETURNXMULTLA,P1,LBXMULTLA,P2,LBL2XEPS/计算CROSSPRODUCTP1P0XP2P0DOUBLEXMULTPOINTP1,POINTP2,POINTP0RETURNP1XP0XP2YP0YP2XP0XP1YP0YDOUBLEXMULTDOUBLEX1,DOUBLEY1,DOUBLEX2,DOUBLEY2,DOUBLEX0,DOUBLEY0RETURNX1X0Y2Y0X2X0Y1Y0/计算三角形面积,输入三顶点DOUBLEAREA_TRIANGLEPOINTP1,POINTP2,POINTP3RETURNFABSXMULTP1,P2,P3/2DOUBLEAREA_TRIANGLEDOUBLEX1,DOUBLEY1,DOUBLEX2,DOUBLEY2,DOUBLEX3,DOUBLEY3RETURNFABSXMULTX1,Y1,X2,Y2,X3,Y3/2/计算三角形面积,输入三边长DOUBLEAREA_TRIANGLEDOUBLEA,DOUBLEB,DOUBLECDOUBLESABC/2RETURNSQRTSSASBSC77/计算多边形面积,顶点按顺时针或逆时针给出DOUBLEAREA_POLYGONINTN,POINTPDOUBLES10,S20INTIFORI0ICONSTDOUBLEPIACOS1/计算圆心角LAT表示纬度,90PIPIDLNGPIPIIFDLNGPIDLNGPIPIDLNGLAT1PI/180,LAT2PI/180RETURNACOSCOSLAT1COSLAT2COSDLNGSINLAT1SINLAT2/计算距离,R为球半径DOUBLELINE_DISTDOUBLER,DOUBLELNG1,DOUBLELAT1,DOUBLELNG2,DOUBLELAT2DOUBLEDLNGFABSLNG1LNG2PI/180WHILEDLNGPIPIDLNGPIPIIFDLNGPIDLNGPIPIDLNGLAT1PI/180,LAT2PI/180RETURNRSQRT22COSLAT1COSLAT2COSDLNGSINLAT1SINLAT2/计算球面距离,R为球半径INLINEDOUBLESPHERE_DISTDOUBLER,DOUBLELNG1,DOUBLELAT1,DOUBLELNG2,DOUBLELAT2RETURNRANGLELNG1,LAT1,LNG2,LAT27三角形INCLUDESTRUCTPOINTDOUBLEX,YSTRUCTLINEPOINTA,B78DOUBLEDISTANCEPOINTP1,POINTP2RETURNSQRTP1XP2XP1XP2XP1YP2YP1YP2YPOINTINTERSECTIONLINEU,LINEVPOINTRETUADOUBLETUAXVAXVAYVBYUAYVAYVAXVBX/UAXUBXVAYVBYUAYUBYVAXVBXRETXUBXUAXTRETYUBYUAYTRETURNRET/外心POINTCIRCUMCENTERPOINTA,POINTB,POINTCLINEU,VUAXAXBX/2UAYAYBY/2UBXUAXAYBYUBYUAYAXBXVAXAXCX/2VAYAYCY/2VBXVAXAYCYVBYVAYAXCXRETURNINTERSECTIONU,V/内心POINTINCENTERPOINTA,POINTB,POINTCLINEU,VDOUBLEM,NUAAMATAN2BYAY,BXAXNATAN2CYAY,CXAXUBXUAXCOSMN/2UBYUAYSINMN/2VABMATAN2AYBY,AXBXNATAN2CYBY,CXBXVBXVAXCOSMN/2VBYVAYSINMN/2RETURNINTERSECTIONU,V79/垂心POINTPERPENCENTERPOINTA,POINTB,POINTCLINEU,VUACUBXUAXAYBYUBYUAYAXBXVABVBXVAXAYCYVBYVAYAXCXRETURNINTERSECTIONU,V/重心/到三角形三顶点距离的平方和最小的点/三角形内到三边距离之积最大的点POINTBARYCENTERPOINTA,POINTB,POINTCLINEU,VUAXAXBX/2UAYAYBY/2UBCVAXAXCX/2VAYAYCY/2VBBRETURNINTERSECTIONU,V/费马点/到三角形三顶点距离之和最小的点POINTFERMENTPOINTPOINTA,POINTB,POINTCPOINTU,VDOUBLESTEPFABSAXFABSAYFABSBXFABSBYFABSCXFABSCYINTI,J,KUXAXBXCX/3UYAYBYCY/3WHILESTEP1E10FORK0KDISTANCEV,ADISTANCEV,BDISTANCEV,CUV80RETURNU8三维几何/三维几何函数库INCLUDEDEFINEEPS1E8DEFINEZEROXX0XXEPSINTDOT_INPLANE_EXPOINT3P,POINT3S1,POINT3S2,POINT3S3RETURNDOT_INPLANE_INP,S1,S2,S3/判两点在线段同侧,点在线段上返回0,不共面无意义INTSAME_SIDEPOINT3P1,POINT3P2,LINE3LRETURNDMULTXMULTSUBTLA,LB,SUBTP1,LB,XMULTSUBTLA,LB,SUBTP2,LBEPSINTSAME_SIDEPOINT3P1,POINT3P2,POINT3L1,POINT3L2RETURNDMULTXMULTSUBTL1,L2,SUBTP1,L2,XMULTSUBTL1,L2,SUBTP2,L2EPS/判两点在线段异侧,点在线段上返回0,不共面无意义INTOPPOSITE_SIDEPOINT3P1,POINT3P2,LINE3LRETURNDMULTXMULTSUBTLA,LB,SUBTP1,LB,XMULTSUBTLA,LB,SUBTP2,LBEPSINTSAME_SIDEPOINT3P1,POINT3P2,POINT3S1,POINT3S2,POINT3S3RETURNDMULTPVECS1,S2,S3,SUBTP1,S1DMULTPVECS1,S2,S3,SUBTP2,S1EPS/判两点在平面异侧,点在平面上返回0INTOPPOSITE_SIDEPOINT3P1,POINT3P2,PLANE3SRETURNDMULTPVECS,SUBTP1,SADMULTPVECS,SUBTP2,SADEFINEEPS1E8DEFINEZEROXX0XX011RET011VOID_GRAHAMINTN,POINTP,INTFORP1P2P0,I1IEPS|ZEROP1YPIYP2X/N,P2Y/NPKP0,P0P1QSORTP1,N1,SIZEOFPOINT,GRAHAM_CPFORCH0P0,CH1P1,CH2P2,SI3I2VOID_GRAHAMINTN,POINTP,INTFORP1P2P0,I1IEPS|ZEROP1YPIYP2X/N,P2Y/NPKP0,P0P1QSORTP1,N1,SIZEOFPOINT,GRAHAM_CPFORCH0P0,CH1P1,CH2P2,SI3I2ELSEIFPOINTAXPOINTBXEPSRETURN1ELSERETURN0INT_WIPESAMEPOINTP,INTNINTI,KQSORTP,N,SIZEOFPOINT,WIPESAME_CPFORKI1I0XXSTRUCTPOINTINTX,YINTGCDINTA,INTBRETURNBGCDB,ABA/多边形上的网格点个数INTGRID_ONEDGEINTN,POINTPINTI,RET0FORI0IDEFINEEPS1E8STRUCTPOINTDOUBLEX,YDOUBLEXMULTPOINTP1,POINTP2,POINTP0RETURNP1XP0XP2YP0YP2XP0XP1YP0YDOUBLEDISTANCEPOINTP1,POINTP2RETURNSQRTP1XP2XP1XP2XP1YP2YP1YP2YDOUBLEDISPTOLINEPOINTP,POINTL1,POINTL291RETURNFABSXMULTP,L1,L2/DISTANCEL1,L2POINTINTERSECTIONPOINTU1,POINTU2,POINTV1,POINTV2POINTRETU1DOUBLETU1XV1XV1YV2YU1YV1YV1XV2X/U1XU2XV1YV2YU1YU2YV1XV2XRETXU2XU1XTRETYU2YU1YTRETURNRET/判直线和圆相交,包括相切INTINTERSECT_LINE_CIRCLEPOINTC,DOUBLER,POINTL1,POINTL2RETURNDISPTOLINEC,L1,L2EPS|T2EPSTXL1YL2YTYL2XL1XRETURNXMULTL1,C,TXMULTL2,