{"id":2003,"date":"2022-08-11T13:59:08","date_gmt":"2022-08-11T05:59:08","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2003"},"modified":"2022-08-13T13:50:11","modified_gmt":"2022-08-13T05:50:11","slug":"atcoder-beginner-contest-263","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-263\/","title":{"rendered":"AtCoder Beginner Contest 263"},"content":{"rendered":"<h2><span class=\"ez-toc-section\" id=\"%E4%BC%A0%E9%80%81%E9%97%A8\"><\/span>\u4f20\u9001\u95e8<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"https:\/\/atcoder.jp\/contests\/abc263\">https:\/\/atcoder.jp\/contests\/abc263<\/a><\/li>\n<\/ul>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69e4b0c9b4fbe\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69e4b0c9b4fbe\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-263\/#%E4%BC%A0%E9%80%81%E9%97%A8\" title=\"\u4f20\u9001\u95e8\">\u4f20\u9001\u95e8<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-263\/#Problem_E_Sugoroku_3\" title=\"Problem E. Sugoroku 3\">Problem E. Sugoroku 3<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-263\/#Problem_F_Tournament\" title=\"Problem F. Tournament\">Problem F. Tournament<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-263\/#Problem_G_Erasing_Prime_Pairs\" title=\"Problem G. Erasing Prime Pairs\">Problem G. Erasing Prime Pairs<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-263\/#Problem_Ex_Intersection_2\" title=\"Problem Ex. Intersection 2\">Problem Ex. Intersection 2<\/a><\/li><\/ul><\/nav><\/div>\n\n<h2><span class=\"ez-toc-section\" id=\"Problem_E_Sugoroku_3\"><\/span>Problem E. Sugoroku 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"https:\/\/www.yystv.cn\/p\/1881\">\u88ab\u9057\u5fd8\u7684\u6e38\u620f\u53f2\uff1a\u201c\u7eb8\u724c\u9a6c\u91cc\u5965\u201d\u548c\u201c\u684c\u4e0a\u585e\u5c14\u8fbe\u201d<\/a><\/li>\n<\/ul>\n<p>\u9898\u89e3\uff1a\u5148\u5199\u8f6c\u79fb\u65b9\u7a0b\uff0c\u53d1\u73b0\u81ea\u73af\u7684\u60c5\u51b5\u53ef\u4ee5\u6d88\u6389\uff0c\u7136\u540e\u5c31\u5f88 straight forward\u3002<br \/>\n\uff08<a href=\"https:\/\/atcoder.jp\/contests\/abc263\/editorial\/4558\">\u5b98\u65b9\u9898\u89e3<\/a> \u5c45\u7136\u6ca1\u6709\u770b\u61c2\u3002\u3002\u3002\uff09<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/number&gt;\r\n#include &lt;lastweapon\/fenwicktree&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(2e5) + 9;\r\nInt f&#x5B;N]; int a&#x5B;N];\r\nint n;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); REP(i, n-1) RD(a&#x5B;i]);\r\n    fenwick_tree&lt;Int&gt; T(n);\r\n    DWN(i, n-1, 0) f&#x5B;i] = (T.sum(i+1, i+a&#x5B;i]+1) + (a&#x5B;i]+1)) \/ a&#x5B;i];\r\n    cout &lt;&lt; f&#x5B;0] &lt;&lt; endl;\r\n}\r\n\r\n\r\n<\/pre>\n<h2><span class=\"ez-toc-section\" id=\"Problem_F_Tournament\"><\/span>Problem F. Tournament<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>dp[u][i] \u8868\u793a\u5f53\u524d\u8282\u70b9 u\uff0c\u83b7\u80dc\u7684\u73a9\u5bb6\u4e3a i \u7684\u6700\u5927\u5f97\u5206\u3002\u90a3\u4e48 i \u5f53\u524d\u8f6e\u6b21\u7684\u8fde\u80dc\u60c5\u51b5\u662f\u53ef\u4ee5\u901a\u8fc7 u \u7684\u9ad8\u5ea6\u63a8\u7b97\u51fa\u6765\u7684\u3002<br \/>\n\u5e76\u4e14\u73a9\u5bb6 i \u7684\u5f97\u5206\u548c\u5bf9\u624b\u662f\u65e0\u5173\u7684\uff0c\u56e0\u6b64 i \u5b9e\u9645\u4e0a\u662f\u53ef\u4ee5\u4e0d\u8bb0\u5f55\u5728\u72b6\u6001\u4e2d\u7684\uff0c\u590d\u6742\u5ea6 O(n2^n)\u3002<\/p>\n<p>\u5b9e\u9645\u5728\u5199\u7684\u65f6\u5019\uff0c\u5728\u53f6\u5b50\u5904\u7ed3\u7b97\u5f97\u5206\u4f1a\u66f4\u597d\u5199\u3002<br \/>\n\u72b6\u6001\u6539\u6210 dp[u][k] \u8868\u793a\u5f53\u524d\u8282\u70b9\u4e3a u\uff0c\u4e14\u8be5\u8282\u70b9\u7684\u80dc\u5229\u8005\uff0c\u672a\u6765\u5411\u4e0a\u8fd8\u4f1a\u8fde\u80dc k \u573a\u7684\u6700\u5927\u5f97\u5206\u3002<br \/>\n\uff08\u8fd9\u4e2a\u5728\u72b6\u6001\u4e2d\u5f15\u5165\u672a\u6765\u4e8b\u4ef6\u7684\u65b9\u6cd5\u5f88\u7c7b\u4f3c\u90a3\u4e2a SPOJ ZUMA\uff09<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/bitwise&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(16);\r\nLL dp&#x5B;1&lt;&lt;N]&#x5B;N+1]; int C&#x5B;1&lt;&lt;N]&#x5B;N+1];\r\nint n;\r\n\r\n#define lx (x&lt;&lt;1)\r\n#define rx (lx|1)\r\nLL f(int x, int k) {\r\n    if (x &gt;= _1(n)) return C&#x5B;x-_1(n)]&#x5B;k];\r\n    LL &amp;z = dp&#x5B;x]&#x5B;k];\r\n    if (!z) {\r\n        ++k;\r\n        z = max(f(lx,k)+f(rx,0),f(lx,0)+f(rx,k));\r\n    }\r\n    return z;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); REP(i, _1(n)) REP_1(j, n) RD(C&#x5B;i]&#x5B;j]);\r\n    cout &lt;&lt; f(1, 0) &lt;&lt; endl;\r\n}\r\n\r\n\r\n<\/pre>\n<h2><span class=\"ez-toc-section\" id=\"Problem_G_Erasing_Prime_Pairs\"><\/span>Problem G. Erasing Prime Pairs<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u5e26\u82b1\u6811\u53ef\u4ee5\u5904\u7406\u8fb9\u6743\u7684\u60c5\u51b5\u4e48\uff0c\u6211\u4e0d\u592a\u786e\u5b9a= =<br \/>\n\u90a3\u4e48\u9996\u5148\u4e0d\u8003\u8651 1 \u7684\u60c5\u51b5\uff0c\u5c31\u662f\u4e8c\u5206\u56fe\u5339\u914d\uff0c\u4e8e\u662f\u6211\u4eec\u53ef\u4ee5\u679a\u4e3e 1 \u4e4b\u95f4\u7684\u5339\u914d\u91cd\u6570\uff0c\u7136\u540e\u5f53\u6210\u4e8c\u5206\u56fe\u5339\u914d\u6765\u505a\uff0c\u8fd9\u4e2a\u51fd\u6570\u663e\u7136\u662f\u51f8\u7684\uff0c\u90a3\u4e48\u53ef\u4ee5\u4e8c\u5206\u7b54\u6848\u3002<br \/>\n\u53e6\u4e00\u65b9\u9762\u8fd9\u4e2a\u51f8\u51fd\u6570\u5341\u5206\u7279\u6b8a\uff0cdelta \u662f {1,1,1,1,0,0,0,0,-1,-1,-1,-1} \u8fd9\u6837\u7684 pattern\uff0c\u53ef\u4ee5\u76f4\u63a5\u8ba1\u7b97\u4e24\u8fb9\u7684\u51fd\u6570\u503c\uff0c\u627e\u5230\u6700\u4f18\u70b9\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_Ex_Intersection_2\"><\/span>Problem Ex. Intersection 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7ed9\u5b9a n \u6761\u76f4\u7ebf\uff0c\u95ee\u6240\u6709\u7684\u4ea4\u70b9\u91cc\uff0c\u8ddd\u79bb\u539f\u70b9\u7b2c k \u8fdc\u7684\u70b9\u7684\u8ddd\u79bb\u662f\u591a\u5c11\u3002<\/p>\n<p>\u6211\u4eec\u8981\u8bbe\u6cd5\u907f\u514d\u7b97\u51fa\u6240\u6709\u7684\u4ea4\u70b9\u3002<br \/>\n\u8003\u8651\u4e8c\u5206\u7b54\u6848\uff0c\u90a3\u4e48\u5b50\u95ee\u9898 f(x) \u53d8\u6210 n \u6761\u76f4\u7ebf\u88ab\u534a\u5f84\u4e3a x \u7684\u5706\u5207\u5272\uff0c\u7136\u540e\u8fd9 n \u6761\u7ebf\u6bb5\u6c42\u4ea4\u70b9\u603b\u6570\uff0c<br \/>\n\u56e0\u4e3a\u6240\u6709\u4ea4\u70b9\u90fd\u5728\u5706\u5468\u4e0a\uff0c\u6240\u4ee5\u53ef\u4ee5\u5f00\u4e2a\u6811\u72b6\u6570\u7ec4\u7528\u8f90\u89d2\u505a\u626b\u63cf\u7ebf\uff0c\u590d\u6742\u5ea6 O(nlogn)\u3002<\/p>\n<p>\u96be\u70b9\u6700\u540e\u53ea\u6709\u76f4\u7ebf\u548c\u5706\u6c42\u4ea4\u70b9\u3002\u3002\u3002\uff08\u8fd8\u597d\u6a21\u677f\u91cc\u6709\u73b0\u6210\u7684\u3002\u3002\u76f8\u5207\u7684\u60c5\u51b5\u4e0d\u7528\u8003\u8651\uff0c\u56e0\u4e3a\u6d4b\u5ea6\u4e3a 0\u3002\u3002<br \/>\n\u6700\u540e\u8fd8\u9700\u8981\u7528\u4e0d\u7b49\u5f0f\u4f30\u8ba1\u4e00\u4e0b\u4e8c\u5206\u7684\u4e0a\u754c\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/geometry&gt;\r\n#include &lt;lastweapon\/fenwicktree&gt;\r\n\r\nusing namespace lastweapon;\r\nusing namespace CG;\r\n\r\nconst int N = int(5e4) + 9;\r\nDB d&#x5B;N]; Line L&#x5B;N];\r\nint n, K;\r\n\r\nint f(DB r) {\r\n    Circle C(Po(0, 0), r); r *= r;\r\n    vector&lt;pair&lt;double, int&gt;&gt; P; int m = 0;\r\n    REP(i, n) if (d&#x5B;i] &lt; r){\r\n        Po p0, p1; C.getIntersect(L&#x5B;i], p0, p1);\r\n        P.PB({p0.arg(), m}); P.PB({p1.arg(), m});\r\n        ++m;\r\n    }\r\n\r\n    int z = 0; VI l(m, -1); fenwick_tree&lt;int&gt; T(m*2); SRT(P);\r\n    REP(i, m*2) {\r\n        int x = P&#x5B;i].se;\r\n        if (~l&#x5B;x]) {\r\n            T.add(l&#x5B;x], -1);\r\n            z += T.sum(l&#x5B;x], i);\r\n        } else {\r\n            T.add(l&#x5B;x] = i, 1);\r\n        }\r\n    }\r\n    return z;\r\n}\r\n\r\nint main(){\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n#endif\r\n\r\n    RD(n, K); REP(i, n) {\r\n        int A,B,C; RD(A,B,C);\r\n        if (!A)\r\n            L&#x5B;i] = Line(Po(0, (DB)-C\/B), Po(1, (DB)-C\/B));\r\n        else if (!B)\r\n            L&#x5B;i] = Line(Po((DB)-C\/A, 0), Po((DB)-C\/A, 1));\r\n        else if (!C)\r\n            L&#x5B;i] = Line(Po(0, 0), Po(-B, A));\r\n        else\r\n            L&#x5B;i] = Line(Po((DB)-C\/A, 0), Po(0, (DB)-C\/B));\r\n        d&#x5B;i] = dist2(L&#x5B;i], Po(0, 0));\r\n    }\r\n\r\n    DB l = 0, r = 1e7;\r\n    DO(233) {\r\n        DB m = (l + r) \/ 2;\r\n        if (f(m) &lt; K) l = m;\r\n        else r = m;\r\n    }\r\n    printf(&quot;%.9f\\n&quot;, l);\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4f20\u9001\u95e8 https:\/\/atcoder.jp\/contests\/abc263 Problem E. Sugoroku 3 \u88ab\u9057\u5fd8\u7684\u6e38\u620f\u53f2\uff1a\u201c\u7eb8\u724c\u9a6c\u91cc\u5965\u201d\u548c\u201c\u684c\u4e0a\u585e\u5c14\u8fbe\u201d \u9898\u89e3\uff1a\u5148\u5199\u8f6c\u79fb\u65b9\u7a0b\uff0c\u53d1\u73b0\u81ea\u73af\u7684\u60c5\u51b5\u53ef\u4ee5\u6d88\u6389\uff0c\u7136\u540e\u5c31\u5f88 straight forward\u3002 \uff08\u5b98\u65b9\u9898\u89e3 \u5c45\u7136\u6ca1\u6709\u770b\u61c2\u3002\u3002\u3002\uff09 #include &lt;lastweapon\/number&gt; #include &lt;lastweapon\/fenwicktree&gt; using namespace lastweapon; const int N = int(2e5) + 9; Int f&#x5B;N]; int a&#x5B;N]; int n; int main(){ #ifndef ONLINE_JUDGE freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin); \/\/freopen(&quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&quot;, &quot;w&quot;, stdout); #endif RD(n); REP(i, n-1) RD(a&#x5B;i]); fenwick_tree&lt;Int&gt; T(n); DWN(i, n-1, 0) f&#x5B;i] = (T.sum(i+1, [&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-2003","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wj","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2003","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=2003"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2003\/revisions"}],"predecessor-version":[{"id":2004,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2003\/revisions\/2004"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2003"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2003"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2003"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}