{"id":1857,"date":"2022-01-12T11:48:57","date_gmt":"2022-01-12T03:48:57","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1857"},"modified":"2023-04-30T18:43:23","modified_gmt":"2023-04-30T10:43:23","slug":"noi-2021","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/noi-2021\/","title":{"rendered":"NOI 2021"},"content":{"rendered":"<h2>Day 1<\/h2>\n<h2>\u8f7b\u91cd\u8fb9<\/h2>\n<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P7735\">P7735 [NOI2021] \u8f7b\u91cd\u8fb9<\/a><br \/>\n\u5bf9\u4e8e\u6bcf\u6b21\u64cd\u4f5c\u6253\u4e00\u4e2a\u65b0\u7684\u65f6\u95f4\u6233\uff0c\u7528\u8fd9\u4e2a\u65f6\u95f4\u6233\u5bf9\u8def\u5f84\u67d3\u8272\uff0c\u90a3\u4e48\u3002\u3002\u3002<br \/>\n\u91cd\u8fb9\u6570 = \u76f8\u540c\u989c\u8272\u7684\u76f8\u90bb\u70b9\u5bf9\u6570 = \u8def\u5f84\u957f\u5ea6 &#8211; \u989c\u8272\u6bb5\u6570\uff0c\u4e8e\u662f\u53ea\u9700\u8981\u6c42\u51fa\u989c\u8272\u6bb5\u6570\u3002<\/li>\n<\/ul>\n<p>\u7528 <a href=\"https:\/\/www.luogu.com.cn\/problem\/P2486\">[SDOI2011]\u67d3\u8272<\/a> \u7684\u4ee3\u7801\u7a0d\u5fae\u6539\u6539\u5373\u53ef\u3002<\/p>\n<h2>\u8def\u5f84\u4ea4\u70b9<\/h2>\n<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P7736\">P7736 [NOI2021] \u8def\u5f84\u4ea4\u70b9<\/a><\/li>\n<li><a href=\"https:\/\/oi-wiki.org\/graph\/lgv\/\">LGV \u5f15\u7406<\/a><\/li>\n<\/ul>\n<h2>\u5e86\u5178<\/h2>\n<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P7737\">Luogu P7737 [NOI2021] \u5e86\u5178<\/a><\/li>\n<li><a href=\"https:\/\/djy-juruo.blog.luogu.org\/solution-p7737\">https:\/\/djy-juruo.blog.luogu.org\/solution-p7737<\/a><\/li>\n<\/ul>\n<p>\u56fe\u8bba\u9898\uff0c\u7b97\u6cd5\u90fd\u4e0d\u96be\uff0c\u4f46\u662f\u8981\u62fc\u7684\u4e1c\u897f\u5f88\u591a\uff0c\u6bd4\u8f83\u8003\u9a8c\u5e95\u529b\u3002\u3002\u3002<a href=\"https:\/\/www.luogu.com.cn\/record\/66274545\">\u66b4\u529b Floyd \u53ef\u4ee5\u62ff 20 \u5206<\/a>\u3002\u3002<\/p>\n<p>\u6b63\u89e3\u5148 scc()\uff0c\u7136\u540e\u9898\u76ee\u7684\u6761\u4ef6\u544a\u8bc9\u6211\u4eec\u53ef\u4ee5\u7528\u6811\u6765\u4ee3\u66ff scc() \u540e\u7684 dag \u53bb\u8868\u793a\u53ef\u8fbe\u5173\u7cfb\uff0c<br \/>\nk=0 \u7684\u60c5\u51b5\uff0c\u76f4\u63a5\u5728\u6811\u4e0a\u7528\u524d\u7f00\u548c\u51cf\u51cf\u5373\u53ef\uff0c\u7136\u540e <a href=\"https:\/\/djy-juruo.blog.luogu.org\/solution-p7737\">\u8fd9\u4e2a\u9898\u89e3<\/a> \u544a\u8bc9\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u865a\u6811\u6765\u907f\u514d\u8ba8\u8bba k\u3002\u3002<\/p>\n<p>\u6211\u4eec\u7528 <a href=\"https:\/\/www.shuizilong.com\/house\/archives\/atl\/\">atl \u91cc\u63d0\u4f9b\u7684 scc()<\/a>\uff0c<br \/>\n\u518d\u4ece <a href=\"https:\/\/www.luogu.com.cn\/record\/57570966\">\u8fd9\u4e2a\u9898\u91cc\u627e\u6765 lca<\/a>\uff0c\uff08\u7528\u500d\u589e\u7956\u5148\u6211\u4f1a TLE\u3002\u3002\uff09<br \/>\n\u518d\u4ece <a href=\"https:\/\/codeforces.com\/contest\/1320\/submission\/72277718\">\u8fd9\u4e2a\u9898\u91cc\u627e\u6765\u865a\u6811<\/a>\uff0c<\/p>\n<p>\u6700\u540e\u7f1d\u5408\u5728\u4e00\u8d77\uff0c\u66b4\u529b bfs() \u5373\u53ef\uff0c\uff08Floyd \u7684\u8bdd\u8c8c\u4f3c\u8981\u5f00\u8def\u5f84\u6570\u548c\u6743\u503c\u548c\u4e24\u4e2a\u6570\u7ec4\u3002\uff09<\/p>\n<p>btw\uff0c\u65e0\u8bba Kosaraju\u3001\u8fd8\u662f Tarjan\uff0c\u90fd\u662f\u57fa\u4e8e dfs() \u7684\u7b97\u6cd5\uff0c\u5f3a\u8fde\u901a\u7f29\u70b9\u5b8c\u6210\u4e4b\u540e\u7684\u7ed3\u6784\uff0c\u90fd\u662f\u6ee1\u8db3\u9006\u5411\u62d3\u6251\u5e8f\u7684\uff0c\u53d6\u53cd\u540e\uff0c\u76f4\u63a5\u628a 1 \u53f7\u8282\u70b9\u4f5c\u4e3a\u6839\u8282\u70b9\u5373\u53ef\uff0c\u53ef\u4ee5\u7701\u4e00\u4e2a\u62d3\u6251\u6392\u5e8f\u3002\u3002\u3002<br \/>\n&#8211; <a href=\"https:\/\/stackoverflow.com\/questions\/32750511\/does-tarjans-scc-algorithm-give-a-topological-sort-of-the-scc\">https:\/\/stackoverflow.com\/questions\/32750511\/does-tarjans-scc-algorithm-give-a-topological-sort-of-the-scc<\/a><\/p>\n<h1>Day 2<\/h1>\n<h2>\u91cf\u5b50\u901a\u4fe1<\/h2>\n<h2>\u5bc6\u7801\u7bb1<\/h2>\n<h2>\u673a\u5668\u4eba\u6e38\u620f<\/h2>\n<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/P7740\">P7740 [NOI2021] \u673a\u5668\u4eba\u6e38\u620f<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Day 1 \u8f7b\u91cd\u8fb9 P7735 [NOI2021] \u8f7b\u91cd\u8fb9 \u5bf9\u4e8e\u6bcf\u6b21\u64cd\u4f5c\u6253\u4e00\u4e2a\u65b0\u7684\u65f6\u95f4\u6233\uff0c\u7528\u8fd9\u4e2a\u65f6\u95f4\u6233\u5bf9\u8def\u5f84\u67d3\u8272\uff0c\u90a3\u4e48\u3002\u3002\u3002 \u91cd\u8fb9\u6570 = \u76f8\u540c\u989c\u8272\u7684\u76f8\u90bb\u70b9\u5bf9\u6570 = \u8def\u5f84\u957f\u5ea6 &#8211; \u989c\u8272\u6bb5\u6570\uff0c\u4e8e\u662f\u53ea\u9700\u8981\u6c42\u51fa\u989c\u8272\u6bb5\u6570\u3002 \u7528 [SDOI2011]\u67d3\u8272 \u7684\u4ee3\u7801\u7a0d\u5fae\u6539\u6539\u5373\u53ef\u3002 \u8def\u5f84\u4ea4\u70b9 P7736 [NOI2021] \u8def\u5f84\u4ea4\u70b9 LGV \u5f15\u7406 \u5e86\u5178 Luogu P7737 [NOI2021] \u5e86\u5178 https:\/\/djy-juruo.blog.luogu.org\/solution-p7737 \u56fe\u8bba\u9898\uff0c\u7b97\u6cd5\u90fd\u4e0d\u96be\uff0c\u4f46\u662f\u8981\u62fc\u7684\u4e1c\u897f\u5f88\u591a\uff0c\u6bd4\u8f83\u8003\u9a8c\u5e95\u529b\u3002\u3002\u3002\u66b4\u529b Floyd \u53ef\u4ee5\u62ff 20 \u5206\u3002\u3002 \u6b63\u89e3\u5148 scc()\uff0c\u7136\u540e\u9898\u76ee\u7684\u6761\u4ef6\u544a\u8bc9\u6211\u4eec\u53ef\u4ee5\u7528\u6811\u6765\u4ee3\u66ff scc() \u540e\u7684 dag \u53bb\u8868\u793a\u53ef\u8fbe\u5173\u7cfb\uff0c k=0 \u7684\u60c5\u51b5\uff0c\u76f4\u63a5\u5728\u6811\u4e0a\u7528\u524d\u7f00\u548c\u51cf\u51cf\u5373\u53ef\uff0c\u7136\u540e \u8fd9\u4e2a\u9898\u89e3 \u544a\u8bc9\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u865a\u6811\u6765\u907f\u514d\u8ba8\u8bba k\u3002\u3002 \u6211\u4eec\u7528 atl \u91cc\u63d0\u4f9b\u7684 scc()\uff0c \u518d\u4ece \u8fd9\u4e2a\u9898\u91cc\u627e\u6765 lca\uff0c\uff08\u7528\u500d\u589e\u7956\u5148\u6211\u4f1a TLE\u3002\u3002\uff09 \u518d\u4ece \u8fd9\u4e2a\u9898\u91cc\u627e\u6765\u865a\u6811\uff0c [&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-1857","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-tX","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1857","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=1857"}],"version-history":[{"count":2,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1857\/revisions"}],"predecessor-version":[{"id":2681,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1857\/revisions\/2681"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1857"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1857"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1857"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}