{"id":285,"date":"2012-07-04T02:35:57","date_gmt":"2012-07-03T18:35:57","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=285"},"modified":"2012-07-08T03:06:04","modified_gmt":"2012-07-07T19:06:04","slug":"srm-548","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-548\/","title":{"rendered":"SRM 548"},"content":{"rendered":"

Brief description: <\/h3>\n

Problem 250. KingdomAndTrees
\n\u7ed9\u5b9a\u4e00\u4e2a\u6570\u5217\uff0c\u8981\u6c42\u4fee\u590d\u6210\u9012\u589e\u5e8f\u5217\u3002\u3002\uff08\u6240\u6709\u9879\u90fd\u662f\u6b63\u6570\u3002\u3002\u3002
\n\u3002\u5b9a\u4e49\u4fee\u590d\u4ee3\u4ef7\u4e3a\u53d8\u52a8\u6700\u5927\u7684\u6570\u5b57\u6539\u53d8\u4e86\u591a\u5c11\u3002\u3002\u6c42\u6700\u5c0f\u4fee\u590d\u4ee3\u4ef7\u3002\u3002\u3002<\/p>\n

Problem 450. KingdomAndDice
\n\u7ed9\u5b9a\u4e24\u5757\u9ab0\u5b50\u3002\u3002\u6570\u5b57\u9009\u81ea {1, x} \u3002\u3002
\n\u5176\u4e2d\u4e00\u5757\u9ab0\u5b50\u4e0a\u7684\u6570\u5b57\u5df2\u7ecf\u5168\u90e8\u786e\u5b9a\u3002\u3002\u53e6\u4e00\u5757\u9ab0\u5b50\u90e8\u5206\u786e\u5b9a\u3002\u3002
\n\u3002\u3002\u5148\u8981\u6c42\u786e\u5b9a\u5269\u4e0b\u7684\u6570\u5b57\u3002\u3002\u4f7f\u5f97\u8be5\u6e38\u620f\u5c3d\u53ef\u80fd\u516c\u5e73\u3002<\/p>\n

Problem 1000. KingdomAndCities
\n\u8ba1\u6570\uff1a\u6c42 n \u4e2a\u9876\u70b9\u3001m \u6761\u8fb9\u3001\u5176\u4e2d\u524d k \u4e2a\u9876\u70b9\u6070\u597d\u8fde 2 \u6761\u8fb9\u65f6\u5f62\u6210\u8fde\u901a\u56fe\u7684\u65b9\u6848\u6570\u3002
\n( n, m <= 50, k <= 2 .. .\n\n<\/p>\n

Analysis: <\/h3>\n

Problem 250. KingdomAndTrees
\n\u3002\u3002\u3002\u679a\u4e3e i, j \u5bf9\u6bcf\u5bf9 i, j \u66f4\u65b0\u4e00\u4e0b\u4e0a\u754c\u3002
\n\u3002\uff08\u5982\u679c\u51fa\u73b0 Ai <= 1 \u5219\u9501\u5b9a\u5176\u4e3a 1 \u3002\u3002\u91cd\u65b0\u66f4\u65b0\u4e0a\u754c\u3002\u3002\u3002\n\u3002\uff08\u597d\u50cf\u4e5f\u53ef\u4ee5\u4e8c\u5206\u7b54\u6848\u8d2a\u5fc3\u3002\u3002\n\nProblem 450. KingdomAndDice\n\u3002\u3002\u3002\u7565\uff09 \u88f8 O(n5) \u591a\u91cd\u80cc\u5305\u3002\u3002\u3002\ndp[i][j] \u8868\u793a\u5f53\u524d\u4f7f\u7528\u4e86 i \u4e2a\u7269\u54c1\uff0c\u80fd\u5426\u5f97\u5230\u548c\u7b49\u4e8e j \u7684\u65b9\u6848\u3002\n\nProblem 1000. KingdomAndCities\n\u3002\u3002\u3002( \u79fb\u6b65\u3002\u3002\u3002<\/a><\/p>\n

\r\nclass KingdomAndTrees {\r\npublic:\r\n\tint minLevel(vector <int> A) {\r\n\r\n\t\tint n = SZ(A), res = 0;\r\n\r\n\t\tREP(i, n) FOR(j, i+1, n){\r\n\t\t    int t = (j - i + A[i] - A[j] + 1) \/ 2;\r\n\t\t    if (A[i] - t > 0) checkMax(res, t);\r\n\t\t    else checkMax(res, j - i - A[j] + 1);\r\n\t\t}\r\n\r\n\t\treturn res;\r\n\t}\r\n};\r\n<\/pre>\n
\r\n.. .\r\nconst int N = 59, M = N * N;\r\n\r\nbool dp[N][M]; int cnt[N];\r\nint n, m, s, nn, b;\r\n\r\nclass KingdomAndDice {\r\npublic:\r\n\tdouble newFairness(vector <int> A, vector <int> B, int X) {\r\n\r\n\t    n = SZ(A); s = n * n; m = s \/ 2, nn = 0, b = 0;\r\n\r\n\t    SRT(B), RST(cnt);\r\n\t    DWN(i, n, 0) if (A[i] == 0){\r\n            ++nn;\r\n\t    }\r\n\t    else {\r\n\t        int t = lower_bound(ALL(B), A[i]) - B.begin();\r\n            --cnt[t], b += t;\r\n\t    }\r\n\r\n        cnt[0] = nn; REP(i, n){\r\n            if (i == n - 1) cnt[i+1] = min(nn, cnt[i+1] + max(0, X - B[i]));\r\n            else cnt[i+1] = min(nn, cnt[i+1] + max(0, B[i+1] - B[i] - 1));\r\n        }\r\n\r\n        RST(dp), dp[0][b] = true;\r\n\r\n        REP(ii, n+1) REP(j, cnt[ii]){\r\n            DWN(i, nn, 0) DWN_1(j, s-ii, b){\r\n                if (dp[i][j]) dp[i+1][j + ii] = true;\r\n            }\r\n        }\r\n\r\n\r\n        if (dp[nn][m]) return (DB) m \/ s;\r\n\r\n        if (!(s&1)){\r\n            REP(i, M){\r\n                if (m-i>=0 && dp[nn][m-i]) return (DB) (m - i) \/ s;\r\n                if (m+i<=s && dp[nn][m+i]) return (DB) (m + i) \/ s;\r\n            }\r\n        }\r\n        else {\r\n            REP(i, M){\r\n                if (m+i<=s && dp[nn][m+i]) return (DB) (m + i) \/ s;\r\n                if (m-i>=0 && dp[nn][m-i]) return (DB) (m - i) \/ s;\r\n            }\r\n        }\r\n\t}\r\n};\r\n<\/pre>\n
\r\n.. .\r\nconst int N = 59;\r\n\r\nint C[N*(N-1)\/2+1][N], S[N][N], A[N][N];\r\nint n, m, k;\r\n\r\n\r\nint f0(int n, int m){\r\n    return A[n][m];\r\n}\r\n\r\nint f1(int n, int m){\r\n    int res = 0; --n, m -= 2;\r\n    FOR(i, 1, n) FOR_1(j, 0, m)\r\n        INC(res, pdt(i, n-i, C[n][i], f0(n-i, m-j), f0(i, j)));\r\n    DIV(res, 2); INC(res, pdt(C[n][2], f0(n, m)));\r\n    return res;\r\n}\r\n\r\nint f1_(int n, int m){\r\n    int res = 0; --n, m -= 2;\r\n    FOR(i, 1, n) FOR_1(j, 0, m)\r\n        INC(res, pdt(i, n-i, C[n][i], f0(n-i, m-j), f0(i, j)));\r\n    INC(res, pdt(sqr_M(C[n][1]), f0(n, m)));\r\n    return res;\r\n}\r\n\r\nint f2(int n, int m){\r\n\r\n    int res = f1_(n-1, m-1); n -= 2, m -= 4;\r\n    INC(res, pdt(sqr_M(C[n][2]), f0(n, m)));\r\n\r\n    FOR(i, 1, n) FOR_1(j, 0, m){\r\n        INC(res, pdt(_I(2), sqr_M(i), sqr_M(n-i), C[n][i], f0(n-i, m-j), f0(i, j)));\r\n        INC(res, pdt(i, n-i, C[n][i], sum(C[n-i][2], C[i][2]), f0(n-i, m-j), f0(i, j)));\r\n    }\r\n\r\n    #define i3 n-i1-i2\r\n    #define j3 m-j1-j2\r\n\r\n    FOR(i1, 0, n) FOR_1(j1, 0, m)\r\n        FOR(i2, 0, n-i1+1) FOR_1(j2, 0, m-j1)\r\n            INC(res, pdt(i1, sqr_M(i2), i3 , C[n][i1], C[n-i1][i2], f0(i3, j3), f0(i2, j2), f0(i1, j1)));\r\n\r\n    return res;\r\n}\r\n\r\n\r\nint f(int n, int m, int k){\r\n    if (k == 0) return f0(n, m);\r\n    else if (k == 1) return f1(n, m);\r\n    else return f2(n, m);\r\n}\r\n\r\nclass KingdomAndCities {\r\npublic:\r\n\tint howMany(int n, int k, int m) {\r\n\r\n\t    ::n = n, ::m = m, ::k = k;\r\n\r\n        FOR_1_C(i, 0, max(n, n*(n-1)\/2)){\r\n            C[i][0] = 1;REP_C(j, min(max(2, m), i)) C[i][j+1] = sum(C[i-1][j+1], C[i-1][j]);\r\n        }\r\n\r\n\t    S[0][0] = A[0][0] = 1; REP_1(i, n) FOR_1_C(j, 0, min(m, C[i][2])){\r\n            A[i][j] = S[i][j] = C[C[i][2]][j];\r\n            FOR(ii, 1, i) FOR_1(jj, 0, j) DEC(A[i][j], pdt(C[i-1][ii-1], A[ii][jj], S[i-ii][j-jj]));\r\n\t    }\r\n\r\n        return f(n, m, k);\r\n\t}\r\n};\r\n<\/pre>\n
External link: <\/h3>\n
http:\/\/community.topcoder.com\/stat?c=coder_room_stats&rd=15170&cr=22727863<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description: Problem 250. KingdomAndTrees \u7ed9\u5b9a\u4e00\u4e2a\u6570\u5217\uff0c\u8981\u6c42\u4fee\u590d\u6210\u9012\u589e\u5e8f\u5217\u3002\u3002\uff08\u6240\u6709\u9879\u90fd\u662f\u6b63\u6570\u3002\u3002\u3002 \u3002\u5b9a\u4e49\u4fee\u590d\u4ee3\u4ef7\u4e3a\u53d8\u52a8\u6700\u5927\u7684\u6570\u5b57\u6539\u53d8\u4e86\u591a\u5c11\u3002\u3002\u6c42\u6700\u5c0f\u4fee\u590d\u4ee3\u4ef7\u3002\u3002\u3002 Problem 450. KingdomAndDice \u7ed9\u5b9a\u4e24\u5757\u9ab0\u5b50\u3002\u3002\u6570\u5b57\u9009\u81ea {1, x} \u3002\u3002 \u5176\u4e2d\u4e00\u5757\u9ab0\u5b50\u4e0a\u7684\u6570\u5b57\u5df2\u7ecf\u5168\u90e8\u786e\u5b9a\u3002\u3002\u53e6\u4e00\u5757\u9ab0\u5b50\u90e8\u5206\u786e\u5b9a\u3002\u3002 \u3002\u3002\u5148\u8981\u6c42\u786e\u5b9a\u5269\u4e0b\u7684\u6570\u5b57\u3002\u3002\u4f7f\u5f97\u8be5\u6e38\u620f\u5c3d\u53ef\u80fd\u516c\u5e73\u3002 Problem 1000. KingdomAndCities \u8ba1\u6570\uff1a\u6c42 n \u4e2a\u9876\u70b9\u3001m \u6761\u8fb9\u3001\u5176\u4e2d\u524d k \u4e2a\u9876\u70b9\u6070\u597d\u8fde 2 \u6761\u8fb9\u65f6\u5f62\u6210\u8fde\u901a\u56fe\u7684\u65b9\u6848\u6570\u3002 ( n, m<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[17],"tags":[],"class_list":["post-285","post","type-post","status-publish","format-standard","hentry","category-topcoder"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-4B","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/285","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=285"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/285\/revisions"}],"predecessor-version":[{"id":289,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/285\/revisions\/289"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=285"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=285"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=285"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}