{"id":1790,"date":"2021-10-19T15:44:00","date_gmt":"2021-10-19T07:44:00","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1790"},"modified":"2021-10-20T09:52:28","modified_gmt":"2021-10-20T01:52:28","slug":"codeforces-round-749","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-749\/","title":{"rendered":"Codeforces Round #749"},"content":{"rendered":"<p><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-747\/\">\u53c8\u662f<\/a> \u4e00\u8f6e\u6784\u9020 Round\u3002\u3002\u3002<br \/>\n\u8981\u60f3\u4e0a\u5206\u5fc5\u987b\u8981\u77ac\u79d2\u6389 E\u3001F\u3002\u3002\u3002<\/p>\n<p><a href=\"https:\/\/codeforces.com\/contest\/1586\">https:\/\/codeforces.com\/contest\/1586<\/a><br \/>\n<a href=\"https:\/\/zhuanlan.zhihu.com\/p\/422490422\">https:\/\/zhuanlan.zhihu.com\/p\/422490422<\/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-6a0ac559990df\" 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-6a0ac559990df\"  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\/codeforces-round-749\/#Problem_E_Moment_of_Bloom\" title=\"Problem E. Moment of Bloom\">Problem E. Moment of Bloom<\/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\/codeforces-round-749\/#Problem_F_Defender_of_Childhood_Dreams\" title=\"Problem F. Defender of Childhood Dreams\">Problem F. Defender of Childhood Dreams<\/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\/codeforces-round-749\/#Problem_G_Omkar_and_Time_Travel\" title=\"Problem G. Omkar and Time Travel\">Problem G. Omkar and Time Travel<\/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\/codeforces-round-749\/#Problem_H_Omkar_and_Tours\" title=\"Problem H. Omkar and Tours\">Problem H. Omkar and Tours<\/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\/codeforces-round-749\/#Problem_I_Omkar_and_Mosaic\" title=\"Problem I. Omkar and Mosaic\">Problem I. Omkar and Mosaic<\/a><\/li><\/ul><\/nav><\/div>\n\n<h2><span class=\"ez-toc-section\" id=\"Problem_E_Moment_of_Bloom\"><\/span>Problem E. Moment of Bloom<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u6784\u9020\u3002<br \/>\n\u4efb\u53d6\u4e00\u9897\u751f\u6210\u6811\uff0c\u7136\u540e\u76f4\u63a5\u6811\u4e0a\u66b4\u529b\u62c9\u8def\u5f84\u5373\u53ef\uff0c\u4e0d\u9700\u8981\u5199 lca = =\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_F_Defender_of_Childhood_Dreams\"><\/span>Problem F. Defender of Childhood Dreams<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u6784\u9020\u3002<br \/>\n\u5047\u8bbe\u6709 c \u79cd\u989c\u8272\uff0c\u90a3\u4e48\u6700\u5927\u80fd\u652f\u6301 c^k\u00a0\u4e2a\u70b9\uff0c\u7b54\u6848\u5c31\u662f ceil(log(n,k))\u3002<br \/>\n\u5982\u4f55\u6784\u9020\uff1f\u6bcf\u6b21\u5c06\u5f53\u524d\u70b9\u96c6\uff0c\u6309\u7167\u987a\u5e8f\u62c6\u6210 k \u7ec4\uff0c\u7ec4\u5916\u90e8\u4e4b\u95f4\u5168\u90e8\u8fde\u989c\u8272 c\uff0c\u5185\u90e8\u4e0d\u518d\u4f7f\u7528\u989c\u8272 c\uff0c\u9012\u5f52\u6784\u9020\u4e0b\u53bb\u5373\u53ef\u3002<\/p>\n<p>\u5b9e\u73b0\u8d77\u6765\u8c8c\u4f3c\u53ea\u8981\u4e00\u884c\uff0c\u4e0d\u9700\u8981\u61a8\u61a8\u7684\u53bb\u5199\u9012\u5f52\u3002\u3002\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_G_Omkar_and_Time_Travel\"><\/span>Problem G. Omkar and Time Travel<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u9898\u76ee\u80cc\u666f\u662f\u547d\u8fd0\u77f3\u4e4b\u95e8\uff01<br \/>\n\u611f\u89c9\u6709\u70b9\u50cf <a href=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-global-round-15\/\">Codeforces Global Round 15 \u7684 F<\/a> \u554a\u3002\u3002\u3002<br \/>\n\u6211\u4eec\u4e0d\u59a8\u7528\u90a3\u4e2a\u9898\u7684\u8bed\u8a00\u91cd\u65b0\u53d9\u8ff0\u8fd9\u4e2a\u9898\uff0c\u770b\u770b\u6709\u4ec0\u4e48\u4e0d\u540c\u3002<\/p>\n<ul>\n<li>\u521d\u59cb\u6240\u91cc\u7684\u4f20\u9001\u95e8\u90fd\u662f active \u7684<\/li>\n<li>\u4f20\u9001\u4e4b\u540e\u4f1a\u8ba9\u4f20\u9001\u4f4d\u7f6e\u5728\u76ee\u6807\u70b9\u4e4b\u540e\u7684\u4f20\u9001\u95e8\u66f4\u65b0\u4e3a active<\/li>\n<li>\u7ecf\u8fc7\u7684 inactive \u4e0d\u4f1a\u53d8\u6210 active<\/li>\n<li>\u6700\u540e\u6c42\u7684\u4ece\u603b\u7684\u65f6\u95f4\u53d8\u6210\u4f20\u9001\u53d1\u751f\u7684\u6b21\u6570<\/li>\n<\/ul>\n<p>\u7ed3\u679c\u611f\u89c9\u53cd\u800c\u66f4\u7b80\u5355\u4e86\u3002\u3002\u3002dp \u72b6\u6001\u4e5f\u7c7b\u4f3c\u3002\u3002<br \/>\nf[i] \u8868\u793a\u518d\u56de\u5230\u8fd9\u4e2a\u4f20\u9001\u95e8\u9700\u8981\u7ecf\u8fc7\u4f20\u9001\u591a\u5c11\u6b21\u5373\u53ef\uff0c\u53ea\u9700\u8981\u8003\u8651\u88ab\u8fd9\u7ec4\u533a\u95f4\u5b8c\u5168\u5305\u542b\u7684\u533a\u95f4\u5373\u53ef\uff0c\u53ef\u4ee5\u6392\u5e8f\u540e\u7528 \u6811\u72b6\u6570\u7ec4 \u7b80\u5355\u7ef4\u62a4\u3002<br \/>\n\u8003\u8651\u6700\u540e\u6240\u6709\u72b6\u6001\u90fd inactive \u7684\u60c5\u51b5\uff0c\u7b54\u6848\u5c31\u662f\u6240\u6709 f[i] \u7684\u548c\u3002<\/p>\n<p>\u6700\u540e\u5982\u679c\u8be2\u95ee\u5141\u8bb8\u4e00\u4e9b\u72b6\u6001\u4e3a active\uff0c\u53ea\u8981\u5904\u7406\u51fa\u8fd9\u4e9b\u72b6\u6001\u662f\u5426\u53ef\u4ee5\u8df3\u8fc7\u5373\u53ef\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_H_Omkar_and_Tours\"><\/span>Problem H. Omkar and Tours<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><del>\u611f\u89c9\u6bd4\u524d\u9762\u51e0\u4e2a\u9898\u90fd\u7b80\u5355<\/del><br \/>\n\u6709\u70b9\u50cf <a href=\"https:\/\/www.shuizilong.com\/house\/archives\/facebook-hacker-cup-2021-round3\/\">\u524d\u51e0\u5929 FHC R3 \u7684\u6700\u540e\u4e00\u9898<\/a>\u3002<br \/>\n\u79bb\u7ebf\u5e76\u67e5\u96c6\u5373\u53ef\uff0c\u7b2c\u4e8c\u95ee\u7c7b\u4f3c\u865a\u6811\u6c42\u76f4\u5f84\uff0c\u540c\u6837\u53ef\u4ee5\u5728\u5e76\u67e5\u96c6\u91cc\u7b80\u5355\u7ef4\u62a4\u3002<br \/>\n\u9700\u8981\u6c42\u6811\u4e0a\u4e24\u70b9\u4e4b\u95f4\u8fb9\u6743\u7684\u6700\u5927\u503c\uff0c\u663e\u7136\u500d\u589e\u7956\u5148\u6700\u597d\u5199\u3002\uff08<del>\u5982\u679c E \u9898\u4e0d\u5c0f\u5fc3\u5199\u4e86 lca \u53ef\u4ee5\u7c98\u8fc7\u6765\u3002\u3002\u3002<\/del>\uff09<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_I_Omkar_and_Mosaic\"><\/span>Problem I. Omkar and Mosaic<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u6784\u9020\uff1f<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u53c8\u662f \u4e00\u8f6e\u6784\u9020 Round\u3002\u3002\u3002 \u8981\u60f3\u4e0a\u5206\u5fc5\u987b\u8981\u77ac\u79d2\u6389 E\u3001F\u3002\u3002\u3002 https:\/\/codeforces.com\/contest\/1586 https:\/\/zhuanlan.zhihu.com\/p\/422490422 Problem E. Moment of Bloom \u6784\u9020\u3002 \u4efb\u53d6\u4e00\u9897\u751f\u6210\u6811\uff0c\u7136\u540e\u76f4\u63a5\u6811\u4e0a\u66b4\u529b\u62c9\u8def\u5f84\u5373\u53ef\uff0c\u4e0d\u9700\u8981\u5199 lca = =\u3002 Problem F. Defender of Childhood Dreams \u6784\u9020\u3002 \u5047\u8bbe\u6709 c \u79cd\u989c\u8272\uff0c\u90a3\u4e48\u6700\u5927\u80fd\u652f\u6301 c^k\u00a0\u4e2a\u70b9\uff0c\u7b54\u6848\u5c31\u662f ceil(log(n,k))\u3002 \u5982\u4f55\u6784\u9020\uff1f\u6bcf\u6b21\u5c06\u5f53\u524d\u70b9\u96c6\uff0c\u6309\u7167\u987a\u5e8f\u62c6\u6210 k \u7ec4\uff0c\u7ec4\u5916\u90e8\u4e4b\u95f4\u5168\u90e8\u8fde\u989c\u8272 c\uff0c\u5185\u90e8\u4e0d\u518d\u4f7f\u7528\u989c\u8272 c\uff0c\u9012\u5f52\u6784\u9020\u4e0b\u53bb\u5373\u53ef\u3002 \u5b9e\u73b0\u8d77\u6765\u8c8c\u4f3c\u53ea\u8981\u4e00\u884c\uff0c\u4e0d\u9700\u8981\u61a8\u61a8\u7684\u53bb\u5199\u9012\u5f52\u3002\u3002\u3002 Problem G. Omkar and Time Travel \u9898\u76ee\u80cc\u666f\u662f\u547d\u8fd0\u77f3\u4e4b\u95e8\uff01 \u611f\u89c9\u6709\u70b9\u50cf Codeforces Global Round 15 \u7684 F \u554a\u3002\u3002\u3002 \u6211\u4eec\u4e0d\u59a8\u7528\u90a3\u4e2a\u9898\u7684\u8bed\u8a00\u91cd\u65b0\u53d9\u8ff0\u8fd9\u4e2a\u9898\uff0c\u770b\u770b\u6709\u4ec0\u4e48\u4e0d\u540c\u3002 \u521d\u59cb\u6240\u91cc\u7684\u4f20\u9001\u95e8\u90fd\u662f active \u7684 \u4f20\u9001\u4e4b\u540e\u4f1a\u8ba9\u4f20\u9001\u4f4d\u7f6e\u5728\u76ee\u6807\u70b9\u4e4b\u540e\u7684\u4f20\u9001\u95e8\u66f4\u65b0\u4e3a [&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-1790","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-sS","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1790","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=1790"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1790\/revisions"}],"predecessor-version":[{"id":1791,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1790\/revisions\/1791"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1790"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1790"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1790"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}