{"id":425,"date":"2018-08-09T17:19:13","date_gmt":"2018-08-09T17:19:13","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=425"},"modified":"2018-08-09T17:19:13","modified_gmt":"2018-08-09T17:19:13","slug":"%e7%89%9b%e5%ae%a2%e5%a4%9a%e6%a0%a1%e7%ac%ac%e4%b8%83%e5%9c%ba-problem-j-sudoku-subrectangles","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=425","title":{"rendered":"\u725b\u5ba2\u591a\u6821\u7b2c\u4e03\u573a Problem J Sudoku Subrectangles"},"content":{"rendered":"

\u9898\u89e3<\/h2>\n

\u6ce8\u610f \u8fd9\u548c\u6570\u72ec\u4e0d\u4e00\u6837\uff0c\u662f\u8981\u6c42\u5b50\u77e9\u9635\u4e2d\u6bcf\u4e00\u884c \u6216<\/strong> \u6bcf\u4e00\u5217\u7684\u5b57\u7b26\u53ea\u51fa\u73b0\u4e00\u6b21<\/p>\n

\u8fd9\u4e2a\u95ee\u9898\u5751\u4e86\u4e0d\u5c11\u4eba<\/p>\n

\u5269\u4e0b\u7684\u6309\u7167\u5b98\u65b9\u9898\u89e3\u5c31\u5b8c\u6210
\n\u2022 \u6ce8\u610f\u523052\u79cd\u5b57\u7b26\uff0c\u5b50\u77e9\u5f62\u6700\u591a52\u884c\uff0c52\u5217\u3002
\n\u2022 \u4e00\u4e2a5252<\/em>nm\u7684\u505a\u6cd5\u662f\u663e\u7136\u7684\uff0c\u53ef\u4ee5\u4f18\u5316\u523052*nm\u3002
\n\u2022 \u679a\u4e3e\u4e0a\u4e0b\u8fb9\u754c(\u6700\u591a\u5dee52)
\n\u2022 \u5f53\u5de6\u7aef\u70b9\u786e\u5b9a\u540e\uff0c\u53f3\u7aef\u70b9\u7684\u8303\u56f4\u662f\u8fde\u7eed\u7684\u4e00\u6bb5\uff0c\u5e76\u4e14\u5355\u8c03
\n\u2022 \u626b\u4e00\u904d\u5373\u53ef\uff0c\u53ef\u4ee5\u4f7f\u7528\u4f4d\u8fd0\u7b97\u964d\u4f4e\u590d\u6742\u5ea6\u3002<\/p>\n

AC\u4ee3\u7801<\/h2>\n
#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <array>\n\nusing namespace std;\nusing ll = long long;\n\nconst int maxn = 1000 + 10;\nint n, m;\nchar s[maxn][maxn];\nint horizontal[maxn][maxn], vertical[maxn][maxn];\narray<int, maxn> pos, len;\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    cin >> n >> m;\n    for (int i = 1; i <= n; ++i) {\n        cin >> (s[i] + 1);\n        pos.fill(0);\n        for (int j = 1; j <= m; ++j) {\n            horizontal[i][j] = min(horizontal[i][j - 1] + 1, j - pos[s[i][j]]);\n            pos[s[i][j]] = j;\n        }\n    }\n    for (int j = 1; j <= m; ++j) {\n        pos.fill(0);\n        for (int i = 1; i <= n; ++i) {\n            vertical[i][j] = min(vertical[i - 1][j] + 1, i - pos[s[i][j]]);\n            pos[s[i][j]] = i;\n        }\n    }\n    ll ans = 0;\n    for (int j = 1; j <= m; ++j) {\n        len.fill(0);\n        for (int i = 1; i <= n; ++i) {\n            for (int k = 0; k < horizontal[i][j]; ++k) {\n                len[k] = min(len[k] + 1, vertical[i][j - k]);\n                if (k) len[k] = min(len[k], len[k - 1]);\n                ans += len[k];\n            }\n            for (int k = horizontal[i][j]; k < 54; k++) len[k] = 0;\n        }\n    }\n    cout << ans << '\\n';\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u89e3 \u6ce8\u610f \u8fd9\u548c\u6570\u72ec\u4e0d\u4e00\u6837\uff0c\u662f\u8981\u6c42\u5b50\u77e9\u9635\u4e2d\u6bcf\u4e00\u884c \u6216 \u6bcf\u4e00\u5217\u7684\u5b57\u7b26\u53ea\u51fa\u73b0\u4e00\u6b21 \u8fd9\u4e2a\u95ee\u9898\u5751\u4e86\u4e0d\u5c11\u4eba \u5269\u4e0b\u7684\u6309\u7167\u5b98 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,49,22],"tags":[57],"class_list":["post-425","post","type-post","status-publish","format-standard","hentry","category-c","category-49","category-22","tag-57"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-6R","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/425","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=425"}],"version-history":[{"count":0,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/425\/revisions"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=425"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=425"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=425"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}