{"id":1231,"date":"2015-12-15T01:52:01","date_gmt":"2015-12-14T17:52:01","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1231"},"modified":"2015-12-15T05:30:16","modified_gmt":"2015-12-14T21:30:16","slug":"jag-spring-contest-2015","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/jag-spring-contest-2015\/","title":{"rendered":"JAG Spring Contest 2015"},"content":{"rendered":"<p><a href=\"http:\/\/jag2015spring.contest.atcoder.jp\/assignments\">\u63d0\u4ea4\u5730\u5740<\/a><\/p>\n<h2>Overview:<\/h2>\n<p>\u505a ASC 42 \u7684 B \u9898\u7684\u65f6\u5019\u9047\u5230\u7684\u95ee\u9898\u3002\u3002\u3002ASC 42 \u7684\u9898\u76ee\u662f\uff1a<br \/>\n\u521d\u59cb\u6709 m \u5143\u94b1\uff0c\u76ee\u6807\u662f\u6070\u597d\u62e5\u6709 n \u5143\u94b1<br \/>\n\u6bcf\u8f6e\u4f60\u53ef\u4ee5\u538b\u81f3\u591a\u5f53\u524d\u4f60\u6240\u62e5\u6709\u7684\u94b1\u6570\u8fdb\u884c\u8d4c\u535a\uff0cp \u7684\u6982\u7387\u7ffb\u500d\uff0cq \u7684\u6982\u7387\u5931\u53bb\u8d4c\u6ce8\u3002<br \/>\n\u81f3\u591a\u8fdb\u884c t \u4e2a\u56de\u5408\uff0c\u95ee\u6700\u4f18\u7b56\u7565\u4e0b\u8fbe\u5230\u76ee\u6807\u7684\u6982\u7387\u3002<br \/>\n(t &lt;= 300, p &lt; 50\u3002)<\/p>\n<p>YY \u4e86\u4e00\u4e0b\u7ed3\u8bba\uff0c\u5047\u8bbe\u5f53\u524d\u6709 m \u5143\u94b1\uff0c\u6bcf\u6b21\u538b min(m, n-m) \u5c31\u53ef\u4ee5\u4e86\u3002<br \/>\n\u52a0\u4e4b\u9898\u76ee\u9650\u5236\u5f88\u5f3a\uff0c\u6a21\u62df DP \u4e00\u4e0b\u5c31\u51fa\u6765\u4e86\u3002\u5728 camp \u7fa4\u91cc\u9042\u95ee\u4e86\u4e00\u4e0b p >= 50 \u7684\u60c5\u51b5\u4e0b\u7ed3\u8bba\u8fd8\u6210\u7acb\u5417\u3002\u3002<br \/>\n\u679c\u7136\u6709\u5b8c\u6574\u7248\u7684\u9898\u76ee\u3002<\/p>\n<p><!--more--><\/p>\n<hr \/>\n<p>Problem C. Casino<br \/>\n\u521d\u59cb\u6709 m \u5143\u94b1\uff0c\u76ee\u6807\u662f\u62e5\u6709 >= n \u5143\u94b1\uff0c<br \/>\n\u6bcf\u8f6e\u4f60\u53ef\u4ee5\u538b\u81f3\u591a\u5f53\u524d\u4f60\u6240\u62e5\u6709\u7684\u94b1\u6570\u8fdb\u884c\u8d4c\u535a\uff08\u5fc5\u987b\u6574\u6570\uff09\uff0cp \u7684\u6982\u7387\u7ffb\u500d\uff0c(1-p) \u7684\u6982\u7387\u5931\u53bb\u8d4c\u6ce8\u3002<br \/>\n\u95ee\u6700\u4f18\u7b56\u7565\u4e0b\u8fbe\u5230\u76ee\u6807\u7684\u6982\u7387\uff0c\u4ee5\u53ca\u6240\u6709\u5408\u6cd5\u7684\u7b2c\u4e00\u6b65\u7684\u65b9\u6848\uff08\u8d85\u8fc7 200 \u4e2a\u53ea\u9700\u8f93\u51fa\u6700\u5927\u548c\u6700\u5c0f\u7684 100 \u4e2a\uff09\u3002<br \/>\n\uff080 &lt;= p &lt;= 1, 0 &lt; m &lt; n &lt;= 10^9)<\/p>\n<p>\u9996\u5148\u7279\u5224\u6389 p = 1 \u6216 p = 0 \u7684\u8fb9\u754c\u60c5\u51b5\u3002\uff08\u7531\u4e8e\u7ed3\u5c40\u56fa\u5b9a\uff0c\u6240\u4ee5 [1, m] \u90fd\u662f\u5408\u6cd5\u89e3\uff0c\u5373\u4f7f\u52a0\u4e0a\u53bb\u4f1a\u8d85\u8fc7 n\u3002\uff09<br \/>\n\u8003\u8651\u548c ASC \u90a3\u9898\u7684\u4e3b\u8981\u4e0d\u540c\uff0c\u4e3b\u8981\u662f\u6570\u636e\u8303\u56f4\u53d8\u5927\uff0c\u5e76\u4e14\u6ca1\u6709\u4e86\u538b\u4f4f\u6b21\u6570\u7684\u9650\u5236\u3002<br \/>\n\u90a3\u4e48\u9996\u5148\u8003\u8651 p = 0.5 \u7684\u60c5\u51b5\uff0c\u6bcf\u8f6e\u8d4c\u6ce8\u7684\u671f\u671b\u6536\u76ca\u90fd\u4e3a 0\uff0c\uff08\u4e0e\u538b\u591a\u5c11\u65e0\u5173\uff09\u3002<br \/>\n\u6839\u636e<a href=\"https:\/\/zh.wikipedia.org\/wiki\/%E9%9E%85_(%E6%A6%82%E7%8E%87%E8%AE%BA)\">\u9785\u8bba<\/a>\u4e2d\u7684\u53ef\u9009\u505c\u6b62\u5b9a\u7406\u3002\u505c\u65f6\u7684\u9785\u7684\u671f\u671b\u503c\u7b49\u4e8e\u5176\u521d\u59cb\u503c\uff0c\u56e0\u800c\u5728 n \u7ec8\u6b62\u7684\u6982\u7387\u4e3a m\/n\u3002<br \/>\n\uff08\u6240\u6709 [1, min(m, n-m)] \u7684\u503c\u90fd\u4e3a\u5408\u6cd5\u89e3\uff09<\/p>\n<p>\u53e6\u5916\u4e24\u79cd\u60c5\u51b5\uff0c\u76f4\u89c2\u7684\u770b\u4e0a\u53bb\u3002\u3002\u3002<\/p>\n<ul>\n<li>p > 0.5 \u65f6\uff0c\u5e73\u5747\u8d77\u6765\uff0c\u8d4c\u5f92\u8d62\u4e86\u94b1\uff0c\u5219\u968f\u7740\u65f6\u95f4\u7684\u6d41\u901d\uff0c\u8d4c\u5f92\u7684\u8d22\u4ea7\u662f\u4e00\u4e2a\u4e0b\u9785\u3002<br \/>\n\u56e0\u800c\u6211\u4eec\u5e0c\u671b\u91c7\u53d6\u4e00\u79cd \u201c\u6b65\u6b65\u4e3a\u8425\u201d \u7684\u7b56\u7565\uff0c\u6eda\u96ea\u7403\uff0c\u6162\u6162\u7684\u79ef\u7d2f\u81ea\u5df1\u7684\u4f18\u52bf\u3002<br \/>\n\uff08\u76f4\u611f\uff1a\u671f\u5f85\u5024\u7684\u306b\u306f\u826f\u3044\u308f\u3051\u3060\u304b\u3089\u9577\u6642\u9593\u3084\u3063\u3066\u308c\u3070\u52dd\u3066\u308b\u3063\u3057\u3087\uff01\uff09\n<\/li>\n<li>p < 0.5 \u65f6\uff0c\u5e73\u5747\u8d77\u6765\uff0c\u8d4c\u5f92\u8f93\u4e86\u94b1\uff0c\u5219\u968f\u7740\u65f6\u95f4\u7684\u6d41\u901d\uff0c\u8d4c\u5f92\u7684\u8d22\u4ea7\u662f\u4e00\u4e2a\u4e0a\u9785\u3002 \n\u56e0\u800c\u6211\u4eec\u5e0c\u671b\u91c7\u53d6\u4e00\u79cd \u201c\u5b81\u4e3a\u7389\u788e\u201d \u7684\u7b56\u7565\uff0c\u4e00\u5c0f\u535a\u5927\uff0c\u53bb\u5e0c\u5180\u6bd5\u5176\u529f\u4e8e\u4e00\u5f79\uff01\n\uff08\u76f4\u611f\uff1a\u671f\u5f85\u5024\u7684\u306b\u4e0d\u5229\u3060\u304b\u3089\u9577\u5f15\u304f\u3068\u30b8\u30ea\u8ca7\uff0c\u308f\u3093\u3061\u3083\u3093\u72d9\u3063\u3066\u3044\u304f\u3057\u304b\u306a\u3044\uff01\uff09\n<\/li>\n<\/ul>\n<p>\u56e0\u800c\u524d\u8005\u6211\u4eec\u6bcf\u6b21\u53ea\u538b 1\uff0c\u540e\u8005\u6211\u4eec\u6bcf\u6b21\u538b min(m, n-m)\u3002<\/p>\n<p>\u3002\u3002\u3002Is that true?&#8230;<\/p>\n<p>\u5148\u8bc1\u660e\u524d\u8005\u3002\u3002<br \/>\n\u4ee4 $$q = 1-p, r = \\frac{q}{p}, f_x $$ \u8868\u793a\u5f53\u524d\u6709 $$x$$ \u65f6\u7684\u671f\u671b\uff0c\u5047\u8bbe\u6bcf\u6b21\u53ea\u538b 1\uff0c\u6211\u4eec\u6709\uff1a<br \/>\nf[m] = pf[m+1] + qf[m-1]<br \/>\nf[0] = 1<br \/>\nf[1] = 0<\/p>\n<p>\u89e3\u5f97\uff1a$$, f_m = \\frac{1-r^m}{1-r^n}$$\u3002(\u968f\u673a\u5f98\u5f8a\u3002\u3002\u3002<\/p>\n<p>\u8003\u8651\u53cd\u8bc1\u6cd5\uff0c\u5982\u679c\u4e0d\u4e00\u5b9a\u662f\u6bcf\u6b21\u53ea\u538b 1\uff0c\u90a3\u4e48\u4e0a\u9762\u53ea\u80fd\u662f\u4e0d\u7b49\u5f0f\uff0c\u9996\u5148\u6709 $$f_m \\geq \\frac{1-r^m}{1-r^n}$$<br \/>\n\u518d\u8005\u5982\u679c\u5b58\u5728 1 \u4ee5\u5916\u7684\u6700\u4f18\u65b9\u6848\uff0c\u5047\u8bbe\u4e3a d\uff0c\u90a3\u4e48\u6709<br \/>\n $$f_m = pf_{m+d} + qf_{m-d} \\geq p\\frac{1-r^{m+d}}{1-r^n} + q\\frac{1-r^{m-d}}{1-r^n} $$<\/p>\n<p>\u3002\u3002\u3002\u6211\u4eec\u8981\u8bc1\u660e\u8fd9\u4e2a\u503c &lt; $\\frac{1-r^m}{1-r^n}$\u3002<\/p>\n<p>\u5316\u7b80\u4e00\u4e0b\u5f97\uff1a$$ 1-pr^{m+d}-qr^{m-d} &lt; 1-r^m$$\uff1f<br \/>\n\u3002\u3002\u3002\u4f46\u662f\u6211\u597d\u50cf\u63a8\u4e0d\u8fc7\u53bb\u3002\u3002\u3002<\/p>\n<p>\u6362\u4e2a\u65b9\u6cd5\u3002\u3002\u3002<\/p>\n<p>\u628a d \u7684\u60c5\u51b5\u770b\u4f5c\u662f\u82e5\u5e72 1 \u7684\u60c5\u51b5\u53e0\u52a0\u6210\u7684\uff08+-d \u65f6\u505c\u6b62\uff09\u3002\u3002<br \/>\n\u90a3\u4e48\u4e3a\u4e86\u5f97\u5230 +d\uff0c\u6211\u4eec\u8981\u4e48\u4e00\u6b65\u8d70\u8fc7\u53bb p\u3002<br \/>\n\u8981\u4e48\u901a\u8fc7\u82e5\u5e72 1 \u7684\u60c5\u51b5\u53e0\u52a0\u8fc7\u53bb\u3002\u3002\u3002($$\\frac{1-r^d}{1-r^{2d}}$$)<br \/>\n\u901a\u8fc7\u4e00\u4e9b\u5fae\u79ef\u5206\u7684\u77e5\u8bc6\u3002\u3002\u3002\uff08<a href=\"http:\/\/www.wolframalpha.com\/input\/?i=%281-%28%281-p%29%2Fp%29%5E2%29+-+%281-%28%281-p%29%2Fp%29%5E%284%29%29+p\">http:\/\/www.wolframalpha.com\/input\/?i=%281-%28%281-p%29%2Fp%29%5E2%29+-+%281-%28%281-p%29%2Fp%29%5E%284%29%29+p<\/a>&#8230;<\/p>\n<p>\u53ef\u4ee5\u63a8\u65ad\u51fa\u540e\u8005\u5728 p>1\/2 \u7684\u60c5\u51b5\u4e0b\u662f\u5927\u4e8e p \u7684\u3002\u3002<br \/>\n\u56e0\u800c\u6b64\u65f6\u6700\u4f18\u65b9\u6848\u4e3a 1\u3002<\/p>\n<p>Problem L. Wall Making Game<\/p>\n<p>https:\/\/discuss.codechef.com\/questions\/26237\/caos3-editorial<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(20) + 9;\r\nchar Board&#x5B;N]&#x5B;N]; int SG&#x5B;N]&#x5B;N]&#x5B;N]&#x5B;N];\r\nint h, w;\r\n\r\nint sg(int x0, int y0, int x1, int y1){\r\n    \r\n    int &amp;z = SG&#x5B;x0]&#x5B;y0]&#x5B;x1]&#x5B;y1];\r\n    \r\n    if (z == -1){\r\n        if (x0 &gt;= x1 || y0 &gt;= y1) z = 0;\r\n        else{\r\n            set&lt;int&gt; H; FOR(x, x0, x1) FOR(y, y0, y1){\r\n                if (Board&#x5B;x]&#x5B;y] == '.'){\r\n                    H.insert(sg(x0, y0, x, y) ^ sg(x0, y+1, x, y1) ^\r\n                         sg(x+1, y0, x1, y) ^ sg(x+1, y+1, x1, y1)) ;\r\n                }\r\n            }\r\n    \r\n            REP(i, H.size()+1) if (H.find(i) == H.end()){\r\n                z = i;\r\n                break;\r\n            }\r\n        }\r\n    }\r\n    return z;\r\n}\r\n\r\n\r\nint main(){\r\n    \r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen(&quot;\/users\/xiaodao\/desktop\/Exercise\/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    while (cin &gt;&gt; h &gt;&gt; w){\r\n        REP(i, h) scanf(&quot;%s&quot;, Board&#x5B;i]); FLC(SG, -1);\r\n        puts(sg(0, 0, h, w) ? &quot;First&quot; : &quot;Second&quot;);\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u63d0\u4ea4\u5730\u5740 Overview: \u505a ASC 42 \u7684 B \u9898\u7684\u65f6\u5019\u9047\u5230\u7684\u95ee\u9898\u3002\u3002\u3002ASC 42 \u7684\u9898\u76ee\u662f\uff1a \u521d\u59cb\u6709 m \u5143\u94b1\uff0c\u76ee\u6807\u662f\u6070\u597d\u62e5\u6709 n \u5143\u94b1 \u6bcf\u8f6e\u4f60\u53ef\u4ee5\u538b\u81f3\u591a\u5f53\u524d\u4f60\u6240\u62e5\u6709\u7684\u94b1\u6570\u8fdb\u884c\u8d4c\u535a\uff0cp \u7684\u6982\u7387\u7ffb\u500d\uff0cq \u7684\u6982\u7387\u5931\u53bb\u8d4c\u6ce8\u3002 \u81f3\u591a\u8fdb\u884c t \u4e2a\u56de\u5408\uff0c\u95ee\u6700\u4f18\u7b56\u7565\u4e0b\u8fbe\u5230\u76ee\u6807\u7684\u6982\u7387\u3002 (t &lt;= 300, p &lt; 50\u3002) YY \u4e86\u4e00\u4e0b\u7ed3\u8bba\uff0c\u5047\u8bbe\u5f53\u524d\u6709 m \u5143\u94b1\uff0c\u6bcf\u6b21\u538b min(m, n-m) \u5c31\u53ef\u4ee5\u4e86\u3002 \u52a0\u4e4b\u9898\u76ee\u9650\u5236\u5f88\u5f3a\uff0c\u6a21\u62df DP \u4e00\u4e0b\u5c31\u51fa\u6765\u4e86\u3002\u5728 camp \u7fa4\u91cc\u9042\u95ee\u4e86\u4e00\u4e0b p >= 50 \u7684\u60c5\u51b5\u4e0b\u7ed3\u8bba\u8fd8\u6210\u7acb\u5417\u3002\u3002 \u679c\u7136\u6709\u5b8c\u6574\u7248\u7684\u9898\u76ee\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":[147],"tags":[],"class_list":["post-1231","post","type-post","status-publish","format-standard","hentry","category-jag"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-jR","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1231","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=1231"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1231\/revisions"}],"predecessor-version":[{"id":1232,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1231\/revisions\/1232"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1231"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1231"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1231"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}