{"id":1668,"date":"2020-07-29T07:16:45","date_gmt":"2020-07-28T23:16:45","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1668"},"modified":"2020-12-19T03:45:03","modified_gmt":"2020-12-18T19:45:03","slug":"boi-2020","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/","title":{"rendered":"BOI 2020"},"content":{"rendered":"<p><!--more--><\/p>\n<h1><span class=\"ez-toc-section\" id=\"BOI_2020\"><\/span>BOI 2020<span class=\"ez-toc-section-end\"><\/span><\/h1>\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-69f7154497821\" 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-69f7154497821\"  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\/boi-2020\/#BOI_2020\" title=\"BOI 2020\">BOI 2020<\/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\/boi-2020\/#Day_1\" title=\"Day 1\">Day 1<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#Problem_A_Colors\" title=\"Problem A. Colors\">Problem A. Colors<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E6%84%8F\" title=\"\u9898\u610f\">\u9898\u610f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E8%A7%A3\" title=\"\u9898\u89e3\">\u9898\u89e3<\/a><\/li><\/ul><\/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\/boi-2020\/#Problem_B_Mixture\" title=\"Problem B. Mixture\">Problem B. Mixture<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E6%84%8F-2\" title=\"\u9898\u610f\">\u9898\u610f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E8%A7%A3-2\" title=\"\u9898\u89e3\">\u9898\u89e3<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#Problem_C_Joker\" title=\"Problem C. Joker\">Problem C. Joker<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E6%84%8F-3\" title=\"\u9898\u610f\">\u9898\u610f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E8%A7%A3-3\" title=\"\u9898\u89e3\">\u9898\u89e3<\/a><\/li><\/ul><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#Day_2\" title=\"Day 2\">Day 2<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#Problem_A_Graph\" title=\"Problem A. Graph\">Problem A. Graph<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E6%84%8F-4\" title=\"\u9898\u610f\">\u9898\u610f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E8%A7%A3-4\" title=\"\u9898\u89e3\">\u9898\u89e3<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-16\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#Problem_B_Village\" title=\"Problem B. Village\">Problem B. Village<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-17\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E6%84%8F-5\" title=\"\u9898\u610f\">\u9898\u610f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-18\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E8%A7%A3-5\" title=\"\u9898\u89e3\">\u9898\u89e3<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-19\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#Problem_C_Viruses\" title=\"Problem C. Viruses\">Problem C. Viruses<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-20\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E6%84%8F-6\" title=\"\u9898\u610f\">\u9898\u610f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-21\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/boi-2020\/#%E9%A2%98%E8%A7%A3-6\" title=\"\u9898\u89e3\">\u9898\u89e3<\/a><\/li><\/ul><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n\n<h1><span class=\"ez-toc-section\" id=\"Day_1\"><\/span>Day 1<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p><a href=\"https:\/\/codeforces.com\/contest\/1386\">\u4f20\u9001\u95e8<\/a><br \/>\n<a href=\"https:\/\/hackmd.io\/@E-5gxTGiSByBOKpvsaKa_g\/HJDNb1Aev\">HackMD<\/a><br \/>\n<a href=\"https:\/\/t.me\/algorithm_daily_of_minako\/382\">\u7ade\u30d7\u30ed\u65e5\u5e38<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_A_Colors\"><\/span>Problem A. Colors<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E6%84%8F\"><\/span>\u9898\u610f<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u4ea4\u4e92\u5f0f\u95ee\u9898\uff0c\u7ed9\u5b9a n\uff0c\u6bcf\u6b21\u4f60\u53ef\u4ee5\u5c06\u5934\u53d1\u67d3\u6210 1-n \u4e2d\u95f4\u7684\u4e00\u4e2a\u6570\u5b57\uff0c\u5982\u679c\u76f8\u90bb\u4e24\u6b21\u7684\u6570\u5b57\u5dee\u7684\u7edd\u5bf9\u503c &gt;= C\uff0c\u90a3\u4e48\u7537\u670b\u53cb\u4f1a\u6ce8\u610f\uff0c\u8fd4\u56de 1\uff0c\u5426\u5219\u8fd4\u56de 0\u3002\u6bcf\u4e2a\u989c\u8272\u53ea\u80fd\u7528\u4e00\u6b21\uff0c\u7528\u5c3d\u53ef\u80fd\u5c11\u7684\u8be2\u95ee\u627e\u5230 C\u3002<\/p>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E8%A7%A3\"><\/span>\u9898\u89e3<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u5f88\u4f18\u96c5\u7684\u500d\u589e\u6784\u9020\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_B_Mixture\"><\/span>Problem B. Mixture<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E6%84%8F-2\"><\/span>\u9898\u610f<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u52a8\u6001\u7ef4\u62a4\u82e5\u5e72\u74f6\u8c03\u5473\u6599\uff0c\u6bcf\u74f6\u8c03\u5473\u6599\u4e2d\u88c5\u6709\u4e00\u5b9a\u8d28\u91cf\u7684 \u76d0\uff0c\u80e1\u6912\u4e0e\u5927\u849c \u7684\u6df7\u5408\u7269\uff0c\u7ed9\u5b9a\u7f8e\u98df\u5bb6\u6700\u559c\u6b22\u7684\u8c03\u5473\u6599\u7684\u7ec4\u6210\uff0c\u6bcf\u6b21\u8be2\u95ee\uff0c\u53ef\u4ee5\u589e\u52a0\u4e00\u74f6\u65b0\u7684\u8c03\u5473\u6599\u6216\u8005\u5220\u9664\u4e00\u74f6\u4e4b\u524d\u6dfb\u52a0\u8fc7\u7684\u8c03\u5473\u6599\uff0c\u8fd4\u56de\u81f3\u5c11\u9700\u8981\u51e0\u74f6\u53ef\u4ee5\u6df7\u5408\u51fa\u7f8e\u98df\u5bb6\u6700\u559c\u6b22\u7684\u53e3\u5473\u3002<\/p>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E8%A7%A3-2\"><\/span>\u9898\u89e3<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u4e0d\u4f1a\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_C_Joker\"><\/span>Problem C. Joker<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E6%84%8F-3\"><\/span>\u9898\u610f<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u7ed9\u5b9a\u4e00\u5f20\u6709 n \u4e2a\u70b9 m \u6761\u8fb9\u7684\u65e0\u5411\u56fe\uff0c\u6bcf\u6b21\u8be2\u95ee\u7ed9\u51fa\u4e00\u4e2a\u533a\u95f4 [L, R]\uff0c\u95ee\u662f\u5426\u5b58\u5728\u5947\u73af\uff0c\u4f7f\u5f97\u73af\u4e2d\u4e0d\u5305\u542b\u533a\u95f4\u4e2d\u7684\u70b9\u3002<\/p>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E8%A7%A3-3\"><\/span>\u9898\u89e3<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u662f\u5426\u5b58\u5728\u5947\u73af\uff0c\u7b49\u4ef7\u4e8e\u4e8c\u5206\u56fe\u5224\u5b9a\u3002\u9759\u6001\u53ef\u4ee5 dfs\uff0c\u52a8\u6001\u7684\u8bdd\u53ef\u4ee5 dsu\uff0c\u6700\u540e\u5916\u9762\u5957\u4e00\u5c42\u83ab\u961f\u7b97\u6cd5\u5373\u53ef\u3002<\/p>\n<p>\u5f53\u7136\u4e5f\u53ef\u4ee5\u76f4\u63a5\u7528 lct\uff01<\/p>\n<p>\u5bf9\u4e8e\u5220\u9664 [l, r] \u533a\u95f4\u7684\u8fb9\uff0c\u6211\u4eec\u53ef\u4ee5\u7528\u7c7b\u4f3c\u7834\u73af\u4e3a\u94fe\u7684\u65b9\u6cd5\uff0c\u8f6c\u5316\u4e3a\u6bcf\u6b21\u8be2\u95ee\u4fdd\u7559 (r, l+m) \u533a\u95f4\u7684\u8fb9\uff0c\u663e\u7136\u8fb9\u8d8a\u5c11\u8d8a\u5bb9\u6613\u5408\u6cd5\uff0c\u6ee1\u8db3\u5355\u8c03\u6027\u3002\u6211\u4eec\u6309\u7167\u65f6\u95f4\u987a\u5e8f\u4f9d\u6b21\u63d2\u5165\u6240\u6709\u8fb9\uff0c\u7528 double-point \u7ef4\u62a4\u51fa\u5904\u7406\u5230\u65f6\u95f4 r \u65f6\uff0c\u6700\u5927\u7684 l \u4f7f\u5f97\u5f53\u524d\u7684\u72b6\u6001\u5408\u6cd5\u5373\u53ef\u3002\u8fd9\u6837\u5c31\u53ef\u4ee5\u8d34 <a href=\"https:\/\/github.com\/lychees\/ACM-Training\/tree\/master\/Archive\/BZOJ\/4025%20%E4%BA%8C%E5%88%86%E5%9B%BE\">BZOJ 4025<\/a> \u7684\u4ee3\u7801\u4e86\u3002<\/p>\n<h1><span class=\"ez-toc-section\" id=\"Day_2\"><\/span>Day 2<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p><a href=\"https:\/\/codeforces.com\/contest\/1387\">\u4f20\u9001\u95e8<\/a><br \/>\n<a href=\"https:\/\/t.me\/algorithm_daily_of_minako\/377\">\u7ade\u30d7\u30ed\u65e5\u5e38<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_A_Graph\"><\/span>Problem A. Graph<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E6%84%8F-4\"><\/span>\u9898\u610f<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u8fb9\u88ab\u7ea2\u3001\u84dd\u67d3\u8272\u7684\u65e0\u5411\u56fe\uff0c\u6c42\u4e00\u7ec4\u8282\u70b9\u7684\u6743\u503c\u65b9\u6848\uff0c\u6ee1\u8db3\u5bf9\u6240\u6709\u7684\u7ea2\u8fb9\uff0c\u5173\u8054\u7684\u8282\u70b9\u7684\u6743\u503c\u548c\u4e3a 1\uff0c\u5bf9\u6240\u6709\u7684\u84dd\u8fb9\uff0c\u6743\u503c\u548c\u4e3a 2\uff0c\u6ee1\u8db3\u6761\u4ef6\u7684\u57fa\u7840\u4e0a\uff0c\u6700\u5c0f\u5316\u6240\u6709\u8282\u70b9\u7684\u6743\u503c\u548c\u3002<\/p>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E8%A7%A3-4\"><\/span>\u9898\u89e3<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u8ba9\u4eba\u60f3\u8d77\u4e86\u4e4b\u524d Atcoder \u4e0a\u7684\u4e00\u9053\u67d3\u8272\u7684\u9898\u3002\u4e0d\u8fc7\u8fd9\u4e2a\u9898\u662f\u5b9e\u6570\u3002\u505a\u6cd5\u662f\u968f\u4fbf\u627e\u4e2a\u70b9\u548c\u521d\u59cb\u6807\u8bb0\u4e00\u8def dfs \u4e0b\u53bb\u628a\u6bcf\u4e2a\u8282\u70b9\u6807\u8bb0\u6210 <code>ax+b<\/code> \u7684\u5f62\u5f0f\uff0c\u5176\u4e2d a \u5c5e\u4e8e\u96c6\u5408 {-1, 0, 1}\uff0cx \u662f\u4e00\u4e2a\u5f85\u5b9a\u7cfb\u6570\uff0c\u6700\u540e\u7b97\u51fa x \u7684\u503c\u5373\u53ef\uff0c\u9700\u8981\u4e00\u4e9b insight\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_B_Village\"><\/span>Problem B. Village<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E6%84%8F-5\"><\/span>\u9898\u610f<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u6811\uff0c\u6c42\u4e24\u7ec4\u9519\u4f4d\u6392\u5217\u7684\u65b9\u6848 P\uff0c\u5206\u522b\u4f7f\u5f97 <code>\\sum dist(i, P[i])<\/code> \u7684\u6743\u503c\u548c\u6700\u5927\u548c\u6700\u5c0f\u3002<\/p>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E8%A7%A3-5\"><\/span>\u9898\u89e3<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u9996\u5148\u6700\u5c0f\u7684\u8bdd\u663e\u7136\u5c3d\u53ef\u80fd\u4ea4\u6362\u76f8\u90bb\u7684\u7ed3\u70b9\u7f16\u53f7\u5c31\u597d\u4e86\uff0c\u6211\u4eec\u5c31\u6bcf\u6b21\u627e\u53f6\u5b50\uff0c\u5982\u679c\u6ca1\u6709\u4ea4\u6362\u8fc7\uff0c\u5c31\u548c\u7236\u8282\u70b9\u4ea4\u6362\uff0c\u8fd9\u6837\u6700\u540e\u6709\u53ef\u80fd\u8fd8\u5269\u4e00\u4e2a\uff0c\u6ca1\u5173\u7cfb\u968f\u4fbf\u627e\u4e00\u4e2a\u76f8\u90bb\u7ed3\u70b9\u518d\u4ea4\u6362\u4e00\u6b21\u5c31\u597d\u3002<\/p>\n<p>\u5bf9\u4e8e\u6700\u5927\u7684\u60c5\u51b5\uff0c\u6211\u4eec\u8003\u5bdf\u6bcf\u6761\u8fb9 <code>(u,v)<\/code>\uff0c\u90a3\u4e48\u8fd9\u6761\u8fb9\u8d21\u732e\u7684\u4e0a\u754c\u662f <code>min(sz[u], sz[v])<\/code>\uff0c\u6211\u4eec\u53d1\u73b0\u53ef\u4ee5\u6784\u9020\u65b9\u6848\u8ba9\u6240\u6709\u8fb9\u7684\u4e0a\u754c\u90fd\u8fbe\u5230\uff0c\u65b9\u6cd5\u662f\u53ea\u8981\u8003\u5bdf\u91cd\u5fc3\uff0c\u8ba9\u6bcf\u4e2a\u70b9\u90fd\u6807\u8bb0\u5728\u53e6\u4e00\u9897\u5b50\u6811\u4e2d\u5373\u53ef\u3002<\/p>\n<p>\u8fd9\u6837\u770b\u7684\u8bdd\uff0c\u4f3c\u4e4e\u662f\u9700\u8981\u627e\u4e00\u4e0b\u91cd\u5fc3\u7684\u3002\u3002\u3002\u4f46\u662f <a href=\"https:\/\/codeforces.com\/contest\/1387\/submission\/87770865\">\u6700\u5feb\u7684\u63d0\u4ea4\u4ee3\u7801<\/a> \u76f4\u63a5\u5c31\u4e0a\u4e86\u3002\u3002\u53ea\u8981\u8bc1\u660e\u8fd9\u6837\u6784\u9020\u4e4b\u540e\uff0c\u53ef\u4ee5\u627e\u5230\u4e00\u4e2a\u8282\u70b9\u4f5c\u4e3a\u6839\uff0c\u4f7f\u5f97\u6bcf\u4e2a\u8282\u70b9\u90fd\u4e0d\u843d\u5165\u540c\u4e00\u5b50\u6811\u4e2d\u5c31\u884c\u4e86\u3002\u3002\u800c\u8fd9\u662f\u663e\u7136\u7684\uff0c\u56e0\u4e3a\u4ee5\u91cd\u5fc3\u5206\u5272\u7684\u8bdd\uff0c\u5b50\u6811\u7684 size \u4e0d\u4f1a\u8d85\u8fc7 n\/2\u3002<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Problem_C_Viruses\"><\/span>Problem C. Viruses<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E6%84%8F-6\"><\/span>\u9898\u610f<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u57fa\u56e0\u5e8f\u5217\u662f\u4e00\u4e2a\u7531 n \u79cd\u6570\u5b57\u5f62\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u5176\u4e2d 0\u30011 \u4e3a\u7ec8\u6b62\u5b57\u7b26\uff0c\u5176\u4ed6\u4e3a\u75c5\u6bd2\u5b57\u7b26\uff0c\u7ed9\u5b9a\u4e00\u5f20\u57fa\u56e0\u7a81\u53d8\u7684\u8868\u683c\uff0c\u6bcf\u4e2a\u8868\u683c\u8868\u793a\u4e00\u4e2a\u75c5\u6bd2\u5b57\u7b26\u53ef\u80fd\u4f1a\u7a81\u53d8\u6210\u7684\u57fa\u56e0\u4e32\uff0c\u4e00\u4e2a\u57fa\u56e0\u5e8f\u5217\u6bcf\u4e00\u79d2\u4e2d\uff0c\u4f1a\u6709\u4e00\u4e2a\u75c5\u6bd2\u5b57\u7b26\u7a81\u53d8\uff0c\u4e00\u4e9b\u75c5\u6bd2\u5b57\u7b26\u53ef\u80fd\u6709\u591a\u79cd\u7a81\u53d8\u65b9\u5411\u3002\u7ed9\u5b9a\u4e00\u4e9b\u6a21\u5f0f\u4e32\u4f5c\u4e3a\u6297\u4f53\uff0c\u95ee\u6bcf\u4e2a\u75c5\u6bd2\u5b57\u7b26\u6240\u80fd\u5f62\u6210\u7684\u6700\u77ed\u7684\uff0c\u4e0d\u88ab\u4efb\u610f\u4e00\u4e2a\u6297\u4f53\u6240\u8bc6\u522b\u7684\u7ec8\u6b62\u5e8f\u5217\u7684\u957f\u5ea6\uff08\u6216\u8005\u8f93\u51fa\u4e0d\u5b58\u5728\uff09\u3002<\/p>\n<h3><span class=\"ez-toc-section\" id=\"%E9%A2%98%E8%A7%A3-6\"><\/span>\u9898\u89e3<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>\u6ca1\u6709\u75c5\u6bd2\u4e32\u7684\u65f6\u5019\u663e\u7136\u53ef\u4ee5\u7528\u7c7b\u4f3c\u6700\u77ed\u8def\u7684\u65b9\u6cd5 dp \u51fa\u6700\u77ed\u957f\u5ea6\u3002\u3002\u6709\u75c5\u6bd2\u4e32\u7684\u65f6\u5019\u5f00\u4e2a\u81ea\u52a8\u673a\u5c31\u597d\u3002\u3002\u7531\u4e8e\u6211\u4eec\u9700\u8981\u652f\u6301\u5408\u5e76\u5b57\u7b26\u4e32\u7684\u64cd\u4f5c\uff0c\u6240\u4ee5 dp \u72b6\u6001\u9700\u8981\u52a0\u7ef4\uff0c\u8bb0\u5f55\u5728\u81ea\u52a8\u673a\u4e2d\u7684\u72b6\u6001\u533a\u95f4\uff0c\u5177\u4f53\u8bf4\u6765\u5c31\u662f <code>dp[i][st][ed]<\/code> \u8868\u793a\u57fa\u56e0 i \u5c55\u5f00\u4e4b\u540e\uff0c\u4ece\u72b6\u6001 st \u5230\u72b6\u6001 ed \u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u3002<\/p>\n<p><a href=\"https:\/\/codeforces.com\/contest\/1387\/submission\/88233757\">\u51b2\u4e86\u4e00\u53d1<\/a> \u679c\u65ad TLE \u4e86\u3002\u867d\u7136\u672c\u8d28\u4e0a\u662f\u6700\u77ed\u8def\u6a21\u578b\uff0c\u4f46\u662f\u672c\u9898\u7684\u8fb9\u662f\u5e7f\u4e49\u7684\uff0c\u53ef\u80fd\u4f1a\u4e0e\u591a\u4e2a\u8282\u70b9\u5173\u8054\uff0cDijkstra \u7740\u5b9e\u4e0d\u592a\u597d\u5199\uff0c\u6240\u4ee5\u7528\u4e86 Bellman_Ford\uff0c\u8003\u8651\u5230\u74f6\u9888\u4e3b\u8981\u5728\u677e\u5f1b\uff08Relax\uff09\u64cd\u4f5c\u4e0a\uff08\u6bcf\u6b21\u90fd\u8981\u8dd1\u4e00\u904d\u795e\u4f3c Floyd \u7684 DP\uff09\uff0c\u611f\u89c9\u6539\u6210 SPFA \u53ef\u8fc7\u3002<\/p>\n<p>\u6362\u4e86 SPFA \u4e4b\u540e\u8fd8\u662f\u6709\u4e00\u4e2a\u70b9\u8fc7\u4e0d\u53bb\uff0c\u770b\u6765\u672c\u9898\u6570\u636e\u8fd8\u662f\u5f88\u826f\u5fc3\u7684\u3002\u3002<\/p>\n<p>\u770b\u4e86\u4e00\u4e0b\u5176\u4ed6\u4eba\u7684\u641e\u6cd5\uff0c\u6700\u5feb\u7684 <a href=\"https:\/\/codeforces.com\/contest\/1387\/submission\/87771947\">WZYYN<\/a> \u540c\u5b66\u975e\u5e38\u5389\u5bb3\uff0c\u76f4\u63a5 Bellman_Ford \u52a0\u4e86\u4e00\u4e2a\u5947\u602a\u7684\u526a\u679d\u5c31\u8fc7\u4e86\uff0c\u7136\u540e <a href=\"https:\/\/codeforces.com\/contest\/1387\/submission\/87781698\">duality<\/a> \u770b\u8d77\u6765\u662f\u5e38\u89c4\u7684 SPFA\uff0c\u5728 Relax \u7684\u65f6\u5019\u8df3\u8fc7\u4e86\u65e0\u7a77\u7684\u60c5\u51b5\uff0c\u539f\u7406\u5c31\u8ddf\u4e00\u4e9b\u77e9\u9635\u4e58\u6cd5\u7684\u9898\u76ee\uff0c\u9700\u8981\u4f18\u5316\u6389\u5185\u5c42\u5faa\u73af\u7684\u53d6\u6a21\u5dee\u4e0d\u591a\u3002<\/p>\n<p>\u7136\u540e <a href=\"https:\/\/codeforces.com\/contest\/1387\/submission\/87793448\">BenQ<\/a> \u548c <a href=\"https:\/\/codeforces.com\/contest\/1387\/submission\/87776530\">jiangly<\/a> \u7684\u7ed9\u90fd\u662f Dijkstra \u6b63\u89e3\u3002\u6700\u731b\u7684\u662f <a href=\"https:\/\/codeforces.com\/contest\/1387\/submission\/87788401\">liouzhou_101<\/a>\uff0c\u76f4\u63a5\u5361\u65f6\uff0c\u5c45\u7136\u8fd8\u5361\u8fc7\u53bb\u4e86 Orz\u3002\u3002\u3002\uff08<a href=\"https:\/\/codeforces.com\/contest\/1387\/submission\/88237324\">\u6240\u4ee5\u6211\u4e5f\u5361\u65f6\u5427\u3002\u3002&gt; &lt;\u3002\u3002\u3002<\/a>\uff09<\/p>\n","protected":false},"excerpt":{"rendered":"","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-1668","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-qU","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1668","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=1668"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1668\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1668"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}