{"id":724,"date":"2013-04-29T02:16:37","date_gmt":"2013-04-28T18:16:37","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=724"},"modified":"2013-06-22T03:33:45","modified_gmt":"2013-06-21T19:33:45","slug":"north-america-greater-ny-2012","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/north-america-greater-ny-2012\/","title":{"rendered":"North America – Greater NY 2012"},"content":{"rendered":"

\u3002\\\u7701\u8d5b\u8bad\u7ec3\u7b2c\u4e00\u5f39\/\u3002\u3002\u3002
\nhttp:\/\/acm.hust.edu.cn\/vjudge\/contest\/view.action?cid=22824#overview<\/a><\/p>\n

Problem D. Maximum Random Walk<\/h2>\n

Brief description: <\/h3>\n

\u3002\u3002\u4e00\u7ef4\u968f\u673a\u6e38\u52a8\u7cfb\u5217\u95ee\u9898\uff0c\u5411\u53f3\u7684\u6982\u7387\u4e3a r\uff0c\u5411\u5de6\u7684\u6982\u7387\u4e3a l\uff0c\u9759\u6b62\u7684\u6982\u7387\u4e3a s\u3002
\n\u8be2\u95ee n \u6b65\u540e rightmost (\u5386\u53f2\u4e0a\u7684\u6700\u53f3\u4f4d\u7f6e) \u7684\u671f\u671b\u3002<\/p>\n

<\/p>\n

Analysis: <\/h3>\n

… \u6bd4\u8d5b\u65f6\u53ea\u60f3\u5230 O(n3) \u7684\u505a\u6cd5\u3002\u3002\uff08dp[\u7b2ci\u6b65][rightmost \u4f4d\u7f6e][current \u4f4d\u7f6e]\u3002\u3002\u3002
\n\u3002\u770b\u5230 n = 1000\u3002\u3002\u6ca1\u6562\u6572\u3002\u3002\u3002\u8d5b\u540e\u53d1\u73b0 HDU \u7684\u6570\u636e\u662f n = 100\u3002\u3002\u3002
\n\u3002\u3002\u4ea4\u4e0a\u53bb\u53d1\u73b0 UVa O(n3) \u4e5f\u662f\u53ef\u8fc7\u7684\u3002\u3002\u3002<\/p>\n

\u5012\u63a8\u3002\u3002\uff09<\/a>
\n\u6211\u50bb\u903c\u4e86\u3002\u3002\u987a\u63a8\u660e\u663e\u66f4\u597d\u505a\u4e00\u70b9\u3002\u3002\uff09<\/a><\/p>\n

\r\nconst int N = 1009;\r\n\r\nDB dp[2][N][2*N], l, r, s;\r\nint n;\r\n\r\nDB f(int n){\r\n    int p = 0, q = 1; RST(dp[p]); dp[p][0][0+N] = 1;\r\n\r\n    REP(i, n){\r\n        swap(p, q); RST(dp[p]);\r\n#define v dp[p]\r\n#define u dp[q][j][k+N]\r\n#define jj (j==k?j+1:j)\r\n        FOR_1(j, 0, i) FOR_1(k, -i+2*j, j) if (u){\r\n            v[j][k+N] += u * s;\r\n            v[j][k-1+N] += u * l;\r\n            v[jj][k+1+N] += u * r;\r\n        }\r\n    }\r\n    swap(p, q);\r\n    DB res = 0; REP_1(j, n) FOR_1(k, -n+2*j, j) res += u * j;\r\n    return res;\r\n}\r\n<\/pre>\n
Problem F. The King’s Ups and Downs<\/h2>\n
Brief description: <\/h3>\n
A001250: Number of alternating permutations of order n. <\/a>
\n(n <= 20)\n\n\n
Analysis: <\/h3>\n
\u3002\u3002\u3002\u76f4\u63a5\u5206\u6790 A000111<\/a> \u5427\u3002\u3002\u3002
\n… \u3002\u3002\u3002\u6bd4\u8d5b\u65f6\u5f53\u7136\u662f SCDP<\/a> \u4ea4\u4e86\u4e2a\u8868\u3002\u3002
\n\u3002\u3002\u3002\uff08\u3002\u3002\u7136\u540e\u8fd9\u4e2a\u5e8f\u5217\u662f\u975e\u5e38\u4f18\u7f8e\u7684\u3002\u3002\u6307\u6570\u751f\u6210\u51fd\u6570\u5c31\u662f sec x + tan x \u3002\u3002|| \uff09\u3002\u3002\u3002<\/p>\n
\u2014\u2014\u2014\u2014\u2014\u2014 UPD \u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014
\n\u3002\u3002\u3002niuox \u521a\u521a\u544a\u8bc9\u6211\u8fd9\u9898\u6839\u672c\u4e0d\u7528\u72b6\u6001\u538b\u7f29\u3002\u3002\u76f4\u63a5 O(n2) DP<\/a> \u5c31\u597d\u3002\u3002\u3002\u3002\uff08<\/p>\n
http:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=1117603<\/a><\/p>\n
F[\u957f\u5ea6][\u672b\u5c3e] \u3002\u3002\u672b\u4e24\u4f4d\u9012\u589e\u7684\u65b9\u6848\u6570\u3002\u3002\u672b\u4e24\u4f4d\u9012\u51cf\u7684\u65b9\u6848\u6570\u53ef\u4ee5\u955c\u50cf\u5f97\u5230\u3002\u3002\u3002
\n\u3002\u3002\u7136\u540e\u5728\u63a8 F[][] \u7684\u8fc7\u7a0b\u4e2d\u4e4b\u6240\u4ee5\u53ea\u9700\u8981\u77e5\u9053\u672b\u5c3e\u7684\u6570\u5b57\u662f\u591a\u5c11\u3002\u3002\u56e0\u4e3a\u524d\u9762\u5927\u4e8e\u7b49\u4e8e\u672b\u5c3e\u6570\u5b57\u7684\u503c\u3002\u3002\u90fd\u53ef\u4ee5 +1\u3002\u3002\u7136\u540e\u7ed3\u6784\u4e0d\u53d8\u3002\u3002<\/p>\n
dp[i][j] \u8868\u793a\u957f\u5ea6\u4e3ai\u4ee5j\u7ed3\u5c3e\u7684\u5408\u6cd5\u7684\u6392\u5217\u4e2a\u6570\uff08\u75311…i\u7ec4\u6210\u7684\u6392\u5217\uff09\u3002
\n\u8fd8\u8981\u6e05\u695a\u4e00\u4e2a\u7ed3\u8bba\uff1a
\n\u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3ai-1\u7684\u5b57\u7b26\u4e32\uff0c\u7531{1,2,…,i}\u7ec4\u6210\u7684\u5408\u6cd5\u6392\u5217\u6570\u548c\u7531{1,2,…,j-1,j+1,…,i+1}
\n\u7ec4\u6210\u7684\u5408\u6cd5\u6392\u5217\u6570\u662f\u76f8\u540c\u7684\u3002<\/p>\n
\u2014\u2014\u2014\u2014\u2014\u2014 http:\/\/blog.csdn.net\/morgan_xww\/article\/details\/6847305<\/a>\n<\/p><\/blockquote>\n
\u3002\u3002\uff08\u3002\u3002\u8fd9\u4e0d\u5c31\u662f 2011 Dalian Regional Onsite \u7684 Problem E<\/a> \u4e48= =\u3002\u3002\u3002<\/p>\n
\r\nconst int N = 22;\r\n\r\nLL A[N], F[N][N];\r\nint n;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    A[1] = F[1][0] = 1; FOR_1_N(n, 2, 20){\r\n        REP(i, n) A[n] += F[n][i] = F[n-1][n-i-1] + F[n][i-1];\r\n        A[n] *= 2;\r\n    }\r\n\r\n    Rush{\r\n        RD(Case, n);\r\n        printf(&quot;%d %lld\\n&quot;, Case, A[n]);\r\n    }\r\n}\r\n<\/pre>\n
Problem G. Mad Veterinarian<\/h2>\n
Brief description: <\/h3>\n
\u3002\u3002\u3002\u7ed9\u5b9a\u4e00\u4e9b\u7269\u8d28\u8f6c\u6362\u673a\u5668\u3002\u3002
\n{S1} <=> {S2}\u3002\u3002 ( \u53ef\u4ee5\u53cd\u8fc7\u6765\u7528\u3002\u3002
\n\u3002\u3002\u3002\u95ee\u4ece\u521d\u59cb\u96c6\u5408\u5230\u76ee\u6807\u96c6\u5408\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u3002\u3002\u5e76\u8f93\u51fa\u65b9\u6848\u3002\u3002\uff08\u591a\u91cd\u96c6\u3002\u3002\u3002<\/p>\n
Analysis: <\/h3>\n
\u3002\u3002\u3002\u6570\u636e\u8303\u56f4\u5f88\u5c0f\u3002\u3002\u3002 bfs() \u5373\u53ef\u3002\u3002
\n\uff08\u867d\u7136\u8fd9\u79cd\u9898\u4e0a\u754c\u4e0d\u597d\u4f30\u8ba1\u3002\u3002\u53ea\u80fd\u5c3d\u91cf\u53d6\u7684\u5927\u4e00\u4e9b\u3002\u3002= =\u3002\u3002
\n\uff08\u7136\u540e\u4e00\u76f4\u6ca1\u8bfb\u51fa\u6765\u3002\u3002\u662f\u8981\u6070\u597d\u8fbe\u5230\u76ee\u6807\u96c6\u5408\u3002\u3002\u8fd8\u662f >= \u5c31\u884c\u3002\u3002\u8dd1\u51fa\u6837\u4f8b\u624d\u80fd\u77e5\u9053\u3002||\u3002\u3002\u3002<\/p>\n
http:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=1112918<\/a>
\n\u6bd4\u8d5b\u65f6\u4ea4\u4e86\u516b\u4e5d\u53d1\u3002\u3002\u3002\u8d5b\u540e\u4ea4\u5230 HDU \u5c31\u8fc7\u4e86\u3002\u3002\u3002\u597d\u50cf UVa \u8fd9\u9898\u7684\u6570\u636e\u662f\u6709\u95ee\u9898\u7684\u3002\u3002||<\/p>\n
External link: <\/h3>\n","protected":false},"excerpt":{"rendered":"
\u3002\\\u7701\u8d5b\u8bad\u7ec3\u7b2c\u4e00\u5f39\/\u3002\u3002\u3002 http:\/\/acm.hust.edu.cn\/vjudge\/contest\/view.action?cid=22824#overview Problem D. Maximum Random Walk Brief description: \u3002\u3002\u4e00\u7ef4\u968f\u673a\u6e38\u52a8\u7cfb\u5217\u95ee\u9898\uff0c\u5411\u53f3\u7684\u6982\u7387\u4e3a r\uff0c\u5411\u5de6\u7684\u6982\u7387\u4e3a l\uff0c\u9759\u6b62\u7684\u6982\u7387\u4e3a s\u3002 \u8be2\u95ee n \u6b65\u540e rightmost (\u5386\u53f2\u4e0a\u7684\u6700\u53f3\u4f4d\u7f6e) \u7684\u671f\u671b\u3002<\/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":[15],"tags":[],"class_list":["post-724","post","type-post","status-publish","format-standard","hentry","category-online"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-bG","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/724","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=724"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/724\/revisions"}],"predecessor-version":[{"id":725,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/724\/revisions\/725"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=724"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=724"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=724"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}