{"id":2005,"date":"2022-08-15T19:04:57","date_gmt":"2022-08-15T11:04:57","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2005"},"modified":"2022-08-16T20:49:23","modified_gmt":"2022-08-16T12:49:23","slug":"atcoder-beginner-contest-264","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-264\/","title":{"rendered":"AtCoder Beginner Contest 264"},"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\/abc264\">https:\/\/atcoder.jp\/contests\/abc264<\/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-69e4d20744f7c\" 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-69e4d20744f7c\"  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-264\/#%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-264\/#Problem_C_Matrix_Reducing\" title=\"Problem C. Matrix Reducing\">Problem C. Matrix Reducing<\/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-264\/#Problem_D_%E2%80%9Credocta%E2%80%9Dswapii1\" title=\"Problem D. &#8220;redocta&#8221;.swap(i,i+1)\">Problem D. &#8220;redocta&#8221;.swap(i,i+1)<\/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-264\/#Problem_E_Blackout_2\" title=\"Problem E. Blackout 2\">Problem E. Blackout 2<\/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-264\/#Problem_F_Monochromatic_Path\" title=\"Problem F. Monochromatic Path\">Problem F. Monochromatic Path<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-264\/#Problem_G_String_Fair\" title=\"Problem G. String Fair\">Problem G. String Fair<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/atcoder-beginner-contest-264\/#Problem_Ex_Perfect_Binary_Tree\" title=\"Problem Ex. Perfect Binary Tree\">Problem Ex. Perfect Binary Tree<\/a><\/li><\/ul><\/nav><\/div>\n\n<h2><span class=\"ez-toc-section\" id=\"Problem_C_Matrix_Reducing\"><\/span>Problem C. Matrix Reducing<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u6570\u636e\u8303\u56f4\u5f88\u5c0f\uff0c\u968f\u4fbf\u505a\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\nconst int N = 10;\r\nint A&#x5B;N]&#x5B;N], B&#x5B;N]&#x5B;N];\r\nint h1, w1, h2, w2; VI H;\r\n\r\nbool dfs(int k1 = 0, int k2 = 0, int h0 = 0, int w0 = 0) {\r\n    if (k1 == h2) {\r\n        if (k2 == w2) {\r\n            return 1;\r\n        } else {\r\n            FOR(w, w0, w1-(w2-1)+k2) {\r\n                bool ok = 1;\r\n                REP(i, h2) if (A&#x5B;H&#x5B;i]]&#x5B;w] != B&#x5B;i]&#x5B;k2]) {\r\n                    ok = 0;\r\n                    break;\r\n                }\r\n                if (!ok) continue;\r\n                if (dfs(k1, k2+1, h0, w0+1)) return 1;\r\n            }\r\n        }\r\n    } else {\r\n        FOR(h, h0, h1-(h2-1)+k1) {\r\n            H.push_back(h);\r\n            if (dfs(k1+1, k2, h0+1, w0)) return 1;\r\n            H.pop_back();\r\n        }\r\n    }\r\n    return 0;\r\n}\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    RD(h1, w1); REP(i, h1) REP(j, w1) RD(A&#x5B;i]&#x5B;j]);\r\n    RD(h2, w2); REP(i, h2) REP(j, w2) RD(B&#x5B;i]&#x5B;j]);\r\n    puts(dfs() ? &quot;Yes&quot; : &quot;No&quot;);\r\n}\r\n\r\n<\/pre>\n<h2><span class=\"ez-toc-section\" id=\"Problem_D_%E2%80%9Credocta%E2%80%9Dswapii1\"><\/span>Problem D. &#8220;redocta&#8221;.swap(i,i+1)<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u66b4\u529b\u6c42\u4e0b\u9006\u5e8f\u5bf9\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_E_Blackout_2\"><\/span>Problem E. Blackout 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u79bb\u7ebf\u540e\u5012\u53d9\u5e76\u67e5\u96c6\u505a\u6cd5\u663e\u7136\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\n#include &lt;lastweapon\/dsu&gt;\r\nusing namespace lastweapon;\r\nconst int N = int(5e5) + 9;\r\n\r\nint n, m, en, qn;\r\nstruct edge {\r\n    int a, b; bool ok;\r\n    void in() {\r\n        RD(a, b); ok = 1;\r\n        if (a &gt; n) a = 0;\r\n        if (b &gt; n) b = 0;\r\n    }\r\n} E&#x5B;N];\r\nint Q&#x5B;N], Z&#x5B;N];\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, m, en); REP(i, en) E&#x5B;i].in();\r\n    RD(qn); REP(i, qn) E&#x5B;--RD(Q&#x5B;i])].ok = 0;\r\n    dsu d(n+1); REP(i, en) if (E&#x5B;i].ok) d.merge(E&#x5B;i].a, E&#x5B;i].b);\r\n\r\n    DWN(i, qn, 0) {\r\n        Z&#x5B;i] = d.size(0);\r\n        d.merge(E&#x5B;Q&#x5B;i]].a, E&#x5B;Q&#x5B;i]].b);\r\n    }\r\n\r\n    REP(i, qn) printf(&quot;%d\\n&quot;, Z&#x5B;i]-1);\r\n}\r\n\r\n<\/pre>\n<p>atl \u7684 dsu \u5c45\u7136\u8fd8\u5e26 size \u51fd\u6570\u3002\u3002\u3002<br \/>\n\u81f3\u4e8e\u80fd\u4e0d\u80fd\u5728\u7ebf\u561b\u3002\u3002\u3002\u3002\u3002\u3002<br \/>\n&#8211; <a href=\"https:\/\/twitter.com\/kyopro_friends\/status\/1558460630847594496\">https:\/\/twitter.com\/kyopro_friends\/status\/1558460630847594496<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_F_Monochromatic_Path\"><\/span>Problem F. Monochromatic Path<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u6bd4\u8d5b\u65f6\u72b6\u6001\u8bbe\u8ba1\u7684\u65f6 dp[2][n][m] \u7136\u540e\u8f6c\u79fb\u5199\u7206\u4e86\u3002\u3002\u6d6a\u8d39\u4e86\u5927\u91cf\u65f6\u95f4\u3002\u3002<br \/>\n\u679c\u7136\u72b6\u6001\u8981 dp[2][2][n][m] \u624d\u884c\u56e7\u3002\u3002\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_G_String_Fair\"><\/span>Problem G. String Fair<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u66b4\u529b\u81ea\u52a8\u673a dp\uff0c\u4f30\u8ba1\u51fa\u4e00\u4e2a\u5b57\u7b26\u4e32\u957f\u5ea6\u7684\u4e0a\u754c\uff0c\u5982\u679c\u7b54\u6848\u4e00\u76f4\u6709\u66f4\u65b0\u5c31\u8ba4\u4e3a\u662f\u65e0\u7a77\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_Ex_Perfect_Binary_Tree\"><\/span>Problem Ex. Perfect Binary Tree<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u6709\u70b9\u50cf\u662f\u52a8\u6001 dp\u3002\u3002\u3002\uff08\u4f46\u662f\u8fd9\u4e2a\u9898\u53ea\u6709\u52a0\u53f6\u5b50\u6ca1\u6709\u4fee\u6539\u3002\u3002\u6bd4\u5982\u6211\u4eec\u90fd\u76f4\u5230\u52a0\u53f6\u5b50\u6c42\u76f4\u5f84\u662f\u6709\u7b80\u5355\u7b97\u6cd5\u7684\u3002\u3002\uff09<br \/>\n\u90a3\u4e48\u6211\u4eec\u53ea\u8981\u6bcf\u6b21\u52a0\u4e00\u4e2a\u53f6\u5b50\u53bb\u66f4\u65b0\u5411\u4e0a\u7684\u6240\u6709\u8def\u5f84\u5373\u53ef\uff0c\u4e2d\u95f4\u7ef4\u62a4\u4e00\u4e0b delta \u3002\u3002\u6bcf\u6b21\u5411\u4e0a\u66f4\u65b0\u7684\u6df1\u5ea6\u4e0d\u4f1a\u8d85\u8fc7 log(n)\u3002\u3002\u6df1\u5ea6\u5927\u4e8e\u8fd9\u4e2a\u6570\u7684\u53f6\u5b50\u76f4\u63a5\u8df3\u8fc7\u5373\u53ef\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/number&gt;\r\nusing namespace lastweapon;\r\nconst int N = int(3e5) + 9, LOGN = 20;\r\nVI adj&#x5B;N]; Int f&#x5B;N]&#x5B;LOGN], s&#x5B;N]&#x5B;LOGN]; int p&#x5B;N], d&#x5B;N];\r\nint n;\r\n\r\nvoid upd(int x) {\r\n    int y = p&#x5B;x]; d&#x5B;x] = d&#x5B;y] + 1; if (d&#x5B;x] &gt;= LOGN) return;\r\n    Int d = f&#x5B;x]&#x5B;0] = 1; for (int i=0;x;++i) {\r\n        s&#x5B;y]&#x5B;i] += d; d *= (s&#x5B;y]&#x5B;i] - f&#x5B;x]&#x5B;i]); f&#x5B;y]&#x5B;i+1] += d;\r\n        x = y; y = p&#x5B;x];\r\n    }\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    MOD = 998244353;\r\n    RD(n); cout &lt;&lt; (f&#x5B;0]&#x5B;0] = 1) &lt;&lt; endl;\r\n    FOR(i, 1, n) {\r\n        adj&#x5B;--RD(p&#x5B;i])].PB(i); upd(i);\r\n        Int z = 0; REP(i, LOGN) z += f&#x5B;0]&#x5B;i];\r\n        cout &lt;&lt; z &lt;&lt; endl;\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4f20\u9001\u95e8 https:\/\/atcoder.jp\/contests\/abc264 Problem C. Matrix Reducing \u6570\u636e\u8303\u56f4\u5f88\u5c0f\uff0c\u968f\u4fbf\u505a\u3002 #include &lt;lastweapon\/io&gt; using namespace lastweapon; const int N = 10; int A&#x5B;N]&#x5B;N], B&#x5B;N]&#x5B;N]; int h1, w1, h2, w2; VI H; bool dfs(int k1 = 0, int k2 = 0, int h0 = 0, int w0 = 0) { if (k1 == h2) { if (k2 == w2) { [&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-2005","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wl","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2005","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=2005"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2005\/revisions"}],"predecessor-version":[{"id":2006,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2005\/revisions\/2006"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2005"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2005"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2005"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}