Acm竞赛常用算法与数据结构

经过我初步的整理,一个比较完整的归类已经完成,现在发布给大家,希望可以方便大家练习,如有不足,还请大家见谅,这个可能会随时有更新,请大家注意.如果有什么要求或补充的可以跟贴提出,勿水!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!OJ上的一些水题(可用来练手和增加自信)(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成树算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)拓扑排序(poj1094)(5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串(poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书page149):1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)(poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化(poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)同时由于个人练习的时候可能有些偏向性,可能上面的总结不是很全,还请大家提出和指正,而且由于ACM 的题目中专门针对某个算法的题目可能比较少出现,所以上面的分类中的题有可能有多种解法或者是一些算法的综合,这都不会影响大家做题,希望练习的同学能够认真,扎实地训练,做到真正的理解算法,掌握算法.同时在论坛上还有许多前辈的分类,总结,大家也可以按自己的情况采用.注意FTP上有很多的资料,希望大家好好地利用.如果同学能在明年暑假前能掌握上面大部分算法,那你也基本上达到了训练的目的,到暑假的时候你就可以选择自己比较喜欢的方面进行加深和强化,而且同学们不要觉得看算法的证明是很麻烦的事,这可以加强你的思维能力,这在ACM中也很重要.同时也希望老队员能帮助我整理习题和题目分类.同时ACM的题目是没有范围的,只能在平时中多积累多练习,多比别人多努力一点,你就会比别人多一线希望.动态规划、搜索方面的资料Dp状态设计与方程总结1.不完全状态记录<1>青蛙过河问题<2>利用区间dp2.背包类问题<1> 0-1背包，经典问题<2>无限背包，经典问题<3>判定性背包问题<4>带附属关系的背包问题<5> + -1背包问题<6>双背包求最优值<7>构造三角形问题<8>带上下界限制的背包问题(012背包)3.线性的动态规划问题<1>积木游戏问题<2>决斗（判定性问题）<3>圆的最大多边形问题<4>统计单词个数问题<5>棋盘分割<6>日程安排问题<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)<8>方块消除游戏(某区间可以连续消去求最大效益)<9>资源分配问题<10>数字三角形问题<11>漂亮的打印<12>邮局问题与构造答案<13>最高积木问题<14>两段连续和最大<15>2次幂和问题<16>N个数的最大M段子段和<17>交叉最大数问题4.判定性问题的dp(如判定整除、判定可达性等)<1>模K问题的dp<2>特殊的模K问题，求最大(最小)模K的数<3>变换数问题5.单调性优化的动态规划<1>1-SUM问题<2>2-SUM问题<3>序列划分问题(单调队列优化)6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)<1>凸多边形的三角剖分问题<2>乘积最大问题<3>多边形游戏(多边形边上是操作符,顶点有权值)<4>石子合并(N^3/N^2/NLogN各种优化)7.贪心的动态规划<1>最优装载问题<2>部分背包问题<3>乘船问题<4>贪心策略<5>双机调度问题Johnson算法8.状态dp<1>牛仔射击问题(博弈类)<2>哈密顿路径的状态dp<3>两支点天平平衡问题<4>一个有向图的最接近二部图9.树型dp<1>完美服务器问题(每个节点有3种状态)<2>小胖守皇宫问题<3>网络收费问题<4>树中漫游问题<5>树上的博弈<6>树的最大独立集问题<7>树的最大平衡值问题<8>构造树的最小环1001 1037 1048 1049 1051 1067 1115 1151 1201 1205 1216 1240 1241 1242 1251 1292 1331 1334 1337 1338 1350 1365 1382 1383 1394 1402 1405 1414 1494 1514 1622 1715 1730 1755 1760 1763 1796 1813 1879 1889 1904 1915 1949 2001 2022 2099 2104 2108 2172 2176 2201 2208 2321 2345 2351 2376 2388 2405 2417 2433模拟问题：1006 1009 1012 1016 1019 1023 1026 1028 1038 1042 1045 1051 1056 1057 1058 1061 1065 1066 1068 1072 1073 1078 1087 1088 1097 1098 1099 1103 1111 1121 1124 1126 1128 1133 1138 1146 1152 1154 1160 1175 1178 1187 1194 1207 1222 1224 1244 1259 1267 1274 1275 1277 1278 1279 1281 1282 1294 1295 1300 1308 1317 1324 1339 1351 1362 1392 1393 1397 1398 1399 1400 1402 1432 1434 1444 1452 1475 1487 1493 1497 1517 1526 1527 1530 1531 1552 1569 1573 1592 1601 1610 1623 1631 1641 1652 1657 1659 1682 1692 1700 1702 1707 1708 1712 1728 1732 1737 1746 1747 1750 1752 1754 1758 1764 1768 1774 1797 1799 1804 1807 1811 1822 1824 1831 1834 1837 1838 1842 1844 1845 1854 1858 1862 1870 1881 1884 1889 1896 1906 1921 1951 1969 1978 2000 2022 2040 2046 2047 2051 2072 2084 2101 2112 2131 2133 2138 2148 2153 2156 2160 2164 2172 2178 2184 2185 2187 2189 21932196 2201 2204 2208 2211 2212 2220 2229 2233 2239 2240 2261 2262 2269 2277 2288 2301 2309 2311 2312 2316 2320 2321 2322 2328 2330 2350 2389 2405 2410 2414 2420 2421 2483 2508 2560 2569 2572 2593 2613 2617 2680 2681 2731 2732 2743动态规划：1013 1022 1025 1027 1074 1076 1093 1094 1100 1107 1108 1136 1149 1183 1196 1200 1206 1227 1234 1245 1249 1250 1276 1303 1346 1353 1366 1368 1387 1424 1425 1428 1446 1448 1449 1454 1459 1462 1463 1470 1474 1475 1483 1484 1490 1499 1503 1512 1515 1520 1524 1539 1540 1554 1563 1567 1579 1602 1607 1611 1629 1638 1642 1651 1666 1695 1713 1717 1731 1733 1736 1738 1743 1756 1757 1787 1792 1800 1819 1853 1864 1877 1880 1893 1913 1918 1925 1953 1985 1986 1988 1991 1995 2002 2014 2025 2042 2058 2059 2067 2068 2069 2081 2096 2127 2136 2142 2144 2156 2180 2189 2202 2206 2213 2224 2227 2242 2244 2254 2255 2264 2271 2278 2280 2281 2283 2284 2297 2319 2337 2338 2341 2349 2353 2354 2366 2372 2374 2397 2401 2402 2414 2422 2424 2432 2498 2501 2521 2522 2527 2536 2547 2561 2563 2565 2568 2581 2591 2598 2604 2621 2624 2625 2626 2641 2642 2667 2673 2683 2685 2692 2702 2710 2711 2734 2739 2744 2745字符串处理问题：1002 1004 1005 1008 1016 1019 1046 1048 1049 1050 1051 1052 1053 1054 1055 1056 1061 1063 1086 1089 1091 1094 1099 1101 1103 1111 1115 1117 1118 1120 1123 1125 1126 1129 1130 1136 1139 1143 1150 1151 1152 1154 1159 1160 1168 1170 1177 1178 1179 1180 1181 1184 1188 1189 1190 1191 1192 1195 1197 1243 1295 1315 1325 1392 1582 1698 1707 1720 1729 1808 1831 1854 1858 1905 1963 1969 1970 1984搜索问题：1002 1003 1008 1031 1038 1039 1041 1060 1063 1069 1080 1083 1088 1089 1103 1144 1155 1190 1204 1217 1229 1249 1297 1301 1344 1355 1361 1412 1415 1435 1443 1457 1479 1505 1518 1530 1593 1649 1671 1675 1686 1709 1711 1719 1742 1832 1909 1935 1940 1977 1984 2031 2033 2043 2053 2093 2103 2110 2128 2165 2233 2241 2252 2276 2288 2355 2372 2374 2412 2416 2418 2437 2440 2442 2466 2471 2475 2477 2509 2515 2531 2534 2580 2588 2594 2631 2633 2688数论问题：1007 1028 1088 1113 1133 1160 1222 1278 1284 1312 1314 1385 1489 1526 1530 1569 1577 1596 1601 1652 1657 1712 1797 1842 1889 1906 1951 20002022 2028 2060 2095 2105 2156 2189 2212 2233 2277 2288 2305 2316 2320 2330 2360 2371 2400 2410 2414几何问题：1010 1032 1037 1041 1081 1090 1104 1123 1139 1165 1199 1426 1439 1460 1472 1597 1608 1648 1683 1910 2015 2102 2107 2157 2228 2234 2318 2335 2347 2352 2361 2370 2375 2394 2403树型结构问题：1011 1038 1043 1062 1141 1159 1167 1203 1319 1335 1387 1406 1481 1511 1542 1586 1610 1635 1674 1700 1752 1788 1805 1809 1900 1944 1955 1959 1965 1990 2243 2425图表问题：1015 1030 1082 1084 1085 1105 1119 1127 1130 1140 1203 1311 1377 1420 1453 1465 1492 1589 1798 1802 1919 1935 2016 2236 2238 2281 2326匹配问题：1002 1059 1077 1137 1140 1157 1197 1231 1364 1516 1525 1576 1626 1654 1882 2067 2192 2221 2223 2333 2362 2404pku题目分类麻烦题：1697, 1712, 1713, 1720, 1729, 1765, 1772, 1858, 1872, 1960, 1963, 2050, 2122, 2162, 2219, 2237,简单题目：1000, 1003, 1004, 1005, 1007, 1046, 1207, 1226, 1401, 1504, 1552, 1607, 1657, 1658, 1674, 1799, 1862, 1906, 1922, 1929, 1931, 1969, 1976, 2000, 2005, 2017, 2027, 2070, 2101, 2105, 2109, 2116, 2136, 2160, 2190, 2232, 2234, 2275, 2301, 2350, 2363, 2389, 2393, 2413, 2419,推荐：1063, 1064, 1131, 1140, 1715, 2163,杂题：1014, 1218, 1316, 1455, 1517, 1547, 1580, 1604, 1663, 1678, 1749, 1804, 2013, 2014, 2056, 2059, 2100, 2188, 2189, 2218, 2229, 2249, 2290, 2302, 2304, 2309, 2313, 2316, 2323, 2326, 2368, 2369, 2371, 2402, 2405, 2407,推荐：1146, 1147, 1148, 1171, 1389, 1433, 1468, 1519, 1631, 1646, 1672, 1681, 1700, 1701, 1705, 1728, 1735, 1736, 1752, 1754, 1755, 1769, 1781, 1787, 1796, 1797, 1833, 1844, 1882, 1933, 1941, 1978, 2128, 2166, 2328, 2383, 2420,高精度：1001, 1220, 1405, 1503,排序：1002, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 2388, 2418, 推荐：1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,搜索容易：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349, 推荐：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,数据结构容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395,不易：1145, 1177, 1195, 1227, 1661, 1834,推荐：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 2119, 2274,动态规划容易：1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926, 1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029, 2033, 2063, 2081, 2082, 2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385, 2392, 2424,不易：1019, 1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707, 1733, 1737, 1837, 1850, 1920, 1934, 1937, 1964, 2039, 2138, 2151, 2161, 2178,推荐：1015, 1635, 1636, 1671, 1682, 1692, 1704, 1717, 1722, 1726, 1732, 1770, 1821,1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411,字符串：1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782, 1790, 1866, 1888, 1896, 1951, 2003, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408,贪心：1042, 1065, 1230, 1323, 1477, 1716, 1784,图论容易：1161, 1164, 1258, 1175, 1308, 1364, 1776, 1789, 1861, 1939, 1940, 1943, 2075, 2139, 2387, 2394, 2421,不易：1041, 1062, 1158, 1172, 1201, 1275, 1718, 1734, 1751, 1904, 1932, 2173, 2175, 2296,网络流：1087, 1273, 1698, 1815, 2195,匹配：1274, 1422, 1469, 1719, 2060, 2239,Euler：1237, 1637, 1394, 2230,推荐：2049, 2186,计算几何容易：1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318,不易：1685, 1687, 1696, 1873, 1901, 2172, 2333,凸包：1113, 1228, 1794, 2007, 2187,模拟容易：1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 1791, 1835, 1970, 2317, 2325, 2390,不易：1012, 1082, 1099, 1114, 1642, 1677, 1684, 1886,数学容易：1061, 1091, 1142, 1289, 1305, 1306, 1320, 1565, 1665, 1666, 1730, 1894, 1914, 2006, 2042, 2142, 2158, 2174, 2262, 2305, 2321, 2348,不易：1067, 1183, 1430, 1759, 1868, 1942, 2167, 2171, 2327,推荐：1423, 1450, 1640, 1702, 1710, 1721, 1761, 1830, 1930, 2140,。

A C M程序设计常用算法与数据结构参考ACM程序设计常用算法与数据结构参考Tomsdinary目录前言 (7)排序算法 (8)插入排序 (8)选择排序 (10)冒泡排序 (11)希尔排序 (12)随机化快速排序 (14)归并排序 (18)堆排序 (19)大整数处理 (22)包含头文件 (22)定义 (22)实现 (24)流输出 (24)流输入 (24)赋值 (25)转换函数 (26)规范化符号化 (26)带符号乘法 (27)无符号取模 (27)整数乘法 (28)整数加法 (30)带符号加法 (32)浮点乘法 (33)浮点加法 (35)带符号减法 (36)整数减法 (37)浮点减法 (40)带符号比较 (41)无符号比较 (42)无符号乘方 (43)带符号乘方 (43)使用方法 (44)高级数据结构 (44)普通二叉搜素树 (44)包含头文件 (44)定义 (44)实现 (47)删树 (50)插入元素到树 (50)复制树 (53)求树的高度 (56)删除元素 (57)使用方法 (59)基本线段树模式 (60)基本并查集模式 (62)散列实现的一种方式参考 (63)定义与实现 (63)使用方法 (72)堆 (72)包含头文件 (72)定义与实现 (73)使用方法 (75)图相关算法 (76)图的深度优先和广度优先算法举例 (76)无向图最小生成树的Kruskal算法举例 (78)无向图最小生成树的Prim算法举例 (80)有向图的单源最短路径Dijkstra算法举例 (82)有向图的多源最短路径Floyd算法举例 (84)拓扑排序举例 (85)AOE网的算法举例 (88)求图的一个中心算法举例 (92)求图的P个中心算法举例 (95)SPFA算法举例 (99)割顶和块的算法举例 (102)计算几何算法 (105)向量模 (105)向量点积 (105)向量叉积 (105)左右判断 (106)相交判断 (106)正规相交交点 (106)判断多边形凸 (107)任意多变形面积 (107)凸包问题的快包实现举例 (108)STL算法参考 (113)accumulate() (113)adjacent_difference() (113)adjacent_find() (114)binary_search() (114)copy() (115)copy_backward() (115)count() (116)count_if() (116)equal() (116)fill() (118)fill_n() (118)find() (118)find_if() (118)find_end() (119)find_first_of() (119)for_each() (120)generate() (120)generate_n() (120)includes() (121)inner_product() (121)inplace_merge() (122)iter_swap() (122)lexicographical_compare() (123)lower_bound() (124)max() (124)max_element() (125)min() (125)min_element() (125)merge() (126)mismatch() (126)next_permutation() (127)nnth_element() (127)partial_sort() (128)partial_sort_copy() (129)partial_sum() (129)prev_permutation() (130)random_shuffle() (130)remove() (131)remove_copy() (132)remove_if() (132)remove_copy_if() (132)replace() (133)replace_copy() (133)replace_if() (133)replace_copy_if() (133)reverse() (134)reverse_copy() (134)rotate() (134)rotate_copy() (135)search() (135)search_n() (135)set_difference() (136)set_symmetric_difference() (137)set_union() (138)sort() (138)stable_partition() (139)stable_sort() (139)swap() (140)swap_range() (140)transform() (140)unique() (141)unique_copy() (142)upper_bound() (142)make_heap() (143)pop_heap() (143)push_heap() (144)sort_heap() (144)字符串处理 (145)KMP算法举例 (145)C++语言可用头文件 (147)<algorithm> (147)<bitset> (147)<complex> (147)<deque> (147)<exception> (147)<fstream> (147)<functional> (147)<iomanip> (148)<ios> (148)<iosfwd> (148)<iostream> (148)<iso646.h> (148)<istream> (148)<iterator> (148)<limits> (149)<list> (149)<locale> (149)<map> (149)<memory> (149)<new> (149)<numeric> (149)<ostream> (150)<queue> (150)<set> (150)<sstream> (150)<stdexcept> (150)<streambuf> (150)<string> (151)<strstream> (151)<utility> (151)<valarray> (151)<vector> (151)<cassert> (151)<cctype> (151)<cerrno> (151)<cfloat> (152)<ciso646> (152)<climits> (152)<clocale> (152)<cmath> (152)<csetjmp> (152)<csignal> (152)<cstdarg> (152)<cstddef> (152)<cstdio> (153)<cstdlib> (153)<cstring> (153)<ctime> (153)<cwchar> (153)<cwctype> (153)前言如今的程序设计已不再是个人英雄时代了，程序的设计和开发实施需要靠团队成员的积极配合和合作。

ACM必须的算法1.最短路(Floyd、Dijstra,BellmanFord)2.最小生成树(先写个prim,kruscal要用并查集，不好写)3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换第二阶段：练习复杂一点，但也较常用的算法。

：1. 二分图匹配（匈牙利），最小路径覆盖2. 网络流，最小费用流。

3. 线段树.4. 并查集。

5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp6.博弈类算法。

博弈树，二进制法等。

7.最大团，最大独立集。

8.判断点在多边形内。

9. 差分约束系统. 10. 双向广度搜索、A*算法，最小耗散优先.相关的知识图论：路径问题 0/1边权最短路径 BFS 非负边权最短路径（Dijkstra）可以用Dijkstra解决问题的特征负边权最短路径Bellman-Ford Bellman-Ford的Yen-氏优化差分约束系统 Floyd 广义路径问题传递闭包极小极大距离 / 极大极小距离 EulerPath / Tour 圈套圈算法混合图的 Euler Path / TourHamilton Path / Tour 特殊图的Hamilton Path / Tour 构造生成树问题最小生成树第k小生成树最优比率生成树 0/1分数规划度限制生成树连通性问题强大的DFS算法无向图连通性割点割边二连通分支有向图连通性强连通分支 2-SAT最小点基有向无环图拓扑排序有向无环图与动态规划的关系二分图匹配问题一般图问题与二分图问题的转换思路最大匹配有向图的最小路径覆盖0 / 1矩阵的最小覆盖完备匹配最优匹配稳定婚姻网络流问题网络流模型的简单特征和与线性规划的关系最大流最小割定理最大流问题有上下界的最大流问题循环流最小费用最大流 / 最大费用最大流弦图的性质和判定组合数学解决组合数学问题时常用的思想逼近递推 / 动态规划概率问题Polya定理计算几何 / 解析几何计算几何的核心：叉积 / 面积解析几何的主力：复数基本形点直线，线段多边形凸多边形 / 凸包凸包算法的引进，卷包裹法Graham扫描法水平序的引进，共线凸包的补丁完美凸包算法相关判定两直线相交两线段相交点在任意多边形内的判定点在凸多边形内的判定经典问题最小外接圆近似O(n)的最小外接圆算法点集直径旋转卡壳，对踵点多边形的三角剖分数学 / 数论最大公约数Euclid算法扩展的Euclid算法同余方程 / 二元一次不定方程同余方程组线性方程组高斯消元法解mod 2域上的线性方程组整系数方程组的精确解法矩阵行列式的计算利用矩阵乘法快速计算递推关系分数分数树连分数逼近数论计算求N的约数个数求phi(N)求约数和快速数论变换……素数问题概率判素算法概率因子分解数据结构组织结构二叉堆左偏树二项树胜者树跳跃表样式图标斜堆reap统计结构树状数组虚二叉树线段树矩形面积并圆形面积并关系结构Hash表并查集路径压缩思想的应用 STL中的数据结构vectordequeset / map动态规划 / 记忆化搜索动态规划和记忆化搜索在思考方式上的区别最长子序列系列问题最长不下降子序列最长公共子序列最长公共不下降子序列一类NP问题的动态规划解法树型动态规划背包问题动态规划的优化四边形不等式函数的凸凹性状态设计规划方向线性规划常用思想二分最小表示法串KMPTrie结构后缀树/后缀数组 LCA/RMQ有限状态自动机理论排序选择/冒泡快速排序堆排序归并排序基数排序拓扑排序排序网络中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化 (poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487,poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,po j2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj333 6,poj3315,poj2148,poj1263)初期:一.基本算法:(1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法. (4)递推.(5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,po j2240)(3)最小生成树算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)拓扑排序 (poj1094)(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串 (poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排)(poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,po j2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书 page149):1.E[j]=opt{D+w(i,j)}(poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1 ]+zij} (最长公共子序列)(poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)。

ACM常用算法ACM常考算法ACM小组内部预定函数Ver 2.0 by IcyFenix数学问题：1.精度计算――大数2.精度计算――乘法（大数3.精度计算――乘法（大阶乘5.精度计算――减法9.快速傅立叶变换（FFT）字符串处理：1.字符串替换计算几何：1.叉乘法求任意多边形面积5.射向法判断点是否在多边形内部9.点到线段最短距离数论：1.x的二进制长度5.求解模线性方程组(中国余数定理) 图论：1.Prim算法求最小生成树排序/查找：1.快速排序数据结构：1.顺序队列乘小数）6.任意进制转换10.Ronberg算法计算积分2.字符串查找2.求三角形面积6.判断点是否在线段上10.求两直线的交点2.返回x的二进制表示中从低到高的第i位6.筛法素数产生器2.Dijkstra算法求单源最短路径2.希尔排序2.顺序栈数乘大数）4.精度计算――加法7.最大公约数、最小公倍数8.组合序列11.行列式计算12.求排列组合数3.字符串截取3.两矢量间角度4.两点距离（2D、3D）7.判断两线段是否相交8.判断线段与直线是否相交11.判断一个封闭图形是12.Graham扫描法寻凹集还是凸集找凸包3.模取幂运算4.求解模线性方程7.判断一个数是否素数3.Bellman-ford算法求4.Floyd算法求每对单源最短路径节点间最短路径3.选择法排序4.二分查找3.链表4.链栈ACM常考算法5.二叉树一、数学问题1.精度计算――大数阶乘语法：int result=factorial(int n); 参数：n：n 的阶乘返回阶乘结果的位数值：注意：源程序：本程序直接输出n!的结果，需要返回结果请保留long a[] 需要math.hint factorial(int n){long a[__];int i,j,l,c,m=0,w; a=1;for(i=1;ii++) { c=0;for(j=0;jj++) {a[j]=a[j]*i+c; c=a[j]/__; a[j]=a[j]%__; }if(c0) {m++;a[m]=c;} }w=m*4+log10(a[m])+1;printf(“\n%ld",a[m]);for(i=m-1;ii--) printf("%4.4ld",a[i]);return w; }2.精度计算――乘法（大数乘小数）语法：mult(char c[],char t[],int m); 参数：c[]：被乘数，用字符串表示，位数不限t[]：结果，用字符串表示m：乘数，限定10以内返回null 值：注意：需要string.hACM常考算法源程序：void mult(char c[],char t[],int m) {int i,l,k,flag,add=0; char s; l=strlen(c);for (i=0;ii++)s[l-i-1]=c[i]-'0';for (i=0;ii++) {k=s[i]*m+add;if (k=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;ii++)t[l-1-i]=s[i]+'0'; t[l]='\0'; }3.精度计算――乘法（大数乘大数）语法：mult(char a[],char b[],char s[]); 参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回null 值：注意：源程序：空间复杂度为o(n^2) 需要string.hvoid mult(char a[],char b[],char s[]) {int i,j,k=0,alen,blen,sum=0,res={0},flag=0; char result;alen=strlen(a);blen=strlen(b);for (i=0;ialen;i++)for (j=0;jblen;j++) res[i][j]=(a[i]-'0')*(b[j]-'0'); for (i=alen-1;ii--) {for (j=blen-1;jj--) sum=sum+res[i+blen-j-1][j]; result[k]=sum%10; k=k+1;ACM常考算法sum=sum/10; }for (i=blen-2;ii--) {for (j=0;jj++) sum=sum+res[i-j][j]; result[k]=sum%10; k=k+1;sum=sum/10; }if (sum!=0) {result[k]=sum;k=k+1;} for (i=0;ii++) result[i]+='0';for (i=k-1;ii--) s[i]=result[k-1-i]; s[k]='\0';while(1) {if (strlen(s)!=strlen(a)s=='0') strcpy(s,s+1); elsebreak; } }4.精度计算――加法语法：add(char a[],char b[],char s[]); 参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回null 值：注意：源程序：空间复杂度为o(n^2) 需要string.hvoid add(char a[],char b[],char back[]) {int i,j,k,up,x,y,z,l; char *c; if (strlen(a)strlen(b)) l=strlen(a)+2;elsel=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(i0) x='0'; else x=a[i];ACM常考算法if(j0) y='0'; else y=b[j]; z=x-'0'+y-'0'; if(up) z+=1;if(z9) {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;kk--) back[i++]=c[k]; back[i]='\0'; }5.精度计算――减法语法：sub(char s1[],char s2[],char t[]); 参数：s1[]：被减数，用字符串表示，位数不限s2[]：减数，用字符串表示，位数不限t[]：结果，用字符串表示返回null 值：注意：源程序：默认s1=s2，程序未处理负数情况需要string.hvoid 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;ii--,l1--) {if (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) {s1[k]+=10;s1[k-1]-=1;k--;} while(l1=0) {t[l1]=s1[l1];l1--;} loop:if (t=='0') {ACM常考算法l1=strlen(s1);for (i=0;il1-1;i++) t[i]=t[i+1]; t[l1-1]='\0'; goto loop; }if (strlen(t)==0) {t='0';t='\0';} }6.任意进制转换语法：conversion(char s1[],char s2[],long d1,long d2); 参数：s[]：原进制数字，用字符串表示s2[]：转换结果，用字符串表示d1：原进制数d2：需要转换到的进制数返回null 值：注意：源程序：高于9的位数用大写'A'～'Z'表示，2～16位进制通过验证void conversion(char s[],char s2[],long d1,long d2) {long i,j,t,num; char c; num=0;for (i=0;s[i]!='\0';i++) {if (s[i]='9's[i]='0') t=s[i]-'0';else t=s[i]-'A'+10;num=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;jj++){c=s2[j];s2[j]=s[i-j];s2[i-j]=c;} s2[i+1]='\0'; }7.最大公约数、最小公倍数ACM常考算法语法：resulet=hcf(int a,int b)、result=lcd(int a,int b) 参数：a：int a，求最大公约数或最小公倍数b：int b，求最大公约数或最小公倍数返回返回最大公约数（hcf）或最小公倍数（lcd）值：注意：源程序：lcd 需要连同hcf 使用int hcf(int a,int b) {int r=0; while(b!=0) {r=a%b; a=b; b=r; }return(a); }lcd(int u,int v,int h) {return(u*v/h); }8.组合序列语法：m_of_n(int m,int n1,int m1,int* a,int head) 参数：m：组合数C的上参数n1：组合数C的下参数m1：组合数C的上参数，递归之用*a：1～n的整数序列数组head：头指针返回null 值：注意：源程序：*a需要自行产生初始调用时，m=m1、head=0调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);ACM常考算法void m_of_n(int m,int n1,int m1,int* a,int head) {int i,t;if(m10 || m1n1)return; if(m1==n1) {for(i=0;ii++) couta[i]' '; // 输出序列cout'\n'; 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[],int l,int il); 参数：pr[n]：输入的实部pi[n]：数入的虚部n，k：满足n=2^k fr[n]：输出的实部fi[n]：输出的虚部l：逻辑开关，0 FFT，1 ifFTil：逻辑开关，0 输出按实部/虚部；1 输出按模/幅角返回null 值：注意：源程序：需要math.hvoid 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=1.0; pi=0.0; p=6.__-__6/(1.0*n);pr=cos(p); pi=-sin(p);ACM常考算法if (l!=0) pi=-pi; for (i=2; i=n-1; i++) {p=pr[i-1]*pr; q=pi[i-1]*pi;s=(pr[i-1]+pi[i-1])*(pr+pi); pr[i]=p-q; pi[i]=s-p-q; }for (it=0; it=n-2; it=it+2) {vr=fr[it]; vi=fi[it];fr[it]=vr+fr[it+1]; fi[it]=vi+fi[it+1];fr[it+1]=vr-fr[it+1]; fi[it+1]=vi-fi[it+1]; }m=n/2; nv=2;for (l0=k-2; l0 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]; s=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)for (i=0; i=n-1; i++) {pr[i]=sqrt(fr[i]*fr[i]+fi[i]*fi[i]); if (fabs(fr[i])0.000001*fabs(fi[i])) {if ((fi[i]*fr[i])0) pi[i]=90.0; else pi[i]=-90.0; } elsepi[i]=atan(fi[i]/fr[i])*360.0/6.__-__6; } return; }10.Ronberg算法计算积分语法：result=integral(double a,double b);ACM常考算法参数：a：积分上限b：积分下限function积分函数f：返回值：f在（a,b）之间的积分值注意：源程序：function f(x)需要自行修改，程序中用的是sina(x)/x 需要math.h 默认精度要求是1e-5double 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(xb) {s+=f(x); x+=h; }t2=(t1+h*s)/2.0; s2=t2+(t2-t1)/3.0; if(k==1) {k++;h/=2.0;t1=t2;s1=s2; goto loop; }c2=s2+(s2-s1)/15.0; if(k==2){c1=c2;k++;h/=2.0; t1=t2;s1=s2; goto loop; }r2=c2+(c2-c1)/63.0; if(k==3){r1=r2; c1=c2;k++; h/=2.0;t1=t2;s1=s2; goto loop; }while(fabs(1-r1/r2)1e-5){ r1=r2;c1=c2;k++; h/=2.0;ACM常考算法t1=t2;s1=s2; goto 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的余子式*/if(n2) {for(z=0;zz++) {for(j=0;jj++)for(k=0;kk++)if(k=z) b[j][k]=s[j+1][k+1]; else b[j][k]=s[j+1][k];if(z%2==0) r=s[z]*js(b,n-1); /*递归调用*/ else r=(-1)*s[z]*js(b,n-1); total=total+r; } }else if(n==2)total=s*s-s*s; return total; }12.求排列组合数语法：result=P(long n,long m); / result=long C(long n,long m); 参数：m：排列组合的上系数n：排列组合的下系数返回排列组合数ACM常考算法值：注意：源程序：符合数学规则：m＝nlong P(long n,long m) {long p=1; while(m!=0){p*=n;n--;m--;} return p; }long C(long n,long m) {long i,c=1; i=m;while(i!=0){c*=n;n--;i--;} while(m!=0) {c/=m;m--;} return c; }二、字符串处理1.字符串替换语法：replace(char str[],char key[],char swap[]); 参数：str[]：在此源字符串进行替换操作key[]：被替换的字符串，不能为空串swap[]替换的字符串，可以为空串，为空串表示在源字符中删除key[] ：返回null 值：注意：源程序：默认str[]长度小于1000，如否，重新设定设定tmp大小需要string.hvoid replace(char str[],char key[],char swap[]) {int l1,l2,l3,i,j,flag; char tmp; l1=strlen(str); l2=strlen(key);l3=strlen(swap);for (i=0;i=l1-l2;i++)ACM常考算法{flag=1;for (j=0;jj++)if (str[i+j]!=key[j]) {flag=0;break;} if (flag) {strcpy(tmp,str);strcpy(tmp[i],swap);strcpy(tmp[i+l3],str[i+l2]); strcpy(str,tmp); i+=l3-1;l1=strlen(str); } } }2.字符串查找语法：result=strfind(char str[],char key[]); 参数：str[]：在此源字符串进行查找操作key[]：被查找的字符串，不能为空串返回如果查找成功，返回key在str中第一次出现的位置，否则返回-1 值：注意：源程序：需要string.hint strfind(char str[],char key[]) {int l1,l2,i,j,flag; l1=strlen(str); l2=strlen(key);for (i=0;i=l1-l2;i++) {flag=1;for (j=0;jj++)if (str[i+j]!=key[j]) {flag=0;break;} if (flag)return i; }return -1; }3.字符串截取语法：mid(char str[],int start,int len,char strback[]) 参数：str[]：操作的目标字符串start：从第start个字符串开始，截取长度为len的字符ACM常考算法len：从第start个字符串开始，截取长度为len的字符strback[ 截取的到的字符]：返回值：0：超出字符串长度，截取失败；1：截取成功注意：需要string.h源程序：int mid(char str[],int start,int len,char strback[]) {int l,i,k=0; l=strlen(str);if (start+lenl)return 0; for (i=start;istart+len;i++) strback[k++]=str[i]; strback[k]='\0'; return 1; }三、计算几何1.叉乘法求任意多边形面积语法：result=polygonarea(Point *polygon,int N); 参数：*polyg多变形顶点数组on：N：多边形顶点数目返回多边形面积值：注意：源程序：支持任意多边形，凹、凸皆可多边形顶点输入时按顺时针顺序排列typedef struct { double x,y; } Point;double polygonarea(Point *polygon,int N) {int i,j;double area = 0;for (i=0;ii++) { j = (i + 1) % N;area += polygon[i].x * polygon[j].y; area -= polygon[i].y *polygon[j].x; }ACM常考算法area /= 2;return(area 0 ? -area : area); }2.求三角形面积语法：result=area3(float x1,float y1,float x2,float y2,float x3,float y3); 参数：x1～3：三角形3个顶点x坐标y1～3：三角形3个顶点y坐标返回三角形面积值：注意：源程序：需要math.hfloat area3(float x1,float y1,float x2,float y2,float x3,float y3) {float a,b,c,p,s;a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); b=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3)); c=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)); p=(a+b+c)/2;s=sqrt(p*(p-a)*(p-b)*(p-c)); return s; }3.两矢量间角度语法：result=angle(double x1,double y1,double x2,double y2); 参数：x/y1～两矢量的坐标2：返回两的角度矢量值：注意：源程序：返回角度为弧度制，并且以逆时针方向为正方向需要math.h#define PI 3.__-__double angle(double x1,double y1,double x2,double y2) {ACM常考算法double dtheta,theta1,theta2; theta1 = atan2(y1,x1); theta2 =atan2(y2,x2); dtheta = theta2 - theta1; while (dtheta PI) dtheta -= PI*2; while (dtheta -PI) dtheta += PI*2; return(dtheta); }4.两点距离（2D、3D）语法：result=distance_2d(float x1,float x2,float y1,float y2); 参数：x/y/z1各点的x、y、z坐标～2：返回两点之间的距离值：注意：源程序：需要math.hfloat 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=insidepolygon(Point *polygon,int N,Point p); 参数：*polyg多边形顶点数组on：N：多边形顶点个数p：被判断点返回0：点在多边形内部；1：点在多边形外部值：注意：若p点在多边形顶点或者边上，返回值不确定，需另行判断ACM常考算法源程序：需要math.h#define MIN(x,y) (x y ? x : y)#define MAX(x,y) (x y ? x : y) typedef struct { double x,y; } Point;int insidepolygon(Point *polygon,int N,Point p) {int counter = 0; int i;double xinters; Point p1,p2;p1 = polygon;for (i=1;ii++) { p2 = polygon[i % N];if (p.y MIN(p1.y,p2.y)) {if (p.y = MAX(p1.y,p2.y)) {if (p.x = MAX(p1.x,p2.x)) { if (p1.y != p2.y) { xinters =(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(__); elsereturn(INSIDE); }6.判断点是否在线段上语法：result=Pointonline(Point p1,Point p2,Point p); 参数：p1、p2：线段的两个端点p：被判断点返回0：点在不在线段上；1：点在线段上值：注意：源程若p线段端点上返回1 需要math.hACM常考算法序：#define MIN(x,y) (x y ? x : y)#define MAX(x,y) (x y ? x : y) typedef struct {double x,y; } Point;int FC(double x1,double x2) {if (x1-x20.000002x1-x2-0.000002)return 1;else return 0; }int Pointonline(Point p1,Point p2,Point p) {double 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)return 0;if ((MIN(p1.x,p2.x)=p.xp.x=MAX(p1.x,p2.x))(MIN(p1.y,p2.y)=p.yp.y=MAX(p1.y,p2.y))) return 1;else return 0; }7.判断两线段是否相交语法：result=sectintersect(Point p1,Point p2,Point p3,Point p4); 参数：p1～两条线段的四个端点4：返回0：两线段不相交；1：两线段相交；2两线段首尾相接值：注意：源程序：p1!=p2;p3!=p4;#define MIN(x,y) (x y ? x : y)#define MAX(x,y) (x y ? x : y) typedef struct { double x,y; } Point;int lineintersect(Point p1,Point p2,Point p3,Point p4) {Point tp1,tp2,tp3; if((p1.x==p3.xp1.y==p3.y)||(p1.x==p4.xp1.y==p4.y)||(p2.x==p3.xp2.y==p3.y )||(p2.x==p4.xp2.y==p4.y)) return 2; //快速排斥试验if((MIN(p1.x,p2.x)p3.xp3.xMAX(p1.x,p2.x)MIN(p1.y,p2.y)p3.yMAX(p1.y,p2.y))|| ACM常考算法(MIN(p1.x,p2.x)p4.xp3.xMAX(p1.x,p2.x)MIN(p1.y,p2.y)p3.yMAX(p1.y,p2.y))) ; else return 0;//跨立试验tp1.x=p1.x-p3.x; tp1.y=p1.y-p3.y; tp2.x=p4.x-p3.x; tp2.y=p4.y-p3.y; tp3.x=p2.x-p3.x; tp3.y=p2.y-p3.y;if ((tp1.__tp2.y-tp1.y*tp2.x)*(tp2.__tp3.y-tp2.y*tp3.x)=0)return 1;else return 0; }8.判断线段与直线是否相交语法：result=lineintersect(Point p1,Point p2,Point p3,Point p4); 参数：p1、p2：线段的两个端点p3、p4：直线上的两个点返回0：线段直线不相交；1：线段和直线相交值：注意：源程序：如线段在直线上，返回1typedef struct { double x,y; } Point;int lineintersect(Point p1,Point p2,Point p3,Point p4) {Point tp1,tp2,tp3; tp1.x=p1.x-p3.x; tp1.y=p1.y-p3.y; tp2.x=p4.x-p3.x; tp2.y=p4.y-p3.y; tp3.x=p2.x-p3.x; tp3.y=p2.y-p3.y;if ((tp1.__tp2.y-tp1.y*tp2.x)*(tp2.__tp3.y-tp2.y*tp3.x)=0)return 1;else return 0; }9.点到线段最短距离语法：result=mindistance(Point p1,Point p2,Point q); 参数：p1、线段的两个端点p2：ACM常考算法q：判断点返回点q到线段p1p2的距离值：注意：源程序：需要math.h#define MIN(x,y) (x y ? x : y)#define MAX(x,y) (x y ? x : y) typedef struct { double x,y; } Point;double mindistance(Point p1,Point p2,Point q) {int flag=1; double k; Point s;if (p1.x==p2.x) {s.x=p1.x;s.y=q.y;flag=0;} if (p1.y==p2.y){s.x=q.x;s.y=p1.y;flag=0;} if (flag) {k=(p2.y-p1.y)/(p2.x-p1.x);s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1); s.y=k*(s.x-p1.x)+p1.y; }if (MIN(p1.x,p2.x)=s.xs.x=MAX(p1.x,p2.x))return sqrt((q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y)); elsereturnMIN(sqrt((q.x-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y-p1.y)),sqrt((q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y))); }10.求两直线的交点语法：result=mindistance(Point p1,Point p2,Point q); 参数：p1～直线上不相同的两点p4：*p：通过指针返回结果返回1：两直线相交；2：两直线平行值：注意：源程序：如需要判断两线段交点，检验k和对应k1（注释中）的值是否在0～1之间，用在0～1之间的那个求交点ACM常考算法typedef struct { double x,y; } Point;int linecorss(Point p1,Point p2,Point p3,Point p4,Point *p) {double k; //同一直线if ((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)==0(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)==0) return 2; //平行，不同一直线if ((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)==0) return 0;k=((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));//k1=((p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)); (*p).x=p1.x+k*(p2.x-p1.x);(*p).y=p1.y+k*(p2.y-p1.y); return 1;//有交点}11.判断一个封闭图形是凹集还是凸集语法：result=convex(Point *p,int n); 参数：*p：封闭曲线顶点数组n：封闭曲线顶点个数返回1：凸集；-1：凹集；0：曲线不符合要求无法计算值：注意：源程序：默认曲线为简单曲线：无交叉、无圈typedef struct { double x,y; } Point;。

ACM竞赛中的数学方法初步(一)ACM竞赛是一个从数字、数据结构到计算机原理的广泛内容的竞赛，也是一个需要创造性思维、快速计算和应用数学知识的竞赛。

数学概念和算法在ACM竞赛中起着重要的作用。

以下是一些ACM竞赛中基本的数学方法。

1.组合：组合即是从给定的数或对象中选择出若干个数或者对象并成一组的所有方案的总数，组合数常表示为C(n,m)。

在ACM竞赛中，组合数有很多应用，如背包问题、统计问题等。

2.排列：排列是指从n个不同的元素当中选取m个不同的元素进行排列，则有n!/(n-m)!种排列；如果选取的元素不相同，则每一个排列都是不同的，称为有序排列；反之，如果选取的元素相同，则每一个排列的不同之处只在于元素的排列顺序不同，称为无序排列。

3.数学运算：在ACM中，基本的数学运算有加减乘除，还包括取余操作（%），取模操作（mod）等。

如果这些操作未能掌握，通常需要进行一些练习，理解其计算过程。

4.递推公式：递推公式也称为递归公式。

在ACM竞赛中，很多算法都运用了递推公式，如斐波那契数列、卡特兰数等。

因此，了解这些递推公式的通项表达式和递推表达式有助于学习和掌握这些算法。

5.数论：数论是研究整数和整数间相互关系的一门数学学科。

在ACM竞赛中，数论经常出现在解决一些经典问题，如质数判定、最大公约数、最小公倍数等。

掌握数论知识可以帮助选手快速解决这些问题。

综上所述，ACM竞赛中的数学方法多种多样，从组合到数论，但所有的方法都是为了解决计算机科学中的问题。

因此，在考试之前，希望选手们能够了解这些基本的数学方法，不断提升自己的解题能力并勇攀高峰。

ACM程序设计常用算法与数据结构参考Tomsdinary目录前言 (5)排序算法 (7)插入排序 (7)选择排序 (8)冒泡排序 (9)希尔排序 (9)随机化快速排序 (11)归并排序 (13)堆排序 (15)大整数处理 (16)包含头文件 (16)定义 (16)实现 (18)流输出 (18)流输入 (19)赋值 (19)转换函数 (19)规范化符号化 (20)带符号乘法 (20)无符号取模 (20)整数乘法 (21)整数加法 (23)带符号加法 (24)浮点乘法 (25)浮点加法 (26)带符号减法 (27)整数减法 (28)浮点减法 (30)带符号比较 (31)无符号比较 (31)无符号乘方 (32)带符号乘方 (33)使用方法 (33)高级数据结构 (34)普通二叉搜素树 (34)定义 (34)实现 (36)删树 (38)插入元素到树 (38)复制树 (40)求树的高度 (42)求叶子的个数 (43)删除元素 (43)使用方法 (45)基本线段树模式 (45)基本并查集模式 (47)散列实现的一种方式参考 (48)定义与实现 (48)使用方法 (53)堆 (54)包含头文件 (54)定义与实现 (54)使用方法 (56)图相关算法 (56)图的深度优先和广度优先算法举例 (56)无向图最小生成树的Kruskal算法举例 (58)无向图最小生成树的Prim算法举例 (59)有向图的单源最短路径Dijkstra算法举例 (60)有向图的多源最短路径Floyd算法举例 (62)拓扑排序举例 (62)AOE网的算法举例 (64)求图的一个中心算法举例 (67)求图的P个中心算法举例 (69)SPFA算法举例 (71)割顶和块的算法举例 (73)计算几何算法 (75)向量模 (75)向量点积 (75)向量叉积 (75)左右判断 (76)相交判断 (76)正规相交交点 (76)判断多边形凸 (76)任意多变形面积 (77)凸包问题的快包实现举例 (77)STL算法参考 (81)accumulate() (81)adjacent_difference() (81)binary_search() (82)copy() (82)copy_backward() (83)count() (83)count_if() (83)equal() (83)equal_range() (84)fill() (84)fill_n() (84)find() (85)find_if() (85)find_end() (85)find_first_of() (86)for_each() (86)generate() (86)generate_n() (86)includes() (87)inner_product() (87)inplace_merge() (88)iter_swap() (88)lexicographical_compare() (88)lower_bound() (89)max() (89)max_element() (90)min() (90)min_element() (90)merge() (91)mismatch() (91)next_permutation() (91)nnth_element() (92)partial_sort() (92)partial_sort_copy() (93)partial_sum() (93)prev_permutation() (94)random_shuffle() (94)remove() (95)remove_copy() (95)remove_if() (95)remove_copy_if() (95)replace() (96)replace_copy() (96)replace_if() (96)replace_copy_if() (96)reverse_copy() (97)rotate() (97)rotate_copy() (97)search() (98)search_n() (98)set_difference() (98)set_intersection() (99)set_symmetric_difference() (99)set_union() (100)sort() (100)stable_partition() (101)stable_sort() (101)swap() (101)swap_range() (101)transform() (102)unique() (102)unique_copy() (103)upper_bound() (103)make_heap() (104)pop_heap() (104)push_heap() (104)sort_heap() (105)字符串处理 (105)KMP算法举例 (105)C++语言可用头文件 (106)<algorithm> (106)<bitset> (106)<complex> (107)<deque> (107)<exception> (107)<fstream> (107)<functional> (107)<iomanip> (107)<ios> (107)<iosfwd> (107)<iostream> (108)<iso646.h> (108)<istream> (108)<iterator> (108)<limits> (108)<list> (108)<locale> (108)<map> (109)<new> (109)<numeric> (109)<ostream> (109)<queue> (109)<set> (109)<sstream> (109)<stack> (110)<stdexcept> (110)<streambuf> (110)<string> (110)<strstream> (110)<utility> (110)<valarray> (110)<vector> (110)<cassert> (111)<cctype> (111)<cerrno> (111)<cfloat> (111)<ciso646> (111)<climits> (111)<clocale> (111)<cmath> (111)<csetjmp> (111)<csignal> (112)<cstdarg> (112)<cstddef> (112)<cstdio> (112)<cstdlib> (112)<cstring> (112)<ctime> (112)<cwchar> (112)<cwctype> (112)前言如今的程序设计已不再是个人英雄时代了，程序的设计和开发实施需要靠团队成员的积极配合和合作。

acm常用算法和数据结构1.引言1.1 概述概述部分是对整篇文章进行简要介绍，让读者了解本文的主题和内容。

下面是对1.1概述部分的内容的编写建议：概述部分旨在向读者介绍本文的主要内容和目的。

本文主要讨论ACM （算法竞赛）中常用的算法和数据结构。

ACM常用算法和数据结构是指在解决各类计算机编程竞赛或算法题目时经常使用的，被广泛验证和应用的算法和数据结构。

本文主要分为引言、正文和结论三个部分。

引言部分描述了本文整体的构架和目的，正文部分详细介绍了常用算法和数据结构的分类和特点，结论部分对本文进行总结，并探讨了这些常用算法和数据结构在实际应用中的前景。

在正文部分的常用算法中，我们将介绍一些经典的排序算法，如冒泡排序、插入排序和快速排序等，同时还会讨论一些常见的查找算法，如顺序查找和二分查找等。

这些算法都有着不同的时间复杂度和空间复杂度，以及各自适用的场景。

在数据结构部分，我们将详细介绍数组和链表这两种最基础的数据结构。

数组是一种线性存储结构，可以用于存储同一类型的一组数据，并且支持随机访问。

链表则是由一系列节点组成的，每个节点包含数据和指向下一个节点的指针，链表常用于实现队列、栈和链表等数据结构。

最后在结论部分，我们将对本文进行总结，强调常用算法和数据结构在实际应用中的重要性和价值。

并探讨这些算法和数据结构在日常编程工作中的应用前景，以帮助读者更好地理解和应用这些常用算法和数据结构。

通过本文的学习，读者将能够掌握ACM竞赛中的常用算法和数据结构的基本原理和应用方法，进一步提升算法思维和编程能力，为解决实际问题提供高效的解决方案。

文章结构部分的内容可以包括以下内容：文章结构旨在为读者提供对整篇文章内容的整体把握，方便读者在需要时能够快速定位和浏览特定的内容部分。

以下是本文的整体结构：1. 引言1.1 概述1.2 文章结构1.3 目的2. 正文2.1 常用算法2.1.1 排序算法2.1.2 查找算法2.2 数据结构2.2.1 数组2.2.2 链表3. 结论3.1 总结常用算法和数据结构3.2 应用前景在本文中，首先在引言部分对整篇文章进行了概述，说明了文章的目的和内容。

ACM常见算法ACM算法⼀、数论算法 1．求两数的最⼤公约数 2．求两数的最⼩公倍数 3．素数的求法 A.⼩范围内判断⼀个数是否为质数： B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：⼆、图论算法1．最⼩⽣成树A.Prim算法：B.Kruskal算法：(贪⼼) 按权值递增顺序删去图中的边，若不形成回路则将此边加⼊最⼩⽣成树。

2.最短路径 A.标号法求解单源点最短路径： B.Floyed算法求解所有顶点对之间的最短路径： C. Dijkstra 算法：3.计算图的传递闭包4．⽆向图的连通分量 A.深度优先 B 宽度优先（种⼦染⾊法）5．关键路径⼏个定义：顶点1为源点，n为汇点。

a. 顶点事件最早发⽣时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0; b. 顶点事件最晚发⽣时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n); c. 边活动最早开始时间 Ee[I], 若边I由<j,k>表⽰，则Ee[I] = Ve[j]; d. 边活动最晚开始时间 El[I], 若边I由<j,k>表⽰，则El[I] = Vl[k] – w[j,k]; 若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。

求解⽅法： a. 从源点起topsort,判断是否有回路并计算Ve; b. 从汇点起topsort,求Vl; c. 算Ee 和 El;6．拓扑排序找⼊度为0的点，删去与其相连的所有边，不断重复这⼀过程。

例寻找⼀数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.7.回路问题 Euler回路(DFS) 定义：经过图的每条边仅⼀次的回路。

（充要条件：图连同且⽆奇点） Hamilton回路定义：经过图的每个顶点仅⼀次的回路。

ACM小组内部预定函数Ver 2.0 by IcyFenix 数学问题：1.精度计算——大数阶乘2.精度计算——乘法（大数乘小数）3.精度计算——乘法（大数乘大数）4.精度计算——加法5.精度计算——减法6.任意进制转换7.最大公约数、最小公倍数8.组合序列9.快速傅立叶变换（FFT）10.Ronberg算法计算积分11.行列式计算12.求排列组合数字符串处理：1.字符串替换2.字符串查找3.字符串截取计算几何：1.叉乘法求任意多边形面积2.求三角形面积3.两矢量间角度4.两点距离（2D、3D）5.射向法判断点是否在多边形内部6.判断点是否在线段上7.判断两线段是否相交8.判断线段与直线是否相交9.点到线段最短距离10.求两直线的交点11.判断一个封闭图形是凹集还是凸集12.Graham扫描法寻找凸包数论：1.x的二进制长度2.返回x的二进制表示中从低到高的第i位3.模取幂运算4.求解模线性方程5.求解模线性方程组(中国余数定理)6.筛法素数产生器7.判断一个数是否素数图论：1.Prim算法求最小生成树2.Dijkstra算法求单源最短路径3.Bellman-ford算法求单源最短路径4.Floyd算法求每对节点间最短路径排序/查找：1.快速排序2.希尔排序3.选择法排序4.二分查找数据结构：1.顺序队列2.顺序栈3.链表4.链栈5.二叉树一、数学问题1.精度计算——大数阶乘语法：int result=factorial(int n);参数：n： n 的阶乘返回值： 阶乘结果的位数注意：本程序直接输出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;j<=m;j++){a[j]=a[j]*i+c;c=a[j]/10000;a[j]=a[j]%10000;}if(c>0) {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[]： 结果，用字符串表示m： 乘数，限定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<l;i++)s[l-i-1]=c[i]-'0';for (i=0;i<l;i++){k=s[i]*m+add;if (k>=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<l;i++)t[l-1-i]=s[i]+'0';t[l]='\0';}3.精度计算——乘法（大数乘大数）语法：mult(char a[],char b[],char s[]);参数：a[]： 被乘数，用字符串表示，位数不限b[]： 乘数，用字符串表示，位数不限t[]： 结果，用字符串表示返回值： null注意：空间复杂度为 o(n^2)需要 string.h源程序：void mult(char a[],char b[],char s[]){int i,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0;char result[65];alen=strlen(a);blen=strlen(b);for (i=0;i<alen;i++)for (j=0;j<blen;j++) res[i][j]=(a[i]-'0')*(b[j]-'0');for (i=alen-1;i>=0;i--){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;j<=i;j++) sum=sum+res[i-j][j];result[k]=sum%10;k=k+1;sum=sum/10;}if (sum!=0) {result[k]=sum;k=k+1;}for (i=0;i<k;i++) result[i]+='0';for (i=k-1;i>=0;i--) s[i]=result[k-1-i];s[k]='\0';while(1){if (strlen(s)!=strlen(a)&&s[0]=='0')strcpy(s,s+1);elsebreak;}}4.精度计算——加法语法：add(char a[],char b[],char s[]);参数：a[]： 被乘数，用字符串表示，位数不限b[]： 乘数，用字符串表示，位数不限t[]： 结果，用字符串表示返回值： null注意：空间复杂度为 o(n^2)需要 string.h源程序：void add(char a[],char b[],char back[]){int i,j,k,up,x,y,z,l;char *c;if (strlen(a)>strlen(b)) l=strlen(a)+2; elsel=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(j<0) y='0'; else y=b[j];z=x-'0'+y-'0';if(up) z+=1;if(z>9) {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[]： 结果，用字符串表示注意：默认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--){if (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) {s1[k]+=10;s1[k-1]-=1;k--;}while(l1>=0) {t[l1]=s1[l1];l1--;}loop:if (t[0]=='0'){l1=strlen(s1);for (i=0;i<l1-1;i++) t[i]=t[i+1];t[l1-1]='\0';goto loop;}if (strlen(t)==0) {t[0]='0';t[1]='\0';}}6.任意进制转换语法：conversion(char s1[],char s2[],long d1,long d2);参数：s[]： 原进制数字，用字符串表示s2[]： 转换结果，用字符串表示d1： 原进制数d2： 需要转换到的进制数注意：高于9的位数用大写'A'～'Z'表示，2～16位进制通过验证 源程序：void conversion(char s[],char s2[],long d1,long d2){long i,j,t,num;char c;num=0;for (i=0;s[i]!='\0';i++){if (s[i]<='9'&&s[i]>='0') t=s[i]-'0'; elset=s[i]-'A'+10;num=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<i/2;j++){c=s2[j];s2[j]=s[i-j];s2[i-j]=c;}s2[i+1]='\0';}7.最大公约数、最小公倍数语法：resulet=hcf(int a,int b)、result=lcd(int a,int b)参数：a： int a，求最大公约数或最小公倍数b： int b，求最大公约数或最小公倍数返回值： 返回最大公约数（hcf）或最小公倍数（lcd）注意：lcd 需要连同 hcf 使用源程序：int hcf(int a,int b){int r=0;while(b!=0){r=a%b;a=b;b=r;}return(a);}lcd(int u,int v,int h){return(u*v/h);}8.组合序列语法：m_of_n(int m, int n1, int m1, int* a, int head)参数：m： 组合数C的上参数n1： 组合数C的下参数m1： 组合数C的上参数，递归之用*a： 1～n的整数序列数组head： 头指针返回值： null注意：*a需要自行产生初始调用时，m=m1、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(m1<0 || m1>n1) return;if(m1==n1){for(i=0;i<m;i++) cout<<a[i]<<' '; // 输出序列 cout<<'\n';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[],doublefi[],int l,int il);参数：pr[n]： 输入的实部pi[n]： 数入的虚部n，k： 满足n=2^kfr[n]： 输出的实部fi[n]： 输出的虚部l： 逻辑开关，0 FFT，1 ifFTil： 逻辑开关，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<=n-2; it=it+2){vr=fr[it]; vi=fi[it];fr[it]=vr+fr[it+1]; fi[it]=vi+fi[it+1];fr[it+1]=vr-fr[it+1]; fi[it+1]=vi-fi[it+1]; }m=n/2; nv=2;for (l0=k-2; l0>=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];s=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)for (i=0; i<=n-1; i++){pr[i]=sqrt(fr[i]*fr[i]+fi[i]*fi[i]);if (fabs(fr[i])<0.000001*fabs(fi[i])){if ((fi[i]*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-5源程序：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(x<b){s+=f(x);x+=h;}t2=(t1+h*s)/2.0;s2=t2+(t2-t1)/3.0;if(k==1){k++;h/=2.0;t1=t2;s1=s2;goto loop;}c2=s2+(s2-s1)/15.0;if(k==2){c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}r2=c2+(c2-c1)/63.0;if(k==3){r1=r2; c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}while(fabs(1-r1/r2)>1e-5){r1=r2;c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto 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<n;z++){for(j=0;j<n-1;j++)for(k=0;k<n-1;k++)if(k>=z)b[j][k]=s[j+1][k+1]; else b[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.求排列组合数语法：result=P(long n,long m); / result=long C(long n,long m);参数：m： 排列组合的上系数n： 排列组合的下系数返回值： 排列组合数注意：符合数学规则：m<＝n源程序：long P(long n,long m){long p=1;while(m!=0){p*=n;n--;m--;}return p;}long C(long n,long m){long i,c=1;i=m;while(i!=0){c*=n;n--;i--;}while(m!=0){c/=m;m--;}return c;}二、字符串处理1.字符串替换语法：replace(char str[],char key[],char swap[]);参数：str[]： 在此源字符串进行替换操作key[]： 被替换的字符串，不能为空串swap[]： 替换的字符串，可以为空串，为空串表示在源字符中删除key[]返回值： null注意：默认str[]长度小于1000，如否，重新设定设定tmp大小需要 string.h源程序：void 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;i<=l1-l2;i++){flag=1;for (j=0;j<l2;j++)if (str[i+j]!=key[j]) {flag=0;break;}if (flag){strcpy(tmp,str);strcpy(&tmp[i],swap);strcpy(&tmp[i+l3],&str[i+l2]);strcpy(str,tmp);i+=l3-1;l1=strlen(str);}}}2.字符串查找语法：result=strfind(char str[],char key[]);参数：str[]： 在此源字符串进行查找操作key[]： 被查找的字符串，不能为空串返回值： 如果查找成功，返回key在str中第一次出现的位置，否则返回-1注意：需要 string.h源程序：int strfind(char str[],char key[]){int l1,l2,i,j,flag;l1=strlen(str);l2=strlen(key);for (i=0;i<=l1-l2;i++){flag=1;for (j=0;j<l2;j++)if (str[i+j]!=key[j]) {flag=0;break;}if (flag) return i;}return -1;}3.字符串截取语法：mid(char str[],int start,int len,char strback[])参数：str[]： 操作的目标字符串start： 从第start个字符串开始，截取长度为len的字符len： 从第start个字符串开始，截取长度为len的字符strback[]： 截取的到的字符返回值： 0：超出字符串长度，截取失败；1：截取成功注意：需要 string.h源程序：int mid(char str[],int start,int len,char strback[]){int l,i,k=0;l=strlen(str);if (start+len>l) return 0;for (i=start;i<start+len;i++)strback[k++]=str[i];strback[k]='\0';return 1;}三、计算几何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;i<N;i++) {j = (i + 1) % N;area += polygon[i].x * polygon[j].y;area -= polygon[i].y * polygon[j].x;}area /= 2;return(area < 0 ? -area : area);}2.求三角形面积语法：result=area3(float x1,float y1,float x2,float y2,float x3,floaty3);参数：x1～3： 三角形3个顶点x坐标y1～3： 三角形3个顶点y坐标返回值： 三角形面积注意：需要 math.h源程序：float area3(float x1,float y1,float x2,float y2,floatx3,float y3){float a,b,c,p,s;a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));b=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));c=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));p=(a+b+c)/2;s=sqrt(p*(p-a)*(p-b)*(p-c));return s;}3.两矢量间角度语法：result=angle(double x1, double y1, double x2, double y2);参数：x/y1～两矢量的坐标2：返回值： 两的角度矢量注意：返回角度为弧度制，并且以逆时针方向为正方向需要 math.h源程序：#define PI 3.1415926double angle(double x1, double y1, double x2, double y2){double dtheta,theta1,theta2;theta1 = atan2(y1,x1);theta2 = atan2(y2,x2);dtheta = theta2 - theta1;while (dtheta > PI)dtheta -= PI*2;while (dtheta < -PI)dtheta += PI*2;return(dtheta);}4.两点距离（2D、3D）语法：result=distance_2d(float x1,float x2,float y1,float y2);参数：x/y/z1～各点的x、y、z坐标2：返回值： 两点之间的距离注意：需要 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,floatz2){return(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2)));}5.射向法判断点是否在多边形内部语法：result=insidepolygon(Point *polygon,int N,Point p);参数：*polygon： 多边形顶点数组N： 多边形顶点个数p： 被判断点返回值： 0：点在多边形内部；1：点在多边形外部注意：若p点在多边形顶点或者边上，返回值不确定，需另行判断需要 math.h源程序：#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct {double x,y;} Point;int insidepolygon(Point *polygon,int N,Point p){int counter = 0;int i;double x int ers;Point p1,p2;p1 = polygon[0];for (i=1;i<=N;i++) {p2 = polygon[i % N];if (p.y > MIN(p1.y,p2.y)) {if (p.y <= MAX(p1.y,p2.y)) {if (p.x <= MAX(p1.x,p2.x)) {if (p1.y != p2.y) {x int ers =(p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;if(p1.x == p2.x || p.x <= x int ers)counter++;}}}}p1 = p2;}if (counter % 2 == 0)return(OUTSIDE);elsereturn(INSIDE);}6.判断点是否在线段上语法：result=Pointonline(Point p1,Point p2,Point p);参数：p1、p2： 线段的两个端点p： 被判断点返回值： 0：点在不在线段上；1：点在线段上注意：若p线段端点上返回1需要 math.h源程序：#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct {double x,y;} Point;int FC(double x1,double x2){if (x1-x2<0.000002&&x1-x2>-0.000002) return 1; else return 0;}int Pointonline(Point p1,Point p2,Point p){double 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) return 0;if ((MIN(p1.x,p2.x)<=p.x&&p.x<=MAX(p1.x,p2.x))&&(MIN(p1.y,p2.y)<=p.y&&p.y<=MAX(p1.y,p2.y)))return 1; else return 0;}7.判断两线段是否相交语法：result=sectintersect(Point p1,Point p2,Point p3,Point p4);参数：p1～两条线段的四个端点4：返回0：两线段不相交；1：两线段相交；2两线段首尾相接值：注意：p1!=p2;p3!=p4;源程序：#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct {double x,y;} Point;int lineintersect(Point p1,Point p2,Point p3,Point p4){Point tp1,tp2,tp3;if((p1.x==p3.x&&p1.y==p3.y)||(p1.x==p4.x&&p1.y==p4.y)||(p2.x==p3.x&&p2.y==p3.y)|| (p2.x==p4.x&&p2.y==p4.y))return 2;//快速排斥试验if((MIN(p1.x,p2.x)<p3.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p3.y<MAX(p1.y,p2.y)) ||(MIN(p1.x,p2.x)<p4.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p3.y<MAX( p1.y,p2.y)));else return 0;//跨立试验tp1.x=p1.x-p3.x;tp1.y=p1.y-p3.y;tp2.x=p4.x-p3.x;tp2.y=p4.y-p3.y;tp3.x=p2.x-p3.x;tp3.y=p2.y-p3.y;if ((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0) return 1; else return 0;}8.判断线段与直线是否相交语法：result=lineintersect(Point p1,Point p2,Point p3,Point p4);参数：p1、p2： 线段的两个端点p3、p4： 直线上的两个点返回值： 0：线段直线不相交；1：线段和直线相交注意：如线段在直线上，返回 1源程序：typedef struct {double x,y;} Point;int lineintersect(Point p1,Point p2,Point p3,Point p4){Point tp1,tp2,tp3;tp1.x=p1.x-p3.x;tp1.y=p1.y-p3.y;tp2.x=p4.x-p3.x;tp2.y=p4.y-p3.y;tp3.x=p2.x-p3.x;tp3.y=p2.y-p3.y;if((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0)return 1; else return 0;}9.点到线段最短距离语法：result=mindistance(Point p1,Point p2,Point q);参数：p1、线段的两个端点p2：q： 判断点返回点q到线段p1p2的距离值：注意：需要 math.h源程序：#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct {double x,y;} Point;double mindistance(Point p1,Point p2,Point q){int flag=1;double k;Point s;if (p1.x==p2.x) {s.x=p1.x;s.y=q.y;flag=0;}if (p1.y==p2.y) {s.x=q.x;s.y=p1.y;flag=0;}if (flag){k=(p2.y-p1.y)/(p2.x-p1.x);s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1);s.y=k*(s.x-p1.x)+p1.y;}if (MIN(p1.x,p2.x)<=s.x&&s.x<=MAX(p1.x,p2.x))return sqrt((q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y));elsereturnMIN(sqrt((q.x-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y-p1.y)),sqrt((q.x-p2.x)*(q.x-p2.x )+(q.y-p2.y)*(q.y-p2.y)));}10.求两直线的交点语法：result=mindistance(Point p1,Point p2,Point q);参数：p1～直线上不相同的两点p4：*p通过指针返回结果：返回1：两直线相交；2：两直线平行值：注意：如需要判断两线段交点，检验k和对应k1（注释中）的值是否在0～1之间，用在0～1之间的那个求交点源程序：typedef struct {double x,y;} Point;int linecorss(Point p1,Point p2,Point p3,Point p4,Point *p){double k;//同一直线if ((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)==0&&(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)==0) return 2;//平行，不同一直线if ((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)==0) return 0;k=((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));//k1=((p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x) -(p4.x-p3.x)*(p2.y-p1.y));(*p).x=p1.x+k*(p2.x-p1.x);(*p).y=p1.y+k*(p2.y-p1.y);return 1;//有交点}11.判断一个封闭图形是凹集还是凸集语法：result=convex(Point *p,int n);参数：*p： 封闭曲线顶点数组n： 封闭曲线顶点个数返回值： 1：凸集；-1：凹集；0：曲线不符合要求无法计算注意：默认曲线为简单曲线：无交叉、无圈源程序：typedef struct {double x,y;} Point;int convex(Point *p,int n){int i,j,k;int flag = 0;double z;if (n < 3)return(0);for (i=0;i<n;i++) {j = (i + 1) % n;k = (i + 2) % n;z = (p[j].x - p[i].x) * (p[k].y - p[j].y);z -= (p[j].y - p[i].y) * (p[k].x - p[j].x);if (z < 0)flag |= 1;else if (z > 0)flag |= 2;if (flag == 3)return －1; //CONCAVE}if (flag != 0)return 1; //CONVEXelsereturn 0;}12.Graham扫描法寻找凸包语法：Graham_scan(Point PointSet[],Point ch[],int n,int &len);参数：PointSet输入的点集[]：ch[]： 输出的凸包上的点集，按照逆时针方向排列n： PointSet中的点的数目len： 输出的凸包上的点的个数返回值： null源程序：struct Point{float x,y;};float multiply(Point p1,Point p2,Point p0){return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));}float distance(Point p1,Point p2){return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));}void Graham_scan(Point PointSet[],Point ch[],int n,int &len){int i,j,k=0,top=2;Point tmp;for(i=1;i<n;i++)if((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x)))k=i;tmp=PointSet[0];PointSet[0]=PointSet[k];PointSet[k]=tmp;for (i=1;i<n-1;i++){k=i;for (j=i+1;j<n;j++)if ( (multiply(PointSet[j],PointSet[k],PointSet[0])>0) || ((multiply(PointSet[j],PointSet[k],PointSet[0])==0)&&(distance(PointSet[0],PointSet[j])<distance(PointSet[0],PointSet[k]))) )k=j;tmp=PointSet[i];PointSet[i]=PointSet[k];PointSet[k]=tmp;}ch[0]=PointSet[0];ch[1]=PointSet[1];ch[2]=PointSet[2];for (i=3;i<n;i++){while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;ch[++top]=PointSet[i];}len=top+1;}四、数论1.x的二进制长度语法：result=BitLength(int x);参数：x： 测长的x返回值： x的二进制长度源程序：int BitLength(int x){int d = 0;while (x > 0) {x >>= 1;d++;}return d;}2.返回x的二进制表示中从低到高的第i位语法：result=BitAt(int x, int i);参数：x： 十进制 xi： 要求二进制的第i位返回值： 返回x的二进制表示中从低到高的第i位注意：最低位为第一位源程序：int BitAt(int x, int i){return ( x & (1 << (i-1)) );}3.模取幂运算语法：result=Modular_Expoent(int a,int b,int n);参数：a、b、n： a^b mod n 的对应参数返回值： a^b mod n 的值注意：需要BitLength和BitAt源程序：int Modular_Expoent(int a,int b,int n){int i, y=1;for (i = BitLength(b); i > 0; i--){y = (y*y)%n;if (BitAt(b,i) > 0)y = (y*a)%n;}return y;}4.求解模线性方程语法：result＝modular_equation(int a,int b,int n);参数：a、b、n： ax=b (mod n) 的对应参数返回值： 方程的解源程序：int ext_euclid(int a,int b,int &x,int &y) //求gcd(a,b)=ax+by{int t,d;if (b==0) {x=1;y=0;return a;}d=ext_euclid(b,a %b,x,y);t=x;x=y;y=t-a/b*y;return d;}void modular_equation(int a,int b,int n){int e,i,d;int x,y;d=ext_euclid(a,n,x,y);if (b%d>0)printf("No answer!\n");else{e=(x*(b/d))%n;for (i=0;i<d;i++)printf("The %dth answer is :%ld\n",i+1,(e+i*(n/d))%n);}}5.求解模线性方程组(中国余数定理)语法：result=Modular_Expoent(int a,int b,int n);参数：B[]、a=B[] (mod W[]) 的对应参数W[]：返回值： a 的值注意：其中W[],B[]已知，W[i]>0且W[i]与W[j]互质, 求a 源程序：int ext_euclid(int a,int b,int &x,int &y) //求gcd(a,b)=ax+by{int t,d;if (b==0) {x=1;y=0;return a;}d=ext_euclid(b,a %b,x,y);t=x;x=y;y=t-a/b*y;return d;}int China(int B[],int W[],int k){int i;int d,x,y,a=0,m,n=1;for (i=0;i<k;i++)n*=W[i];for (i=0;i<k;i++){m=n/W[i];d=ext_euclid(W[i],m,x,y);a=(a+y*m*B[i])%n;}if (a>0) return a;else return(a+n);}6.筛法素数产生器语法：result=prime(int a[],int n);参数：a[]： 用于返回素数的数组n： 产生n以内的素数，按升序放入a[]中返回值： n以内素数的个数注意：其中W[],B[]已知，W[i]>0且W[i]与W[j]互质, 求a 源程序：int prime(int a[],int n){int i,j,k,x,num,*b;n++;n/=2;b=(int *)malloc(sizeof(int)*(n+1)*2);a[0]=2;a[1]=3;num=2;for(i=1;i<=2*n;i++)b[i]=0;for(i=3;i<=n;i+=3)for(j=0;j<2;j++){x=2*(i+j)-1;while(b[x]==0){a[num++]=x;for(k=x;k<=2*n;k+=x)b[k]=1;}}return num;}7.判断一个数是否素数语法：result=comp(int n);参数：n： 判断n是否素数返回值： 素数返回1，否则返回0源程序：int comp(int n){int i,flag=1;for (i=2;i<=sqrt(n);i++)if (n%i==0) {flag=0;break;}if (flag==1) return 1; else return 0;}五、图论1.Prim算法求最小生成树语法：prim(Graph G,int vcount,int father[]);参数：G： 图，用邻接矩阵表示vcount： 表示图的顶点个数father[]： 用来记录每个节点的父节点返回值： null注意：常数max_vertexes为图最大节点数常数infinity为无穷大源程序：#define infinity 1000000#define max_vertexes 5typedef int Graph[max_vertexes][max_vertexes];void prim(Graph G,int vcount,int father[]){int i,j,k;intlowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes];for (i=0;i<vcount;i++){lowcost[i]=G[0][i];closeset[i]=0;used[i]=0;father[i]=-1;}used[0]=1;for (i=1;i<vcount;i++){j=0;while (used[j]) j++;for (k=0;k<vcount;k++)if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k;father[j]=closeset[j];used[j]=1;for (k=0;k<vcount;k++)if (!used[k]&&(G[j][k]<lowcost[k])){ lowcost[k]=G[j][k];closeset[k]=j; }}}2.Dijkstra算法求单源最短路径语法：result=Dijkstra(Graph G,int n,int s,int t, int path[]);参数：G： 图，用邻接矩阵表示n： 图的顶点个数s： 开始节点t： 目标节点path[]： 用于返回由开始节点到目标节点的路径返回值： 最短路径长度注意：输入的图的权必须非负顶点标号从0开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Dijkstra(Graph G,int n,int s,int t, int path[]){int i,j,w,minc,d[max_vertexes],mark[max_vertexes];for (i=0;i<n;i++) mark[i]=0;for (i=0;i<n;i++){ d[i]=G[s][i];path[i]=s; }mark[s]=1;path[s]=0;d[s]=0;for (i=1;i<n;i++){minc=infinity;w=0;for (j=0;j<n;j++)if ((mark[j]==0)&&(minc>=d[j])){minc=d[j];w=j;}mark[w]=1;for (j=0;j<n;j++)if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j])){ d[j]=d[w]+G[w][j];path[j]=w; }}return d[t];}3.Bellman-ford算法求单源最短路径语法：result=Bellman_ford(Graph G,int n,int s,int t,int path[],intsuccess);参数：G： 图，用邻接矩阵表示n： 图的顶点个数s： 开始节点t： 目标节点path[]： 用于返回由开始节点到目标节点的路径success： 函数是否执行成功返回值： 最短路径长度注意：输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0顶点标号从0开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Bellman_ford(Graph G,int n,int s,int t,int path[],intsuccess){int i,j,k,d[max_vertexes];for (i=0;i<n;i++) {d[i]=infinity;path[i]=0;}d[s]=0;for (k=1;k<n;k++)for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}success=0;for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]) return 0;success=1;return d[t];}4.Floyd-Warshall算法求每对节点间最短路径语法：Floyd_Washall(Graph G,int n,Graph D,Graph P);参数：G： 图，用邻接矩阵表示n： 图的顶点个数D： D[i,j]表示从i到j的最短距离P： P[i,j]表示从i到j的最短路径上j 的父节点返回值： null源程序：void Floyd_Washall(Graph G,int n,Graph D,Graph P){int i,j,k;for (i=0;i<n;i++)for (j=0;j<n;j++){ D[i][j]=G[i][j];P[i][j]=i; }for (i=0;i<n;i++) { D[i][i]=0;P[i][i]=0; }for (k=0;k<n;k++)for (i=0;i<n;i++)for (j=0;j<n;j++)if (D[i][j]>D[i][k]+D[k][j]){ D[i][j]=D[i][k]+D[k][j];P[i][j]=P[k][j]; }}六、排序/查找1.快速排序语法：quicksort(int l,int r,int b[]);参数：l： 排序上界，开始时l=0r： 排序下界，开始时r=数组元素个数b[]： 被排序的元素返回值： null注意：输出升序序列源程序：void quicksort(int l,int r,int b[]){int i,j,x;if(l>=r) return;i=l;j=r;x=b[i];while(i!=j){while(b[j]>x&&j>i) j--;if(i<j){b[i]=b[j];i++;}while(b[i]<x&&j>i)i++;if(i<j){b[j]=b[i];j--;}}b[i]=x;quicksort(l,j-1,b);quicksort(i+1,r,b);}2.希尔排序语法：shellsort(int a[],int n);参数：n： 数组元素个数a[]： 待排序数组返回值： null注意：输出升序序列源程序：void shellsort(int a[],int n){int i,j,g;int temp,k;g=n/2;while(g!=0){for(i=g+1;i<=n;i++){temp=a[i];j=i-g;while(j>0){k=j+g;if(a[j]<=a[k])j=0;else{temp=a[j];a[j]=a[k];a[k]=temp;}j=j-g;}}g=g/2;}}3.选择法排序语法：sort(int t[],int n);参数：t[]： 待排序数组n： 数组t[]元素的个数返回值： null注意：输出升序序列小规模排序用源程序：void sort(int t[],int n){int i,j,k,temp;for (i=0;i<n;i++){k=i;for (j=i;j<n;j++) if (t[j]<t[k]) k=j;temp=t[i];t[i]=t[k];t[k]=temp;}}4.二分查找语法：result=search_bin(int *t,int k);参数：t[]： 待查找数组k： 查找关键字返回值： 如果k在t[]中存在，输出i：t[i]=k，否则输出－1注意：要求查找数组是有序升序序列源程序：int search_bin(int *t,int k){int low=1,high=10,mid;while (low<=high){mid=(low+high)/2;if (k==t[mid]) return mid;else if (k<t[mid]) high=mid-1;else low=mid+1;}return -1;}七、数据结构1.顺序队列。

acm设计知识点ACM 设计知识点ACM（Association for Computing Machinery）是计算机科学领域的一个重要组织，该组织旨在推动计算机科学的研究和应用。

在参加ACM竞赛或进行计算机科学相关研究时，了解一些ACM设计知识点是非常重要的。

本文将介绍一些常见的ACM设计知识点，并对其进行简要的概述和应用。

一、动态规划动态规划是ACM竞赛中常见的一种解题思路。

其核心思想是将一个大问题分解为若干个小问题，在解决小问题时保存部分解，避免重复计算。

动态规划一般需要定义状态转移方程和边界条件，并通过迭代或递归来实现。

经典的动态规划问题有背包问题、最长公共子序列等。

二、贪心算法贪心算法是一种简单而高效的算法思想，但并不适用于所有问题。

贪心算法每次选择当前最优解，不考虑未来可能出现的情况。

因此，在使用贪心算法解决问题时，需要进行严格的证明以确保其正确性。

常见的贪心算法应用包括最小生成树、Dijkstra算法等。

三、图论算法图论是ACM设计中的重要知识点之一。

图是由顶点和边组成的一种数据结构，有很多实际应用。

图论算法包括最短路径算法（如Dijkstra算法、Floyd-Warshall算法）、最小生成树算法（如Prim算法、Kruskal算法）、拓扑排序、最大流算法（如Ford-Fulkerson算法）等。

四、字符串处理字符串处理是ACM竞赛中经常遇到的问题之一。

常见的字符串处理问题包括字符串匹配、字符串转换、字符串排序、字符串压缩等。

在解决这些问题时，可以运用基本的字符串操作和常用的字符串匹配算法（如KMP算法、Boyer-Moore算法）。

五、数据结构良好的数据结构是高效算法的基础。

在ACM设计中，熟悉并正确应用数据结构是至关重要的。

常见的数据结构包括数组、链表、栈、队列、树、图、堆、哈希表等。

对于ACM竞赛或算法设计，需要根据问题的特点选择合适的数据结构以优化算法效率。

六、搜索算法搜索算法在ACM设计中有着广泛的应用。

16个ACM经典算法介绍一、排序算法：1.冒泡排序：基于比较的排序算法，通过不断交换相邻元素将最大元素逐渐向后移动。

2.插入排序：基于比较的排序算法，通过将元素逐个插入到已排好序的部分中，最终得到完全有序的序列。

3.归并排序：基于分治的排序算法，将待排序序列划分为一系列子序列，然后将子序列进行合并，最终得到完全有序的序列。

4.快速排序：基于分治的排序算法，通过选择一个基准元素将序列划分为两部分，然后递归地对两部分进行排序。

5.堆排序：基于堆的排序算法，通过构建最大堆或最小堆来实现排序。

二、查找算法：6.二分查找：基于有序序列的查找算法，通过将待查找值与序列中间元素进行比较，逐渐缩小查找范围。

7.哈希表：基于哈希函数的查找算法，通过将键值对存储在哈希表中，实现高效的查找。

三、图算法：8.深度优先（DFS）：基于栈的算法，通过递归地访问顶点的邻接顶点，实现图的遍历。

9.广度优先（BFS）：基于队列的算法，通过访问顶点的邻接顶点，实现图的遍历。

10. 最小生成树算法：用来求解无向图的最小生成树，常用的有Prim算法和Kruskal算法。

11. 最短路径算法：用来求解有向图或带权重的无向图的最短路径，常用的有Dijkstra算法和Floyd-Warshall算法。

四、动态规划算法：12.最长上升子序列（LIS）：用来求解一个序列中最长严格递增子序列的长度。

13.背包问题：用来求解在给定容量下，能够装入尽量多的物品的问题。

五、字符串算法：14.KMP算法：用来在一个文本串S中查找一个模式串P的出现位置的算法，通过预处理模式串，利用已经匹配过的子串，跳过一定长度进行下一轮匹配。

15. Boyer-Moore算法：用来在一个文本串S中查找一个模式串P的出现位置的算法，通过从模式串末尾开始匹配，利用好后缀和坏字符规则，跳过一定长度进行下一轮匹配。

16.字符串匹配算法：用来在一个文本串S中查找多个模式串的出现位置的算法，常用的有AC自动机和后缀树。