BZOJ Solution—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,。

以下为王道论坛机试教程中的107道题目的练习地址，全部免费使用。

可以无限次提交。

（1）排序：/problem.php?id=1111（2）成绩排序：/problem.php?id=1112（3）特殊排序：/problem.php?id=1113（4）EXCEL排序：/problem.php?id=1114（5）字符串内排序：/problem.php?id=1115（6）日期差值：/problem.php?id=1116（7）Day of Week：/problem.php?id=1117（8）今年的第几天？：/problem.php?id=1118（9）打印日期：/problem.php?id=1119（10）统计同成绩学生人数：/problem.php?id=1120（11）Sort：/problem.php?id=1108（12）谁是你的潜在朋友：/problem.php?id=1033（13）剩下的树：/problem.php?id=1070（14）输出梯形：/problem.php?id=1121（15）叠筐：/problem.php?id=1087（16）Repeater：/problem.php?id=1086（17）找x：/problem.php?id=1122（18）查找学生信息：/problem.php?id=1123（19）打印极值点下标：/problem.php?id=1124（20）查找：/problem.php?id=1125（21）FatMouse ：/problem.php?id=1109（22）今年暑假不AC：/problem.php?id=1071（23）迷瘴：/problem.php?id=1390（24）Repair the Wall：/problem.php?id=1107（25）To Fill or Not to Fill：/problem.php?id=1416（26）括号匹配问题：/problem.php?id=1072（27）简单计算器：/problem.php?id=1100（28）堆栈的使用：/problem.php?id=1083（29）计算表达式：/problem.php?id=1047（30）哈夫曼树：/problem.php?id=1106（31）搬水果：/problem.php?id=1073（32）二叉树遍历：/problem.php?id=1084（33）二叉树：/problem.php?id=1074（34）树查找：/problem.php?id=1089（35）二叉排序树：/problem.php?id=1104（36）二叉搜索树：/problem.php?id=1105（37）还是A+B：/problem.php?id=1126（38）守形数：/problem.php?id=1127（39）特殊乘法：/problem.php?id=1075（40）反序数：/problem.php?id=1128（41）对称平方数：/problem.php?id=1050（42）Digital Roots：/problem.php?id=1036（43）又一版A+B：/problem.php?id=1129（44）数制转换：/problem.php?id=1130（45）进制转换：/problem.php?id=1131（46）八进制：/problem.php?id=1132（47）最大公约数：/problem.php?id=1049（48）最小公倍数：/problem.php?id=1133（49）Least Common Multiple ：/problem.php?id=1134 （50）素数判定：/problem.php?id=1044（51）素数：/problem.php?id=1135（52）Prime Number：/problem.php?id=1136（53）Goldbach's Conjecture：/problem.php?id=1095 （54）质因数的个数：/problem.php?id=1137（55）整除问题：/problem.php?id=1053（56）约数的个数：/problem.php?id=1138（57）人见人爱 A ^ B：/problem.php?id=1076 （58）A sequence of numbers ：/problem.php?id=1101 （59）Tr A：/problem.php?id=1082（60）a+b：/problem.php?id=1139（61）N的阶乘：/problem.php?id=1098（62）进制转换：/problem.php?id=1131（63）浮点数加法：/problem.php?id=1110（64）大整数排序：/problem.php?id=1141（65）10进制VS 2进制：/problem.php?id=1142 （66）畅通工程：/problem.php?id=1143（67）More is better ：/problem.php?id=1102（68）连通图：/problem.php?id=1080（69）How Many Tables：/problem.php?id=1099 （70）Head of a Gang：/problem.php?id=1420（71）还是畅通工程：/problem.php?id=1069（72）Freckles：/problem.php?id=1088（73）Jungle Roads：/problem.php?id=1208（74）畅通工程：/problem.php?id=1144（75）继续畅通工程：/problem.php?id=1145（76）最短路：/problem.php?id=1146（77）最短路径问题：/problem.php?id=1225（78）最短路径：/problem.php?id=1147（79）I Wanna Go Home：/problem.php?id=1210 （80）Legal or Not：/problem.php?id=1148（81）确定比赛名次：/problem.php?id=1077（82）产生冠军：/problem.php?id=1103（83）百鸡问题：/problem.php?id=1149（84）Abc：/problem.php?id=1150（85）求最大值：/problem.php?id=1039（86）胜利大逃亡：/problem.php?id=1209（87）非常可乐：/problem.php?id=1078（88）汉诺塔III：/problem.php?id=1151（89）Prime ring problem ：/problem.php?id=1090 （90）Oil Deposit：/problem.php?id=1153（91）全排列：/problem.php?id=1155（92）Tempter of the bone：/problem.php?id=1097 （93）N阶楼梯上楼问题：/problem.php?id=1156 （94）不容易系列之一：/problem.php?id=1157 （95）吃糖果：/problem.php?id=1079（96）拦截导弹：/problem.php?id=1085（97）合唱队形：/problem.php?id=1094（98）Coincidence：/problem.php?id=1158（99）搬寝室：/problem.php?id=1081（100）Greedy Tino：/problem.php?id=1096 （101）采药：/problem.php?id=1093（102）Piggy-Bank：/problem.php?id=1091 （103）珍惜现在，感恩生活：/problem.php?id=1092 （104）字符串的查找删除：/problem.php?id=1064 （105）产生冠军：/problem.php?id=1103（106）单词替换：/problem.php?id=1159（107）字符串去特定字符：/problem.php?id=1160。

背包问题（3）：完全背包完全背包也是⼀种基本的背包问题模型，其基本特点是：每种物品可以放⽆限多次。

这个问题⾮常类似于0/1背包问题，所不同的是每种物品有⽆限件。

也就是从每种物品的⾓度考虑，与它相关的策略已并⾮取或不取两种，⽽是有取0件、取1件、取2件……等很多种。

完全背包问题的⼀般描述为：有N个物品，第i个物品的重量与价值分别为W[i]与P[i]。

背包容量为V，问在每个物品有⽆限个（物品必须保持完整）的情况下，如何让背包装⼊的物品具有更⼤的价值总和。

其⼀般解题思路为：令 f[i][j] 表⽰从编号1~i的物品中挑选任意数量的任意物品放⼊容量为j的背包中得到的最⼤价值，那么有f[i][j]=max { f[i−1][j]，f[i−1][j−k∗W[i]]+k∗P[i] } （0≤k && k∗W[i]≤j）编写代码时，可采⽤如下的循环。

for ( i=1;i<=N;i++) // 依次对每个物品进⾏处理for (j=1;j<=V;j++)for (k=1; k<=V/W[i];k++) // 物品最多只能放多少件{If (k*W[i]<=j)f[i][j]=max(f[i-1][j],f[i-1][j-k*W[i]]+k*P[i]);elsef[i][j]=f[i-1][j];}所求的最优值为f[N][V]。

同样完全背包也可以进⾏空间优化，将⼆维数组优化为⼀维数组，即f[j]=max { f[j]，f[j−k∗W[i]]+k∗P[i] } （0≤k && k∗W[i]≤j）编写代码时，⼀般采⽤如下的⼆重循环。

for (i=1;i<=N;i++) // 装⼊背包的物品个数为Nfor ( j=W[i];j<=V;j++) // 完全背包按由⼩到⼤顺序枚举重量f[j]=max(f[j],f[j-W[i]]+P[i]); // 状态转移所求的最优值为f[V]。

第1~10题为基础题，第11~20题为提高题，第21~33为综合题注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。

^_^基础题：【1 Prime Frequency】【问题描述】给出一个仅包含字母和数字（0-9, A-Z 以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。

输入：输入的第一行给出一个整数T( 0<T<201)，表示测试用例个数。

后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。

字符串的长度是小于2001的一个正整数。

输出：对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。

这些字符按字母升序排列。

所谓“字母升序”意谓按ASCII 值升序排列。

如果没有字符的频率是素数，输出“empty”（没有引号）。

注：试题来源：Bangladesh National Computer Programming Contest在线测试：UV A 10789提示先离线计算出[2‥2200]的素数筛u[]。

然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u [p[i]]=1且ASCLL码值为i的字符）。

若没有频率为素数的字符，则输出失败信息。

【2 Twin Primes】【问题描述】双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul Stäckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。

在本题中请你给出第S对双素数，其中S是输入中给出的整数。

ACM题分类汇总2009年05月11日星期一 13:40原帖：一些图论、网络流入门题总结、汇总/zfy0701/blog/item/b8332b5c7b2dd545fbf2c052.html搜索题目推荐及解题报告/zfy0701/blog/item/c6e216ed18a9d24a78f05589.html字符串题目推荐及解题报告/zfy0701/blog/item/440e923e1bc4183870cf6c89.html ------------------------最短路问题此类问题类型不多，变形较少POJ 2449 Remmarguts' Date(中等)/JudgeOnline/problem?id=2449题意：经典问题：K短路解法：dijkstra+A*(rec)，方法很多相关：/JudgeOnline/showcontest?contest_id=1144该题亦放在搜索推荐题中POJ 3013 - Big Christmas Tree(基础)/JudgeOnline/problem?id=3013题意：最简单最短路，但此题要过，需要较好的程序速度和，还要注意精度解法：DijkstraPOJ 3463 - Sightseeing(中等)/JudgeOnline/problem?id=3463题意：最短路和比最短路大1的路的数量解法：需要真正理解dijkstraPOJ 3613 - Cow Relays(较难)/JudgeOnline/problem?id=3613题意：求经过N条边的最短路解法：floyd + 倍增，贪心POJ 3621 - Sightseeing Cows(中等)/JudgeOnline/problem?id=3621题意：求一个环路，欢乐值 / 总路径最大解法：参数搜索 + 最短路(ms 原始的bellman tle, 用spfa才过)POJ 3635 - full tank?(中等)/JudgeOnline/problem?id=3635题意：最短路变形解法：广搜相关：/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.htm l生成树问题基本的生成树就不放上来了POJ 1639 - Picnic Planning(较难)/JudgeOnline/problem?id=1639题意：顶点度数有限制的最小生成树解法：贪心 + prim/kruskalPOJ 1679 - The Unique MST(基础)/JudgeOnline/problem?id=1679题意：判断MST是否唯一解法：prim就行，不过还是易错的题POJ 2728 - Desert King(中等)/JudgeOnline/problem?id=2728题意：所谓最优比率生成树解法：参数搜索 + primPOJ 3164 - Command Network(难)/JudgeOnline/problem?id=3164题意：最小树形图解法：刘朱算法，这个考到的可能性比较小吧？POJ 3522 - Slim Span(基础)/JudgeOnline/problem?id=3522题意：求一颗生成树，让最大边最小边差值最小解法：kruskal活用连通性，度数，拓扑问题此类问题主要牵扯到DFS，缩点等技巧POJ 1236 - Network of Schools(基础)/JudgeOnline/problem?id=1236题意：问添加多少边可成为完全连通图解法：缩点，看度数POJ 1659 - Frogs' Neighborhood(基础)/JudgeOnline/problem?id=1659题意：根据度序列构造图解法：贪心，详细证明参见havel定理POJ 2553 - The Bottom of a Graph(基础)/JudgeOnline/problem?id=2553POJ 2186 - Popular Cows(基础)/JudgeOnline/problem?id=2186题意：强连通分量缩点图出度为0的点POJ 2762 - Going from u to v or from v to u?(中等)/JudgeOnline/problem?id=2762题意：单向连通图判定解法：缩点 + dp找最长链POJ 2914 - Minimum Cut(难)/JudgeOnline/problem?id=2914题意：无向图最小割解法：Stoer-Wagner算法，用网络流加枚举判定会挂POJ 2942 - Knights of the Round Table(难)/JudgeOnline/problem?id=2942题意：求双联通分量(或称块)中是否含奇圈解法：求出双连通分量后做黑白染色进行二分图图判定相关：/zfy0701/blog/item/57ada7ed104ce9d2b31cb104.htmlPOJ 3177 - Redundant Paths(中等)/JudgeOnline/problem?id=3177POJ 3352 - Road Construction(中等)/JudgeOnline/problem?id=3352题意：添加多少条边可成为双向连通图解法：把割边分开的不同分量缩点构树，看入度建议对比下1236，有向图添加多少条边变成强连通图POJ 3249 - Test for Job(基础)/JudgeOnline/problem?id=3249解法：bfs / dfs + dpPOJ 3592 - Instantaneous Transference(基础)/JudgeOnline/problem?id=3592解法：缩点，最长路，少人做的水题，注意细节POJ 3687 - Labeling Balls(中等)/JudgeOnline/problem?id=3687解法：拓扑排序POJ 3694 - Network(中等)/JudgeOnline/problem?id=3694解法：双连通分量+并查集2-SAT问题此类问题理解合取式的含义就不难POJ 2723 - Get Luffy Out(中等)/JudgeOnline/problem?id=2723 POJ 2749 - Building roads(较难)/JudgeOnline/problem?id=2749解法：二分 + 2-SAT判定POJ 3207 - Ikki's Story IV - Panda's Trick(基础) /JudgeOnline/problem?id=3207 解法：简单的2-sat，不过其他方法更快POJ 3648- Wedding(中等)/JudgeOnline/problem?id=3648解法：用2-sat做会比较有意思，但是暴搜照样0msPOJ 3678 - Katu Puzzle(基础)/JudgeOnline/problem?id=3678解法：直接按合取式构图验证就行了POJ 3683 - Priest John's Busiest Day(中等)/JudgeOnline/problem?id=3683解法：n^2枚举点之间的相容性构图，求解2-SAT最大流问题变形很多，最小割最大流定理的理解是关键POJ 1149 - PIGS(较难)/JudgeOnline/problem?id=1149绝对经典的构图题POJ 1273 - Drainage Ditches(基础)/JudgeOnline/problem?id=1273最大流入门POJ 1459 - Power Network(基础)/JudgeOnline/problem?id=1459基本构图POJ 1637 - Sightseeing tour(Crazy)/JudgeOnline/problem?id=1637题意：求混合图的欧拉迹是否存在解法：无向边任意定向，构图，详建黑书P324POJ 1815 - Friendship(中等)/JudgeOnline/problem?id=1815题意：求最小点割解法：拆点转换为边割相关：/zfy0701/blog/item/a521f230b06dea9fa9018e0e.htmlPOJ 1966 - Cable TV Network(中等)/JudgeOnline/problem?id=1966题意：去掉多少点让图不连通解法：任定一源点，枚举汇点求点割集(转换到求边割)，求其中最小的点割POJ 2112 - Optimal Milking(基础)/JudgeOnline/problem?id=2112二分枚举，最大流POJ 2391 - Ombrophobic Bovines(中等)/JudgeOnline/problem?id=2391题意：floyd, 拆点，二分枚举相关：/zfy0701/blog/item/3e0006c4f73f0eaf8226acff.htmlPOJ 2396 - Budget(中等)/JudgeOnline/problem?id=2396题意：有源汇的上下界可行流解法：用矩阵-网络流模型构图，然后拆边相关：/zfy0701/blog/item/6449d82a64e15e3e5343c1ba.html ，最小割模型在竞赛中的应用POJ 2455 - Secret Milking Machine(基础)/JudgeOnline/problem?id=2455二分枚举，一般来说需要写对边容量的更新操作而不是每次全部重新构图POJ 2699 - The Maximum Number of Strong Kings(较难)/JudgeOnline/problem?id=2699解法：枚举人数 + 最大流(感谢xpcnq_71大牛的建图的提示)POJ 2987 - Firing(较难)/JudgeOnline/problem?id=2987题意：最大权闭包解法：先边权放大，第一问总量-最大流，第二问求最小割相关：/blog/cns!4D861A02A3382142!1109.entry?&_ c02_owner=1Profit(中等)/Problem_Show.asp?id=1352最大权闭包图的特殊情况ZOJ 2071 - Technology Trader 也是此类型，懒了没做/show_problem.php?pid=2071POJ 3084 - Panic Room(中等，好题)/JudgeOnline/problem?id=3084题意：略解法：根据最小割建模POJ 3155 - Hard Life(很挑战一题)/JudgeOnline/problem?id=3155题意：最大密度子图解法：参数搜索 + 最大权闭合图，A.V.Goldberg的论文(nb解法)最小割模型在信息学竞赛中的应用一文中也有讲POJ 3189 - Steady Cow Assignment(中等)/JudgeOnline/problem?id=3189题意：寻找最小的区间完成匹配解法：这题充分说明SAP的强大，纯暴力可过。

2016团体程序设计天梯赛-决赛-部分题解 第⼀个卡的题是“到底是不是太胖了”，当时以为卡精度，因为各种eps都过不了。

但是结束后队友说不卡精度，随便⼀个eps就过了--，可能是代码写搓了。

但是更好的⽅法是全部变成整数做来规避精度的问题。

具体见代码：1 #include <stdio.h>2 #include <algorithm>3 #include <string.h>4 #include <vector>5 #include <map>6 #include <set>7 #include <queue>8 #include <iostream>9using namespace std;10const int inf = 0x3f3f3f3f;11 typedef long long ll;12const int N = 500 + 5;1314int main()15{16int T;17 cin >> T;18while(T--)19 {20int h,w;21 cin >> h >> w;22int biaozhun = 2*(h-100);23if(w*100>biaozhun*9*9 && w*100<biaozhun*11*9) puts("You are wan mei!");24else if(w*100>=biaozhun*11*9) puts("You are tai pang le!");25else puts("You are tai shou le!");26 }27 }View Code 然后是红⾊警报这题，⼀开始以为是和上次的删边并查集⼀样，但是⽐赛时发现没法做，⽐赛结束后仓⿏学长说可以并查集做，但是他没有通过全部数据。

第三十届ACM/ICPC 世界总决赛题目解析斯坦福大学王颖本次比赛的题目请见/icpc/Finals/2006WorldFinalProblemSet.pdf Problem A本题的大意是，给出一些机票，每个机票都是一条路线，比如城市A->城市B->城市K->…->城市N，并且每张机票有一个价格。

我们可以只用一张机票的一部分，比如城市A->城市B->城市K，然后就丢弃这张机票。

但有两个条件，第一，必须在机票的起始城市才能使用机票，也就是说，我们不能用上面的机票从城市B到城市K；第二，如果使用了一张机票的部分，以后就不能使用剩下的部分。

现在给出一条路线，我们要按顺序访问一系列的城市。

给出所有可以购买的机票，每种机票可以买无限张，问怎样可以用最少的花费完成整个旅途。

本题的数据规模颇小，机票最多20种，而每个机票最多经过10个城市。

由于机票可以重复购买，城市必须按顺序经过，很容易想到要用动态规划。

但从比赛过程中可以发现，无数的队伍被这题卡住了，而且很少的队伍能够一次通过。

问题就在于，并不是只能访问指定路径上的城市，而是可以访问一些辅助的城市来减小花费。

所以，我们要用一个二元组(i,j)来表示一个状态。

其中i表示指定路径上已经按顺序访问了的城市数量，j表示当前所在城市。

通过机票的信息，不难得到状态之间的一个有向图，而我们要求的其实就是一个最短路径。

注意到这个图是有圈的，所以我们不能直接用动态规划，而是需要用最短路算法。

本题初看觉得规模甚小，此时则可以发现最多能有20*10=200个城市，共可以有10*200=2000个状态，还是颇有规模的。

总结：想清楚后此题并不复杂。

但比赛时必须保持头脑清醒，分析清楚题意，才可能顺利解决此题。

比赛中虽然很多队伍做出此题，但很少有队伍一次做对，更有一些队伍一直困在这题，可见比赛中队伍普遍紧张，没能仔细的去考虑。

Problem B典型的最小费用最大流，不多说了。