{"id":1844,"date":"2021-12-17T06:17:58","date_gmt":"2021-12-16T22:17:58","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1844"},"modified":"2021-12-17T06:32:07","modified_gmt":"2021-12-16T22:32:07","slug":"codeforces-round-759-div-2-based-on-technocup-2022-elimination-round-3","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-759-div-2-based-on-technocup-2022-elimination-round-3\/","title":{"rendered":"Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3)"},"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<p><a href=\"https:\/\/codeforces.com\/blog\/entry\/97795\">https:\/\/codeforces.com\/blog\/entry\/97795<\/a><br \/>\n<a href=\"https:\/\/zhuanlan.zhihu.com\/p\/444714636\">https:\/\/zhuanlan.zhihu.com\/p\/444714636<\/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-6a09338ba13a8\" 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-6a09338ba13a8\"  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-759-div-2-based-on-technocup-2022-elimination-round-3\/#%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\/codeforces-round-759-div-2-based-on-technocup-2022-elimination-round-3\/#Problem_D_Yet_Another_Sorting_Problem\" title=\"Problem D. Yet Another Sorting Problem\">Problem D. Yet Another Sorting Problem<\/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-759-div-2-based-on-technocup-2022-elimination-round-3\/#Problem_E_Frequency_Queries\" title=\"Problem E. Frequency Queries\">Problem E. Frequency Queries<\/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-759-div-2-based-on-technocup-2022-elimination-round-3\/#Problem_F_Non-equal_Neighbours\" title=\"Problem F. Non-equal Neighbours\">Problem F. Non-equal Neighbours<\/a><\/li><\/ul><\/nav><\/div>\n\n<p>\u8fd9\u573a\u56e0\u4e3a\u51fa\u539f\u9898\u88ab\u55b7\u60e8\u4e86\u3002\u3002\u3002<\/p>\n<p>Problem C : <a href=\"https:\/\/po.kattis.com\/problems\/biblioteket\">https:\/\/po.kattis.com\/problems\/biblioteket<\/a><br \/>\nProblem D : <a href=\"https:\/\/open.kattis.com\/problems\/bread\">https:\/\/open.kattis.com\/problems\/bread<\/a> | <a href=\"https:\/\/judge.u-aizu.ac.jp\/onlinejudge\/description.jsp?id=0448\">https:\/\/judge.u-aizu.ac.jp\/onlinejudge\/description.jsp?id=0448<\/a><br \/>\nProblem F : <a href=\"https:\/\/atcoder.jp\/contests\/arc115\/tasks\/arc115_e\">https:\/\/atcoder.jp\/contests\/arc115\/tasks\/arc115_e<\/a><\/p>\n<p>\u7279\u522b\u662f F \u9898\u7684\u5f71\u54cd\u6700\u4e3a\u4e25\u91cd\u3002\u3002\u3002\uff08\u4f46\u662f\u6211\u89c9\u5f97\u8fd9\u4e2a F \u9898\u771f\u7684\u662f\u4e00\u4e2a\u597d\u9898\u554a\u3002\u3002\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_D_Yet_Another_Sorting_Problem\"><\/span>Problem D. Yet Another Sorting Problem<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7ed9\u5b9a\u8981\u7ed9\u6570\u7ec4\u3002\u53ef\u4ee5\u5bf9\u6570\u7ec4\u8fdb\u884c\u64cd\u4f5c\uff0c\u6bcf\u6b21\u9009\u62e9\u4e09\u4e2a\u4e0d\u540c\u7684\u4e0b\u6807(i, j, k)\u3002<br \/>\n\u4ea4\u6362\u8fd9\u4e09\u4e2a\u4f4d\u7f6e\u7684\u6570\u3002a[i]\u79fb\u52a8\u5230a[j]\uff0ca[j]\u79fb\u52a8\u5230a[k]\uff0ca[k]\u79fb\u52a8\u5230a[i]\u3002<br \/>\n\u95ee\u80fd\u4e0d\u80fd\u901a\u8fc7\u82e5\u5e72\u6b21\u64cd\u4f5c\uff0c\u8ba9\u6570\u7ec4\u6709\u5e8f\uff08\u975e\u51cf\uff09\u3002<\/p>\n<p>\u5bfb\u627e invariant \u3002\u3002\u3002\u4f3c\u4e4e\u8fd9\u4e2a\u4e09\u5143\u4ea4\u6362\u64cd\u4f5c\u4e0d\u6539\u53d8\u9006\u5e8f\u5bf9\u7684\u5947\u5076\u6027\u3002\u3002<br \/>\n\u731c\u60f3\u9006\u5e8f\u5bf9\u662f\u5076\u6570\u4e00\u5b9a\u6709\u89e3\u3002\u3002\u3002<\/p>\n<p>\u4ea4\u4e86\u4e00\u53d1\u4e0a\u53bb WA \u4e86\u3002\u3002\u3002<br \/>\n\u6700\u540e\u53d1\u73b0\u6ca1\u8003\u8651\u76f8\u7b49\u7684\u6570\u3002\u3002<\/p>\n<p>\u5982\u679c\u6709\u76f8\u7b49\u7684\u6570\uff0c\u90a3\u4e48\u4e00\u5b9a\u6709\u89e3\uff0c\u56e0\u4e3a\u53ef\u4ee5\u62ff\u8fd9\u4e2a\u6570\u5145\u5f53\u7f13\u5b58\u533a= =\u3002\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_E_Frequency_Queries\"><\/span>Problem E. Frequency Queries<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7ed9\u5b9a\u4e00\u68f5n\u8282\u70b9\u7684\u6811\uff0c\u6811\u4e0a\u6bcf\u4e2a\u8282\u70b9\u6709\u4e00\u4e2a\u6570\u5b57\uff08\u8303\u56f41~n\uff09\u3002\u6709q\u4e2a\u67e5\u8be2\uff0c\u6bcf\u4e2a\u67e5\u8be2\u7ed9\u51fa\u4e09\u4e2a\u6570 v, l, k\u3002<br \/>\n\u95ee\u8282\u70b9v\u5230\u6839\u7684\uff08\u6700\u77ed\uff09\u8def\u5f84\u4e0a\u7684\u6240\u6709\u6570\u5b57\uff0c\u51fa\u73b0\u6b21\u6570\u5927\u4e8e\u7b49\u4e8el\u6b21\u7684\u6570\u5b57\u4e2d\uff0c\u51fa\u73b0\u6b21\u6570\u6392\u7b2ck\u7684\u662f\u4ec0\u4e48\uff1f\uff08\u53ef\u80fd\u6709\u51fa\u73b0\u6b21\u6570\u76f8\u540c\u7684\uff0c\u8fd9\u65f6\u5019\u8f93\u51fa\u4efb\u610f\u90fd\u53ef\uff09<\/p>\n<p>\u79bb\u7ebf\u6811\u72b6\u6570\u7ec4 + \u4e8c\u5206\u67e5\u627e\u3002\u3002\u633a\u65e0\u804a\u7684\u9898\u3002\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_F_Non-equal_Neighbours\"><\/span>Problem F. Non-equal Neighbours<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7ed9\u5b9an\u4e2a\u6b63\u6574\u6570$a_1,\\cdots,a_n$\uff0c\u6c42\u6ee1\u8db3\u4e0b\u9762\u6761\u4ef6\u7684\u6570\u7ec4$b$\u7684\u4e2a\u6570<\/p>\n<ul>\n<li>$1\\le b_i \\le a_i$<\/li>\n<li>$b_i \\ne b_{i &#8211; 1}, i\\in [1, n &#8211; 1]$<\/li>\n<\/ul>\n<p>\u7b2c\u4e00\u611f\u89c9\u662f DP \u4f18\u5316\u3002\u3002\u3002\u4f46\u662f\u5982\u679c\u72b6\u6001\u8bbe\u8ba1\u6210 f[][] \u597d\u50cf\u5c31\u8d70\u8fdb\u6b7b\u80e1\u540c\u4e86\u3002\u3002\u9898\u89e3\u8bf4\u8981\u7b1b\u5361\u5c14\u6811\u3002\u3002\u4e0d\u8fc7\u4e0d\u4f1a\u4e5f\u80fd\u505a\u3002\u3002<br \/>\n\u72b6\u6001\u8bbe\u8ba1\u6210 f[]\uff0c\u7136\u540e\u5e94\u7528\u5bb9\u65a5\u539f\u7406\uff0c\u679a\u4e3e\u540e\u7f00\u6709\u591a\u5c11\u8fde\u7eed\u76f8\u7b49\u7684\u6570\u5b57\u3002\u3002\u8fd9\u6837\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a O(n2) \u7684 dp\uff0c\u5df2\u7ecf\u6210\u529f\u4e86\u4e00\u5927\u534a\u3002\u3002\u3002<br \/>\n\u8003\u8651 dp \u4f18\u5316\u3002\u3002\u53ef\u4ee5\u7528\u5355\u8c03\u6808\u548c\u90e8\u5206\u548c\u6f02\u4eae\u7684\u4f18\u5316\u5230 O(n)\u3002\u3002\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4f20\u9001\u95e8 https:\/\/codeforces.com\/blog\/entry\/97795 https:\/\/zhuanlan.zhihu.com\/p\/444714636 \u8fd9\u573a\u56e0\u4e3a\u51fa\u539f\u9898\u88ab\u55b7\u60e8\u4e86\u3002\u3002\u3002 Problem C : https:\/\/po.kattis.com\/problems\/biblioteket Problem D : https:\/\/open.kattis.com\/problems\/bread | https:\/\/judge.u-aizu.ac.jp\/onlinejudge\/description.jsp?id=0448 Problem F : https:\/\/atcoder.jp\/contests\/arc115\/tasks\/arc115_e \u7279\u522b\u662f F \u9898\u7684\u5f71\u54cd\u6700\u4e3a\u4e25\u91cd\u3002\u3002\u3002\uff08\u4f46\u662f\u6211\u89c9\u5f97\u8fd9\u4e2a F \u9898\u771f\u7684\u662f\u4e00\u4e2a\u597d\u9898\u554a\u3002\u3002\u3002 Problem D. Yet Another Sorting Problem \u7ed9\u5b9a\u8981\u7ed9\u6570\u7ec4\u3002\u53ef\u4ee5\u5bf9\u6570\u7ec4\u8fdb\u884c\u64cd\u4f5c\uff0c\u6bcf\u6b21\u9009\u62e9\u4e09\u4e2a\u4e0d\u540c\u7684\u4e0b\u6807(i, j, k)\u3002 \u4ea4\u6362\u8fd9\u4e09\u4e2a\u4f4d\u7f6e\u7684\u6570\u3002a[i]\u79fb\u52a8\u5230a[j]\uff0ca[j]\u79fb\u52a8\u5230a[k]\uff0ca[k]\u79fb\u52a8\u5230a[i]\u3002 \u95ee\u80fd\u4e0d\u80fd\u901a\u8fc7\u82e5\u5e72\u6b21\u64cd\u4f5c\uff0c\u8ba9\u6570\u7ec4\u6709\u5e8f\uff08\u975e\u51cf\uff09\u3002 \u5bfb\u627e invariant \u3002\u3002\u3002\u4f3c\u4e4e\u8fd9\u4e2a\u4e09\u5143\u4ea4\u6362\u64cd\u4f5c\u4e0d\u6539\u53d8\u9006\u5e8f\u5bf9\u7684\u5947\u5076\u6027\u3002\u3002 \u731c\u60f3\u9006\u5e8f\u5bf9\u662f\u5076\u6570\u4e00\u5b9a\u6709\u89e3\u3002\u3002\u3002 \u4ea4\u4e86\u4e00\u53d1\u4e0a\u53bb WA \u4e86\u3002\u3002\u3002 \u6700\u540e\u53d1\u73b0\u6ca1\u8003\u8651\u76f8\u7b49\u7684\u6570\u3002\u3002 \u5982\u679c\u6709\u76f8\u7b49\u7684\u6570\uff0c\u90a3\u4e48\u4e00\u5b9a\u6709\u89e3\uff0c\u56e0\u4e3a\u53ef\u4ee5\u62ff\u8fd9\u4e2a\u6570\u5145\u5f53\u7f13\u5b58\u533a= =\u3002\u3002 Problem E. Frequency Queries \u7ed9\u5b9a\u4e00\u68f5n\u8282\u70b9\u7684\u6811\uff0c\u6811\u4e0a\u6bcf\u4e2a\u8282\u70b9\u6709\u4e00\u4e2a\u6570\u5b57\uff08\u8303\u56f41~n\uff09\u3002\u6709q\u4e2a\u67e5\u8be2\uff0c\u6bcf\u4e2a\u67e5\u8be2\u7ed9\u51fa\u4e09\u4e2a\u6570 v, l, k\u3002 \u95ee\u8282\u70b9v\u5230\u6839\u7684\uff08\u6700\u77ed\uff09\u8def\u5f84\u4e0a\u7684\u6240\u6709\u6570\u5b57\uff0c\u51fa\u73b0\u6b21\u6570\u5927\u4e8e\u7b49\u4e8el\u6b21\u7684\u6570\u5b57\u4e2d\uff0c\u51fa\u73b0\u6b21\u6570\u6392\u7b2ck\u7684\u662f\u4ec0\u4e48\uff1f\uff08\u53ef\u80fd\u6709\u51fa\u73b0\u6b21\u6570\u76f8\u540c\u7684\uff0c\u8fd9\u65f6\u5019\u8f93\u51fa\u4efb\u610f\u90fd\u53ef\uff09 \u79bb\u7ebf\u6811\u72b6\u6570\u7ec4 + [&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-1844","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-tK","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1844","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=1844"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1844\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}