{"id":1744,"date":"2021-08-11T13:14:11","date_gmt":"2021-08-11T05:14:11","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1744"},"modified":"2021-08-11T13:30:08","modified_gmt":"2021-08-11T05:30:08","slug":"codeforces-round-737-div-2","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-737-div-2\/","title":{"rendered":"Codeforces Round #737 (Div. 2)"},"content":{"rendered":"<h1><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><\/h1>\n<p><a href=\"https:\/\/codeforces.com\/contest\/1557\">https:\/\/codeforces.com\/contest\/1557<\/a><\/p>\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-69dc9433883e7\" 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-69dc9433883e7\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-737-div-2\/#%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-1'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-737-div-2\/#Problem_B_Moamen_and_k-subarrays\" title=\"Problem B. Moamen and k-subarrays\">Problem B. Moamen and k-subarrays<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-737-div-2\/#Problem_C_Moamen_and_XOR\" title=\"Problem C. Moamen and XOR\">Problem C. Moamen and XOR<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-737-div-2\/#Problem_D_Ezzat_and_Grid\" title=\"Problem D. Ezzat and Grid\">Problem D. Ezzat and Grid<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-737-div-2\/#Problem_E_Assiut_Chess\" title=\"Problem E. Assiut Chess\">Problem E. Assiut Chess<\/a><\/li><\/ul><\/nav><\/div>\n\n<p>\u8bf4\u7740\u8981\u56de Div1\uff0c\u7ed3\u679c\u5206\u8d8a\u6765\u8d8a\u4f4e\u4e86\u3002\u3002\u3002<br \/>\n\u4e0a\u7d2b\u540d\u597d\u96be\u554a\u3002\u3002\u3002\u3002\uff08\u66b4\u98ce\u54ed\u6ce3\uff09<\/p>\n<h1><span class=\"ez-toc-section\" id=\"Problem_B_Moamen_and_k-subarrays\"><\/span>Problem B. Moamen and k-subarrays<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\uff0c\u62c6\u6210 k \u4e2a \u5b50\u6bb5\uff0c\u518d\u91cd\u65b0\u6392\u5e8f\uff0c\u95ee\u8fd9\u6837\u662f\u5426\u80fd\u5c06\u8fd9\u4e2a\u6570\u7ec4\u6392\u5e8f\uff0c\u4fdd\u8bc1\u6570\u5b57\u4e0d\u76f8\u540c\u3002<\/p>\n<p>\u7136\u540e\u5f00\u59cb\u9ed8\u8ba4\u9700\u8981\u62c6 n \u4efd\uff0c\u7136\u540e\u770b\u76f8\u90bb\u4f4d\u7f6e\u5982\u679c\u518d\u6392\u5e8f\u540e\u4e5f\u76f8\u90bb\u5c31\u8ba9\u9700\u8981\u62c6\u7684\u4efd\u6570 -1.<\/p>\n<h1><span class=\"ez-toc-section\" id=\"Problem_C_Moamen_and_XOR\"><\/span>Problem C. Moamen and XOR<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p>\u7ed9\u5b9a n,k \u95ee\u6709\u591a\u5c11\u7ec4\u957f\u5ea6\u4e3a n \u7684\u6570\u7ec4 a\uff0c\u6ee1\u8db3 &amp;&amp; \u548c\u5927\u4e8e\u7b49\u4e8e xor \u548c\u3002(ai &lt;= 2^k)<\/p>\n<p>\u5bf9 n \u5206\u5947\u5076\u8ba8\u8bba\u5373\u53ef\uff0c\u6bd4\u8d5b\u7684\u65f6\u5019\u5bf9\u5e42\u6b21\u53d6\u6a21\u7ed3\u679c debug \u4e86\u597d\u4e45\u4e0d\u80fd\u66f4\u8822\u3002\u3002\u3002<\/p>\n<h1><span class=\"ez-toc-section\" id=\"Problem_D_Ezzat_and_Grid\"><\/span>Problem D. Ezzat and Grid<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p>\u7ed9\u5b9a\u4e00\u4e2a 01 \u77e9\u9635\uff0c\u95ee\u81f3\u5c11\u5220\u6389\u591a\u5c11\u884c\uff0c\u4f7f\u5f97\u76f8\u90bb\u884c \u81f3\u5c11\u518d\u67d0\u4e00\u5217\u90fd\u6709 1\u3002<\/p>\n<p>\u5bf9\u4e8e\u6bcf\u4e00\u884c\uff0c\u6211\u4eec\u5411\u4e0b\u8fde\u8fb9\uff0c\u8fd9\u4e2a\u4e1c\u897f\u663e\u7136\u662f\u4e00\u4e2a dag\uff0cdp \u6c42\u6700\u957f\u94fe\u5373\u53ef\u3002<br \/>\n\u56e0\u4e3a\u662f\u6c42\u6700\u957f\u94fe\uff0c\u53ef\u4ee5\u5bf9\u56fe\u53ef\u4ee5\u6709\u6240\u7b80\u5316\uff0c\u5c06\u8fb9\u7684\u89c4\u6a21\u7f29\u5c0f\u4e3a O(n)\u3002<\/p>\n<p>\u6240\u4ee5\u96be\u70b9\u5728\u4e8e\u5982\u4f55\u7528\u6570\u636e\u7ed3\u6784\u5e2e\u52a9\u5efa\u56fe\u3002<br \/>\n\u6700\u7b80\u5355\u7684\u65b9\u5f0f\u5f53\u7136\u662f\u7528 set \u53bb\u7ef4\u62a4\u533a\u95f4\u96c6\u5408\uff0c\u8fd9\u4e2a\u4e1c\u897f\u5728\u5f88\u591a\u8ba1\u7b97\u51e0\u4f55\u9898\u76ee\u91cc\u5e94\u8be5\u7ecf\u5e38\u4f1a\u7528\u5230\u3002<\/p>\n<h1><span class=\"ez-toc-section\" id=\"Problem_E_Assiut_Chess\"><\/span>Problem E. Assiut Chess<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p>\u4ea4\u4e92\u9898\u3002\u68cb\u76d8\u4e0a\u6709\u4e00\u4e2a\u770b\u4e0d\u89c1\u7684 King\uff0c\u7ed9\u4f60\u4e00\u4e2a Queen\uff0c\u5728\u9650\u5b9a\u6b65\u6570\u5185\u5c06\u6b7b\u8fd9\u4e2a King\u3002<br \/>\nKing \u4e0d\u80fd\u8d70\u5230\u88ab\u4f60\u4e00\u6b65\u53ef\u4ee5\u5c06\u6b7b\u7684\u4f4d\u7f6e\u3002<\/p>\n<p>\u57fa\u672c\u60f3\u6cd5\u662f\u56fa\u5b9a\u6211\u7684\u4f4d\u7f6e\uff0c\u7136\u540e\u4e00\u6b65\u6b65\u628a\u5bf9\u624b\u5361\u5230\u56db\u89d2\u3002<br \/>\n\u4f46\u662f\u8c8c\u4f3c\u6709\u4e00\u4e9b\u60c5\u51b5\u9700\u8981\u7279\u6b8a\u5904\u7406\uff0c\u6211\u60f3\u4e0d\u592a\u6e05\u695a\u3002\u3002\u3002\u7136\u540e\u770b\u6b65\u6570\u6bd4\u8f83\u5bbd\u677e\u8bd5\u56fe\u7528\u968f\u673a\u5316\u4e71\u641e\u8fc7\u53bb\u4f46\u662f\u5931\u8d25\u4e86\u3002\u3002\u3002<br \/>\n\u561b\u3002\u3002\u3002\u611f\u89c9\u8fd9\u79cd\u9898\u6570\u636e\u7740\u5b9e\u4e5f\u4e0d\u592a\u597d\u51fa\u3002\u3002\u3002\u679c\u4e0d\u5176\u7136\uff0c\u73b0\u573a\u4e5f\u786e\u5b9e\u88ab\u5404\u79cd\u4e71\u641e\u7206\u8fc7\u53bb\u4e86\u3002\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4f20\u9001\u95e8 https:\/\/codeforces.com\/contest\/1557 \u8bf4\u7740\u8981\u56de Div1\uff0c\u7ed3\u679c\u5206\u8d8a\u6765\u8d8a\u4f4e\u4e86\u3002\u3002\u3002 \u4e0a\u7d2b\u540d\u597d\u96be\u554a\u3002\u3002\u3002\u3002\uff08\u66b4\u98ce\u54ed\u6ce3\uff09 Problem B. Moamen and k-subarrays \u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\uff0c\u62c6\u6210 k \u4e2a \u5b50\u6bb5\uff0c\u518d\u91cd\u65b0\u6392\u5e8f\uff0c\u95ee\u8fd9\u6837\u662f\u5426\u80fd\u5c06\u8fd9\u4e2a\u6570\u7ec4\u6392\u5e8f\uff0c\u4fdd\u8bc1\u6570\u5b57\u4e0d\u76f8\u540c\u3002 \u7136\u540e\u5f00\u59cb\u9ed8\u8ba4\u9700\u8981\u62c6 n \u4efd\uff0c\u7136\u540e\u770b\u76f8\u90bb\u4f4d\u7f6e\u5982\u679c\u518d\u6392\u5e8f\u540e\u4e5f\u76f8\u90bb\u5c31\u8ba9\u9700\u8981\u62c6\u7684\u4efd\u6570 -1. Problem C. Moamen and XOR \u7ed9\u5b9a n,k \u95ee\u6709\u591a\u5c11\u7ec4\u957f\u5ea6\u4e3a n \u7684\u6570\u7ec4 a\uff0c\u6ee1\u8db3 &amp;&amp; \u548c\u5927\u4e8e\u7b49\u4e8e xor \u548c\u3002(ai &lt;= 2^k) \u5bf9 n \u5206\u5947\u5076\u8ba8\u8bba\u5373\u53ef\uff0c\u6bd4\u8d5b\u7684\u65f6\u5019\u5bf9\u5e42\u6b21\u53d6\u6a21\u7ed3\u679c debug \u4e86\u597d\u4e45\u4e0d\u80fd\u66f4\u8822\u3002\u3002\u3002 Problem D. Ezzat and Grid \u7ed9\u5b9a\u4e00\u4e2a 01 \u77e9\u9635\uff0c\u95ee\u81f3\u5c11\u5220\u6389\u591a\u5c11\u884c\uff0c\u4f7f\u5f97\u76f8\u90bb\u884c \u81f3\u5c11\u518d\u67d0\u4e00\u5217\u90fd\u6709 1\u3002 \u5bf9\u4e8e\u6bcf\u4e00\u884c\uff0c\u6211\u4eec\u5411\u4e0b\u8fde\u8fb9\uff0c\u8fd9\u4e2a\u4e1c\u897f\u663e\u7136\u662f\u4e00\u4e2a dag\uff0cdp \u6c42\u6700\u957f\u94fe\u5373\u53ef\u3002 \u56e0\u4e3a\u662f\u6c42\u6700\u957f\u94fe\uff0c\u53ef\u4ee5\u5bf9\u56fe\u53ef\u4ee5\u6709\u6240\u7b80\u5316\uff0c\u5c06\u8fb9\u7684\u89c4\u6a21\u7f29\u5c0f\u4e3a O(n)\u3002 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","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-1744","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-s8","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1744","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=1744"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1744\/revisions"}],"predecessor-version":[{"id":1745,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1744\/revisions\/1745"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1744"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1744"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1744"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}