{"id":2039,"date":"2022-11-05T07:07:23","date_gmt":"2022-11-04T23:07:23","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2039"},"modified":"2022-11-05T07:29:51","modified_gmt":"2022-11-04T23:29:51","slug":"codeforces-round-831","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-831\/","title":{"rendered":"Codeforces Round #831"},"content":{"rendered":"<ul>\n<li><a href=\"http:\/\/codeforces.com\/blog\/entry\/108451\">http:\/\/codeforces.com\/blog\/entry\/108451<\/a><\/li>\n<li><a href=\"https:\/\/zhuanlan.zhihu.com\/p\/579487089\">https:\/\/zhuanlan.zhihu.com\/p\/579487089<\/a><\/li>\n<\/ul>\n<h2>\u9898\u610f<\/h2>\n<p>\u7ed9\u4f60\u4e00\u4e2a\u542b\u6709 $n$ \u4e2a\u5143\u7d20\u7684\u53ef\u91cd\u96c6\u5408 $A$\uff0c\u96c6\u5408 $A$ \u7684\u6bcf\u4e2a\u5143\u7d20\u662f\u4e00\u4e2a\u5355\u5143\u7d20\u96c6\u5408 ${a_i}$\u3002<br \/>\n\u5b9a\u4e49\u4e00\u6b21\u64cd\u4f5c\u7531\u4ee5\u4e0b\u4e24\u6b65\u6784\u6210\uff1a<\/p>\n<ul>\n<li>\u9009\u62e9 $A$ \u4e2d\u4e24\u4e2a\u4ea4\u96c6\u4e3a\u7a7a\u7684\u96c6\u5408 $S$, $T$\u3002<\/li>\n<li>\u5220\u9664\u8fd9\u4e24\u4e2a\u96c6\u5408\uff0c\u5c06\u5b83\u4eec\u7684\u5e76\u6dfb\u52a0\u8fdb $A$\u3002<\/li>\n<\/ul>\n<p>\u4e4b\u540e, \u6211\u4eec\u6784\u9020\u4e00\u4e2a\u53ef\u91cd\u96c6\u5408 $M$\uff0c\u8868\u793a\u5f53\u524d\u5269\u4e0b\u7684\u6240\u6709\u96c6\u5408\u7684\u5927\u5c0f\u3002<br \/>\n\u4f60\u53ef\u4ee5\u6267\u884c\u4efb\u610f\u591a\u6b21\u64cd\u4f5c\uff0c\u95ee\u6240\u6709\u4e0d\u540c\u7684 $M$ \u7684\u603b\u6570\u3002<\/p>\n<h2>\u505a\u6cd5<\/h2>\n<p>\u5982\u679c\u521d\u59cb\u7684\u5143\u7d20\u4e92\u4e0d\u76f8\u540c\uff0c\u663e\u7136\u539f\u95ee\u9898\u7b49\u4ef7\u4e8e\u5206\u62c6\u6570\uff0c\u867d\u7136\u539f\u95ee\u9898\u662f\u4ee5\u5408\u5e76\u7684\u65b9\u5f0f\u7ed9\u51fa\u7684\u3002<br \/>\n\u90a3\u4e48\u539f\u95ee\u9898\u7b49\u4ef7\u4e8e\u5e26\u6709\u67d0\u79cd\u9650\u5236\u7684\u5206\u62c6\u6570\uff0c\u9650\u5236\u4e3a\u67d0\u4e9b\u5143\u7d20\u4e4b\u95f4\u5fc5\u987b\u5206\u62c6\u3002<\/p>\n<p>\u5206\u62c6\u6570\u6211\u4eec\u77e5\u9053\u6709\u5f88\u591a\u9ad8\u7ea7\u505a\u6cd5\u3002\u3002\u3002\u6bd4\u5982\u6b27\u62c9\u4e94\u8fb9\u5f62\u6570\u3001\u751f\u6210\u51fd\u6570\u4e91\u4e91\u3002\u3002\u3002\u3002\u4f46\u662f\u8fd9\u4e2a\u9898 $n$ \u53ea\u6709 2000\uff0c\u5927\u6982\u7387\u90fd\u7528\u4e0d\u5230\u3002<\/p>\n<p>\u8003\u8651\u5206\u62c6\u6570\u6700\u6734\u7d20\u7684 DP\u3002\u3002\u3002\u6211\u4eec\u628a\u5206\u62c6\u7684\u7ed3\u679c\u6309\u7167\u4ece\u5927\u5230\u5c0f\u6392\u5e8f\u3002\u3002\u90a3\u4e48\u6bcf\u4e00\u79cd\u60c5\u51b5\u552f\u4e00\u5bf9\u5e94\u4e00\u4e2a\u5355\u8c03\u9012\u51cf\u4e14\u548c\u4e3a n \u7684\u5e8f\u5217\u3002<br \/>\ndp[i][s][j]: \u5f53\u524d\u8003\u5bdf\u524d i \u4e2a\u4f4d\u7f6e\uff0c\u548c\u4e3a s \u4e14\u672b\u5c3e\u4e3a j \u7684\u65b9\u6848\u6570\u3002<br \/>\n\u6709\uff1a<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nconst int N = int(1e3) + 9;\r\nint dp&#x5B;2]&#x5B;N]&#x5B;N];\r\nint n;\r\n\r\nint main() {\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n    RD(n);\r\n\r\n    int p = 0, q = 1; RST(dp&#x5B;p]); dp&#x5B;p]&#x5B;0]&#x5B;n] = 1;\r\n\r\n    REP_1(i, n) {\r\n        swap(p, q); RST(dp&#x5B;p]);\r\n#define u dp&#x5B;q]&#x5B;s]&#x5B;j]\r\n#define v dp&#x5B;p]&#x5B;s+k]&#x5B;k]\r\n        REP(s, n+1) REP(j, n+1) if (u) {\r\n            DWN_1(k, min(j, n-s), 0) v += u;\r\n        }\r\n        cout &lt;&lt; dp&#x5B;p]&#x5B;i]&#x5B;0] + 1 &lt;&lt; &quot; &quot;;\r\n    }\r\n    cout &lt;&lt; endl;\r\n}\r\n<\/pre>\n<p>\u8fd9\u4e2a DP \u53ef\u4ee5\u7528\u90e8\u5206\u548c\u4f18\u5316\u5230 $O(n^3)$\u3002<br \/>\ndp[i][s][j]: \u5f53\u524d\u8003\u5bdf\u524d i \u4e2a\u4f4d\u7f6e\uff0c\u548c\u4e3a s \u4e14\u672b\u5c3e >= j \u7684\u65b9\u6848\u6570\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nconst int N = int(1e3) + 9;\r\nint dp&#x5B;2]&#x5B;N]&#x5B;N];\r\nint n;\r\n\r\nint main() {\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n    RD(n);\r\n\r\n    int p = 0, q = 1; RST(dp&#x5B;p]); dp&#x5B;p]&#x5B;0]&#x5B;n] = 1;\r\n\r\n    REP_1(i, n) {\r\n        swap(p, q); RST(dp&#x5B;p]);\r\n#define u dp&#x5B;q]&#x5B;s]&#x5B;j]\r\n#define v dp&#x5B;p]&#x5B;s+j]&#x5B;j]\r\n        REP(s, n+1) DWN(j, n+1, 0) u += dp&#x5B;q]&#x5B;s]&#x5B;j+1];\r\n        REP(s, n+1) REP(j, n+1) if (u) v += u;\r\n\r\n        cout &lt;&lt; dp&#x5B;p]&#x5B;i]&#x5B;0] + 1 &lt;&lt; &quot; &quot;;\r\n    }\r\n    cout &lt;&lt; endl;\r\n}\r\n<\/pre>\n<p>\u7ee7\u7eed\u8003\u5bdf\u9650\u5236\u3002\u3002\u3002\u7ed3\u8bba\u662f\u3002\u3002\u3002\u5b83\u7b49\u4ef7\u4e8e $s \\leq \\sum \\min(i, c)$<br \/>\n\u5176\u4e2d $c$ \u904d\u5386\u8fc7\u521d\u59cb\u96c6\u5408\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\u51fa\u73b0\u7684\u6b21\u6570\u3002\u3002\u3002<\/p>\n<p>\u8fd9\u4e2a\u7ed3\u8bba\u771f\u7684\u4e0d\u662f\u5f88\u663e\u7136\u3002\u3002\u3002\u611f\u89c9\u9700\u8981\u7528\u5171\u8f6d\u7684\u6027\u8d28 + \u5404\u79cd\u5f52\u7eb3 yy \u51fa\u6765\u3002\u3002\u3002<br \/>\n\u4e8e\u662f\u52a0\u4e0a\u4e0a\u9762\u7684\u9650\u5236\u4f5c\u4e3a\u526a\u679d\u5c31\u53ef\u4ee5 O(n2logn) \u8dd1\u51fa\u6765\u3002\u3002\u3002<\/p>\n<p>\u4f46\u662f\u6211\u4eec\u77e5\u9053\u5176\u5b9e\u5206\u62c6\u6570\u7684\u6734\u7d20 dp \u53ef\u4ee5\u8fdb\u4e00\u6b65\u4f18\u5316\u5230 $O(n2)$\u3002\u3002\u3002<br \/>\n\u539f\u56e0\u662f\u5206\u5dee\u6570\u672c\u8eab\u5c31\u66f4\u7279\u6b8a\u3002\u3002\u3002\u72b6\u6001\u53ef\u4ee5\u8fdb\u4e00\u6b65\u7b80\u5316\u3002\u3002\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>http:\/\/codeforces.com\/blog\/entry\/108451 https:\/\/zhuanlan.zhihu.com\/p\/579487089 \u9898\u610f \u7ed9\u4f60\u4e00\u4e2a\u542b\u6709 $n$ \u4e2a\u5143\u7d20\u7684\u53ef\u91cd\u96c6\u5408 $A$\uff0c\u96c6\u5408 $A$ \u7684\u6bcf\u4e2a\u5143\u7d20\u662f\u4e00\u4e2a\u5355\u5143\u7d20\u96c6\u5408 ${a_i}$\u3002 \u5b9a\u4e49\u4e00\u6b21\u64cd\u4f5c\u7531\u4ee5\u4e0b\u4e24\u6b65\u6784\u6210\uff1a \u9009\u62e9 $A$ \u4e2d\u4e24\u4e2a\u4ea4\u96c6\u4e3a\u7a7a\u7684\u96c6\u5408 $S$, $T$\u3002 \u5220\u9664\u8fd9\u4e24\u4e2a\u96c6\u5408\uff0c\u5c06\u5b83\u4eec\u7684\u5e76\u6dfb\u52a0\u8fdb $A$\u3002 \u4e4b\u540e, \u6211\u4eec\u6784\u9020\u4e00\u4e2a\u53ef\u91cd\u96c6\u5408 $M$\uff0c\u8868\u793a\u5f53\u524d\u5269\u4e0b\u7684\u6240\u6709\u96c6\u5408\u7684\u5927\u5c0f\u3002 \u4f60\u53ef\u4ee5\u6267\u884c\u4efb\u610f\u591a\u6b21\u64cd\u4f5c\uff0c\u95ee\u6240\u6709\u4e0d\u540c\u7684 $M$ \u7684\u603b\u6570\u3002 \u505a\u6cd5 \u5982\u679c\u521d\u59cb\u7684\u5143\u7d20\u4e92\u4e0d\u76f8\u540c\uff0c\u663e\u7136\u539f\u95ee\u9898\u7b49\u4ef7\u4e8e\u5206\u62c6\u6570\uff0c\u867d\u7136\u539f\u95ee\u9898\u662f\u4ee5\u5408\u5e76\u7684\u65b9\u5f0f\u7ed9\u51fa\u7684\u3002 \u90a3\u4e48\u539f\u95ee\u9898\u7b49\u4ef7\u4e8e\u5e26\u6709\u67d0\u79cd\u9650\u5236\u7684\u5206\u62c6\u6570\uff0c\u9650\u5236\u4e3a\u67d0\u4e9b\u5143\u7d20\u4e4b\u95f4\u5fc5\u987b\u5206\u62c6\u3002 \u5206\u62c6\u6570\u6211\u4eec\u77e5\u9053\u6709\u5f88\u591a\u9ad8\u7ea7\u505a\u6cd5\u3002\u3002\u3002\u6bd4\u5982\u6b27\u62c9\u4e94\u8fb9\u5f62\u6570\u3001\u751f\u6210\u51fd\u6570\u4e91\u4e91\u3002\u3002\u3002\u3002\u4f46\u662f\u8fd9\u4e2a\u9898 $n$ \u53ea\u6709 2000\uff0c\u5927\u6982\u7387\u90fd\u7528\u4e0d\u5230\u3002 \u8003\u8651\u5206\u62c6\u6570\u6700\u6734\u7d20\u7684 DP\u3002\u3002\u3002\u6211\u4eec\u628a\u5206\u62c6\u7684\u7ed3\u679c\u6309\u7167\u4ece\u5927\u5230\u5c0f\u6392\u5e8f\u3002\u3002\u90a3\u4e48\u6bcf\u4e00\u79cd\u60c5\u51b5\u552f\u4e00\u5bf9\u5e94\u4e00\u4e2a\u5355\u8c03\u9012\u51cf\u4e14\u548c\u4e3a n \u7684\u5e8f\u5217\u3002 dp[i][s][j]: \u5f53\u524d\u8003\u5bdf\u524d i \u4e2a\u4f4d\u7f6e\uff0c\u548c\u4e3a s \u4e14\u672b\u5c3e\u4e3a j \u7684\u65b9\u6848\u6570\u3002 \u6709\uff1a const int N = int(1e3) + 9; int dp&#x5B;2]&#x5B;N]&#x5B;N]; int n; [&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-2039","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wT","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2039","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=2039"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2039\/revisions"}],"predecessor-version":[{"id":2040,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2039\/revisions\/2040"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2039"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2039"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2039"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}