{"id":161,"date":"2024-04-26T16:04:50","date_gmt":"2024-04-26T08:04:50","guid":{"rendered":"https:\/\/seanxd.com\/?p=161"},"modified":"2024-04-26T16:04:52","modified_gmt":"2024-04-26T08:04:52","slug":"zerojudge-m933","status":"publish","type":"post","link":"https:\/\/seanxd.com\/zh\/zerojudge-m933\/","title":{"rendered":"ZeroJudge M933: \u908f\u8f2f\u96fb\u8def"},"content":{"rendered":"\n\n\n<p class=\"\">\u8acb\u8a2d\u8a08\u4e00\u500b\u7a0b\u5f0f\uff0c\u6a21\u64ec\u4e00\u500b\u57fa\u672c\u7684\u908f\u8f2f\u96fb\u8def\u7cfb\u7d71\u3002\u9019\u500b\u96fb\u8def\u7cfb\u7d71\u7531\u6578\u500b\u8f38\u5165\u7aef\u53e3\u3001\u908f\u8f2f\u9598\u548c\u8f38\u51fa\u7aef\u53e3\u7d44\u6210\uff0c\u60a8\u9700\u8981\u6a21\u64ec\u96fb\u8def\u4e2d\u7684\u8a0a\u865f\u50b3\u905e\u8207\u9598\u7684\u904b\u7b97\u6c42\u51fa\u6240\u6709\u8f38\u51fa\u7aef\u53e3\u7684\u6578\u503c\uff0c\u4e26\u8a08\u7b97\u6574\u500b\u96fb\u8def\u7684\u6700\u5927\u5ef6\u9072\u6642\u9593\u3002<\/p>\n\n\n\n<p class=\"\">\u96fb\u8def\u5305\u542b\u4ee5\u4e0b\u5143\u4ef6\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>\u8f38\u5165\u7aef\u53e3 (Input Ports)<\/strong>\uff1a \u60a8\u5c07\u63a5\u6536\u5e7e\u500b\u4e8c\u9032\u5236\u8a0a\u865f\uff0c\u6bcf\u500b\u8a0a\u865f\u7684\u503c\u70ba 0 \u6216 1\u3002\u9019\u4e9b\u8a0a\u865f\u5c07\u7528\u4f5c\u96fb\u8def\u7684\u8f38\u5165\u3002\u96fb\u8def\u5167\u5171\u6709 P \u500b\u8f38\u5165\u7aef\u53e3\uff0c\u7de8\u865f\u70ba 1 \u5230 P\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u908f\u8f2f\u9598 (Logic Gates\uff09<\/strong>\uff1a \u6709\u56db\u7a2e\u985e\u578b\u7684\u908f\u8f2f\u9598\uff0c\u5206\u5225\u70ba \u300cAND\u3001OR\u3001XOR \u548c NOT \u9598\u300d\u3002\u9019\u4e9b\u9598\u63a5\u6536\u8f38\u5165\u8a0a\u865f\uff0c\u4e26\u6839\u64da\u5176\u529f\u80fd\u9032\u884c\u904b\u7b97\u3002\u96fb\u8def\u5167\u5171\u6709 Q \u500b\u908f\u8f2f\u9598\uff0c\u7de8\u865f\u70ba P+1 \u5230 P+Q\u3002\u5404\u7a2e\u908f\u8f2f\u9598\u7684\u904b\u7b97\u898f\u5247\u5982\u4e0b\uff1a\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>AND \u9598 (AND Gate\uff09<\/strong>\uff1a&nbsp;\u63a5\u6536\u5169\u500b\u8f38\u5165\uff0c\u5982\u679c\u5169\u500b\u8f38\u5165\u7686\u70ba 1\uff0c\u5247\u8f38\u51fa\u70ba 1\uff1b\u5426\u5247\u8f38\u51fa\u70ba 0\u3002<\/li>\n\n\n\n<li class=\"\"><strong>OR \u9598 (OR Gate\uff09<\/strong>\uff1a \u63a5\u6536\u5169\u500b\u8f38\u5165\uff0c\u5982\u679c\u81f3\u5c11\u6709\u4e00\u500b\u8f38\u5165\u70ba 1\uff0c\u5247\u8f38\u51fa\u70ba 1\uff1b\u5982\u679c\u5169\u500b\u8f38\u5165\u7686\u70ba 0\uff0c\u5247\u8f38\u51fa\u70ba 0\u3002<\/li>\n\n\n\n<li class=\"\"><strong>XOR \u9598 (XOR Gate\uff09<\/strong>\uff1a \u63a5\u6536\u5169\u500b\u8f38\u5165\uff0c\u5982\u679c\u5169\u500b\u8f38\u5165\u4e0d\u76f8\u540c\uff0c\u5247\u8f38\u51fa\u70ba 1\uff1b\u5982\u679c\u5169\u500b\u8f38\u5165\u76f8\u540c\uff0c\u5247\u8f38\u51fa\u70ba 0\u3002<\/li>\n\n\n\n<li class=\"\"><strong>NOT \u9598 (NOT Gate\uff09<\/strong>\uff1a \u50c5\u63a5\u6536\u4e00\u500b\u8f38\u5165\uff0c\u4e26\u5c07\u5176\u53cd\u8f49\u3002\u5982\u679c\u8f38\u5165\u70ba 1\uff0c\u5247\u8f38\u51fa\u70ba 0\uff1b\u5982\u679c\u8f38\u5165\u70ba 0\uff0c\u5247\u8f38\u51fa\u70ba 1\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u8f38\u51fa\u7aef\u53e3 (Output Ports\uff09<\/strong>\uff1a \u6700\u7d42\u7d50\u679c\u5c07\u6703\u5f9e\u9019\u4e9b\u7aef\u53e3\u8f38\u51fa\uff0c\u6bcf\u500b\u7aef\u53e3\u5c0d\u61c9\u8457\u67d0\u4e9b\u9598\u7684\u8f38\u51fa\u503c\u3002\u96fb\u8def\u5167\u5171\u6709 R \u500b\u8f38\u51fa\u7aef\u53e3\uff0c\u7de8\u865f\u70ba P+Q+1 \u5230 P+Q+R\u3002<\/li>\n<\/ul>\n\n\n\n<p class=\"\">\u8acb\u6a21\u64ec\u9019\u500b\u96fb\u8def\u7cfb\u7d71\uff0c\u78ba\u5b9a\u6bcf\u500b\u9598\u7684\u8f38\u51fa\u503c\uff0c\u4ee5\u53ca\u8a08\u7b97\u6574\u500b\u96fb\u8def\u7684\u6700\u5927\u5ef6\u9072\u6642\u9593\uff0c\u6700\u5927\u5ef6\u9072\u6642\u9593\u5373\u8a0a\u865f\u5f9e\u8f38\u5165\u7aef\u53e3\u50b3\u905e\u5230\u8f38\u51fa\u7aef\u53e3\u53ef\u80fd\u7d93\u904e\u6700\u591a\u908f\u8f2f\u9598\u7684\u6578\u91cf\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n<figure class=\"wp-block-table nfd-wb-animate nfd-wb-fade-in-bottom-short\"><table class=\"has-fixed-layout\"><thead><tr><th>\u7bc4\u4f8b\u8f38\u5165<\/th><th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead><tbody><tr><td>\u7b2c\u4e00\u884c\u5305\u542b\u56db\u500b\u6574\u6578\uff0c\u4f9d\u5e8f\u70ba <strong>P\u3001Q\u3001R\u3001M<\/strong>\u3002P (1 &lt;= P &lt;= 10<sup>3<\/sup>) \u4ee3\u8868\u8f38\u5165\u7aef\u53e3\u7684\u6578\u91cf\uff1bQ (1 &lt;= Q &lt;= 5\uff0a10<sup>4<\/sup>) \u4ee3\u8868\u908f\u8f2f\u9598\u7684\u6578\u91cf\uff1bR (1 &lt;= R &lt;= 10<sup>3<\/sup>) \u4ee3\u8868\u8f38\u51fa\u7aef\u53e3\u7684\u6578\u91cf\uff1bM \u4ee3\u8868\u9023\u63a5\u7dda\u7684\u6578\u91cf\u3002<br><br>\u63a5\u4e0b\u4f86\u4e00\u884c\u6709 P \u500b\u6574\u6578 v<sub>1<\/sub>, v<sub>2<\/sub>, &#8230;, v<sub>P<\/sub>\uff0c\u4ee3\u8868\u7de8\u865f\u70ba 1 \u5230 P \u8f38\u5165\u7aef\u53e3\u7684\u4e8c\u9032\u5236\u503c\uff080 \u6216 1\uff09\u3002<br><br>\u63a5\u4e0b\u4f86\u4e00\u884c\u6709 Q \u500b\u6574\u6578 t<sub>1<\/sub>, t<sub>2<\/sub>, &#8230;, t<sub>Q<\/sub>\uff0c\u4ee3\u8868\u7de8\u865f\u70ba P+1 \u5230 P+Q\u7684\u908f\u8f2f\u9598\u7684\u985e\u578b (1 \u70ba AND\u30012 \u70ba OR\u30013 \u70ba XOR\u30014 \u70ba NOT\uff09\u3002<br><br>\u6700\u5f8c\u7684 M \u884c\uff0c\u6bcf\u884c\u5305\u542b\u5169\u500b\u6574\u6578\uff0c\u4ee3\u8868\u9023\u63a5\u7dda\u7684\u8d77\u59cb\u7aef\u53e3\u548c\u7d42\u7aef\u7aef\u53e3\u7684\u7de8\u865f\u3002<br><br>\u6bcf\u500b\u8f38\u5165\u7aef\u53e3\u548c\u908f\u8f2f\u9598\u7684\u8f38\u51fa\u6703\u9023\u5230\u81f3\u5c11 1 \u500b\u81f3\u591a 20 \u500b\u5176\u4ed6\u908f\u8f2f\u9598\u548c\u8f38\u51fa\u7aef\u53e3\u7684\u8f38\u5165\uff0c\u4e14\u908f\u8f2f\u9598\u96fb\u8def\u4e0d\u6703\u63a5\u51fa\u8ff4\u8def\u3002<\/td><td>\u7b2c\u4e00\u884c\u8f38\u51fa\u4e00\u500b\u6574\u6578\uff0c\u8868\u793a\u8a08\u7b97\u51fa\u7684\u7279\u5b9a\u7aef\u53e3\u7684\u6700\u5927\u5ef6\u9072\u6642\u9593\uff0c\u6e2c\u8a66\u8cc7\u6599\u4fdd\u8b49\u6700\u5927\u5ef6\u9072\u4e0d\u9ad8\u904e 100\u3002<br>\u7b2c\u4e8c\u884c\u8f38\u51fa R \u500b\u4e8c\u9032\u5236\u503c\uff080 \u6216 1\uff09\uff0c\u4ee3\u8868\u6bcf\u4e00\u500b\u8f38\u51fa\u9598\u7de8\u865f\u7531\u5c0f\u5230\u5927\u7684\u8f38\u51fa\u6578\u503c\u3002<\/td><\/tr><tr><td><strong>4  5  4  13<\/strong><br>1  0  1  0<br>1  2  3  4  1<br>1  5<br>2  5<br>2  6<br>3  6<br>3  7<br>4  7<br>4  8<br>5  10<br>6  9 <br>6  11<br>7  9<br>8  13<br>9  12<\/td><td>2<br>0  1  1  1<\/td><\/tr><tr><td><strong>5  6  4  15<\/strong><br>1  1  0  1  0<br>2  1  3  4  1  3<br>1  6<br>2  7<br>7  13<br>7  6<br>3  7<br>3  8<br>4  8<br>5  9<br>8  10<br>9  10<br>10  14<br>10  11<br>9  11<br>6  12<br>11  15<\/td><td>3<br>1  0  1  0<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\">ZeroJudge M933 \u6e2c\u8cc7<\/figcaption><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">\u6e2c\u8cc7\u89e3\u91cb<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">\u7bc4\u4f8b 1 \u89e3\u91cb\u5716\uff1a<\/h4>\n\n\n\n<figure class=\"wp-block-image size-large is-resized nfd-wb-animate nfd-wb-zoom-in-short nfd-delay-50\"><img decoding=\"async\" width=\"1024\" height=\"522\" loading=\"lazy\" src=\"https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-ShowImage-1024x522.png\" alt=\"ZeroJudge M933: \u908f\u8f2f\u96fb\u8def\n\u7bc4\u4f8b\u6e2c\u8cc71\u89e3\u91cb\u5716\" class=\"wp-image-162\" style=\"width:645px;height:auto\" srcset=\"https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-ShowImage-1024x522.png 1024w, https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-ShowImage-300x153.png 300w, https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-ShowImage-768x391.png 768w, https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-ShowImage-1536x783.png 1536w, https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-ShowImage-2048x1044.png 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\">\u7bc4\u4f8b 2 \u89e3\u91cb\u5716\uff1a<\/h4>\n\n\n\n<figure class=\"wp-block-image size-large is-resized nfd-wb-animate nfd-wb-zoom-in-short nfd-delay-150\"><img decoding=\"async\" width=\"1024\" height=\"679\" loading=\"lazy\" src=\"https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-Image-1024x679.png\" alt=\"ZeroJudge M933: \u908f\u8f2f\u96fb\u8def\n\u7bc4\u4f8b\u6e2c\u8cc72\u89e3\u91cb\u5716\" class=\"wp-image-163\" style=\"width:645px;height:auto\" srcset=\"https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-Image-1024x679.png 1024w, https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-Image-300x199.png 300w, https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-Image-768x510.png 768w, https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-Image-1536x1019.png 1536w, https:\/\/seanxd.com\/wp-content\/uploads\/2024\/04\/Logic-Circuit-Image.png 1694w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n<p class=\"\">\u53ef\u4ee5\u4f7f\u7528\u4e00\u500b <strong>Struct<\/strong> \u4f86<strong>\u5b58\u53d6\u6bcf\u4e00\u500b\u7aef\u9ede\/\u908f\u8f2f\u7aef\u7684\u6578\u503c<\/strong>\uff0c\u5c07\u8cc7\u6599\u90fd\u6536\u5230 <strong>Struct<\/strong> \u4e2d\u4e4b\u5f8c\uff0c\u4f7f\u7528 <strong>BFS<\/strong> \u5148\u8dd1\u8f38\u5165\u7aef\u9ede\uff0c\u5c07\u8f38\u5165\u7aef\u9ede\u7684\u7d42\u9ede\u503c\u7684\u8d77\u9ede\u503c\u5b58\u6210\u76ee\u524d\u7684\u6578\u5b57\u3002\u7d93\u904e\u5224\u65b7\u5df2\u7d93\u53ef\u4ee5\u505a\u908f\u8f2f\u7aef\u7684\u904b\u7b97\u5f8c\u5c31\u53ef\u4ee5\u5c07\u904b\u7b97\u904e\u5f8c\u7684\u503c\u653e\u5230 <strong>Struct<\/strong> \u4e2d\u5b58\u8f38\u51fa\u503c\u7684\u8b8a\u6578\u3002\u5ef6\u9072\u7684\u90e8\u5206\u53ea\u9700\u5224\u65b7\u8dd1\u4e86\u5e7e\u6b21\u7684 <strong>BFS<\/strong> \u518d -1 \u5373\u53ef\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0d<a href=\"https:\/\/zerojudge.tw\/ShowProblem?problemid=m933\" target=\"_blank\" rel=\"noreferrer noopener\">ZeroJudge M933: \u908f\u8f2f\u96fb\u8def<\/a><\/h3>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism line-numbers lang-cpp\" data-lang=\"C++\"><code>#include &lt;iostream&gt;\n#include &lt;vector&gt;\nusing namespace std;\n\nstruct node\n{\n    vector&lt;int&gt;from;\n    vector&lt;int&gt;to;\n    int output = -1;\n    int delay = 0;\n    int gate = -1;\n};\n\nint delay = 0;\nvector&lt;node&gt;vec;\n\nvoid BFS(vector&lt;int&gt;start)\n{\n    if (start.size() == 0) return;\n    delay++;\n    vector&lt;int&gt;newStart;\n    for (int i = 0; i&lt;start.size(); i++)\n    {\n        node vv = vec[start[i]];\n        for (int j = 0; j&lt;vv.to.size(); j++)\n        {\n            int to = vv.to[j];\n            vec[to].from.push_back(start[i]);\n            if ((vec[to].gate == 4 && vec[to].from.size() == 1) || (vec[to].from.size() == 2))\n            {\n                newStart.push_back(to);\n                node point = vec[to];\n                int gate = vec[to].gate;\n                if (gate == 1)\n                {\n                    if (vec[point.from[0]].output == 1 && vec[point.from[1]].output == 1)\n                    {\n                        vec[to].output = 1;\n                    }\n                    else vec[to].output = 0;\n                }\n                else if (gate == 2)\n                {\n                    if (vec[point.from[0]].output == 1 || vec[point.from[1]].output == 1)\n                    {\n                        vec[to].output = 1;\n                    }\n                    else vec[to].output = 0;\n                }\n                else if (gate == 3)\n                {\n                    if (vec[point.from[0]].output != vec[point.from[1]].output) vec[to].output = 1;\n                    else vec[to].output = 0;\n                }\n                else\n                {\n                    if (vec[point.from[0]].output == 0) vec[to].output = 1;\n                    else vec[to].output = 0;\n                }\n            }\n        }\n    }\n    BFS(newStart);\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    int in, out, logic, line;\n    cin &gt;&gt; in &gt;&gt; logic &gt;&gt; out &gt;&gt; line;\n    vector&lt;int&gt;start;\n    for (int i = 0; i&lt;in+out+logic; i++)\n    {\n        node tmp;\n        vec.push_back(tmp);\n    }\n    for (int i = 0; i&lt;in; i++)\n    {\n        int tmp;\n        cin &gt;&gt; tmp;\n        vec[i].output = tmp;\n        start.push_back(i);\n    }\n    for (int i = in; i&lt;in+logic; i++)\n    {\n        int tmp;\n        cin &gt;&gt; tmp;\n        vec[i].gate = tmp;\n    }\n    for (int i = 0; i&lt;line; i++)\n    {\n        int a, b;\n        cin &gt;&gt; a &gt;&gt; b;\n        vec[a-1].to.push_back(b-1);\n    }\n    BFS(start);\n    cout &lt;&lt; delay-1 &lt;&lt; endl;\n    for (int i = in+logic; i&lt;in+logic+out; i++)\n    {\n        cout &lt;&lt; vec[vec[i].from[0]].output &lt;&lt; &quot; &quot;;\n    }\n    cout &lt;&lt; &quot;\\n&quot;;\n}\n\n\/\/ZeroJudge M933\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u8acb\u8a2d\u8a08\u4e00\u500b\u7a0b\u5f0f\uff0c\u6a21\u64ec\u4e00\u500b\u57fa\u672c\u7684\u908f\u8f2f\u96fb\u8def\u7cfb\u7d71\u3002\u9019\u500b\u96fb\u8def\u7cfb\u7d71\u7531\u6578\u500b\u8f38\u5165\u7aef\u53e3\u3001\u908f\u8f2f\u9598\u548c\u8f38\u51fa\u7aef\u53e3\u7d44\u6210\uff0c\u60a8\u9700\u8981\u6a21\u64ec\u96fb\u8def\u4e2d [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[25],"tags":[30,27,20,8,9],"class_list":["post-161","post","type-post","status-publish","format-standard","hentry","category-ioi-apcs","tag-bfs","tag-struct","tag-20","tag-8","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/161","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/comments?post=161"}],"version-history":[{"count":5,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/161\/revisions"}],"predecessor-version":[{"id":171,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/161\/revisions\/171"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/media?parent=161"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/categories?post=161"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/tags?post=161"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}