{"id":687,"date":"2013-02-21T02:38:13","date_gmt":"2013-02-20T18:38:13","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=687"},"modified":"2013-02-22T22:19:21","modified_gmt":"2013-02-22T14:19:21","slug":"glass_garden_problem","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/glass_garden_problem\/","title":{"rendered":"\u57f9\u517b\u76bf\u95ee\u9898"},"content":{"rendered":"

\u8fd9\u4e2a\u6a21\u578b\u6700\u65e9\u89c1\u5230\u662f\u5728 SRM 493 …<\/a> \u53c2\u89c1 hhanger \u7684\u9898\u89e3\u3002\u3002\u3002<\/a> ..<\/p>\n

Brief description: <\/h3>\n

\u7ed9\u4e00\u4e2a n*m \u77e9\u5f62\uff0c\u5176\u4e2d\u6709\u4e9b\u683c\u5b50\u53ef\u4ee5\u9009\uff0c\u6709\u4e9b\u4e0d\u80fd\u9009\u3002\u73b0\u5728\u8981\u6c42\u5728\u53ef\u9009\u7684\u683c\u5b50\u4e2d\u9009\u4e00\u4e9b\u7ec4\u6210\u4e00\u4e2a\u51f8\u7269\uff0c\u51f8\u7269\u8981\u6c42\u6240\u9009\u7684\u6240\u6709\u683c\u5b50\u662f\u76f8\u4e92\u8054\u901a\u7684\uff0c\u5e76\u4e14\u5982\u679c\u540c\u4e00\u884c\/\u5217\u9009\u53d6\u4e86\u4e24\u4e2a\u683c\u5b50\u7684\u8bdd\uff0c\u548c\u5b83\u4eec\u5728\u540c\u4e00\u884c\/\u5217\uff0c\u5e76\u4e14\u5728\u5b83\u4eec\u4e4b\u95f4\u7684\u6240\u6709\u683c\u5b50\u90fd\u9700\u8981\u88ab\u9009\u3002\u95ee\u4e00\u5171\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u9009\u6cd5\u3002\uff08n, m <= 100\uff09<\/p><\/blockquote>\n

<\/p>\n

Analysis: <\/h3>\n

\u6211\u4eec\u9700\u8981\u597d\u597d\u7814\u7a76\u4e0b\u8fd9\u4e2a\u6240\u8c13\u51f8\u7269\u7684\u6027\u8d28\u3002\u9996\u5148\uff0c\u5b83\u662f\u4e2a\u8054\u901a\u4f53\uff0c\u7136\u540e\uff0c\u7531\u4e8e\u51f8\u6027\uff0c\u5176\u6bcf\u4e00\u884c\/\u6bcf\u4e00\u5217\u4e00\u5b9a\u662f\u8fde\u7eed\u7684\u4e00\u6bb5\u3002\u60f3\u60f3\u4e00\u4e0b\u8fd9\u4e2a\u56fe\u5f62\uff0c\u5b83\u7684\u6bcf\u4e00\u884c\u6211\u4eec\u90fd\u53ef\u4ee5\u7528\u4e00\u4e2a\u4e09\u5143\u7ec4\u6765\u8868\u793a(r, a, b)\uff0c\u8868\u793a\u7b2cr\u884c\u9009\u53d6\u7684\u662f\u4ece\u7b2ca\u5217\u5230\u7b2cb\u5217\u7684\u6240\u6709\u5143\u7d20\u3002\u6211\u4eec\u9009\u53d6\u7684\u4e00\u5b9a\u662f\u8fde\u7eed\u7684\u4e00\u4e9b\u884c\uff0c\u6211\u4eec\u8003\u5bdf\u8fd9\u4e9b\u884c\u5404\u81ea\u7684a\u548cb\u6240\u7ec4\u6210\u7684A\u548cB\u5e8f\u5217\u7684\u6027\u8d28\u3002<\/p>\n

A\u6570\u5217\u662f\u6bcf\u4e00\u884c\u6700\u5de6\u8fb9\u5143\u7d20\u7684\u5217\u5750\u6807\u7ec4\u6210\u7684\u6570\u7ec4\uff0cB\u5219\u662f\u6700\u53f3\u8fb9\u5143\u7d20\u7684\u5217\u5750\u6807\u6570\u7ec4\u3002\u4e3a\u4e86\u4fdd\u8bc1\u6bcf\u4e00\u5217\u4e5f\u662f\u8fde\u7eed\u7684\u4e00\u6bb5\uff0cA\u6570\u7ec4\u5fc5\u987b\u662f\u4e00\u4e2a\u5148\u975e\u9012\u589e\uff0c\u518d\u975e\u9012\u51cf\u7684\u6570\u7ec4\uff0c\u800cB\u6570\u7ec4\u4e5f\u7c7b\u4f3c\u3002\u6839\u636e\u8fd9\u4e00\u70b9\uff0c\u4e00\u4e2a\u552f\u4e00\u7684\u51f8\u7269\u5bf9\u5e94\u4e00\u5bf9\u552f\u4e00\u7684A\u548cB\u6570\u7ec4\u3002\u56e0\u6b64\u6211\u4eec\u5c31\u53ef\u4ee5\u6765\u8003\u8651dp\u89e3\u6cd5\u6765\u9009\u53d6A\u548cB\u6570\u7ec4\u4e86\u3002dp[i][j][k][b1][b2]\u8868\u793a\u6700\u540e\u4e00\u884c\u4e3a\u7b2ci\u884c\u7684\uff0c\u7b2ci\u884c\u9009\u53d6\u7b2cj\u5230\u7b2ck\u5217\u7684\u65b9\u6cd5\u6570\uff08b1\u548cb2\u7528\u6765\u8868\u793aA\u5e8f\u5217\u548cB\u6570\u5217\u5206\u522b\u662f\u5426\u5df2\u7ecf\u5728\u975e\u9012\u51cf\/\u975e\u9012\u589e\u72b6\u6001\uff09\u3002\u5bf9\u4e8e\u7b2ci\u884c\uff0c\u4e00\u79cd\u60c5\u51b5\u662f\u6574\u4e2a\u51f8\u7269\u53ea\u6709\u7b2ci\u884c\u7684\u5143\u7d20\uff0c\u8fd9\u4e2a\u662f\u5f88naive\u7684\u60c5\u51b5\uff1b\u53e6\u5916\u4e00\u79cd\u662f\u9664\u4e86\u7b2ci\u884c\uff0c\u8fd8\u6709\u524di-1\u884c\u7684\u4e00\u4e9b\u5143\u7d20\uff0c\u8fd9\u6837\u6211\u4eec\u5c31\u53ef\u4ee5\u5229\u7528\u5230dp[i-1][?][?][?][?]\u7684\u503c\u4e86\u3002\u5177\u4f53\u72b6\u6001\u8f6c\u79fb\u8981\u6839\u636e\u540e\u4e24\u7ef4\u7684\u4e0d\u540c\u6765\u5206\u522b\u5904\u7406\u3002\u5b9e\u9645\u4e0a\uff0c\u5728\u6c42dp[i]\u65f6\uff0c\u6211\u4eec\u9700\u8981\u6c42\u7684\u90fd\u662f\u67d0\u4e00\u6bb5dp[i-1][j1 to j2][k1 to k2][?][?]\u6240\u6709\u5143\u7d20\u7684\u548c\uff0c\u8fd9\u662f\u4e00\u4e2a\u5f88\u7ecf\u5178\u7684\u4e8c\u7ef4\u6570\u7ec4\u6c42\u5b50\u77e9\u9635\u548c\u95ee\u9898\uff0c\u53ef\u4ee5O(n^2)\u5904\u7406\uff0c\u4e4b\u540eO(1)\u8ba1\u7b97\u3002\u72b6\u6001\u8f6c\u79fb\u7684\u65f6\u5019\u8fd8\u9700\u8981\u7279\u522b\u6ce8\u610f\u5230\uff0c\u76f8\u7b49\u5e8f\u5217\u5373\u7b26\u5408\u975e\u9012\u589e\u53c8\u7b26\u5408\u975e\u9012\u51cf\uff0c\u6240\u4ee5A\u548cB\u6570\u7ec4\u51fa\u73b0\u8f6c\u6298\u70b9\u7684\u60c5\u51b5\u4e00\u5b9a\u662f\u51fa\u73b0\u4e86\u4e00\u4e2a\u4e25\u683c\u9012\u589e\/\u4e25\u683c\u9012\u51cf\u7684\u72b6\u6001\uff0c\u8fd9\u6837\u53ef\u4ee5\u4fdd\u8bc1\u6bcf\u4e2a\u72b6\u6001\u88ab\u552f\u4e00\u8868\u793a\uff0c\u907f\u514d\u4e86\u91cd\u590d\u8ba1\u7b97\u3002<\/p><\/blockquote>\n

dp[0\/1][0\/1][l][r]: \u8868\u793a\u5de6\u53f3\u7684\u589e\u51cf\u72b6\u6001\u4e3a b1, b2 \uff0c\u5f53\u524d\u533a\u95f4\u4e3a [l, r] \u65f6\u7684\u72b6\u6001\u3002\u3002
\n\u3002\u3002\u72b6\u6001\u7684\u65f6\u5019\u5148\u4ece\u4e0a\u4e00\u8f6e\u9884\u5904\u7406\u4e8c\u7ef4\u90e8\u5206\u548c\u6570\u7ec4\u3002\u3002\u4e4b\u540e\u5206\u56db\u79cd\u60c5\u51b5\u8ba8\u8bba\u5373\u53ef\u3002\u3002\u3002
\nPetr \u7684\u4ee3\u7801<\/a>\u901a\u8fc7\u8c03\u6574\u8f6c\u79fb\u65b9\u5411\u3002\u3002\u53ef\u4ee5\u907f\u514d\u8fd9\u6b65\u64cd\u4f5c\u3002\u3002\u5f88\u4f18\u8d8a\u3002\u3002\uff09\u3002\u3002<\/p>\n

\u3002\u3002\u5b9e\u73b0\u7684\u65f6\u5019\u5199\u4e86\u4e00\u4e2a Int \u6574\u6570\u7c7b\u3002\u3002\u81ea\u5e26\u53d6\u6a21\u3002\u3002
\n\u4ee3\u7801\u5c3d\u91cf\u4fdd\u6301\u5bf9\u79f0\u53ef\u907f\u514d\u6572\u9519\u3002\u3002\u3002\u3002<\/p>\n

\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 109;\r\n\r\nstruct Int{\r\n    int val;\r\n\r\n    operator int() const{return val;}\r\n\r\n    Int(int val = 0):val(val){\r\n        val %= MOD; if (val < 0) val += MOD;\r\n    }\r\n    inline Int& operator +=(const Int& rhs){\r\n        INC(val, rhs);\r\n        return *this;\r\n    }\r\n    inline Int operator +(const Int& rhs) const{\r\n        return sum(val, rhs.val);\r\n    }\r\n    inline Int operator -(const Int& rhs) const{\r\n        return dff(val, rhs);\r\n    }\r\n};\r\n\r\nInt F[2][2][N][N], S[2][2][N][N]; bool A[N][N];\r\nint n, m;\r\n\r\nInt SS(int b1, int b2, int x1, int x2, int y1, int y2){\r\n    return S[b1][b2][x2+1][y2+1] - S[b1][b2][x2+1][y1] - S[b1][b2][x1][y2+1] + S[b1][b2][x1][y1];\r\n}\r\n\r\nclass AmoebaDivOne {\r\npublic:\r\n\tint count(vector <string> T) {\r\n\r\n\t    n = SZ(T), m = SZ(T[0]); REP_2(i, j, n, m){\r\n\t        int t = isdigit(T[i][j]) ? T[i][j] - '0' : T[i][j] - 'a' + 10;\r\n            A[2*i][2*j] = t & 1, A[2*i][2*j+1] = t & 2;\r\n            A[2*i+1][2*j] = t & 4, A[2*i+1][2*j+1] = t & 8;\r\n\t    }\r\n\r\n\t    n <<= 1, m <<= 1; RST(F); Int res; REP(i, n){\r\n\r\n            RST(S); REP_4(b1, b2, l, r, 2, 2, m, m) S[b1][b2][l+1][r+1] = S[b1][b2][l][r+1] + S[b1][b2][l+1][r] - S[b1][b2][l][r] + F[b1][b2][l][r];\r\n\r\n            RST(F); REP(l, m) FOR(r, l, m){\r\n\r\n                if (A[i][r]) break;\r\n\r\n                F[0][0][l][r] = SS(0, 0, l, r, l, r) + Int(1);\r\n                F[0][1][l][r] = SS(0, 0, l, r, r+1, m-1) + SS(0, 1, l, r, r, m-1);\r\n                F[1][0][l][r] = SS(0, 0, 0, l-1, l, r) + SS(1, 0, 0, l, l, r);\r\n                F[1][1][l][r] = SS(0, 0, 0, l-1, r+1, m-1) + SS(0, 1, 0, l-1, r, m-1) + SS(1, 0, 0, l, r+1, m-1) + SS(1, 1, 0, l, r, m-1);\r\n\r\n                REP_2(b1, b2, 2, 2) res += F[b1][b2][l][r];\r\n            }\r\n\t\t}\r\n\r\n\t\treturn res;\r\n\t}\r\n};\r\n<\/pre>\n
\u8865\u5145: <\/h3>\n
Codeforces Round #167 DIV 1 D. Dima and Figure<\/a>
\n\u6570\u636e\u8303\u56f4\u6269\u5927\u3002\u3002\u4f46\u662f\u6ca1\u6709\u969c\u788d\u3002\u3002
\nSGU 167. I-country.<\/a>
\n\u6700\u503c\u95ee\u9898\u3002\u3002\u9700\u8981\u6253\u5370\u65b9\u6848\u3002\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u4e2a\u6a21\u578b\u6700\u65e9\u89c1\u5230\u662f\u5728 SRM 493 … \u53c2\u89c1 hhanger \u7684\u9898\u89e3\u3002\u3002\u3002 .. Brief description: \u7ed9\u4e00\u4e2a n*m \u77e9\u5f62\uff0c\u5176\u4e2d\u6709\u4e9b\u683c\u5b50\u53ef\u4ee5\u9009\uff0c\u6709\u4e9b\u4e0d\u80fd\u9009\u3002\u73b0\u5728\u8981\u6c42\u5728\u53ef\u9009\u7684\u683c\u5b50\u4e2d\u9009\u4e00\u4e9b\u7ec4\u6210\u4e00\u4e2a\u51f8\u7269\uff0c\u51f8\u7269\u8981\u6c42\u6240\u9009\u7684\u6240\u6709\u683c\u5b50\u662f\u76f8\u4e92\u8054\u901a\u7684\uff0c\u5e76\u4e14\u5982\u679c\u540c\u4e00\u884c\/\u5217\u9009\u53d6\u4e86\u4e24\u4e2a\u683c\u5b50\u7684\u8bdd\uff0c\u548c\u5b83\u4eec\u5728\u540c\u4e00\u884c\/\u5217\uff0c\u5e76\u4e14\u5728\u5b83\u4eec\u4e4b\u95f4\u7684\u6240\u6709\u683c\u5b50\u90fd\u9700\u8981\u88ab\u9009\u3002\u95ee\u4e00\u5171\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u9009\u6cd5\u3002\uff08n, 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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[27],"tags":[],"class_list":["post-687","post","type-post","status-publish","format-standard","hentry","category-27"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-b5","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/687","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=687"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/687\/revisions"}],"predecessor-version":[{"id":689,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/687\/revisions\/689"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=687"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=687"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=687"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}