{"id":568,"date":"2023-03-04T20:33:58","date_gmt":"2023-03-04T12:33:58","guid":{"rendered":"https:\/\/lolife.top\/?p=568"},"modified":"2023-03-04T20:37:55","modified_gmt":"2023-03-04T12:37:55","slug":"acwing-3777-%e7%a0%96%e5%9d%97","status":"publish","type":"post","link":"https:\/\/lolife.top\/?p=568","title":{"rendered":"AcWing 3777. \u7816\u5757"},"content":{"rendered":"\n

\u9898\u76ee<\/h3>\n\n\n\n

n\u4e2a\u7816\u5757\u6392\u6210\u4e00\u6392\uff0c\u4ece\u5de6\u5230\u53f3\u7f16\u53f7\u4f9d\u6b21\u4e3a 1\u223cn\u3002<\/p>\n\n\n\n

\u6bcf\u4e2a\u7816\u5757\u8981\u4e48\u662f\u9ed1\u8272\u7684\uff0c\u8981\u4e48\u662f\u767d\u8272\u7684\u3002<\/p>\n\n\n\n

\u73b0\u5728\u4f60\u53ef\u4ee5\u8fdb\u884c\u4ee5\u4e0b\u64cd\u4f5c\u82e5\u5e72\u6b21\uff08\u53ef\u4ee5\u662f 0 \u6b21\uff09\uff1a<\/p>\n\n\n\n

\u9009\u62e9\u4e24\u4e2a\u76f8\u90bb\u7684\u7816\u5757\uff0c\u53cd\u8f6c\u5b83\u4eec\u7684\u989c\u8272\u3002\uff08\u9ed1\u53d8\u767d\uff0c\u767d\u53d8\u9ed1\uff09<\/p>\n\n\n\n

\u4f60\u7684\u76ee\u6807\u662f\u901a\u8fc7\u4e0d\u8d85\u8fc7 3n \u6b21\u64cd\u4f5c\uff0c\u5c06\u6240\u6709\u7816\u5757\u7684\u989c\u8272\u53d8\u5f97\u4e00\u81f4\u3002<\/p>\n\n\n\n

\u8f93\u5165\u683c\u5f0f<\/strong><\/p>\n\n\n\n

\u7b2c\u4e00\u884c\u5305\u542b\u6574\u6570 T\uff0c\u8868\u793a\u5171\u6709 T\u7ec4\u6d4b\u8bd5\u6570\u636e\u3002<\/p>\n\n\n\n

\u6bcf\u7ec4\u6570\u636e\u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570 n\u3002<\/p>\n\n\n\n

\u7b2c\u4e8c\u884c\u5305\u542b\u4e00\u4e2a\u957f\u5ea6\u4e3a n \u7684\u5b57\u7b26\u4e32 s\u3002\u5176\u4e2d\u7684\u6bcf\u4e2a\u5b57\u7b26\u90fd\u662f W<\/code> \u6216 B<\/code>\uff0c\u5982\u679c\u7b2c i \u4e2a\u5b57\u7b26\u662f W<\/code>\uff0c\u5219\u8868\u793a\u7b2c i\u53f7\u7816\u5757\u662f\u767d\u8272\u7684\uff0c\u5982\u679c\u7b2c i\u4e2a\u5b57\u7b26\u662f B<\/code>\uff0c\u5219\u8868\u793a\u7b2c i\u4e2a\u7816\u5757\u662f\u9ed1\u8272\u7684\u3002<\/p>\n\n\n\n

\u8f93\u51fa\u683c\u5f0f<\/strong><\/p>\n\n\n\n

\u6bcf\u7ec4\u6570\u636e\uff0c\u5982\u679c\u65e0\u89e3\u5219\u8f93\u51fa\u4e00\u884c \u22121\u3002<\/p>\n\n\n\n

\u5426\u5219\uff0c\u9996\u5148\u8f93\u51fa\u4e00\u884c k\uff0c\u8868\u793a\u9700\u8981\u7684\u64cd\u4f5c\u6b21\u6570\u3002<\/p>\n\n\n\n

\u5982\u679c k>0\uff0c\u5219\u8fd8\u9700\u518d\u8f93\u51fa\u4e00\u884c k\u4e2a\u6574\u6570\uff0cp1<\/sub>,p2<\/sub>,\u2026,pk<\/sub>\u3002\u5176\u4e2d pi<\/sub>\u8868\u793a\u7b2c i \u6b21\u64cd\u4f5c\uff0c\u9009\u4e2d\u7684\u7816\u5757\u4e3a pi<\/sub>\u548c pi<\/sub>+1\u53f7\u7816\u5757\u3002<\/p>\n\n\n\n

\u5982\u679c\u65b9\u6848\u4e0d\u552f\u4e00\uff0c\u5219\u8f93\u51fa\u4efb\u610f\u5408\u7406\u65b9\u6848\u5373\u53ef\u3002<\/p>\n\n\n\n

\u6570\u636e\u8303\u56f4<\/strong><\/p>\n\n\n\n

1\u2264T\u226410\uff0c
2\u2264n\u226420\u3002<\/p>\n\n\n\n

\u8f93\u5165\u6837\u4f8b\uff1a<\/strong><\/p>\n\n\n\n

4\n8\nBWWWWWWB\n4\nBWBB\n5\nWWWWW\n3\nBWB<\/code><\/pre>\n\n\n\n
\u8f93\u51fa\u6837\u4f8b\uff1a<\/strong><\/p>\n\n\n\n
3\n6 2 4\n-1\n0\n2\n2 1<\/code><\/pre>\n\n\n\n
\u601d\u8def\uff1a<\/h3>\n\n\n\n
\u5bf9\u4e8e\u6700\u7ec8\u7684\u5b57\u7b26\u4e32\uff0c\u53ea\u6709\u4e24\u79cd\uff0c\u8981\u4e48\u5168\u4e3aW\uff0c\u8981\u4e48\u5168\u4e3aB\uff1b<\/p>\n\n\n\n
\u90a3\u4e48\uff0c\u53ef\u4ee5\u5bf9\u4e24\u79cd\u8f6c\u5316\u65b9\u6cd5\u5206\u522b\u6a21\u62df\uff0c\u4e00\u79cd\u4ee5\u76ee\u6807\u4e3a\u767d\u8272\u8fdb\u884c\u8f6c\u5316\uff0c\u4e00\u79cd\u4ee5\u76ee\u6807\u4e3a\u9ed1\u8272\u8fdb\u884c\u8f6c\u5316<\/p>\n\n\n\n
\u4ee5\u76ee\u6807\u4e3a\u767d\u8272\u4e3a\u4f8b\uff1a\u4ece\u524d\u5f80\u540e\u8fdb\u884c\u904d\u5386\u5b57\u7b26\u4e32\uff0c\u5982\u679cs[i]==\u2018B\u2019\uff0c\u5c31\u5bf9\u5f53\u524d\u4f4d\u7f6e\u8fdb\u884c\u64cd\u4f5c\uff0c\u5c06i\uff0ci+1\u7684\u989c\u8272\u53d8\u6210\u53e6\u4e00\u79cd\u989c\u8272\uff0c\u5982\u679c\u904d\u5386\u5b8c\uff0c\u5b57\u7b26\u4e32\u672b\u5c3e\u4e0d\u4e3a\u2018W\u2019\uff0c\u5219\u4e0d\u80fd\u5b8c\u5168\u8f6c\u5316\u4e3a\u767d\u8272\u3002\u76ee\u6807\u4e3a\u9ed1\u8272\u540c\u7406\u3002\u5982\u679c\u65e2\u4e0d\u80fd\u8f6c\u5316\u4e3a\u5b8c\u5168\u8f6c\u5316\u4e3a\u9ed1\u8272\uff0c\u4e5f\u4e0d\u80fd\u5b8c\u5168\u8f6c\u5316\u4e3a\u767d\u8272\uff0c\u5219\u8f93\u51fa-1\uff1b<\/p>\n\n\n\n
\u4ee3\u7801\uff1a<\/h3>\n\n\n\n
#include<iostream>\n#include<string>\n#include<vector>\nusing namespace std;\nstring s;\nint t, n;\nint main()\n{\n\tcin >> t;\n\twhile (t--)\n\t{\n\t\tint op1 = 0, op2 = 0;\n\t\tcin >> n;\n\t\tcin >> s;\n\t\tstring strw = s, strb = s;\n\t\tvector<int>w, b;\n\t\tfor (int i = 0; i < n - 1; i++)\n\t\t{\n\t\t\t\/\/\u5168\u90e8\u53d8\u6210W\n\t\t\tif (strw[i] == 'B')\n\t\t\t{\n\t\t\t\tstrw[i] = 'W';\n\t\t\t\tif (strw[i + 1] == 'W')strw[i + 1] = 'B';\n\t\t\t\telse strw[i + 1] = 'W';\n\t\t\t\tw.push_back(i + 1);\n\t\t\t\top1++;\n\t\t\t}\n\t\t\t\/\/\u5168\u90e8\u53d8\u6210B\n\t\t\tif (strb[i] == 'W')\n\t\t\t{\n\t\t\t\tstrb[i] = 'B';\n\t\t\t\tif (strb[i + 1] == 'W')strb[i + 1] = 'B';\n\t\t\t\telse strb[i + 1] = 'W';\n\t\t\t\tb.push_back(i + 1);\n\t\t\t\top2++;\n\t\t\t}\n\t\t}\n\t\tif (strw[n - 1] != 'W' && strb[n - 1] != 'B')cout << -1 << endl;\n\t\telse if (strw[n - 1] == 'W')\n\t\t{\n\t\t\tcout << op1 << endl;\n\t\t\tfor (int op : w)\n\t\t\t{\n\t\t\t\tcout << op << \" \";\n\t\t\t}\n\t\t\tif(op1)cout << endl;\n\t\t}\n\t\telse if (strb[n - 1] == 'B')\n\t\t{\n\t\t\tcout << op2 << endl;\n\t\t\tfor (int op : b)\n\t\t\t{\n\t\t\t\tcout << op << \" \";\n\t\t\t}\n\t\t\tif(op2)cout << endl;\n\t\t}\n\t}\n}<\/code><\/pre>\n\n\n\n
<\/p>\n\n\n\n
\u4e5f\u53ef\u4ee5\u5bf9W\u4e0eB\u7684\u4e2a\u6570\u7684\u5947\u5076\u6027\u8fdb\u884c\u5224\u65ad\uff1a<\/p>\n\n\n\n
1.\u5982\u679c\u4e2a\u6570\u90fd\u662f\u5947\u6570\u6b21\uff0c\u5219\u4e0d\u53ef\u80fd\u6784\u9020\u51fa\u6765<\/p>\n\n\n\n
2.\u5982\u679cW\u662f\u5947\u6570\u4e2a\u3002\u90a3\u5c31\u8f6c\u5316\u4e3aW<\/p>\n\n\n\n
3.\u5982\u679cB\u662f\u5947\u6570\u4e2a\uff0c\u6216\u8005B\u548cW\u90fd\u662f\u5076\u6570\u4e2a\u3002\u90a3\u5c31\u8f6c\u5316\u4e3aB
<\/p>\n\n\n\n
\u4ee3\u7801\u5927\u540c\u5c0f\u5f02\uff0c\u5c31\u4e0d\u518d\u5199\u4e86<\/p>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee n\u4e2a\u7816\u5757\u6392\u6210\u4e00\u6392\uff0c\u4ece\u5de6\u5230\u53f3\u7f16\u53f7\u4f9d\u6b21\u4e3a 1\u223cn\u3002 \u6bcf\u4e2a\u7816\u5757\u8981\u4e48\u662f\u9ed1\u8272\u7684\uff0c\u8981\u4e48\u662f\u767d\u8272\u7684\u3002 \u73b0\u5728\u4f60\u53ef […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[20],"tags":[19],"class_list":["post-568","post","type-post","status-publish","format-standard","hentry","category-20","tag-19"],"_links":{"self":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/568","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=568"}],"version-history":[{"count":3,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/568\/revisions"}],"predecessor-version":[{"id":572,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/568\/revisions\/572"}],"wp:attachment":[{"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=568"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=568"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=568"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}