{"id":62,"date":"2025-08-14T03:08:21","date_gmt":"2025-08-13T19:08:21","guid":{"rendered":"http:\/\/thebugmuxi.xyz\/?p=62"},"modified":"2025-08-14T03:12:24","modified_gmt":"2025-08-13T19:12:24","slug":"%e9%a2%98%e7%9b%ae-3185-%e8%93%9d%e6%a1%a5%e6%9d%af2023%e5%b9%b4%e7%ac%ac%e5%8d%81%e5%9b%9b%e5%b1%8a%e7%9c%81%e8%b5%9b%e7%9c%9f%e9%a2%98-t%e5%ad%97%e6%b6%88%e9%99%a4-%e8%a7%a3%e9%a2%98%e6%80%9d","status":"publish","type":"post","link":"https:\/\/www.thebugmuxi.xyz\/index.php\/2025\/08\/14\/%e9%a2%98%e7%9b%ae-3185-%e8%93%9d%e6%a1%a5%e6%9d%af2023%e5%b9%b4%e7%ac%ac%e5%8d%81%e5%9b%9b%e5%b1%8a%e7%9c%81%e8%b5%9b%e7%9c%9f%e9%a2%98-t%e5%ad%97%e6%b6%88%e9%99%a4-%e8%a7%a3%e9%a2%98%e6%80%9d\/","title":{"rendered":"\u9898\u76ee 3185:\u00a0\u84dd\u6865\u676f2023\u5e74\u7b2c\u5341\u56db\u5c4a\u7814\u7a76\u751f\u7ec4\u7701\u8d5b\u771f\u9898-T\u5b57\u6d88\u9664 \u89e3\u9898\u601d\u8def\uff0b\u7b54\u6848"},"content":{"rendered":"\n

<\/h1>\n\n\n\n

\u9898\u76ee\u63cf\u8ff0<\/h2>\n\n\n\n

\u5c0f\u84dd\u6b63\u5728\u73a9\u4e00\u6b3e\u6e38\u620f\uff0c\u6e38\u620f\u4e2d\u6709\u4e00\u4e2an \u00d7 n\u5927\u5c0f\u7684 01 \u77e9\u9635 Ai, j<\/sub>\u00a0\u3002\u5c0f\u84dd\u6bcf\u6b21\u9700\u8981\u9009\u62e9\u4e00\u4e2aT\u5b57\u578b\u7684\u533a\u57df\uff0c\u4e14\u8fd9\u4e2a\u533a\u57df\u5185\u81f3\u5c11\u8981\u6709\u4e00\u4e2a 1 \u3002\u9009\u4e2d\u540e\uff0c\u8fd9\u4e2a\u533a\u57df\u5185\u6240\u6709\u7684\u5143\u7d20\u90fd\u4f1a\u53d8\u6210 0\u3002\u7ed9\u5b9a\u6e38\u620f\u76ee\u524d\u7684\u77e9\u9635\uff0c\u5c0f\u84dd\u60f3\u77e5\u9053\u4ed6\u6700\u591a\u53ef\u4ee5\u8fdb\u884c\u591a\u5c11\u6b21\u4e0a\u8ff0\u64cd\u4f5c\u3002\u00a0T\u5b57\u578b\u533a\u57df\u662f\u6307\u5f62\u5982 (x \u2212 1, y) (x, y) (x + 1, y) (x, y + 1) \u7684\u56db\u4e2a\u70b9\u6240\u5f62\u6210\u7684\u533a \u57df\u3002\u5176\u65cb\u8f6c 90, 180, 270 \u5ea6\u7684\u5f62\u5f0f\u540c\u6837\u4e5f\u89c6\u4f5c T \u5b57\u5f62\u533a\u57df\u3002\u00a0<\/p>\n\n\n\n

\u8f93\u5165\u683c\u5f0f<\/h2>\n\n\n\n

\u8f93\u5165\u5305\u542b\u591a\u7ec4\u6570\u636e\u3002\u8f93\u5165\u7684\u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570 D \u8868\u793a\u6570\u636e\u7ec4\u6570\u3002\u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff0c\u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570n\u3002\u63a5\u4e0b\u6765n\u884c\u6bcf\u884c\u5305\u542bn\u4e2a0\u62161\uff0c\u8868\u793a\u77e9\u9635Ai, j<\/sub>\u7684\u6bcf\u4e2a\u4f4d\u7f6e\u7684\u503c\u3002<\/p>\n\n\n\n

\u8f93\u51fa\u683c\u5f0f<\/h2>\n\n\n\n

\u8f93\u51fa D \u884c\uff0c\u6bcf\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570\u8868\u793a\u5c0f\u84dd\u6700\u591a\u53ef\u4ee5\u5bf9\u5f53\u524d\u8be2\u95ee\u4e2d\u7684\u77e9\u9635\u64cd\u4f5c\u7684\u6b21\u6570\u3002 <\/p>\n\n\n\n

\u6837\u4f8b\u8f93\u5165<\/h2>\n\n\n\n
1\n3\n001\n011\n111<\/pre>\n\n\n\n
\u6837\u4f8b\u8f93\u51fa<\/h2>\n\n\n\n
5<\/pre>\n\n\n\n
\u63d0\u793a<\/h2>\n\n\n\n
\u6211\u4eec\u7528 X \u8868\u793a\u67d0\u6b21\u64cd\u4f5c\u9009\u4e2d\u7684 T \u5b57\u5f62\uff0c\u4ee5\u4e0b\u7ed9\u51fa\u4e00\u79cd\u53ef\u884c\u65b9\u6848\uff1a<\/p>\n\n\n\n
001\u00a0 \u00a0 \u00a0 XXX\u00a0 \u00a0 \u00a0 \u00a00X0\u00a0 \u00a0 \u00a0 \u00a000X\u00a0 \u00a0 \u00a0 0X0\u00a0 \u00a0 \u00a0 \u00a0X00\u00a0<\/p>\n\n\n\n
011 => 0X1 => XXX => 0XX => XX0 => XX0 <\/p>\n\n\n\n
111      111       111       11X       1X0       X00 <\/p>\n\n\n\n
\u5bf9\u4e8e 10% \u7684\u8bc4\u6d4b\u7528\u4f8b\uff0cn = 3 \uff1b<\/p>\n\n\n\n
\u5bf9\u4e8e 40% \u7684\u8bc4\u6d4b\u7528\u4f8b\uff0cn \u2264 30 \uff1b <\/p>\n\n\n\n
\u5bf9\u4e8e\u6240\u6709\u8bc4\u6d4b\u7528\u4f8b\uff0c3 \u2264 n \u2264 2000\uff0c\u77e9\u9635\u4e2d\u4ec5\u542b 0 \u548c 1 \u3002<\/p>\n\n\n\n
\u89e3\u9898\u601d\u8def:\uff08\u8d2a\u5fc3+\u4f18\u5148\u961f\u5217+\u8986\u76d6\u5173\u7cfb\u6620\u5c04\uff09\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u8d2a\u5fc3\u7b56\u7565\uff1a\u6bcf\u6b21\u9009\u62e9\u8986\u76d6\u533a\u57df\u51851\u7684\u4e2a\u6570\u6700\u5c11\u7684T\u5b57\u5f62\u8fdb\u884c\u64cd\u4f5c\u3002\u8fd9\u6837\u505a\u7684\u76ee\u7684\u662f\u4e3a\u4e86\u5c3d\u53ef\u80fd\u5c11\u5730\u6d88\u80171\uff0c\u4ece\u800c\u8fdb\u884c\u66f4\u591a\u7684\u64cd\u4f5c\u3002\u4f46\u662f\uff0c\u7531\u4e8e\u64cd\u4f5c\u540e\u4f1a\u5f71\u54cd\u5176\u4ed6T\u5b57\u5f62\uff0c\u56e0\u6b64\u9700\u8981\u52a8\u6001\u66f4\u65b0\u53d7\u5f71\u54cd\u7684\u64cd\u4f5c\u3002\u4e3a\u4e86\u9ad8\u6548\u66f4\u65b0\uff0c\u6211\u4eec\u9700\u8981\u77e5\u9053\u6bcf\u4e2a\u4f4d\u7f6e\u88ab\u54ea\u4e9bT\u5b57\u5f62\u64cd\u4f5c\u8986\u76d6\u3002\u8fd9\u6837\uff0c\u5f53\u4e00\u4e2a\u4f4d\u7f6e\u88ab\u7f6e0\u540e\uff0c\u6211\u4eec\u53ef\u4ee5\u66f4\u65b0\u6240\u6709\u8986\u76d6\u8be5\u4f4d\u7f6e\u7684T\u5b57\u5f62\u64cd\u4f5c\u76841\u7684\u8ba1\u6570\u3002<\/p>\n\n\n\n
\u6ce8\u610f\u4e8b\u9879:1.\u8fb9\u754c\u5904\u74062.\u6548\u7387\u95ee\u98983.\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
\u9898\u89e3\u7b54\u6848\uff1a\u5168\u7f51\u72ec\u4e00\u4efd\u7b54\u6848 C\u8bed\u8a00\u7f51\u4e0a\u7684\u4e09\u4efd\u89e3\u7b54\u5747\u4e3a\u7248\u4e3b\u63d0\u4f9b<\/p>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <queue>\n#include <algorithm>\n#include <tuple>\nusing namespace std;\n<br>\nconst vector<vector<pair<int, int>>> OFFSETS = {\n    {{-1,0}, {0,0}, {1,0}, {0,1}},   \/\/ \u5411\u4e0b\u5f00\u53e3\n    {{-1,0}, {0,0}, {1,0}, {0,-1}},   \/\/ \u5411\u4e0a\u5f00\u53e3\n    {{0,-1}, {0,0}, {0,1}, {1,0}},   \/\/ \u5411\u53f3\u5f00\u53e3\n    {{0,-1}, {0,0}, {0,1}, {-1,0}}   \/\/ \u5411\u5de6\u5f00\u53e3\n \n<br>\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n \n    int D;\n    cin >> D;\n    while (D--) {\n        int n;\n        cin >> n;\n        vector<string> grid(n);\n        int total_ones = 0;\n        for (int i = 0; i < n; i++) {\n            cin >> grid[i];\n            for (char c : grid[i])\n                if (c == '1') total_ones++;\n        }\n \n        \/\/ \u4e09\u7ef4\u6570\u7ec4\u5b58\u50a8\u6bcf\u79cdT\u5b57\u5f62\u64cd\u4f5c\u76841\u7684\u4e2a\u6570\n        vector<vector<vector<int>>> cnt(n, vector<vector<int>>(n, vector<int>(4, 0)));\n        \/\/ \u6620\u5c04\u6bcf\u4e2a\u683c\u5b50\u88ab\u54ea\u4e9bT\u5b57\u5f62\u64cd\u4f5c\u8986\u76d6\n        vector<vector<vector<tuple<int, int, int>>>> grid_map(n, vector<vector<tuple<int, int, int>>>(n));\n \n        \/\/ \u5c0f\u6839\u5806\uff081\u7684\u6570\u91cf\uff0c\u4e2d\u5fc3x\uff0c\u4e2d\u5fc3y\uff0c\u7c7b\u578b\uff09\n        priority_queue<tuple<int, int, int, int>,\n                      vector<tuple<int, int, int, int>>,\n                      greater<tuple<int, int, int, int>>> pq;\n \n        auto valid = [&](int x, int y) {\n            return x >= 0 && x < n && y >= 0 && y < n;\n        };\n<br>\n        \/\/ \u9884\u586b\u5145cnt\u6570\u7ec4\u548cgrid_map\n        for (int x = 0; x < n; x++) {\n            for (int y = 0; y < n; y++) {\n                for (int type = 0; type < 4; type++) {\n                    bool skip = false;\n                    int ones = 0;\n                    vector<pair<int, int>> points;\n \n                    for (auto [dx, dy] : OFFSETS[type]) {\n                        int nx = x + dx, ny = y + dy;\n                        if (!valid(nx, ny)) {\n                            skip = true;\n                            break;\n                        }\n                        points.push_back({nx, ny});\n                    }\n \n                    if (skip) continue;\n \n                    for (auto [px, py] : points) {\n                        if (grid[px][py] == '1') ones++;\n                        grid_map[px][py].push_back(make_tuple(x, y, type));\n                    }\n                    cnt[x][y][type] = ones;\n                    if (ones > 0) pq.push(make_tuple(ones, x, y, type));\n                }\n            }\n        }\n<br>\n        int ops = 0;\n        while (!pq.empty() && total_ones > 0) {\n            auto [c_old, x, y, type] = pq.top();\n            pq.pop();\n \n            \/\/ \u68c0\u67e5\u662f\u5426\u8fc7\u671f\n            if (cnt[x][y][type] != c_old) continue;\n            if (c_old == 0) continue;\n \n            ops++;\n            vector<pair<int, int>> points;\n            for (auto [dx, dy] : OFFSETS[type]) {\n                points.push_back({x + dx, y + dy});\n            }\n \n            \/\/ \u904d\u5386\u8986\u76d6\u7684\u6bcf\u4e2a\u70b9\n            for (auto [px, py] : points) {\n                if (grid[px][py] == '0') continue;\n \n                \/\/ \u6e05\u9664\u8be5\u70b9\n                grid[px][py] = '0';\n                total_ones--;\n \n                \/\/ \u66f4\u65b0\u6240\u6709\u8986\u76d6\u8be5\u70b9\u7684T\u5b57\u5f62\u64cd\u4f5c\n                for (auto [x2, y2, type2] : grid_map[px][py]) {\n                    if (cnt[x2][y2][type2] > 0) {\n                        cnt[x2][y2][type2]--;\n                        pq.push(make_tuple(cnt[x2][y2][type2], x2, y2, type2));\n                    }\n                }\n            }\n        }\n \n        cout << ops << '\\n';\n    }\n    return 0;\n}\n\/\/ THEBUG MUXI<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u5c0f\u84dd\u6b63\u5728\u73a9\u4e00\u6b3e\u6e38\u620f\uff0c\u6e38\u620f\u4e2d\u6709\u4e00\u4e2an \u00d7 n\u5927\u5c0f\u7684 01 \u77e9\u9635 Ai, j\u00a0\u3002\u5c0f\u84dd\u6bcf\u6b21\u9700\u8981\u9009\u62e9\u4e00\u4e2aT\u5b57 […]<\/p>\n","protected":false},"author":1,"featured_media":14,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[8],"class_list":["post-62","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-leam","tag-8"],"_links":{"self":[{"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/posts\/62","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=62"}],"version-history":[{"count":2,"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/posts\/62\/revisions"}],"predecessor-version":[{"id":64,"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/posts\/62\/revisions\/64"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/media\/14"}],"wp:attachment":[{"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=62"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=62"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.thebugmuxi.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=62"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}