{"id":365,"date":"2022-08-24T22:48:48","date_gmt":"2022-08-24T14:48:48","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=365"},"modified":"2024-09-12T09:35:26","modified_gmt":"2024-09-12T01:35:26","slug":"%e8%bd%ac%e8%bd%bd%e7%94%b1%e6%95%b0%e6%8d%ae%e8%8c%83%e5%9b%b4%e5%8f%8d%e6%8e%a8%e7%ae%97%e6%b3%95%e5%a4%8d%e6%9d%82%e5%ba%a6%e4%bb%a5%e5%8f%8a%e7%ae%97%e6%b3%95%e5%86%85%e5%ae%b9","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=365","title":{"rendered":"[\u8f6c\u8f7d]\u7531\u6570\u636e\u8303\u56f4\u53cd\u63a8\u7b97\u6cd5\u590d\u6742\u5ea6\u4ee5\u53ca\u7b97\u6cd5\u5185\u5bb9"},"content":{"rendered":"

\u4e00\u822cACM\u6216\u8005\u7b14\u8bd5\u9898\u7684\u65f6\u95f4\u9650\u5236\u662f1\u79d2\u62162\u79d2\u3002 \u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0cC++\u4ee3\u7801\u4e2d\u7684\u64cd\u4f5c\u6b21\u6570\u63a7\u5236\u5728 10^{7} \\sim 10^{8}<\/code>\u4e3a\u6700\u4f73\u3002 \u4e0b\u9762\u7ed9\u51fa\u5728\u4e0d\u540c\u6570\u636e\u8303\u56f4\u4e0b\uff0c\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u7b97\u6cd5\u8be5\u5982\u4f55\u9009\u62e9:<\/p>\n

    \n
  1. n \\leq 30<\/code>, \u6307\u6570\u7ea7\u522b, dfs+\u526a\u679d\uff0c\u72b6\u6001\u538b\u7f29dp<\/li>\n
  2. n \\leq 100 \\Rightarrow O\\left(n^{3}\\right)<\/code> \uff0c floyd\uff0c dp\uff0c\u9ad8\u65af\u6d88\u5143<\/li>\n
  3. n \\leq 1000 \\Rightarrow O\\left(n^{2}\\right)<\/code> \uff0cO\\left(n^{2} \\log n\\right)<\/code> \uff0cdp\uff0c\u4e8c\u5206\uff0c\u6734\u7d20\u7248Dijkstra\u3001\u6734\u7d20\u7248Prim\u3001Bellman-Ford<\/li>\n
  4. n \\leq 10000 \\Rightarrow O(n * \\sqrt{n})<\/code> \uff0c\u5757\u72b6\u94fe\u8868\u3001\u5206\u5757\u3001\u83ab\u961f<\/li>\n
  5. n \\leq 100000 \\Rightarrow O(n \\log n) \\Rightarrow><\/code> \u5404\u79cdsort\uff0c\u7ebf\u6bb5\u6811\u3001\u6811\u72b6\u6570\u7ec4\u3001set\/map\u3001heap\u3001\u62d3\u6251\u6392\u5e8f\u3001dijkstra+heap\u3001prim+heap\u3001Kruskal\u3001spfa\u3001\u6c42\u51f8\u5305\u3001\u6c42\u534a\u5e73\u9762\u4ea4\u3001\u4e8c\u5206\u3001CDQ\u5206\u6cbb\u3001\u6574\u4f53\u4e8c\u5206\u3001\u540e\u7f00\u6570\u7ec4\u3001\u6811\u94fe\u5256\u5206\u3001\u52a8\u6001\u6811<\/li>\n
  6. n \\leq 1000000 \\Rightarrow O(n)<\/code> , \u4ee5\u53ca\u5e38\u6570\u8f83\u5c0f\u7684 $$O(n \\log n)$$<\/code> \u7b97\u6cd5 \\Rightarrow<\/code> \u5355\u8c03\u961f\u5217\u3001hash\u3001\u53cc\u6307\u9488\u626b\u63cf\u3001\u5e76\u67e5\u96c6\uff0c kmp\u3001AC\u81ea \u52a8\u673a\uff0c\u5e38\u6570\u6bd4\u8f83\u5c0f\u7684 O(n \\log n)<\/code> \u7684\u505a\u6cd5: sort\u3001\u6811\u72b6\u6570\u7ec4\u3001heap\u3001dijkstra\u3001spfa<\/li>\n
  7. n \\leq 10000000 \\Rightarrow O(n)<\/code> \uff0c\u53cc\u6307\u9488\u626b\u63cf\u3001kmp\u3001AC\u81ea\u52a8\u673a\u3001\u7ebf\u6027\u7b5b\u7d20\u6570<\/li>\n
  8. n \\leq 10^{9} \\Rightarrow O(\\sqrt{n})<\/code> \uff0c\u5224\u65ad\u8d28\u6570<\/li>\n
  9. n \\leq 10^{18} \\Rightarrow O(\\log n)<\/code> \uff0c\u6700\u5927\u516c\u7ea6\u6570\uff0c\u5feb\u901f\u5e42\uff0c\u6570\u4f4dDP<\/li>\n
  10. n \\leq 10^{1000} \\Rightarrow O\\left((\\log n)^{2}\\right)<\/code>\uff0c\u9ad8\u7cbe\u5ea6\u52a0\u51cf\u4e58\u9664<\/li>\n
  11. n \\leq 10^{100000} \\Rightarrow O(\\log k \\times \\log \\log k)<\/code>, k\u8868\u793a\u4f4d\u6570\uff0c\u9ad8\u7cbe\u5ea6\u52a0\u51cf\u3001FFT\/NTT<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    \u4e00\u822cACM\u6216\u8005\u7b14\u8bd5\u9898\u7684\u65f6\u95f4\u9650\u5236\u662f1\u79d2\u62162\u79d2\u3002 \u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0cC++\u4ee3\u7801\u4e2d\u7684\u64cd\u4f5c\u6b21 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,17],"tags":[],"class_list":["post-365","post","type-post","status-publish","format-standard","hentry","category-13","category-17"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/365","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=365"}],"version-history":[{"count":2,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/365\/revisions"}],"predecessor-version":[{"id":751,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/365\/revisions\/751"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=365"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=365"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=365"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}