{"id":1191,"date":"2015-07-26T04:27:27","date_gmt":"2015-07-25T20:27:27","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1191"},"modified":"2015-10-09T02:04:25","modified_gmt":"2015-10-08T18:04:25","slug":"bzoj-2434-noi2011%e9%98%bf%e7%8b%b8%e7%9a%84%e6%89%93%e5%ad%97%e6%9c%ba","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-2434-noi2011%e9%98%bf%e7%8b%b8%e7%9a%84%e6%89%93%e5%ad%97%e6%9c%ba\/","title":{"rendered":"BZOJ 2434. [Noi2011]\u963f\u72f8\u7684\u6253\u5b57\u673a"},"content":{"rendered":"<p><a href=\"http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=2434\">http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=2434<\/a><\/p>\n<h3>Brief description:<\/h3>\n<p>&#8230;  \u8981\u6c42\u4f60\u7ef4\u62a4\u4e00\u7ec4\u5b57\u7b26\u4e32\u3001\u548c\u4e00\u4e2a\u6587\u672c\u6846\u3002\u3002\u652f\u6301\u4e0b\u5217\u64cd\u4f5c\uff1a<\/p>\n<ul>\n<li>\u8f93\u5165\u4e00\u4e2a\u5c0f\u5199\u5b57\u6bcd\u3002<\/li>\n<li>\u9000\u683c\u3002<\/li>\n<li>\u4fdd\u5b58\u5f53\u524d\u6587\u672c\u6846\u4e2d\u7684\u5b57\u7b26\u4e32\u3002<\/li>\n<li>\u8be2\u95ee\u7b2c <code>x<\/code> \u4e2a\u4fdd\u5b58\u7684\u5b57\u7b26\u4e32\uff0c\u5728\u7b2c <code>y<\/code> \u4e2a\u4fdd\u5b58\u7684\u5b57\u7b26\u4e32\u4e2d\uff0c\u51fa\u73b0\u591a\u5c11\u6b21\u3002<\/li>\n<\/ul>\n<p><!--more--><\/p>\n<h3>Analysis:<\/h3>\n<p>\u6811\u72b6\u6570\u7ec4\u7ef4\u62a4 <code>fail<\/code> \u6811\u3002<\/p>\n<p>\u3002\u3002\u3002\u3002\u8003\u8651\u5df2\u7ecf\u6784\u5efa\u597d <code>ACM<\/code>\uff0c\u90a3\u4e48\u6bcf\u6b21\u8be2\u95ee\u53ef\u4ee5\u5728 <code>ACM<\/code> \u4e0a\u62fc\u5199 <code>y<\/code>\u3002\u3002\u3002<\/p>\n<p><a href=\"http:\/\/vjudge.net\/problem\/viewProblem.action?id=16405\">http:\/\/vjudge.net\/problem\/viewProblem.action?id=16405<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\ninline int Run(){\r\n        int ans = 0; RS(str), u = 0; REP_S(cur, str){\r\n            for (int t = u = v; t; t = faill&#x5B;t]) if (id&#x5B;t] == x) ++ans;\r\n        }\r\n        return ans;     \r\n} \r\n<\/pre>\n<p>\u8003\u5bdf Fail \u6811\uff0c\u4ece\u6587\u672c\u4e32\u524d\u7f00\u6240\u5728\u7684\u67d0\u4e2a\u72b6\u6001 <code>t<\/code> \u51fa\u53d1\u6cbf\u7740 fail \u6307\u9488\u5230\u6839\u7ed3\u70b9\u7684\u8def\u5f84\u4e0a\u5305\u542b <code>p<\/code>\uff08\u6a21\u5f0f\u4e32\u6240\u4ee3\u8868\u7684\u72b6\u6001\uff09\u3002\u3002<br \/>\n\u5f53\u4e14\u4ec5\u5f53 <code>t<\/code> \u5904\u5728 <code>p<\/code> \u4e3a\u6839\u7684\u5b50\u6811\u4e2d\u3002\u3002\u3002<\/p>\n<p>\u3002\u3002\u56e0\u6b64\u6211\u4eec\u8003\u8651\u79bb\u7ebf\u7528\u6811\u72b6\u6570\u7ec4\u7ef4\u62a4 fail \u6811\u7684 dfs \u5e8f\u5217\u3002\u3002\u3002<\/p>\n<p><a href=\"https:\/\/gist.github.com\/lychees\/6788733\">https:\/\/gist.github.com\/lychees\/6788733<\/a><\/p>\n<p>\u9996\u5148\u6784\u5efa\u51fa ACM &amp;&amp; fail \u6811 &amp;&amp; dfs \u5e8f\u5217\u3002\u3002 \u4e4b\u540e\u5904\u7406\u6587\u672c\u4e32 t\uff0c\u6bcf\u589e\u52a0\u4e00\u4e2a\u5b57\u7b26\uff0c\u5c31\u6807\u8bb0\u4e00\u4e0b\u5f53\u524d\u6240\u5728\u7684\u8282\u70b9\u3002<br \/>\n\u6bcf\u6b21\u8be2\u95ee <code>p<\/code> \u65f6\u5019\u3002\u3002\u770b\u6a21\u5f0f\u4e32 <code>p<\/code> \u6240\u5bf9\u5e94\u7684\u5b50\u6811\u88ab\u6807\u8bb0\u7684\u6b21\u6570\u5373\u53ef\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n   Init(); int ti = 0; u = 0; REP(i, cn) switch (cmd&#x5B;i]){\r\n        case 'P':\r\n            ECH(it, qry&#x5B;ti]) ans&#x5B;it-&gt;fi] = Sum(L&#x5B;pos&#x5B;it-&gt;se]], R&#x5B;pos&#x5B;it-&gt;se]]);\r\n            ++ti;\r\n            break;\r\n        case 'B':\r\n            Add(L&#x5B;u], -1);\r\n            u = p;\r\n            break;\r\n        default:\r\n            Add(L&#x5B;u = v], 1);\r\n    }\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=2434 Brief description: &#8230; \u8981\u6c42\u4f60\u7ef4\u62a4\u4e00\u7ec4\u5b57\u7b26\u4e32\u3001\u548c\u4e00\u4e2a\u6587\u672c\u6846\u3002\u3002\u652f\u6301\u4e0b\u5217\u64cd\u4f5c\uff1a \u8f93\u5165\u4e00\u4e2a\u5c0f\u5199\u5b57\u6bcd\u3002 \u9000\u683c\u3002 \u4fdd\u5b58\u5f53\u524d\u6587\u672c\u6846\u4e2d\u7684\u5b57\u7b26\u4e32\u3002 \u8be2\u95ee\u7b2c x \u4e2a\u4fdd\u5b58\u7684\u5b57\u7b26\u4e32\uff0c\u5728\u7b2c y \u4e2a\u4fdd\u5b58\u7684\u5b57\u7b26\u4e32\u4e2d\uff0c\u51fa\u73b0\u591a\u5c11\u6b21\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":[1],"tags":[],"class_list":["post-1191","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-jd","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1191","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=1191"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1191\/revisions"}],"predecessor-version":[{"id":1192,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1191\/revisions\/1192"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}