{"id":2338,"date":"2023-02-15T16:57:51","date_gmt":"2023-02-15T08:57:51","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2338"},"modified":"2023-02-15T22:54:10","modified_gmt":"2023-02-15T14:54:10","slug":"the-1st-universal-cup-stage-3-poland","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/the-1st-universal-cup-stage-3-poland\/","title":{"rendered":"The 1st Universal Cup, Stage 3, Poland"},"content":{"rendered":"\n<ul>\n<li><a href=\"https:\/\/qoj.ac\/contest\/1103?v=1\">https:\/\/qoj.ac\/contest\/1103?v=1<\/a><\/li>\n<li><a href=\"https:\/\/twitter.com\/noimi_kyopro\/status\/1624549003038965760\">https:\/\/twitter.com\/noimi_kyopro\/status\/1624549003038965760<\/a><\/li>\n<\/ul>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_84 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-6a2a3e08bb2f6\" 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-6a2a3e08bb2f6\"  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\/the-1st-universal-cup-stage-3-poland\/#Problem_B_Bars\" >Problem B. Bars<\/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\/the-1st-universal-cup-stage-3-poland\/#Problem_C_CtrlC_CtrlV\" >Problem C. Ctrl+C Ctrl+V<\/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\/the-1st-universal-cup-stage-3-poland\/#Problem_D_Dazzling_Mountain\" >Problem D. Dazzling Mountain<\/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\/the-1st-universal-cup-stage-3-poland\/#Problem_E_Euclidean_Algorithm\" >Problem E. Euclidean Algorithm<\/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\/the-1st-universal-cup-stage-3-poland\/#Problem_G_Great_Chase\" >Problem G. Great Chase<\/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\/the-1st-universal-cup-stage-3-poland\/#Problem_I_Investors\" >Problem I. Investors<\/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\/the-1st-universal-cup-stage-3-poland\/#Problem_M_Minor_Evil\" >Problem M. Minor Evil<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Problem_B_Bars\"><\/span>Problem B. Bars<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>n \u4e2a\u4eba\u6392\u6210\u4e00\u6392\u5f00\u9152\u5427\uff0c\u6bcf\u4e2a\u4eba\u53ef\u4ee5\u9009\u62e9\u5f00\u6216\u4e0d\u5f00\uff0c\u4e14\u6bcf\u4e2a\u4eba\u4f1a\u53bb\u81ea\u5df1\u4ee5\u5916\u7684\u5de6\u53f3\u6700\u8fd1 2 \u4e2a\u5f00\u4e1a\u9152\u5427\u5404 1 \u6b21\uff08\u6ca1\u6709\u5219\u4e0d\u53bb\uff09\uff0c\u7b2c i \u4e2a\u4eba\u7684\u9152\u5427\u6bcf\u62db\u5f85\u4e00\u4e2a\u987e\u5ba2\u5f97 p_i \u5143\uff0c\u6700\u5927\u5316\u603b\u5229\u6da6\u3002<\/p>\n<p>\u5148\u5199\u4e2a\u66b4\u529b\u538b\u538b\u60ca\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: \u66b4\u529b; toolbar: true; notranslate\" title=\"\u66b4\u529b\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(1e6) + 9;\r\n\r\nLL f&#x5B;N]; int p&#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#endif\r\n\r\n    Rush {\r\n        RD(n); REP(i, n) RD(p&#x5B;i]);\r\n        fill(f, f+n, 0);\r\n        FOR(i, 1, n) {\r\n            REP(j, i) checkMax(f&#x5B;i], f&#x5B;j] + (LL)(p&#x5B;i]+p&#x5B;j]) * (i-j));\r\n        }\r\n        cout &lt;&lt; f&#x5B;n-1] &lt;&lt; endl;\r\n    }\r\n}\r\n<\/pre>\n<p>\u7b2c\u4e00\u53cd\u5e94\u662f\u51f8\u58f3 dp&#8230; \u4f46\u662f\u7ecf\u8fc7\u4e00\u756a\u5316\u7b80\u8c8c\u4f3c\u6211\u4eec\u9700\u8981\u6c42\u4e00\u4e2a\u4e09\u7ef4\u5411\u91cf\u7684\u70b9\u79ef\u7684\u6700\u503c\u3002\u3002<br \/>\n\u8fd9\u4e2a\u5c31\u7ed9\u6211\u6574\u4e0d\u4f1a\u4e86\u3002\u3002\u3002<\/p>\n<p>\u770b\u4e86\u4e00\u4e0b <a href=\"https:\/\/twitter.com\/maspy_stars\/status\/1353692962232786944\">maspy \u7684\u9898\u89e3<\/a>\uff0c\u539f\u6765\u8fd9\u4e2a\u4e1c\u897f\u53ef\u4ee5\u7c7b\u6bd4\u68af\u5f62\u6c42\u548c\u3002\u3002\u3002\uff08\u8fd9\u5806\u4e1c\u897f\u53e0\u8d77\u6765\u7684\u5f62\u72b6\u5927\u6982\u50cf\u662f\u300a\u9b54\u795e\u82f1\u96c4\u4f20\u300b\u91cc\u7684\u521b\u754c\u5c71\u3002\u3002\uff09<br \/>\n\u7136\u540e\u53ea\u8981\u4fdd\u7559\u5916\u9762\u7684\u51f8\u58f3\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u505a\u6cd5\u4e5f\u548c\u6c42\u51f8\u5305\u7c7b\u4f3c\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: \u51f8\u58f3; toolbar: true; notranslate\" title=\"\u51f8\u58f3\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(1e6) + 9;\r\n\r\nint p&#x5B;N], s&#x5B;N], sn;\r\nint n;\r\n\r\nLL w(int j, int i) {\r\n    return (LL)(p&#x5B;i]+p&#x5B;j])*(i-j);\r\n}\r\n\r\nbool bad(int a, int b, int c) {\r\n    return w(a, b) + w(b, c) &lt;= w(a, c);\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    Rush {\r\n        RD(n); REP(i, n) RD(p&#x5B;i]);\r\n\r\n        sn = 0; REP(i, n) {\r\n            while (sn &gt; 1 &amp;&amp; bad(s&#x5B;sn-1], s&#x5B;sn], i)) --sn;;\r\n            s&#x5B;++sn] = i;\r\n        }\r\n\r\n        LL z = 0; REP_1(i, sn) z += w(s&#x5B;i-1], s&#x5B;i]);\r\n        cout &lt;&lt; z &lt;&lt; endl;\r\n    }\r\n}\r\n\r\n<\/pre>\n<h2><span class=\"ez-toc-section\" id=\"Problem_C_CtrlC_CtrlV\"><\/span>Problem C. Ctrl+C Ctrl+V<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u95ee\u81f3\u5c11\u4fee\u6539\u51e0\u4e2a\u5b57\u7b26\uff0c\u4f7f\u5f97\u5b57\u7b26\u4e32\u4e2d\u4e0d\u5b58\u5728 &#8220;ania&#8221; \u6a21\u5f0f\u4e32\u3002<\/p>\n<p>\u7b7e\u5230\u9898\u3002\u53ef\u4ee5 kmp \u4e0d\u8fc7\u6ca1\u5fc5\u8981\uff08\u56e0\u4e3a\u6a21\u5f0f\u4e32\u592a\u77ed\u4e14\u56fa\u5b9a\uff09\u3002<br \/>\n\u6bcf\u6b21\u5339\u914d\u5230 ania \u65f6\uff0c\u76f4\u63a5\u628a\u672b\u5c3e\u7684 a \u4fee\u6539\u6210\u4e00\u4e2a\u4e0d\u5b58\u5728\u7684\u5b57\u7b26\u5373\u53ef\u3002<br \/>\n\u4e5f\u53ef\u4ee5\u8bb0\u5f55\u8fde\u7eed\u5339\u914d\u7684\u6bb5\u6570 c\uff0c\u7136\u540e\u6bcf\u6b21\u589e\u52a0 (c+1) \/ 2\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\n\r\nconst int N = int(1e6) + 9;\r\n\r\nchar p&#x5B;5] = &quot;ania&quot;;\r\nchar s&#x5B;N];\r\nint n, z, c;\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    Rush {\r\n        n = strlen(RS(s));\r\n        z = 0; c = 0;\r\n\r\n        int j = 0;\r\n        for (int i=0;i&lt;n;++i) {\r\n            if (s&#x5B;i] == p&#x5B;j]) {\r\n                ++j; if (j == 4) {\r\n                    ++c;\r\n                    j = 1;\r\n                }\r\n            }\r\n            else {\r\n                z += (c+1)\/2; c = 0;\r\n                if (s&#x5B;i] == 'a') j = 1;\r\n                else j = 0;\r\n            }\r\n        }\r\n        z += (c+1)\/2;\r\n        cout &lt;&lt; z &lt;&lt; endl;\r\n    }\r\n}\r\n\r\n<\/pre>\n<h2><span class=\"ez-toc-section\" id=\"Problem_D_Dazzling_Mountain\"><\/span>Problem D. Dazzling Mountain<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7ed9\u5b9a\u4e00\u9897\u6709\u6839\u6570\uff0c\u95ee\u6709\u54ea\u4e9b\u6ee1\u8db3\u6761\u4ef6\u7684 x\uff0c\u4f7f\u5f97\u6240\u6709\u5b50\u6811 size \u7b49\u4e8e x \u7684\u8282\u70b9\u5411\u4e0b\u8986\u76d6\u4e86\u6240\u6709\u7684\u53f6\u5b50\u3002<\/p>\n<p>\u663e\u7136\u6839\u8282\u70b9\u6ee1\u8db3\uff0c\u6700\u540e\u6240\u6709\u7684\u53f6\u5b50\u8282\u70b9\u4e5f\u6ee1\u8db3\uff0c<br \/>\n\u6211\u4eec\u4e0d\u59a8\u67aa\u5766\u63a8\u8fdb\uff0c\u5f00\u4e2a map&lt;int, VI> \u8bb0\u5f55\u5f53\u524d\u6bcf\u79cd\u4e0d\u540c\u8986\u76d6\u9762\u79ef\u7684\u6839\u8282\u70b9\u3002<br \/>\n\u6bcf\u6b21\u53d6\u51fa\u9762\u79ef\u6700\u5927\u7684 VI \u4f9d\u6b21\u53d6\u51fa\u5e76\u5f80\u5b69\u5b50\u79fb\u52a8\uff0c\u5f53\u6bcf\u5c42\u6247\u5f62\u7684\u9762\u79ef\u90fd\u76f8\u7b49\u65f6\uff0c\u65e2\u6b64\u65f6 map \u7684 size \u6070\u597d\u4e3a 1 \u65f6\uff0c\u5219\u5f97\u5230\u4e00\u7ec4\u7b26\u5408\u6761\u4ef6\u7684\u7b54\u6848\uff0c\u5982\u679c\u6b64\u65f6\u6247\u5f62\u9762\u79ef\u4e3a 1, \u8bf4\u660e\u5df2\u7ecf\u5230\u4e86\u53f6\u5b50\uff0c\u7b97\u6cd5\u7ed3\u675f\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\n\r\nconst int N = int(1e6) + 9;\r\n\r\nVI adj&#x5B;N]; int sz&#x5B;N], fa&#x5B;N];\r\nint n;\r\n\r\nvoid dfs(int u = 1, int p = 0) {\r\n    sz&#x5B;u] = 1;\r\n    for (auto v: adj&#x5B;u]) if (v != p) {\r\n        fa&#x5B;v] = u; dfs(v, u);\r\n        sz&#x5B;u] += sz&#x5B;v];\r\n    }\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\r\n    Rush {\r\n        RD(n); REP_1(i, n) adj&#x5B;i].clear();\r\n\r\n        DO(n-1) {\r\n            int a, b; RD(a, b);\r\n            adj&#x5B;a].PB(b);\r\n            adj&#x5B;b].PB(a);\r\n        }\r\n\r\n        dfs(); VI z; z.clear();\r\n        map&lt;int, VI&gt; H; H&#x5B;sz&#x5B;1]].PB(1);\r\n\r\n        while (true) {\r\n            int s = H.begin()-&gt;fi; z.PB(s); if (s == 1) break;\r\n\r\n            do {\r\n                auto it = H.end(); --it;\r\n                VI U = it-&gt;se; H.erase(it);\r\n                for (auto u: U) {\r\n                    for (auto v: adj&#x5B;u]) if (v != fa&#x5B;u]) {\r\n                        H&#x5B;sz&#x5B;v]].PB(v);\r\n                    }\r\n                }\r\n            } while (SZ(H) != 1);\r\n        }\r\n\r\n\r\n        SRT(z); cout &lt;&lt; SZ(z) &lt;&lt; endl;\r\n        for (auto zi : z) printf(&quot;%d &quot;, zi);\r\n        puts(&quot;&quot;);\r\n    }\r\n}\r\n<\/pre>\n<h2><span class=\"ez-toc-section\" id=\"Problem_E_Euclidean_Algorithm\"><\/span>Problem E. Euclidean Algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u5982\u679c a, b \u5728\uff0c\u4e14 2<em>a-b>0\uff0c\u5219 2<\/em>a-b \u4e5f\u5728\uff0c\u91cd\u590d\u8fd9\u4e2a\u64cd\u4f5c\u5f97\u5230\u7684\u6700\u5c0f\u7684\u6570\u662f gcd \u7684 1-n \u5185\u7684\u6574\u6570 pair\u6709\u591a\u5c11\u4e2a\u3002<\/p>\n<p>\u4e0d\u4f1a\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_G_Great_Chase\"><\/span>Problem G. Great Chase<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u8b66\u5bdf\u6293\u5c0f\u5077\u3002\u5c0f\u5077\u51fa\u751f\u5728\u6570\u8f74\u539f\u70b9\uff0c\u5f00\u59cb\u5411\u53f3\u4ee5\u901f\u5ea6 v0 \u79fb\u52a8\uff0c\u5b83\u5de6\u53f3\u5206\u522b\u6709\u4e00\u4e9b\u8b66\u5bdf (pi, vi)\uff0cpi \u8868\u793a\u8b66\u5bdf\u7684\u4f4d\u7f6e\uff0cvi \u8868\u793a\u8b66\u5bdf\u7684\u901f\u5ea6\uff0c\u5de6\u8fb9\u7684\u8b66\u5bdf\u5411\u53f3\u8ffd\uff0c\u53f3\u8fb9\u7684\u8b66\u5bdf\u5411\u5de6\u8ffd\uff0c\u4fdd\u8bc1\u5c0f\u5077\u7684\u901f\u5ea6\u5927\u4e8e\u6240\u6709\u8b66\u5bdf\uff0c\u4e14\u6570\u8f74\u4e24\u8fb9\u90fd\u5b58\u5728\u8b66\u5bdf\u3002\u5f53\u5c0f\u5077\u9047\u4e0a\u8b66\u5bdf\u65f6\uff0c\u5c0f\u5077\u4f1a\u5411\u53cd\u5411\u79fb\u52a8\uff0c\u76f4\u5230\u88ab\u4e24\u4e2a\u8b66\u5bdf\u5305\u5939\u3002\u95ee\u88ab\u5305\u5939\u65f6\uff0c\u5c0f\u5077\u79fb\u52a8\u7684\u603b\u8ddd\u79bb\u3002<\/p>\n<p>\u5c0f\u5077\u7684\u8fd0\u52a8\u76f8\u5bf9\u6bd4\u8f83\u590d\u6742\uff0c\u6211\u4eec\u8003\u8651\u4e0d\u7ba1\uff0c\u76f4\u63a5\u4e8c\u5206\u65f6\u95f4\uff0c\u770b\u4e24\u8fb9\u7684\u8b66\u5bdf\u662f\u5426\u80fd\u76f8\u9047\u5373\u53ef\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_I_Investors\"><\/span>Problem I. Investors<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7ed9\u5b9a n \u4e2a\u6570\u5217\uff0c\u4f60\u53ef\u4ee5\u4ece\u4e2d\u7b5b\u9009\u51fa m \u6bb5\u8fde\u7eed\u7684\u5b50\u5e8f\u5217\uff0c\u5c06\u5b83\u4eec\u6574\u4f53 offset \u4e00\u6bb5\u6570\uff0c\u6700\u5c0f\u5316\u6700\u540e\u7684\u9006\u5e8f\u5bf9\u3002<\/p>\n<p>\u663e\u7136\u6700\u4f18\u89e3\u4e00\u5b9a\u662f\u6bcf\u6b21\u90fd\u9009\u4e00\u4e9b\u540e\u7f00\u8fdb\u884c\u64cd\u4f5c\uff0c\u8ba9\u539f\u5e8f\u5217\u5206\u5272\u6210 m+1 \u6bb5\u4e92\u4e0d\u5e72\u6270\u7684\u533a\u95f4\uff0c\u5206\u522b\u7edf\u8ba1\u8fd9\u4e9b\u6bb5\u7684\u9006\u5e8f\u5bf9\u548c\uff0c\u4ee3\u4ef7\u51fd\u6570\u5373\u4e3a\u6bcf\u4e00\u6bb5\u7684\u9006\u5e8f\u5bf9\u3002<\/p>\n<p>\u90a3\u4e48\u663e\u7136\u9006\u5e8f\u5bf9\u51fd\u6570\u7b26\u5408\u7ecf\u5178\u56db\u8fb9\u5f62\u4e0d\u7b49\u5f0f\uff0c\u7531\u6b64\u63a8\u51fa\u51b3\u7b56\u5355\u8c03\u6027\u3002<br \/>\n\u5229\u7528\u961f\u5217\u7ef4\u62a4\u5f53\u524d\u53ef\u884c\u51b3\u7b56\uff0c\u5e76\u7528\u4e8c\u5206\u8ba1\u7b97\u51fa\u76f8\u90bb\u51b3\u7b56\u7684\u5206\u5272\u70b9\u5373\u53ef\uff08\u51b3\u7b56\u4e0d\u52a3\u7684\u6700\u65e9\u65f6\u523b\uff09\u3002<br \/>\n\uff08\u53c2\u8003\u8bd7\u4eba\u5c0f G\uff09<\/p>\n<p>\u4f3c\u4e4e\u8fd8\u5b58\u5728\u5f88\u591a\u795e\u5947\u7684\u505a\u6cd5\uff0c\u4f8b\u5982 <a href=\"https:\/\/qoj.ac\/submission\/77071\">\u76f4\u63a5\u4e8c\u5206\u6bcf\u4e00\u6bb5\u4ee3\u4ef7\u7684\u4e0a\u754c<\/a>\uff1f<br \/>\n\u53e6\u5916\u7784\u4e86\u4e00\u773c <a href=\"https:\/\/qoj.ac\/submission\/76804\">maspy \u7684\u4ee3\u7801<\/a>\uff0c\u4ec0\u4e48\uff0c\u8fd9\u5c45\u7136\u4e5f\u6709 <a href=\"https:\/\/noshi91.github.io\/algorithm-encyclopedia\/d-edge-shortest-path-monge\">\u677f\u5b50<\/a>\uff1f<\/p>\n<pre class=\"brush: cpp; light: false; title: \u56db\u8fb9\u5f62\u4e0d\u7b49\u5f0f; toolbar: true; notranslate\" title=\"\u56db\u8fb9\u5f62\u4e0d\u7b49\u5f0f\">\r\n#include &lt;lastweapon\/io&gt;\r\n#include &lt;lastweapon\/fenwicktree&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(6e3) + 9;\r\n\r\nint a&#x5B;N], f&#x5B;2]&#x5B;N], w&#x5B;N]&#x5B;N]; VI A; int p = 0, q = 1;\r\nint Q&#x5B;N], P&#x5B;N]; int cz, op;\r\nint n, m;\r\n\r\nint calc(int l, int r) {\r\n    return f&#x5B;q]&#x5B;l] + w&#x5B;l+1]&#x5B;r];\r\n}\r\n\r\nint left(int a, int b) {\r\n    int l = a, r = n;\r\n    while (l &lt; r) {\r\n        int m = (l + r) \/ 2;\r\n        if (calc(b, m) &lt;= calc(a, m)) {\r\n            r = m;\r\n        } else {\r\n            l = m + 1;\r\n        }\r\n    }\r\n    return l;\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    Rush {\r\n\r\n        RD(n, m); A.clear(); REP(i, n) A.PB(RD(a&#x5B;i]));\r\n\r\n        if (m &gt;= n-1) {\r\n            puts(&quot;0&quot;);\r\n            continue;\r\n        }\r\n\r\n        UNQ(A); REP(i, n) a&#x5B;i] = LBD(A, a&#x5B;i]);\r\n\r\n        REP(i, n) {\r\n            fenwick_tree&lt;int&gt; T(SZ(A));\r\n            FOR(j, i+1, n) {\r\n                T.add(a&#x5B;j-1], 1);\r\n                w&#x5B;i]&#x5B;j] = w&#x5B;i]&#x5B;j-1] + (j-i) - T.sum(a&#x5B;j]+1);\r\n            }\r\n        }\r\n\r\n        FOR(i, 1, n) f&#x5B;p]&#x5B;i] = w&#x5B;0]&#x5B;i];\r\n\r\n        REP_1(s, m) {\r\n            swap(p, q); cz = 0, op = 0; Q&#x5B;0] = s-1;\r\n\r\n            FOR(i, s, n) {\r\n                \/\/f&#x5B;p]&#x5B;i] = INF; FOR(j, s-1, i) checkMin(f&#x5B;p]&#x5B;i], calc(j, i))\uff1b\r\n                while (cz &lt; op &amp;&amp; P&#x5B;cz] &lt;= i) ++cz;\r\n                f&#x5B;p]&#x5B;i] = calc(Q&#x5B;cz], i);\r\n                int j = left(Q&#x5B;op], i);\r\n                while (cz &lt; op &amp;&amp; j &lt;= P&#x5B;op-1]) j = left(Q&#x5B;--op], i);\r\n                P&#x5B;op] = j; Q&#x5B;++op] = i;\r\n            }\r\n        }\r\n\r\n        cout &lt;&lt; f&#x5B;p]&#x5B;n-1] &lt;&lt; endl;\r\n    }\r\n}\r\n\r\n<\/pre>\n<h2><span class=\"ez-toc-section\" id=\"Problem_M_Minor_Evil\"><\/span>Problem M. Minor Evil<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u7ed9\u5b9a 1 \u5230 n\uff0cn \u4e2a\u6570\u548c m \u7ec4\u64cd\u4f5c\uff08ai, bi\uff09\uff0c\u6bcf\u7ec4\u64cd\u4f5c\u8868\u793a\uff0c\u5f53\u5e8f\u5217\u4e2d\u5b58\u5728 ai \u65f6\uff0c\u53ef\u4ee5\u5220\u9664 bi\uff0c\u4f60\u5fc5\u987b\u6309\u7167\u987a\u5e8f\u51b3\u5b9a\u6bcf\u4e2a\u64cd\u4f5c\u662f\u5426\u6267\u884c\uff0c\u95ee\u662f\u5426\u80fd\u5c06\u7ed9\u5b9a\u96c6\u5408\u4e2d\u7684\u6570\u90fd\u5220\u9664\u3002<\/p>\n<p>\u6bcf\u4e2a\u6570\u8981\u5c3d\u53ef\u80fd\u4e45\u7684\u505a\u8df3\u677f\uff0c\u6211\u4eec\u5e94\u8be5\u8981\u627e\u5230\u5b83\u80fd\u88ab\u5220\u9664\u65f6\u7684\u6700\u665a\u65f6\u523b\u3002<br \/>\n\u7b2c\u4e00\u53cd\u5e94\u53ef\u4ee5\u7c7b\u6bd4 Dijkstra()\uff0c\u505a\u6cd5\u4e5f\u786e\u5b9e\u5982\u6b64\u3002<br \/>\n(\u4e0a\u6b21\u9047\u5230\u7c7b\u4f3c\u7684\u5957\u8def\u5e94\u8be5\u662f\u5728 <a href=\"https:\/\/www.bilibili.com\/video\/BV18Y411T71q?p=3\">Codeforces Round #800 (Div. 1+2) \u7684 C \u9898<\/a>\u3002)<\/p>\n<p>d[i] \u73b0\u5728\u5b9a\u4e49\u4e3a\uff1ai \u4f4d\u7f6e\u53ef\u88ab\u5220\u9664\u7684\u6700\u665a\u65f6\u523b\u3002<br \/>\n\u90a3\u4e48\u5bf9\u4e8e\u6240\u6709\u4e0d\u9700\u8981\u88ab\u5220\u9664\u7684\u4f4d\u7f6e\uff0c\u521d\u59cb d[i] = k+1 \u5373\u53ef\u3002<br \/>\n\u6700\u540e\u53ea\u8981\u6ca1\u6709 d[i] = 0 \u8bf4\u660e\u6240\u6709\u7684\u70b9\u90fd\u53ef\u4ee5\u5728\u67d0\u4e2a\u65f6\u523b\u88ab\u5220\u9664\u3002<\/p>\n<p>\u6240\u4ee5\u548c\u539f\u7248 Dijkstra \u76f8\u6bd4\uff0c\u53ea\u662f\u53d8\u6210\u4e86\u65f6\u5149\u5012\u6d41\uff0c\u4ee5\u53ca\u8fb9\u591a\u4e86\u65f6\u95f4\u7684\u9650\u5236\u800c\u5df2\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: Dijkstra; toolbar: true; notranslate\" title=\"Dijkstra\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(1e6) + 9;\r\nset&lt;int&gt; Q&#x5B;N]; VII adj&#x5B;N]; char s&#x5B;N]; int d&#x5B;N];\r\nint n, k;\r\n\r\nbool dijkstra() {\r\n    REP_1(i, k+1) Q&#x5B;i].clear();\r\n    REP_1(i, n) if (d&#x5B;i] == k+1) Q&#x5B;k+1].insert(i);\r\n\r\n    DWN_1(i, k+1, 2) {\r\n        for (auto u: Q&#x5B;i]) {\r\n            for (auto e: adj&#x5B;u]) {\r\n                int v = e.fi, w = e.se;\r\n                if (d&#x5B;v] &lt; w &amp;&amp; w &lt; i) {\r\n                    if (d&#x5B;v]) Q&#x5B;d&#x5B;v]].erase(Q&#x5B;d&#x5B;v]] .find(v));\r\n                    Q&#x5B;d&#x5B;v] = w].insert(v);\r\n                }\r\n            }\r\n        }\r\n    }\r\n\r\n    REP_1(i, n) if (!d&#x5B;i]) return 0;\r\n    return 1;\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n     \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n#endif\r\n\r\n    Rush {\r\n\r\n        RD(n, k); REP_1(i, n) adj&#x5B;i].clear();\r\n\r\n        REP_1(i, k) {\r\n            int a, b; RD(a, b);\r\n            adj&#x5B;a].PB({b, i});\r\n        }\r\n\r\n        REP_1(i, n) d&#x5B;i] = k+1;\r\n        Rush d&#x5B;RD()] = 0;\r\n\r\n        if (!dijkstra()) {\r\n            puts(&quot;NIE&quot;);\r\n        } else {\r\n            puts(&quot;TAK&quot;);\r\n            REP(i, k) s&#x5B;i] = 'N';\r\n            REP_1(i, n) s&#x5B;d&#x5B;i]-1] = 'T'; s&#x5B;k] = 0;\r\n            puts(s);\r\n        }\r\n    }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/qoj.ac\/contest\/1103?v=1 https:\/\/twitter.com\/noimi_kyopro\/status\/1624549003038965760 Problem B. Bars n \u4e2a\u4eba\u6392\u6210\u4e00\u6392\u5f00\u9152\u5427\uff0c\u6bcf\u4e2a\u4eba\u53ef\u4ee5\u9009\u62e9\u5f00\u6216\u4e0d\u5f00\uff0c\u4e14\u6bcf\u4e2a\u4eba\u4f1a\u53bb\u81ea\u5df1\u4ee5\u5916\u7684\u5de6\u53f3\u6700\u8fd1 2 \u4e2a\u5f00\u4e1a\u9152\u5427\u5404 1 \u6b21\uff08\u6ca1\u6709\u5219\u4e0d\u53bb\uff09\uff0c\u7b2c i \u4e2a\u4eba\u7684\u9152\u5427\u6bcf\u62db\u5f85\u4e00\u4e2a\u987e\u5ba2\u5f97 p_i \u5143\uff0c\u6700\u5927\u5316\u603b\u5229\u6da6\u3002 \u5148\u5199\u4e2a\u66b4\u529b\u538b\u538b\u60ca\u3002 #include &lt;lastweapon\/io&gt; using namespace lastweapon; const int N = int(1e6) + 9; LL f&#x5B;N]; int p&#x5B;N]; int n; int main() { #ifndef ONLINE_JUDGE freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin); #endif Rush { RD(n); REP(i, n) RD(p&#x5B;i]); fill(f, f+n, 0); FOR(i, 1, n) [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_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","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2338","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-BI","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2338","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=2338"}],"version-history":[{"count":21,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2338\/revisions"}],"predecessor-version":[{"id":2361,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2338\/revisions\/2361"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2338"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2338"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2338"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}