{"id":816,"date":"2013-09-06T17:51:19","date_gmt":"2013-09-06T09:51:19","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=816"},"modified":"2013-09-07T20:10:00","modified_gmt":"2013-09-07T12:10:00","slug":"srm-559","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-559\/","title":{"rendered":"SRM 559"},"content":{"rendered":"

<\/p>\n

250. HyperKnight<\/h2>\n

Brief description: <\/h3>\n

\u3002\u3002\u95ee\u5728\u4e00\u4e2a (n, m) \u7684\u68cb\u76d8\u4e2d\u3002\u3002\u4e00\u4e2a\u6b65\u957f\u4e3a (a, b) \u7684 Knight\u3002\u3002\u5408\u6cd5\u79fb\u52a8\u65b9\u6848\u4e3a k \u6b65\u7684\u683c\u5b50\u6709\u591a\u5c11\u4e2a\u3002<\/p>\n

Analysis: <\/h3>\n

\"\"\/<\/a><\/p>\n

\u4e00\u56fe\u6d41\u3002\u3002\u3002<\/p>\n

\r\n#define f8 ((n - 2 * a) * (m - 2 * a))\r\n#define f6  ( ((n - 2 * a) + (m - 2 * a)) * ((a - b) * 2) )\r\n#define f2 ( b * b * 4)\r\n#define f3 ( b * (a - b) * 8 )\r\n#define f4 n*m - f8 - f6 - f2 - f3\r\n\r\nclass HyperKnight {\r\npublic:\r\n  long long countCells(LL a, LL b, LL n, LL m, int k) {\r\n\r\n        if (a < b) swap(a, b);\r\n        if (n < m) swap(n, m);\r\n\r\n        if (k == 8) return f8;\r\n        else if (k == 6) return f6;\r\n        else if (k == 4) return f4;\r\n        else if (k == 3) return f3;\r\n        else if (k == 2) return f2;\r\n\r\n    return 0;\r\n  }\r\n};\r\n<\/pre>\n
500. HatRack<\/h2>\n
Brief description: <\/h3>\n
\u3002\u5927\u6982\u5c31\u662f\u56fa\u5b9a\u8fb9\u3002\u3002\u95ee\u5408\u6cd5\u7684\u5b8c\u5168\u4e8c\u53c9\u6811\u65b9\u6848\u6709\u591a\u5c11\u79cd\u3002\u3002\u3002<\/p>\n
Analysis: <\/h3>\n
\u3002\u3002\u3002\u6bd4\u8d5b\u65f6\u6211\u9519\u8bef\u7684\u8ba4\u4e3a\u6211\u53ef\u4ee5\u901a\u8fc7\u7ec4\u5408\u4e71\u641e<\/a>\u641e\u8fc7\u53bb\u3002\u3002\u7ed3\u679c fst<\/code> \u6210\u50bb\u903c\u3002\u3002
\n\u5176\u5b9e\u76f4\u63a5\u679a\u4e3e\u6839\u540e\u63a5\u8bb0\u5fc6\u5316\u641c\u7d22\u4e0d\u662f\u5f88\u65e0\u8111\u4e48\uff1f\uff01\u3002\u6c42\u653e\u8fc7ww\u3002\u3002\u3002<\/p>\n
\r\nconst int N = 52;\r\nVI adj[N]; LL dp[N][N];\r\nint n;\r\n\r\n#define lx (x<<1)\r\n#define rx (lx|1)\r\nLL f(int u, int p = 0, int x = 1){\r\n\r\n    if (x > n) return 0;\r\n\r\n    LL &res = dp[u][x]; if (res == -1){\r\n        res = 0; VI c; REP(i, SZ(adj[u])) if (adj[u][i] != p) c.PB(adj[u][i]);\r\n        if (x>n\/2) res = !SZ(c); \/\/ suppose to be a leaf ...\r\n        else if (!(n&1) &&  x==n\/2) res = SZ(c) == 1; \/\/ suppose to have one child .. .\r\n        else if (SZ(c) == 2){\r\n            res = f(c[0],u,lx)*f(c[1],u,rx) + f(c[1],u,lx)*f(c[0],u,rx);\r\n        }\r\n    }\r\n    return res;\r\n}\r\n\r\nclass HatRack {\r\npublic:\r\n    long long countWays(vector <int> knob1, vector <int> knob2) {\r\n\r\n        n = SZ(knob1) + 1; REP_1(i, n) CLR(adj[i]);\r\n\r\n        REP(i, SZ(knob1)){\r\n            int x = knob1[i], y = knob2[i];\r\n            adj[x].PB(y), adj[y].PB(x);\r\n        }\r\n\r\n        LL res = 0; REP_1(i, n){\r\n            FLC(dp, -1);\r\n            res += f(i);\r\n        }\r\n        return res;\r\n    }\r\n};\r\n<\/pre>\n
f(u, p, x)<\/code> \u8868\u793a\uff0c\u5f53\u524d\u5728 u<\/code> \u7ed3\u70b9\u3002\u7236\u4eb2\u662f p<\/code>\u3002\u3002\u5728\u5b8c\u5168\u4e8c\u53c9\u6811\u7684\u7f16\u53f7\u662f x<\/code> \u65f6\u7684\u65b9\u6848\u6570\u3002
\nhttps:\/\/gist.github.com\/lychees\/6461529<\/a><\/p>\n
500. CircusTents<\/h2>\n
Brief description: <\/h3>\n
\u3002\u3002\u7ed9\u5b9a\u4e00\u7ec4\u5706\uff0c\u627e\u51fa\u7b2c\u4e00\u4e2a\u4e0a\u7684\u4e00\u70b9\u3002\u3002\u3002\u3002
\n\u3002\u3002\u4f7f\u5f97\u8fd9\u4e2a\u70b9\u5230\u5176\u4ed6\u5706\u7684\u8ddd\u79bb\u6700\u5927\u3002\u3002\u3002\u70b9\u5230\u5706\u7684\u96c6\u5408\u7684\u8ddd\u79bb\u5b9a\u4e49\u4e3a\u5230\u96c6\u5408\u4e2d\u6700\u8fd1\u7684\u5706\u7684\u8ddd\u79bb\u3002\u3002
\n\u3002\u3002\u6c42\u8fd9\u4e2a\u8ddd\u79bb\u3002\u3002\u3002<\/p>\n
Analysis: <\/h3>\n
\u3002\u3002\u3002\u9996\u5148\u6765\u5206\u6790\u4e00\u4e2a\u5706\u7684\u60c5\u51b5\u3002\u3002<\/p>\n
\"\"\/<\/a><\/p>\n
\u3002\u3002\u4e00\u56fe\u6d41\u3002\u3002<\/p>\n
\u3002\u3002\u9996\u5148\u70b9\u5230\u5706\u7684\u8ddd\u79bb\u5c31\u662f\u8fde\u5fc3\u7ebf\u7684\u957f\u5ea6\u51cf\u53bb\u534a\u5f84\u3002\u3002\u3002\u5982\u679c\u8fde\u5fc3\u7ebf\u4e0d\u88ab\u906e\u6321\u7684\u8bdd\u90a3\u4e48\u5c31\u662f\u8fd9\u4e2a\u3002\u3002\u3002\u5426\u5219\u7684\u8bdd\u3002\u3002\u8981\u5148\u4ece\u5706\u540e\u540e\u7ed5\u4e00\u6bb5\u5f27\u3002\u3002
\n\u3002\u3002\u3002\u603b\u4e4b\u4e5f\u5c31\u662f\u8fd9\u4e24\u79cd\u60c5\u51b5\u800c\u5df2\u3002\uff01\uff01\u3002\u3002\u3002\u4e0d\u7ba1\u6211\u4eec\u540e\u9762\u662f\u4e8c\u5206\u8fd8\u662f\u4e09\u5206\u3002\u3002\u3002\u8fd9\u4e2a\u5b50\u51fd\u6570\u90fd\u8981\u5148\u5199\u4e0a\u3002\u3002\u3002\u3002\u3002
\n\u3002\u3002\u3002\u4e3a\u4e86\u5199\u7684\u723d\u3002\u3002\u3002\u3002\u5148\u628a\u7b2c\u4e00\u4e2a\u5706\u5706\u5fc3\u79fb\u52a8\u5230\u539f\u70b9\u3002\u3002\u3002\u5176\u4ed6\u5706\u7684\u5706\u5fc3\u901a\u901a\u65cb\u8f6c\u5230 x<\/code> \u8f74\u4e0a\u3002\u3002\u3002\u5e76\u8bb0\u5f55\u65cb\u8f6c\u89d2 a<\/code>\u3002\u5206\u6c34\u5cad\u89d2\u4e3a p<\/code>\u3002\u3002\u3002<\/p>\n
\r\nstruct Circle{\r\n    Po o; DB r, a, p; \/\/ \u521d\u59cb\u65cb\u8f6c\u89d2\u3001\u5206\u6c34\u5cad\u89d2\r\n    Circle(cPo o=Po(),DB r=0):o(o),r(r){}\r\n    DB d(DB x){\r\n        if (x < p) return dist(R*Po(cos(x), sin(x)), o) - r;\r\n        return R*(x-p) + sqrt(o.len2() - sqr(R)) - r;\r\n    }\r\n} C[N];\r\n<\/pre>\n
\u3002\u3002\u4e0b\u9762\u8003\u8651\u591a\u5706\u60c5\u51b5\u3002\u3002<\/p>\n
\u3002\u3002\u3002\u3002\u591a\u5706\u60c5\u51b5\u4f3c\u4e4e\u975e\u5e38\u6076\u5fc3\u3002\u3002\u56e0\u4e3a\u5f88\u53ef\u80fd\u88ab\u5404\u79cd\u906e\u6321\u3002\u3002\u3002\u4f46\u662f\u5b9e\u9645\u4e0a\u4e00\u65e6\u8981\u53d1\u751f\u906e\u6321\u3002\u3002\u90a3\u4e48\u8fd9\u4e2a\u5706\u80af\u5b9a\u4e0d\u662f\u5173\u952e\u5706\u3002\u3002\u5ffd\u7565\u90fd\u884cww\u3002\u3002\u3002\u3002<\/p>\n
\u7b97\u6cd5\u4e00\uff1a\u4e8c\u5206<\/h4>\n
\"\"\/<\/a><\/p>\n
\u3002\u3002\u9996\u5148\u4e8c\u5206\u7b54\u6848\u3002\u3002\u7136\u540e\u5bf9\u4e8e\u6bcf\u4e2a\u5706\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u5f27\u5ea6\u533a\u95f4\u3002\u3002\u6211\u4eec\u77e5\u9053d() \u51fd\u6570<\/code>\u5177\u6709\u5355\u8c03\u6027\u3002\u3002\u6240\u4ee5\u4e8c\u5206\u5f97\u5230\u6bcf\u4e2a\u5706\u5bf9\u5e94\u7684\u533a\u95f4\u3002\u3002\u3002\u4e4b\u540e\u8dd1\u626b\u63cf\u7ebf\u770b\u4ea4\u96c6\u662f\u5426\u4e3a\u7a7a\u3002\u3002<\/p>\n
\u3002\u3002\u56e0\u4e3a atan2()<\/code> \u7684\u8fd4\u56de\u533a\u95f4\u662f (-PI, PI]<\/code>\u3002\u3002\u3002\u6240\u4ee5\u6211\u901a\u5e38\u559c\u6b22\u628a\u5f27\u5ea6\u6620\u5c04\u5230\u8fd9\u4e2a\u533a\u95f4\u3002\u3002\u3002\u6ce8\u610f\u5f97\u5230\u7684\u5f27\u5ea6\u662f\u4ece (PI+l -> PI-l)<\/code>\u3002\u3002\u522b\u5fd8\u4e86\u52a0\u4e0a\u5f00\u59cb\u7684\u65cb\u8f6c\u3002\u3002
\n\u3002\u3002PI \u53cd\u6b63\u5927\u5bb6\u90fd\u6709\u3002\u5e72\u8106\u53bb\u6389\u3002\u3002\u3002\u6700\u7ec8\u52a0\u5165\u7684\u533a\u95f4\u5c31\u662f (a+l -> a-l)<\/code>\u3002\u3002\u3002
\nhttps:\/\/gist.github.com\/lychees\/6460116#file-1-cpp<\/a><\/p>\n
\u7b97\u6cd5\u4e8c\uff1a\u4e09\u5206<\/h4>\n
\u3002\u3002\u8fd9\u4e2a\u9898\u3002\u3002\u3002\u5c0f\u533a\u95f4\u679a\u4e3e\u76f4\u63a5\u4e09\u5206\u597d\u50cf\u4e5f\u80fd\u8fc7\u3002\u3002\u3002\u3002\u5927\u6982\u56e0\u4e3ad() \u51fd\u6570<\/code>\u51f8\u6027\u6bd4\u8f83\u5f3a\u3002\u3002 \/$:^ ^
\nhttps:\/\/gist.github.com\/lychees\/6460116#file-2-cpp<\/a><\/p>\n
External link: <\/h3>\n
https:\/\/apps.topcoder.com\/wiki\/display\/tc\/SRM+559<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"","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":[17],"tags":[],"class_list":["post-816","post","type-post","status-publish","format-standard","hentry","category-topcoder"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-da","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/816","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=816"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/816\/revisions"}],"predecessor-version":[{"id":817,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/816\/revisions\/817"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=816"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=816"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=816"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}