{"id":1331,"date":"2020-02-23T15:39:16","date_gmt":"2020-02-23T07:39:16","guid":{"rendered":"http:\/\/149.129.74.185\/?p=1331"},"modified":"2020-02-23T15:39:16","modified_gmt":"2020-02-23T07:39:16","slug":"bilibili-11%e5%b0%8fa%e6%9c%80%e5%a4%9a%e4%bc%9a%e6%96%b0%e8%ae%a4%e8%af%86%e7%9a%84%e5%a4%9a%e5%b0%91%e4%ba%ba","status":"publish","type":"post","link":"http:\/\/www.magicmipamipa.com\/?p=1331","title":{"rendered":"[Bilibili] (11)\u5c0fA\u6700\u591a\u4f1a\u65b0\u8ba4\u8bc6\u7684\u591a\u5c11\u4eba"},"content":{"rendered":"<h4 class=\"subject-item-title\" id=\"mcetoc_1e1ofmp190\">\u9898\u76ee\u63cf\u8ff0<\/h4>\n<div class=\"subject-describe\">\n<div class=\"js-question-content subject-question mb2\">\n<p><span>\u5c0f<\/span><span>A<\/span><span>\u53c2\u52a0\u4e86\u4e00\u4e2a<\/span><span>n<\/span><span>\u4eba\u7684\u6d3b\u52a8\uff0c\u6bcf\u4e2a\u4eba\u90fd\u6709\u4e00\u4e2a\u552f\u4e00\u7f16\u53f7<\/span><span>i(i&gt;=0 &amp; i&lt;n)<\/span><span>\uff0c\u5176\u4e2d<\/span><span>m<\/span><span>\u5bf9\u76f8\u4e92\u8ba4\u8bc6\uff0c\u5728\u6d3b\u52a8\u4e2d\u4e24\u4e2a\u4eba\u53ef\u4ee5\u901a\u8fc7\u4e92\u76f8\u90fd\u8ba4\u8bc6\u7684\u4e00\u4e2a\u4eba\u4ecb\u7ecd\u8ba4\u8bc6\u3002\u73b0\u5728\u95ee\u6d3b\u52a8\u7ed3\u675f\u540e\uff0c\u5c0f<\/span><span>A<\/span><span>\u6700\u591a\u4f1a\u8ba4\u8bc6\u591a\u5c11\u4eba\uff1f<\/span><\/p>\n<\/div>\n<h4 id=\"mcetoc_1e1ofmp191\">\u8f93\u5165\u63cf\u8ff0:<\/h4>\n<pre>\u7b2c\u4e00\u884c\u805a\u4f1a\u7684\u4eba\u6570\uff1an\uff08n&gt;=3 &amp; n&lt;10000\uff09\uff1b\r\n\u7b2c\u4e8c\u884c\u5c0fA\u7684\u7f16\u53f7: ai\uff08ai &gt;= 0 &amp; ai &lt; n)\uff1b\r\n\u7b2c\u4e09\u4e92\u76f8\u8ba4\u8bc6\u7684\u6570\u76ee: m\uff08m&gt;=1 &amp; m\r\n&lt; n(n-1)\/2\uff09\uff1b\r\n\u7b2c4\u5230m+3\u884c\u4e3a\u4e92\u76f8\u8ba4\u8bc6\u7684\u5bf9\uff0c\u4ee5','\u5206\u5272\u7684\u7f16\u53f7\u3002<\/pre>\n<h4 id=\"mcetoc_1e1ofmp192\">\u8f93\u51fa\u63cf\u8ff0:<\/h4>\n<pre>\u8f93\u51fa\u5c0fA\u6700\u591a\u4f1a\u65b0\u8ba4\u8bc6\u7684\u591a\u5c11\u4eba\uff1f<\/pre>\n<div class=\"question-oi\">\n<div class=\"question-oi-hd\">\u793a\u4f8b1<\/div>\n<div class=\"question-oi-bd\">\n<div class=\"question-oi-mod\">\n<h4 id=\"mcetoc_1e1ofmp193\">\u8f93\u5165<\/h4>\n<div class=\"question-oi-cont\">\n<pre>7\r\n5\r\n6\r\n1,0\r\n3,1\r\n4,1\r\n5,3\r\n6,1\r\n6,5<\/pre>\n<\/div>\n<\/div>\n<div class=\"question-oi-mod\">\n<h4 id=\"mcetoc_1e1ofmp194\">\u8f93\u51fa<\/h4>\n<div class=\"question-oi-cont\">\n<pre>3<\/pre>\n<hr \/>\n<p>\u4e00\u9053\u975e\u5e38\u5e38\u89c4\u7684\u96c6\u5408\u9898\uff0c\u672c\u4eba\u8ba4\u4e3a\u6211\u8fd9\u4e2aaknow\u7684\u8bbe\u7f6e\u8fd8\u662f\u5f88\u7075\u6027\u7684\u3011<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\">#include&lt;iostream&gt;\r\n#include&lt;memory.h&gt;\r\nusing namespace std;\r\nint root[10006];\r\nvoid unionr(int a, int b){\r\n    root[a] = b;\r\n}\r\nint findroot( int v ){\r\n    if( root[v] == v ) return v;\r\n    else return root[v] = findroot(root[v]);\r\n}\r\nint main(){\r\n    int n,ai,m;\r\n    cin &gt;&gt; n &gt;&gt; ai &gt;&gt; m;\r\n    for( int i = 0 ; i &lt; n ; i ++ ) root[i] = i;\r\n    int aknow = 0;\r\n    for( int i = 0 ; i &lt; m ; i ++ ){\r\n        int a,b;\r\n        scanf(\"%d,%d\",&amp;a,&amp;b);\r\n        if( a == ai || b == ai) aknow--;\r\n        unionr(findroot(a),findroot(b));\r\n    }\r\n    int aroot = findroot(ai);\r\n    for( int i = 0 ; i &lt; n; i ++ )\r\n        if( findroot(i) == aroot &amp;&amp; i != ai ) aknow++;\r\n    printf(\"%d\",aknow);\r\n    return 0;\r\n}<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u63cf\u8ff0 \u5c0fA\u53c2\u52a0\u4e86\u4e00\u4e2an\u4eba\u7684\u6d3b\u52a8\uff0c\u6bcf\u4e2a\u4eba\u90fd\u6709\u4e00\u4e2a\u552f\u4e00\u7f16\u53f7i(i&gt;=0 &amp; i&lt; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,35],"tags":[],"_links":{"self":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1331"}],"collection":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1331"}],"version-history":[{"count":1,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1331\/revisions"}],"predecessor-version":[{"id":1332,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1331\/revisions\/1332"}],"wp:attachment":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1331"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1331"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1331"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}