{"id":1706,"date":"2021-06-30T11:28:06","date_gmt":"2021-06-30T03:28:06","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1706"},"modified":"2022-01-18T15:52:01","modified_gmt":"2022-01-18T07:52:01","slug":"atl","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/atl\/","title":{"rendered":"Atcoder \u7b97\u6cd5\u5e93"},"content":{"rendered":"<p><a href=\"https:\/\/codeforces.com\/blog\/entry\/82400\">Atcoder \u7b97\u6cd5\u5e93\uff08ACL\uff09<\/a> \u51fa\u4e86\u5feb\u4e00\u5e74\u4e86\uff0c\u4e00\u76f4\u6ca1\u4ed4\u7ec6\u770b\uff0c\u8fd9\u4e24\u5929\u5199 <a href=\"https:\/\/zhuanlan.zhihu.com\/p\/380072238\">\u300a\u5929\u624d\u7b97\u6cd5\u5c11\u5973\u300b<\/a> \u7684\u4e3b\u7ebf\u5267\u60c5\uff0c\u6b63\u597d\u590d\u4e60\u4e00\u4e0b\u8fd9\u4e2a\u3002\u4e0d\u8fc7\u8fd9\u73a9\u610f\u66f4\u65b0\u7684\u7740\u5b9e\u633a\u6162\u7684\uff0c\u8fd8\u6ca1\u6211\u7684 Template \u7b97\u6cd5\u591a\u3002\u3002\u3002\u4e0d\u8fc7\u81f3\u5c11\u53ef\u4ee5\u548c rng_58 \u5b66\u4e60\u4e00\u4e0b\u600e\u4e48\u5199 test \u3002\u3002\u3002<\/p>\n<p>\u9996\u5148\u8bb2\u4e00\u4e0b\u600e\u4e48\u50cf STL \u4e00\u6837\u52a0\u5165 cpp \u7684\u9ed8\u8ba4\u5934\u6587\u4ef6\uff0c\u65b9\u6cd5\u5f53\u7136\u662f\u7f16\u8f91\u7f16\u8bd1\u5668\u7684 Search directories\u3002\u8fd9\u4e2a\u5e93\u7ed3\u6784\u975e\u5e38\u7b80\u5355\uff0c\u5bf9\u4e8e\u4e0d\u652f\u6301 ACL \u7684 OJ\uff0c\u4f30\u8ba1\u4e5f\u53ef\u4ee5\u624b\u52a8\u5c55\u5f00\u4e00\u4e0b\u3002<\/p>\n<h2>\u4f8b\u9898<\/h2>\n<p>\u4e3a\u4e86\u63a8\u5e7f\u8fd9\u4e2a\u5e93\uff0crng_58 \u8fd8\u51c6\u5907\u4e86\u4e24\u573a ACL contest\uff0c\u7528\u6765\u6d4b\u8bd5\u6a21\u677f\u3002\u5f53\u7136\u8fd9\u4e2a\u4e1c\u897f\u7684\u9002\u7528\u8303\u56f4\u8fd8\u6709\u5f85\u89c2\u5bdf\uff0c\u6bd5\u7adf\u6a21\u677f\u7684\u7f3a\u70b9\u662f\u4e0d\u80fd\u8fdb\u53bb\u9b54\u6539\uff0c\u6700\u5178\u578b\u7684\u7f3a\u9677\u53ef\u80fd\u5c31\u662f\u65e0\u6cd5\u7ed9 <code>std::set&lt;int&gt;<\/code> \u91cc\u7684\u4e8c\u53c9\u6811\u8282\u70b9\u52a0\u536b\u661f\u6570\u636e <code>size<\/code> \u4ee5\u5b9e\u73b0\u6c42\u7b2c <code>kth<\/code> \u5927\u8fd9\u79cd\u5b9e\u7528\u64cd\u4f5c\u3002\u3002\u3002\uff1f\u3002\u3002\u3002\uff08\u6bd4\u5982\u9700\u8981\u52a0\u536b\u661f\u6570\u636e\u7684\u5e76\u67e5\u96c6\u53ef\u80fd\u4e5f\u6ca1\u6cd5\u641e\u4e86\uff09<\/p>\n<h3>A &#8211; Disjoint Set Union<\/h3>\n<p>\u5e76\u67e5\u96c6<br \/>\n&#8211; <a href=\"https:\/\/vjudge.net\/problem\/AtCoder-abc181_f\">https:\/\/vjudge.net\/problem\/AtCoder-abc181_f<\/a><\/p>\n<h3>B &#8211; Fenwick Tree<\/h3>\n<p>\u6811\u72b6\u6570\u7ec4<\/p>\n<h3>C &#8211; Floor Sum<\/h3>\n<p>\u7b49\u5dee\u6570\u5217\u6bcf\u4e00\u9879\u9664\u4ee5 M \u4e0b\u53d6\u6574\u7684\u548c\u3002\uff08\u8fd9\u73a9\u610f\u5c45\u7136\u4e5f\u9700\u8981\u8fdb\u6a21\u677f\uff1f\uff09<br \/>\n$$\\sum_{i = 0}^{N &#8211; 1} \\lfloor(A \\times i + B) \/ M\\rfloor$$<\/p>\n<h3>D &#8211; Maxflow<\/h3>\n<p>\u6700\u5927\u6d41<br \/>\n&#8211; <a href=\"https:\/\/vjudge.net\/problem\/AtCoder-agc038_f\">https:\/\/vjudge.net\/problem\/AtCoder-agc038_f<\/a><br \/>\n&#8211; <a href=\"https:\/\/atcoder.jp\/contests\/arc107\/tasks\/arc107_f\">https:\/\/atcoder.jp\/contests\/arc107\/tasks\/arc107_f<\/a><br \/>\n&#8211; <a href=\"https:\/\/atcoder.jp\/contests\/abc193\/tasks\/abc193_f\">https:\/\/atcoder.jp\/contests\/abc193\/tasks\/abc193_f<\/a><\/p>\n<pre class=\"brush: python; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nimport sys\r\nfrom atcoder.maxflow import MFGraph\r\nI = lambda: &#x5B;int(x) for x in input().split()]\r\n\r\nn, m = I()\r\ns = 2*n\r\nt = s+1\r\nG = MFGraph(t+1)\r\na = I()\r\nb = I()\r\nz = 0\r\n\r\nfor i in range(n):\r\n    bb = abs(b&#x5B;i])\r\n    z += bb\r\n    G.add_edge(i, i+n, a&#x5B;i] + bb)\r\n    bb *= 2\r\n    if (b&#x5B;i] &lt; 0):\r\n        G.add_edge(i+n, t, bb)\r\n    else:\r\n        G.add_edge(s, i, bb)\r\n\r\nfor i in range(m):\r\n    x, y = I()\r\n    x -= 1\r\n    y -= 1\r\n    G.add_edge(x+n, y, sys.maxsize)\r\n    G.add_edge(y+n, x, sys.maxsize)\r\n\r\nprint(z-G.flow(s,t))\r\n<\/pre>\n<h3>E &#8211; MinCostFlow<\/h3>\n<p>\u6700\u5c0f\u8d39\u7528\u6700\u5927\u6d41<br \/>\n&#8211; <a href=\"https:\/\/atcoder.jp\/contests\/agc034\/tasks\/agc034_d\">https:\/\/atcoder.jp\/contests\/agc034\/tasks\/agc034_d<\/a><\/p>\n<h3>F &#8211; Convolution<\/h3>\n<p>FFT \u5377\u79ef<\/p>\n<h3>G &#8211; SCC<\/h3>\n<p>\u5f3a\u8fde\u901a\u5206\u91cf<\/p>\n<h3>H &#8211; Two SAT<\/h3>\n<p>2SAT<\/p>\n<h3>I &#8211; Number of Substrings<\/h3>\n<p>\u540e\u7f00\u6570\u7ec4<br \/>\n\u91cc\u9762\u7684\u5b9e\u73b0\u7528\u7684\u662f <a href=\"https:\/\/oiwiki.org\/string\/sa\/#sa-is\">sa-is<\/a> \u7ebf\u6027\u6784\u9020\u7b97\u6cd5\u3002<br \/>\n&#8211; <a href=\"https:\/\/atcoder.jp\/contests\/abc141\/submissions\/23884310\">https:\/\/atcoder.jp\/contests\/abc141\/submissions\/23884310<\/a><br \/>\n&#8211; <a href=\"https:\/\/atcoder.jp\/contests\/arc097\/tasks\/arc097_a\">https:\/\/atcoder.jp\/contests\/arc097\/tasks\/arc097_a<\/a><\/p>\n<h3>J &#8211; Segment Tree<\/h3>\n<p>\u7ebf\u6bb5\u6811<\/p>\n<h3>K &#8211; Range Affine Range Sum<\/h3>\n<p>\u61d2\u6807\u8bb0\u7ebf\u6bb5\u6811<\/p>\n<h3>L &#8211; Lazy Segment Tree<\/h3>\n<p>\u61d2\u6807\u8bb0\u7ebf\u6bb5\u6811<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Atcoder \u7b97\u6cd5\u5e93\uff08ACL\uff09 \u51fa\u4e86\u5feb\u4e00\u5e74\u4e86\uff0c\u4e00\u76f4\u6ca1\u4ed4\u7ec6\u770b\uff0c\u8fd9\u4e24\u5929\u5199 \u300a\u5929\u624d\u7b97\u6cd5\u5c11\u5973\u300b \u7684\u4e3b\u7ebf\u5267\u60c5\uff0c\u6b63\u597d\u590d\u4e60\u4e00\u4e0b\u8fd9\u4e2a\u3002\u4e0d\u8fc7\u8fd9\u73a9\u610f\u66f4\u65b0\u7684\u7740\u5b9e\u633a\u6162\u7684\uff0c\u8fd8\u6ca1\u6211\u7684 Template \u7b97\u6cd5\u591a\u3002\u3002\u3002\u4e0d\u8fc7\u81f3\u5c11\u53ef\u4ee5\u548c rng_58 \u5b66\u4e60\u4e00\u4e0b\u600e\u4e48\u5199 test \u3002\u3002\u3002 \u9996\u5148\u8bb2\u4e00\u4e0b\u600e\u4e48\u50cf STL \u4e00\u6837\u52a0\u5165 cpp \u7684\u9ed8\u8ba4\u5934\u6587\u4ef6\uff0c\u65b9\u6cd5\u5f53\u7136\u662f\u7f16\u8f91\u7f16\u8bd1\u5668\u7684 Search directories\u3002\u8fd9\u4e2a\u5e93\u7ed3\u6784\u975e\u5e38\u7b80\u5355\uff0c\u5bf9\u4e8e\u4e0d\u652f\u6301 ACL \u7684 OJ\uff0c\u4f30\u8ba1\u4e5f\u53ef\u4ee5\u624b\u52a8\u5c55\u5f00\u4e00\u4e0b\u3002 \u4f8b\u9898 \u4e3a\u4e86\u63a8\u5e7f\u8fd9\u4e2a\u5e93\uff0crng_58 \u8fd8\u51c6\u5907\u4e86\u4e24\u573a ACL contest\uff0c\u7528\u6765\u6d4b\u8bd5\u6a21\u677f\u3002\u5f53\u7136\u8fd9\u4e2a\u4e1c\u897f\u7684\u9002\u7528\u8303\u56f4\u8fd8\u6709\u5f85\u89c2\u5bdf\uff0c\u6bd5\u7adf\u6a21\u677f\u7684\u7f3a\u70b9\u662f\u4e0d\u80fd\u8fdb\u53bb\u9b54\u6539\uff0c\u6700\u5178\u578b\u7684\u7f3a\u9677\u53ef\u80fd\u5c31\u662f\u65e0\u6cd5\u7ed9 std::set&lt;int&gt; \u91cc\u7684\u4e8c\u53c9\u6811\u8282\u70b9\u52a0\u536b\u661f\u6570\u636e size \u4ee5\u5b9e\u73b0\u6c42\u7b2c kth \u5927\u8fd9\u79cd\u5b9e\u7528\u64cd\u4f5c\u3002\u3002\u3002\uff1f\u3002\u3002\u3002\uff08\u6bd4\u5982\u9700\u8981\u52a0\u536b\u661f\u6570\u636e\u7684\u5e76\u67e5\u96c6\u53ef\u80fd\u4e5f\u6ca1\u6cd5\u641e\u4e86\uff09 A &#8211; Disjoint Set Union \u5e76\u67e5\u96c6 &#8211; https:\/\/vjudge.net\/problem\/AtCoder-abc181_f B &#8211; Fenwick Tree \u6811\u72b6\u6570\u7ec4 C &#8211; Floor Sum \u7b49\u5dee\u6570\u5217\u6bcf\u4e00\u9879\u9664\u4ee5 M \u4e0b\u53d6\u6574\u7684\u548c\u3002\uff08\u8fd9\u73a9\u610f\u5c45\u7136\u4e5f\u9700\u8981\u8fdb\u6a21\u677f\uff1f\uff09 $$\\sum_{i = 0}^{N [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1706","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/s2tdP7-atl","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1706","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1706"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1706\/revisions"}],"predecessor-version":[{"id":1861,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1706\/revisions\/1861"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1706"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1706"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1706"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}