{"id":2586,"date":"2025-01-10T22:37:31","date_gmt":"2025-01-10T14:37:31","guid":{"rendered":"https:\/\/guapicoding.com\/?p=2586"},"modified":"2025-03-11T11:12:08","modified_gmt":"2025-03-11T03:12:08","slug":"%e7%ac%94%e8%af%95%e9%a2%98%e8%ae%b0%ef%bc%9a24%e5%b9%b4%e8%85%be%e8%ae%af%e9%9f%b3%e4%b9%90%e6%98%a5%e6%8b%9b","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=2586","title":{"rendered":"\u7b14\u8bd5\u9898\u8bb0\uff1a24\u5e74\u817e\u8baf\u97f3\u4e50\u6625\u62db"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1287\" target=\"_blank\" rel=\"noreferrer noopener\">208.\u5c0f\u7ea2\u7684\u4e8c\u53c9\u6811\u6784\u9020<\/a>\u2705<\/h2>\n\n\n\n<p><em><strong>\u7b80\u5355\u6570\u5b66\u9898<\/strong><\/em><strong><em>\uff1a<\/em>\u6bcf\u4e00\u5c42\u7684\u503c\u662f\u76f8\u540c\u7684\uff0c\u6700\u5c0f\u5c42\u503c\u7531\u8282\u70b9\u6700\u591a\u7684\u6700\u540e\u4e00\u884c\u51b3\u5b9a\uff0c\u5373\u5168\u88ab1\u586b\u5145\uff0c\u518d\u4e58\u4ee5\u5c42\u6570\u5373\u53ef<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h>\nusing namespace std;\nint main() {\n    int n;\n    cin >> n;\n    cout &lt;&lt; pow(2, n - 1) * n &lt;&lt; endl; \n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u203b<a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1289\" target=\"_blank\" rel=\"noreferrer noopener\">209.\u5c0f\u7ea2\u7684\u8282\u70b9\u67d3\u8272<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>\u6c42\u65b9\u6848\u6570\uff0c\u60f3\u5230\u56de\u6eaf\u641c\u7d22<\/em>\uff0c\u4f46\u662f\u8d85\u65f6\u4e86<\/strong><\/p>\n\n\n\n<p><strong><em>\u4e00\u822c\u56de\u6eaf\u6df1\u641c\u8d85\u65f6\u7684\uff0c\u7528DP\u89e3\u51b3<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u52a8\u6001\u89c4\u5212\u4e4b\u72b6\u6001\u673a<\/strong><\/em><strong><em>\uff1a<\/em>\u5b9a\u4e49dp[i][0\/1]\u4e3a\u524di\u4e2a\u672a\u67d3\u8272\u7684\u8282\u70b9\u7684\u80fd\u51d1\u6210\u548c\u4e3a\u5076\u6570\/\u5947\u6570\u7684\u65b9\u6848\u6570<\/strong><\/p>\n\n\n\n<p><strong>\u72b6\u6001\u8f6c\u79fb\u516c\u5f0f\uff1a<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>dp[i][0] = <\/strong>\n<ul class=\"wp-block-list\">\n<li><span><strong>dp[i-1][0] * 2 + 1<\/strong><\/span>\uff08\u5982\u679c\u7b2ci\u4e2a\u8282\u70b9\u6743\u503c\u4e3a\u5076\u6570\uff09<\/li>\n\n\n\n<li><strong><strong>dp[i-1][0]<\/strong> + <strong><strong>dp[i-1][1]<\/strong><\/strong><\/strong>\uff08\u5982\u679c\u7b2ci\u4e2a\u8282\u70b9\u6743\u503c\u4e3a\u5947\u6570<strong>\uff09<\/strong><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>dp[i][1] = <\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>dp[i-1][1]<span> * 2<\/span><\/strong>\uff08\u5982\u679c\u7b2ci\u4e2a\u8282\u70b9\u6743\u503c\u4e3a\u5076\u6570\uff09<\/li>\n\n\n\n<li><strong><strong>dp[i-1][0]<\/strong> + <strong><strong>dp[i-1][1] + 1<\/strong><\/strong><\/strong>\uff08\u5982\u679c\u7b2ci\u4e2a\u8282\u70b9\u6743\u503c\u4e3a\u5947\u6570\uff09<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p><strong>\u5bf9\u4e8e\u4e0a\u9762\u56db\u4e2a\u65b9\u7a0b\u7684\u89e3\u91ca\uff1a<\/strong>(\u5149\u60f3\u660e\u767d\u72b6\u6001\u8f6c\u79fb\u516c\u5f0f\u60f3\u4e86\u4e00\u4e2a\u5c0f\u65f6)<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u7b2ci\u4e2a\u8282\u70b9\u6743\u503c\u4e3a\u5076\u6570\uff0c\u610f\u5473\u7740\uff1a\n<ul class=\"wp-block-list\">\n<li><strong>\u9009\u62e9\u67d3\u8272\uff0c\u52a0\u5230\u5076\u6570\u548c\u65b9\u6848<\/strong>\uff08<code>dp[i-1][0]<\/code>\uff09\uff0c\u4f1a\u53d8\u6210\u5076\u6570\u548c\u65b9\u6848\uff1b<\/li>\n\n\n\n<li><strong>\u9009\u62e9\u4e0d\u67d3\u8272\uff0c\u7ee7\u627f\u4e0a\u4e00\u4e2a\u5076\u6570\u548c\u65b9\u6848<\/strong>\uff08<code>dp[i-1][0]<\/code>\uff09\uff0c\u4f9d\u7136\u662f\u5076\u6570\u548c\u65b9\u6848\uff1b<\/li>\n\n\n\n<li><strong>\u8fd8\u53ef\u4ee5\u9009\u62e9\u5355\u72ec\u8fd9\u4e2a\u8282\u70b9\u5f00\u4e00\u4e2a\u65b9\u6848<\/strong>\uff0c\u4e5f\u662f\u5076\u6570\u548c\u65b9\u6848\uff0c\u6240\u4ee5 <code>+1<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u7b2ci\u4e2a\u8282\u70b9\u6743\u503c\u4e3a\u5947\u6570\uff0c\u610f\u5473\u7740\uff1a\n<ul class=\"wp-block-list\">\n<li><strong>\u9009\u62e9\u67d3\u8272\uff0c\u52a0\u5230\u5947\u6570\u548c\u65b9\u6848<\/strong>\uff08<code>dp[i-1][1]<\/code>\uff09\uff0c\u4f1a\u53d8\u6210\u5076\u6570\u548c\u65b9\u6848\uff1b<\/li>\n\n\n\n<li><strong>\u9009\u62e9\u4e0d\u67d3\u8272\uff0c\u7ee7\u627f\u4e0a\u4e00\u4e2a\u5076\u6570\u548c\u65b9\u6848<\/strong>\uff08<code>dp[i-1][0]<\/code>\uff09\uff0c\u4f9d\u7136\u662f\u5076\u6570\u548c\u65b9\u6848\uff1b<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u7b2ci\u4e2a\u8282\u70b9\u6743\u503c\u4e3a\u5076\u6570\uff0c\u610f\u5473\u7740\uff1a\n<ul class=\"wp-block-list\">\n<li><strong>\u9009\u62e9\u67d3\u8272\uff0c\u52a0\u5230\u5947\u6570\u548c\u65b9\u6848<\/strong>\uff08<code>dp[i-1][1]<\/code>\uff09\uff0c\u4f1a\u53d8\u6210\u5947\u6570\u548c\u65b9\u6848\uff1b<\/li>\n\n\n\n<li><strong>\u9009\u62e9\u4e0d\u67d3\u8272\uff0c\u7ee7\u627f\u4e0a\u4e00\u4e2a\u5947\u6570\u548c\u65b9\u6848<\/strong>\uff08<code>dp[i-1][1]<\/code>\uff09\uff0c\u4f9d\u7136\u662f\u5947\u6570\u548c\u65b9\u6848\uff1b<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u7b2ci\u4e2a\u8282\u70b9\u6743\u503c\u4e3a\u5947\u6570\uff0c\u610f\u5473\u7740\uff1a\n<ul class=\"wp-block-list\">\n<li><strong>\u9009\u62e9\u67d3\u8272\uff0c\u52a0\u5230\u5076\u6570\u548c\u65b9\u6848<\/strong>\uff08<code>dp[i-1][0]<\/code>\uff09\uff0c\u4f1a\u53d8\u6210\u5947\u6570\u548c\u65b9\u6848\uff1b<\/li>\n\n\n\n<li><strong>\u9009\u62e9\u4e0d\u67d3\u8272\uff0c\u7ee7\u627f\u4e0a\u4e00\u4e2a\u5947\u6570\u548c\u65b9\u6848<\/strong>\uff08<code>dp[i-1][1]<\/code>\uff09\uff0c\u4f9d\u7136\u662f\u5947\u6570\u548c\u65b9\u6848\uff1b<\/li>\n\n\n\n<li><strong>\u8fd8\u53ef\u4ee5\u9009\u62e9\u5355\u72ec\u8fd9\u4e2a\u8282\u70b9\u5f00\u4e00\u4e2a\u65b9\u6848<\/strong>\uff0c\u4e5f\u662f\u5947\u6570\u548c\u65b9\u6848\uff0c\u6240\u4ee5 <code>+1<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h>\nusing namespace std;\nconst int MOD = 1000000007; \nint main() {\n    string str;\n    cin >> str;\n    int i = 1;\n    vector&lt;int> val;\n    vector&lt;int> tmp;\n    for(; i &lt; str.size(); i++) {\n        tmp.push_back(str&#91;i] - '0');\n        i++;\n        if(str&#91;i] == ']') break;\n    }\n    i += 3;\n    \n    int k = 0, basic = 0, white = 0;\n    val.push_back(0); \/\/ \u4e3a\u4e86\u5faa\u73afdp\u65f6\u5bf9\u9f50\u4e0b\u6807\n    for(; i &lt; str.size() - 1; i++) {\n        if(str&#91;i] == 'R') basic += tmp&#91;k];\n        else {\n            val.push_back(tmp&#91;k]);\n            white = 1; \/\/ \u8868\u660e\u6709\u672a\u67d3\u8272\u7684\u8282\u70b9\n        }\n        k++;\n    }\n\n    \/\/ \u5b9a\u4e49dp&#91;i]&#91;0\/1]\u4e3a\u524di\u4e2a\u672a\u67d3\u8272\u7684\u8282\u70b9\u7684\u80fd\u51d1\u6210\u548c\u4e3a\u5076\u6570\/\u5947\u6570\u7684\u65b9\u6848\u6570\n    vector&lt;vector&lt;int>> dp(val.size(), vector&lt;int>(2, 0));\n    \/\/ cout &lt;&lt; \"dp&#91;0]&#91;0] = \" &lt;&lt; dp&#91;0]&#91;0] &lt;&lt; \", \";\n    \/\/ cout &lt;&lt; \"dp&#91;0]&#91;1] = \" &lt;&lt; dp&#91;0]&#91;1] &lt;&lt; endl;\n    for(int i = 1; i &lt; val.size(); i++) {\n        if(val&#91;i] % 2) { \n            dp&#91;i]&#91;0] = (dp&#91;i-1]&#91;0] + dp&#91;i-1]&#91;1]) % MOD; \/\/ \u6ce8\u610f\u4e00\u76f4\u53d6\u4f59\uff0c\u9632\u6b62\u7206\u6570\n            dp&#91;i]&#91;1] = (dp&#91;i-1]&#91;0] + dp&#91;i-1]&#91;1] + 1) % MOD;\n        } else {\n            dp&#91;i]&#91;0] = (dp&#91;i-1]&#91;0] * 2 + 1) % MOD;\n            dp&#91;i]&#91;1] = (dp&#91;i-1]&#91;1] * 2) % MOD;\n        }\n        \/\/ cout &lt;&lt; \"dp&#91;\" &lt;&lt; i &lt;&lt; \"]&#91;0] = \" &lt;&lt; dp&#91;i]&#91;0] &lt;&lt; \", \";\n        \/\/ cout &lt;&lt; \"dp&#91;\" &lt;&lt; i &lt;&lt; \"]&#91;1] = \" &lt;&lt; dp&#91;i]&#91;1] &lt;&lt; endl;\n    }\n    \n    if(basic % 2) cout &lt;&lt; dp&#91;val.size()-1]&#91;1] % MOD &lt;&lt; endl;\n    else  cout &lt;&lt; (dp&#91;val.size()-1]&#91;0] + white) % MOD &lt;&lt; endl;\n \n    return 0;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1290\" target=\"_blank\" rel=\"noreferrer noopener\">210.\u6700\u957f\u5408\u6cd5\u5b50\u4e32\u957f\u5ea6<\/a>\u274c<\/h2>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>208.\u5c0f\u7ea2\u7684\u4e8c\u53c9\u6811\u6784\u9020\u2705 \u7b80\u5355\u6570\u5b66\u9898\uff1a\u6bcf\u4e00\u5c42\u7684\u503c\u662f\u76f8\u540c\u7684\uff0c\u6700\u5c0f\u5c42\u503c\u7531\u8282\u70b9\u6700\u591a\u7684\u6700\u540e\u4e00\u884c\u51b3\u5b9a\uff0c\u5373\u5168\u88ab1\u586b\u5145\uff0c\u518d [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[90,91,82,89],"class_list":["post-2586","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-90","tag-91","tag-82","tag-89"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2586","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2586"}],"version-history":[{"count":4,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2586\/revisions"}],"predecessor-version":[{"id":2604,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2586\/revisions\/2604"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2586"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2586"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2586"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}