{"id":45512,"date":"2023-12-11T15:06:03","date_gmt":"2023-12-11T07:06:03","guid":{"rendered":"https:\/\/wx.kaifamiao.info\/?p=45512"},"modified":"2023-12-11T15:06:03","modified_gmt":"2023-12-11T07:06:03","slug":"%e7%ae%97%e6%b3%95%e9%a2%98%ef%bc%9a%e5%90%8d%e4%ba%ba%e9%97%ae%e9%a2%98%ef%bc%8c%e7%bb%99%e5%87%ba%e6%9c%80%e4%bc%98%e8%a7%a3%e6%b3%95-2","status":"publish","type":"post","link":"http:\/\/wx.kaifamiao.info\/index.php\/2023\/12\/11\/%e7%ae%97%e6%b3%95%e9%a2%98%ef%bc%9a%e5%90%8d%e4%ba%ba%e9%97%ae%e9%a2%98%ef%bc%8c%e7%bb%99%e5%87%ba%e6%9c%80%e4%bc%98%e8%a7%a3%e6%b3%95-2\/","title":{"rendered":"\u7b97\u6cd5\u9898\uff1a\u540d\u4eba\u95ee\u9898\uff0c\u7ed9\u51fa\u6700\u4f18\u89e3\u6cd5"},"content":{"rendered":"

“`” \u53c2\u8003\u56de\u7b54\uff1a<\/p>\n

\u95ee\u9898\u63cf\u8ff0\uff1a<\/p>\n

\u6709n\u4e2a\u4eba\u4ed6\u4eec\u4e4b\u95f4\u8ba4\u8bc6\u4e0e\u5426\u7528\u90bb\u63a5\u77e9\u9635\u8868\u793a(1\u8868\u793a\u8ba4\u8bc6\uff0c0\u8868\u793a\u4e0d\u8ba4\u8bc6)\uff0c\u5e76A\u8ba4\u8bc6B\u5e76\u4e0d\u610f\u5473\u7740B\u8ba4\u8bc6A\uff0c\u4e5f\u5c31\u610f\u5473\u7740\u662f\u4e2a\u6709\u5411\u56fe\u3002\u5982\u679c\u4e00\u4e2a\u4eba\u662f\u540d\u4eba\uff0c\u4ed6\u5fc5\u987b\u6ee1\u8db3\u4e24\u4e2a\u6761\u4ef6\uff0c\u4e00\u4e2a\u662f\u4ed6\u4e0d\u8ba4\u8bc6\u4efb\u4f55\u4eba\uff0c\u53e6\u4e00\u4e2a\u662f\u6240\u6709\u4eba\u5fc5\u987b\u90fd\u8ba4\u8bc6\u4ed6\u3002<\/p>\n

\u89e3\u51b3\u95ee\u9898\uff1a<\/p>\n

\u7528\u4e00\u4e2a\u6570\u7ec4\u4fdd\u5b58\u6240\u6709\u6ca1\u68c0\u67e5\u7684\u4eba\u7684\u7f16\u53f7\uff0c\u904d\u5386\u6570\u7ec4\u4e2d\u7684\u4e24\u4e2a\u4ebai\uff0cj\u3002\u5982\u679ci\u8ba4\u8bc6j\uff0c\u5219i\u5fc5\u5b9a\u4e0d\u662f\u540d\u4eba\uff0c\u5220\u9664i\uff0c\u5982\u679ci\u4e0d\u8ba4\u8bc6j\uff0c\u5219j\u5fc5\u5b9a\u4e0d\u662f\u540d\u4eba\uff0c\u5220\u9664j\uff0c\u6700\u7ec8\u4f1a\u53ea\u5269\u4e0b\u4e00\u4e2a\u4eba\uff0c\u6211\u4eec\u68c0\u67e5\u4e00\u4e0b\u8fd9\u4e2a\u4eba\u662f\u5426\u662f\u540d\u4eba\u5373\u53ef\uff0c\u5982\u679c\u662f\uff0c\u8fd4\u56de\u8fd9\u4e2a\u4eba\uff0c\u5982\u679c\u4e0d\u662f\uff0c\u90a3\u4e48\u8fd9n\u4e2a\u4eba\u4e2d\u5e76\u65e0\u540d\u4eba\u3002<\/p>\n

\u4ee3\u7801\uff1a<\/p>\n

\/\/\u521d\u59cb\u5316\u6570\u7ec4\u7f16\u53f7<\/p>\n

for(int i=a;i<n;i++){\na[i]=i;\n}\nwhile(n>1){\nif(known[a[0]][a[1]]){\n\/\/\u5982\u679ca[0]\u53f7\u8ba4\u8bc6a[1]\u53f7\n\/\/\u5220\u9664a[0]\uff0c\u5220\u9664\u64cd\u4f5c\u7528a[n]\u66ff\u6362\u6389a[0]\u5373\u53ef\uff0c\u518d\u5c06n\u4e0b\u6807\u51cf1\na[0]=a[--n];\n}else{\n\/\/\u5982\u679ca[0]\u53f7\u4e0d\u8ba4\u8bc6a[1]\u53f7\n\/\/\u5220\u9664a[1]\na[1]=a[--n];\n}\n}\n\/\/\u6700\u7ec8\u68c0\u67e5a[0]\u662f\u5426\u4e3a\u540d\u4eba\n\nfor(int i=0;i<n;++i){\n\n\/\/\u4e0d\u8003\u8651\u81ea\u8eab\uff0c\u5e76\u4e14\u68c0\u67e5\u4ed6\u662f\u5426\u8ba4\u8bc6\u67d0\u4e2a\u4eba\uff0c\u5982\u679c\u8ba4\u8bc6\uff0c\u90a3\u4e48\u4e0d\u662f\u540d\u4eba\n\/\/\u68c0\u67e5\u5176\u4ed6\u4eba\u662f\u5426\u8ba4\u8bc6\u4ed6\uff0c\u5982\u679c\u6709\u4eba\u4e0d\u8ba4\u8bc6\u4ed6\uff0c\u90a3\u4e48\u4ed6\u4e5f\u4e0d\u662f\u540d\u4eba\nif((a[0]!=i)&&(known[a[0]][i]||!known[i][a[0]]))\nreturn -1;\n}\nreturn a[0];\n}\n<\/code><\/pre>\n
\u7b97\u6cd5\u4f18\u5316\uff1a<\/p>\n
\u4ee5\u4e0a\u7b97\u6cd5\u9700\u8981\u7528\u4e00\u4e2a\u6570\u7ec4\u6765\u4fdd\u5b58\u6ca1\u6709\u68c0\u67e5\u7684\u4eba\u7684\u7f16\u53f7\uff0c\u610f\u5473\u7740\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(n)\uff0c\u662f\u5426\u53ef\u4ee5\u8ba9\u7a7a\u95f4\u590d\u6742\u5ea6\u964d\u4f4e\u5230O(1)\u5462\uff0c\u7b54\u6848\u662f\u80af\u5b9a\u7684\uff0c\u89e3\u51b3\u65b9\u6cd5\u5c31\u662f\u7528\u4e00\u5934\u626b\u7684\u65b9\u6cd5<\/p>\n
\u8fd9\u91cc\u6211\u4eec\u5c31\u4e0d\u9700\u8981\u7528\u4e00\u4e2a\u6570\u7ec4\u6765\u4fdd\u5b58\u6ca1\u6709\u68c0\u67e5\u7684\u4eba\u7684\u7f16\u53f7\u4e86\uff0c\u6211\u4eec\u76f4\u63a5\u5bf9n\u4e2a\u4eba\u8fdb\u884c\u904d\u5386<\/p>\n
\u904d\u5386\u7684\u65b9\u5f0f\u662f\u5b9a\u4e49\u4e24\u4e2a\u4e0b\u6807\uff0c\u7528\u4e24\u4e2a\u4e0b\u6807\u4e00\u8d77\u5f80\u540e\u626b\uff0c\u5bf9\u4e8e\u4e24\u4e2a\u4e0b\u6807i,j\u800c\u8a00\uff0c\u4fdd\u8bc1[o~i-1]\u6ca1\u6709\u540d\u4eba\uff0c\u5e76\u4e14[i~j-1]\u4e5f\u6ca1\u6709\u540d\u4eba\uff0c\u5982\u679ci\u8ba4\u8bc6j\uff0c\u90a3\u4e48i\u4e0d\u662f\u540d\u4eba\uff0c\u5220\u6389i\uff0c\u5220\u9664\u7684\u65b9\u6cd5\u5c31\u662fi=j,j++\uff0c\u5982\u679ci\u4e0d\u8ba4\u8bc6j\uff0c\u5220\u9664j\uff0c\u5220\u9664\u7684\u65b9\u5f0f\u662fj++\uff0c\u904d\u5386\u7684\u65f6\u5019\u8ba9j\u4e00\u76f4\u52a0\u5c31\u53ef\u4ee5\u4e86\u3002<\/p>\n
int i=0;j=1;\nfor(;j<n;++j){\nif(known[a[i]a[j]])\ni=j;\n}\nfor(j=0;j<n;j++){\nif((i!=j)&&(known[i][j]||!known[j][i]))\nreturn -1;\n}\nreturn i;\n}\n<\/code><\/pre>\n
\u7b97\u6cd5\u4f18\u53162\uff1a<\/p>\n
\u9664\u4e86\u4e00\u5934\u626b\u7684\u4f18\u5316\u65b9\u5f0f\uff0c\u4e5f\u53ef\u4ee5\u7528\u4e24\u5934\u626b\u7684\u65b9\u5f0f\u4f18\u5316\u4ee5\u4e0a\u7684\u7b97\u6cd5\uff0c\u4fdd\u8bc10~i-1\u6ca1\u6709\u540d\u4eba\uff0c\u5e76\u4e14j+1~n\u4e5f\u6ca1\u6709\u540d\u4eba\uff0c\u5982\u679ci\u8ba4\u8bc6j\uff0c\u5220\u9664i\uff0c\u5982\u679ci\u4e0d\u8ba4\u8bc6j\uff0c\u5220\u9664j<\/p>\n
i=0;j=n-1;\nwhile(i<j){\nif(known[i][j]){\n++i;\n}else{\n--j;\n}\n}\nfor(j=0;j<n;++j){\nif(i!=j&&(known[i][j]||!known[j][i]))\nreturn -1\n}\nreturn i;\n}\n<\/code><\/pre>\n
            \"```\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
“`” \u53c2\u8003\u56de\u7b54\uff1a \u95ee\u9898\u63cf\u8ff0\uff1a \u6709n\u4e2a\u4eba\u4ed6\u4eec\u4e4b\u95f4\u8ba4\u8bc6\u4e0e\u5426\u7528\u90bb\u63a5\u77e9\u9635\u8868\u793a(1\u8868\u793a\u8ba4\u8bc6\uff0c0 […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[],"class_list":["post-45512","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45512","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/comments?post=45512"}],"version-history":[{"count":1,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45512\/revisions"}],"predecessor-version":[{"id":45513,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45512\/revisions\/45513"}],"wp:attachment":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/media?parent=45512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/categories?post=45512"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/tags?post=45512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}