{"id":975,"date":"2014-09-22T04:37:19","date_gmt":"2014-09-21T20:37:19","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=975"},"modified":"2014-09-27T03:34:56","modified_gmt":"2014-09-26T19:34:56","slug":"2014-acmicpc-asia-regional-beijing-online","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/2014-acmicpc-asia-regional-beijing-online\/","title":{"rendered":"2014 ACM\/ICPC Asia Regional Beijing Online"},"content":{"rendered":"<h2>Problem 1001. Always Cook Mushroom<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u7ed9\u5b9a\u4e00\u4e2a <code>[1, 1000] x [1, 1000]<\/code> \u7684\u70b9\u9635\uff0c\u6bcf\u4e2a\u70b9\u9635\u4e2d\u7684\u70b9\u6709\u4e00\u4e2a\u6743\u503c\u3002<br \/>\n<code>n<\/code> \u7ec4\u8be2\u95ee\uff0c\u6bcf\u6b21\u8be2\u95ee\u4e00\u4e2a\u7531 (0,0)\u3001(x,0) \u70b9\u4e00\u4ee5\u53ca\u4ece\u539f\u70b9\u51fa\u53d1\u7684\u65b9\u5411\u5411\u91cf (a,b) \u6784\u6210\u7684\u76f4\u89d2\u4e09\u89d2\u5f62\u5305\u56f4\u7684\u70b9\u7684\u6743\u503c\u548c\u3002<br \/>\n<!--more--><\/p>\n<h3>Analysis: <\/h3>\n<p>\u79bb\u7ebf\uff0c\u6781\u89d2\u6392\u5e8f\uff0c\u6811\u72b6\u6570\u7ec4\u3002<br \/>\n<a href=\"http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2788351\">http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2788351<\/a><\/p>\n<h2>Problem 1002. Building<\/h2>\n<h3>Brief description: <\/h3>\n<p>x-\u8f74\u4e0a\u5206\u5e03\u7740 n \u4e2a\u4f4d\u7f6e\u4e3a xi\uff0c\u9ad8\u5ea6\u4e3a hi \u7684\u5efa\u7b51\u7269\uff0c\u95ee\u4f4d\u7f6e\u5728 qi \u7684\u67d0\u4e2a\u4eba\uff0c\u5de6\u53f3\u7684\u89c6\u89d2\u6709\u591a\u5c11\u3002\u4eba\u7684\u9ad8\u5ea6\u4e3a 0\uff0c\u5e76\u4e14\u4e0d\u4e0e\u5efa\u7b51\u7269\u91cd\u53e0\u3002<\/p>\n<h3>Analysis: <\/h3>\n<p>\u6808\u7ef4\u62a4\u4e0b\u51f8\u58f3\u3002<\/p>\n<p><a href=\"http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2773898\">http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2773898<\/a><\/p>\n<p>\uff08\u53c2\u89c1&#8230; <a href=\"https:\/\/www.shuizilong.com\/house\/archives\/%E3%80%90%E7%AC%AC%E2%91%A8%E6%AC%A1-acdream-%E7%BE%A4%E5%8E%9F%E5%88%9B%E7%BE%A4%E8%B5%9B%E3%80%91%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A\/\">SPOJ 13031. Vision Field\/a><br \/>\n<a href=\"https:\/\/www.shuizilong.com\/house\/archives\/tsinsen-a1377-%E6%A5%BC%E6%88%BF%E9%87%8D%E5%BB%BA\/\">Tsinsen A1377. \u697c\u623f\u91cd\u5efa<\/a>\uff09<\/p>\n<h2>Problem 1005. Explosion<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u6709\u5411\u56fe\uff0c\u6bcf\u4e2a\u7ed3\u70b9\u6253\u5f00\u540e\uff0c\u53ef\u4ee5\u81ea\u52a8\u6253\u5f00\u5b83\u7684\u4f20\u9012\u95ed\u5305\u3002<br \/>\n\u95ee\u671f\u671b\u8981\u66b4\u529b\u6253\u5f00\u591a\u5c11\u7ed3\u70b9\uff0c\u53ef\u4ee5\u6253\u5f00\u6240\u6709\u7ed3\u70b9\u3002<\/p>\n<h3>Analysis: <\/h3>\n<p><a href=\"http:\/\/codeforces.ru\/problemset\/problem\/280\/C\">http:\/\/codeforces.ru\/problemset\/problem\/280\/C<\/a><br \/>\n\u505a\u6cd5\u540c\u8fd9\u4e2a\u9898\u3002\u6839\u636e\u671f\u671b\u7684\u7ebf\u6027\u6027\uff0c\u7edf\u8ba1\u6bcf\u4e2a\u7ed3\u70b9\u5bf9\u671f\u671b\u7684\u8d21\u732e\u4e3a 1 \u7684\u6982\u7387\u5373\u53ef\u3002<br \/>\n\u5f3a\u8fde\u901a\u7f29\u70b9\uff0c\u540e\u8f6c\u6362\u6210 DAG\uff0c\u90a3\u4e48\u6bcf\u4e2a\u7ed3\u70b9\u8981\u4e48\u81ea\u5df1\u6253\u5f00\u8981\u4e48\u88ab\u4e00\u4e2a\u80fd\u591f\u5230\u8fbe\u5b83\u7684\u7ed3\u70b9\u6253\u5f00\u3002<\/p>\n<p><a href=\"http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2773890\">http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2773890<\/a><\/p>\n<h2>Problem 1006. Frog<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u9752\u86d9\u8e29\u77f3\u5b50\u8fc7\u6cb3\uff0c\u6cb3\u5bbd [0, m]\uff0c\u6709 n \u4e2a\u77f3\u5b50\u5750\u6807\u5df2\u77e5\u3002\u9752\u86d9\u6bcf\u6b21\u6700\u591a\u8df3 L\uff0c\u521d\u59cb\u5728 0\u3002<br \/>\n\u73b0\u5728\u53ef\u4ee5\u5728\u6cb3\u4e2d\u518d\u653e\u4e00\u4e9b\u77f3\u5b50\uff0c\u8981\u6c42\u5728\u4fdd\u8bc1\u9752\u86d9\u53ef\u4ee5\u8df3\u5230 m \u7684\u60c5\u51b5\u4e0b\uff0c\u4f7f\u5f97\u9752\u86d9\u5728\u8df3\u7684\u6b65\u6570\u6700\u5c11\u7684\u60c5\u51b5\u4e0b\u6b21\u6570\u6700\u591a\u3002<\/p>\n<h3>Analysis: <\/h3>\n<p>\u597d\u9898\uff01<br \/>\n\u3002\u3002\u3002\u5bf9\u5df2\u7ecf\u5b58\u5728\u7684\u77f3\u5b50\u6392\u5e8f\u3002\u4ece\u524d\u5f80\u540e\u4e00\u6b21\u5904\u7406\u3002\u3002\u3002\u5982\u679c\u8fd9\u4e00\u6b65\u53ef\u4ee5\u4e00\u6b65\u8df3\u8fc7\u53bb\uff0c\u8981\u8ba8\u8bba\u662f\u5426\u9752\u86d9\u4e0a\u4e00\u6b65\u5c31\u5df2\u7ecf\u53ef\u4ee5\u8df3\u8fc7\u53bb\u4e86\u3002\uff08\u76f8\u5f53\u4e8e\u53cc\u65b9\u5728\u535a\u5f08\uff0c\u5230\u8fd9\u91cc\u4e3b\u8981\u662f\u77e5\u9053\u9700\u8981\u4fdd\u5b58\u4e0a\u4e00\u6b65\u8df3\u7684\u8ddd\u79bb ll\uff09\u3002\u3002\u5982\u679c\u4e00\u6b65\u8df3\u4e0d\u8fc7\u53bb\uff0c\u90a3\u4e48\u53ef\u4ee5\u77e5\u9053\u6bcf (l+1) \u957f\u5ea6\u81f3\u591a\u9700\u8981\u8df3\u4e24\u6b65\u3002\u8bbe\u8fd9\u4e24\u6b65\u5206\u522b\u662faa\uff0cbb\uff1a<\/p>\n<pre>\r\nll + aa = l+1\r\naa + bb = l+1\r\n<\/pre>\n<p>\u53ef\u77e5\u4e0d\u4f1a\u5f71\u54cd ll\uff0c\u90a3\u4e48\u5bf9\u76f4\u63a5\u7528\u8ddd\u79bb\u5bf9 (l+1) \u53d6\u6a21\uff0c\u53ef\u4ee5\u89c4\u7ea6\u5230\u524d\u9762\u7684\u60c5\u51b5\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5) + 9;\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    Rush{\r\n        int n, m, l; RD(n, m, l); int x = 0, ll = l, c = 0;\r\n        VI I; REP(i, n) I.PB(RD()); I.PB(m); UNQ(I); ECH(i, I){\r\n\r\n            int d = *i - x; x = *i; if (d &gt;= (l+1)){\r\n                c += d \/ (l+1) * 2;\r\n                d %= (l+1);\r\n            }\r\n\r\n            if (d + ll &lt;= l){\r\n                ll += d;\r\n            }\r\n            else{\r\n                ll = d;\r\n                ++c;\r\n            }\r\n        }\r\n        OT(c);\r\n    }\r\n}\r\n<\/pre>\n<p><a href=\"http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2788406\">http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2788406<\/a><\/p>\n<h2>Problem 1008. Hilarity<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u7ed9\u5b9a\u4e00\u68f5\u8fb9\u6743\u4e3a 0\/1 \u7684\u6811\uff0c\u8981\u6c42\u652f\u6301\u4e24\u7c7b\u64cd\u4f5c\uff1a<br \/>\n1. \u8be2\u95ee\u6709\u591a\u5c11\u6761\u8def\u5f84 xor \u548c\u4e3a 1\u3002<br \/>\n2. \u4fee\u6539\u4e00\u6761\u8fb9\u7684\u6743\u503c\u3002<\/p>\n<h3>Analysis: <\/h3>\n<p>\u3002\u3002(u, v) \u8def\u5f84\u7684 xor \u548c\u3002\u3002\u3002\u7b49\u4ef7\u4e8e (1, u) xor (1, v)\u3002\u3002<br \/>\n\u3002\u3002\u4e8e\u662f\u7528\u7ebf\u6bb5\u6811\u7ef4\u62a4\u6240\u4ee5\u4ece (1, x) \u7684\u8def\u5f84\u5c31\u53ef\u4ee5\u4e86\u3002\u3002<br \/>\n\u3002\u3002\u4fee\u6539\u64cd\u4f5c\u7b49\u4ef7\u4e8e\u533a\u95f4\u53d6\u53cd\u3002<\/p>\n<p><a href=\"http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2773880\">http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2773880<\/a><\/p>\n<h2>Problem 1009. Instrusive<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u7ed9\u5b9a\u4e00\u4e2a N*N \u7684\u683c\u5b50\uff0c\u4ece <code>M<\/code> \u5230 <code>T<\/code> \uff0c\u6709\u4e9b\u683c\u5b50\u4e2d\u6709\u521d\u59cb\u72b6\u6001\u6307\u5411\u4e1c\u897f\u5357\u5317\u7684\u6444\u50cf\u5934\uff0c\u6bcf 1s \u987a\u65f6\u9488\u8f6c\u52a8 90 \u5ea6\uff0c\u76d1\u63a7\u8303\u56f4\u4e3a\u6444\u50cf\u5934\u6240\u5728\u7684\u683c\u5b50\u548c\u5b83\u6307\u5411\u7684\u4e00\u4e2a\u683c\u5b50\u3002\u5982\u679c\u5f53\u524d\u683c\u5b50\u548c\u4e0b\u4e00\u4e2a\u683c\u5b50\u51fa\u53d1\u65f6\u523b\u90fd\u6ca1\u88ab\u76d1\uff0c\u5219\u79fb\u52a8\u7684\u4ee3\u4ef7\u662f 1s\uff0c\u5426\u5219\u79fb\u52a8\u9700\u8981 3s\u3002\u53ef\u4ee5\u7b49\u5f85\u4e0d\u52a8\uff0c\u65e0\u8bba\u5f53\u524d\u65f6\u523b\u662f\u5426\u88ab\u76d1\u63a7\uff0c\u7b49\u5f85\u7684\u4ee3\u4ef7\u90fd\u662f 1s\u3002\u6c42\u6700\u5c11\u7684\u65f6\u95f4\u3002<\/p>\n<h3>Analysis: <\/h3>\n<p>Dijkstra\uff0c\u9898\u610f\u4e0d\u662f\u5f88\u6e05\u695a\uff0c\u51e0\u4e4e\u65e0\u6cd5\u4e00\u904d AC\u3002\u3002\u3002<\/p>\n<pre>\r\n\u9898\u610f\r\n\u4f46\u4eceA\u683c\u5b50\u8d70\u5230B\u683c\u5b50\uff0c\u5176\u5b9e\u65f6\u523bAx\uff0c\u5230\u8fbeB\u7684\u65f6\u523bAx+1\uff0c\u5982\u679c\u5728Ax\u65f6\u523bAB\u683c\u5b50\u5747\u4e0d\u88ab\u7167\u4e14AB\u683c\u5b50\u5747\u4e0d\u662f\u7167\u76f8\u673a\uff0c\u4f46\u662fAx+1\u65f6\u523bB\u88ab\u7167\uff0c\u90a3\u4e48\u8fd9\u4e2a\u4ee3\u4ef7\u662f1\u8fd8\u662f3\uff1f\r\nteam0227 \u5317\u4eac\u822a\u7a7a\u822a\u5929\u5927\u5b66 at 2014-09-21 16:25:40\r\n\r\nRE:\u9898\u610f\r\n1\r\nadmin at 2014-09-21 16:27:16                 \r\n<\/pre>\n<p><a href=\"http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2784472\">http:\/\/vjudge.net\/vjudge\/problem\/viewSource.action?id=2784472<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 1001. Always Cook Mushroom Brief description: \u7ed9\u5b9a\u4e00\u4e2a [1, 1000] x [1, 1000] \u7684\u70b9\u9635\uff0c\u6bcf\u4e2a\u70b9\u9635\u4e2d\u7684\u70b9\u6709\u4e00\u4e2a\u6743\u503c\u3002 n \u7ec4\u8be2\u95ee\uff0c\u6bcf\u6b21\u8be2\u95ee\u4e00\u4e2a\u7531 (0,0)\u3001(x,0) \u70b9\u4e00\u4ee5\u53ca\u4ece\u539f\u70b9\u51fa\u53d1\u7684\u65b9\u5411\u5411\u91cf (a,b) \u6784\u6210\u7684\u76f4\u89d2\u4e09\u89d2\u5f62\u5305\u56f4\u7684\u70b9\u7684\u6743\u503c\u548c\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":[34],"tags":[],"class_list":["post-975","post","type-post","status-publish","format-standard","hentry","category-34"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fJ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/975","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=975"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/975\/revisions"}],"predecessor-version":[{"id":976,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/975\/revisions\/976"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=975"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=975"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=975"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}