{"id":950,"date":"2014-08-27T00:15:20","date_gmt":"2014-08-26T16:15:20","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=950"},"modified":"2014-08-30T11:32:15","modified_gmt":"2014-08-30T03:32:15","slug":"codeforces-round-263","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-263\/","title":{"rendered":"Codeforces Round #263"},"content":{"rendered":"<h2>Problem B. Appleman and Tree<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u7ed9\u5b9a\u4e00\u68f5\u6709\u6839\u6811\uff0c\u6bcf\u4e2a\u70b9\u6709\u9ed1\u767d\u4e24\u79cd\u989c\u8272\uff0c\u95ee\u6709\u591a\u5c11\u79cd\u6811\u7684\u5212\u5206\u65b9\u6848\uff0c<br \/>\n\u4f7f\u5f97\u6bcf\u4e2a\u8054\u901a\u5757\u4e2d\u90fd\u6070\u597d\u6709\u4e00\u4e2a\u9ed1\u8272\u7ed3\u70b9\u3002<\/p>\n<h3>Analysis: <\/h3>\n<p>\u6811 DP\uff0c\u5b50\u6811\u5408\u5e76\u3002\u8bbe\uff1a<\/p>\n<ul>\n<li>f[u] \u8868\u793a\u4ee5 u \u4e3a\u6839\u7684\u5b50\u6811\u4e2d\uff0c\u7ecf\u8fc7\u5212\u5206\u8fc7\u540e\uff0c\u4e0e u \u76f8\u8fde\u7684\u8054\u901a\u5757\u6070\u597d\u5305\u542b\u4e00\u4e2a\u9ed1\u8272\u7ed3\u70b9\u7684\u65b9\u6848\u6570\u3002<\/li>\n<li>g[u] \u8868\u793a\u4ee5 u \u4e3a\u6839\u7684\u5b50\u6811\u4e2d\uff0c\u7ecf\u8fc7\u5212\u5206\u8fc7\u540e\uff0c\u4e0e u \u76f8\u8fde\u7684\u8054\u901a\u5757\u3002\u3002\u3002\u4e0d\u5305\u542b\u9ed1\u8272\u7ed3\u70b9\u7684\u65b9\u6848\u6570\u3002<\/li>\n<\/ul>\n<p>\u8f6c\u79fb\u8ba8\u8bba\u662f\u5426\u5207\u5272 <code>(u, v)<\/code> \u8fd9\u6761\u8fb9\u5373\u53ef\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nvoid dfs(int u = 0){\r\n    ECH(it, adj&#x5B;u]){\r\n        dfs(v);\r\n        f&#x5B;u] = f&#x5B;u]*(f&#x5B;v]+g&#x5B;v]) + g&#x5B;u]*f&#x5B;v];\r\n        g&#x5B;u] *= (f&#x5B;v]+g&#x5B;v]);\r\n    }\r\n}\r\n<\/pre>\n<p>http:\/\/codeforces.com\/contest\/461\/submission\/7612452<\/p>\n<p>C:<\/p>\n<h3>Brief description: <\/h3>\n<p>\u7ed9\u5b9a\u4e00\u5f20\u7eb8\uff0c\u652f\u6301\u4e24\u4e2a\u64cd\u4f5c\uff1a\u3002<br \/>\n\u3002\u3002\u6cbf\u67d0\u4e2a\u4f4d\u7f6e\u5bf9\u6298\u3002<br \/>\n\u3002\u3002\u8be2\u95ee\u67d0\u4e2a\u533a\u95f4\u7eb8\u5f20\u7684\u4f53\u79ef\u3002<\/p>\n<h3>Analysis: <\/h3>\n<p>\u6811\u72b6\u6570\u7ec4\u3002\u5bf9\u4e8e\u6298\u53e0\u64cd\u4f5c\uff0c\u6211\u4eec\u603b\u662f\u679a\u4e3e\u8f83\u77ed\u7684\u4e00\u90e8\u5206\uff0c\u52a0\u5230\u8f83\u957f\u7684\u4e00\u90e8\u5206\u4e2d\u53bb\u3002<br \/>\n\u6bcf\u4e2a\u4f4d\u7f6e\u53ea\u4f1a\u7528\u6765\u5408\u5e76\u4e00\u6b21\u3002\u603b\u590d\u6742\u5ea6 O(nlogn)\u3002\u3002<\/p>\n<p>\u5177\u4f53\u8bf4\u6765\u6211\u4eec\u9700\u8981\u8bb0\u5f55 <code>ll<\/code>, <code>rr<\/code>, <code>rev<\/code> \u4e09\u4e2a\u503c\u3002\u3002<br \/>\n\u5206\u522b\u8868\u793a\u4e24\u4fa7\u7684\u504f\u79fb\uff0c\u4ee5\u53ca\u662f\u5426\u7ffb\u8f6c\u3002\u3002\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\n\r\nnamespace BIT{\r\n    int C&#x5B;N], n;\r\n    void Add(int x, int d){\r\n        for (;x&lt;=n;x+=low_bit(x)) C&#x5B;x] += d;\r\n    }\r\n    int Sum(int x){\r\n        int z=0;for (;x;x^=low_bit(x)) z += C&#x5B;x];\r\n        return z;\r\n    }\r\n    int Sum(int l, int r){\r\n        return Sum(r) - Sum(l-1);\r\n    }\r\n    int At(int x){\r\n        int z=C&#x5B;x],p=low_bit(x);for (--x;x&amp;&amp;low_bit(x)&lt;p;x^=low_bit(x)) z -= C&#x5B;x];\r\n        return z;\r\n    }\r\n} using namespace BIT;\r\n\r\nbool rev; int ll, rr;\r\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#define len (rr-ll+1)\r\n#define pp (2*p)\r\n\r\n    REP_1_C(i, RD(n)) Add(i, 1); ll=1,rr=n;rev=0; Rush{\r\n        if (RD()==1){ \/\/ Fold\r\n            int p; RD(p); if (pp&lt;=len){\r\n                if (!rev){\r\n                    REP_1(i, p) Add(ll+pp-i, At(ll+i-1)); ll += p;\r\n                }\r\n                else{\r\n                    REP_1(i, p) Add(rr-pp+i, At(rr-i+1)); rr -= p;\r\n                }\r\n            }\r\n            else{\r\n                rev ^= 1; p=len-p; if (!rev){\r\n                    REP_1(i, p) Add(ll+pp-i, At(ll+i-1)); ll += p;\r\n                }\r\n                else{\r\n                    REP_1(i, p) Add(rr-pp+i , At(rr-i+1)); rr -= p;\r\n                }\r\n            }\r\n        }\r\n        else{ \/\/ Query\r\n            int a, b; RD(a, b);\r\n            OT(rev ? Sum(rr-b+1, rr-a) : Sum(ll+a, ll+b-1));\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<p>http:\/\/codeforces.com\/contest\/461\/submission\/7612792<\/p>\n<p>D\uff1a<\/p>\n<pre>\r\n1   2   3\r\n 12  23\r\n2  123  2\r\n 23  12\r\n3   2   1\r\n\r\n<\/pre>\n<pre>\r\n  1  2\r\n1  12  2\r\n 12  12\r\n2  12  1\r\n  2  1\r\n<\/pre>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\n\r\nconst int N = int(2e6) + 9;\r\n\r\nint n;\r\n\r\nnamespace DSU{ \/\/ Disjoint Set Union\r\n    int P&#x5B;N], R&#x5B;N];\r\n    inline void Make(int x){\r\n        P&#x5B;x] = x, R&#x5B;x] = 0;\r\n    }\r\n    inline int Find(int x){\r\n        return P&#x5B;x] == x ? x : P&#x5B;x] = Find(P&#x5B;x]);\r\n    }\r\n    inline void Unionn(int x, int y){\r\n        if (R&#x5B;x] == R&#x5B;y]) ++R&#x5B;x];\r\n        else if (R&#x5B;x] &lt; R&#x5B;y]) swap(x, y);\r\n        P&#x5B;y] = x;\r\n    }\r\n    inline void Union(int x, int y){\r\n        int xx = Find(x), yy = Find(y);\r\n        if (xx == yy){\r\n            return;\r\n        }\r\n        else{\r\n            Unionn(xx, yy);\r\n        }\r\n    }\r\n\r\n    void Union(int x, int y, int z){\r\n        if (z) Union(x,y+n+2),Union(x+n+2,y);\r\n        else Union(x,y),Union(x+n+2,y+n+2);\r\n    }\r\n\r\n    inline void Init(int n){\r\n        REP(i, n) Make(i);\r\n    }\r\n} using namespace DSU;\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    RD(n); Init(2*(n+2)); Rush{\r\n        int a, b; RD(a, b); int u = abs(a-b), v = n-1 - abs(a+b-n-1);\r\n        if (u &gt; v) swap(u, v);\r\n        Union(u, v+2, RC()=='o');\r\n    }\r\n\r\n    REP(i, n+2) if (Find(i) == Find(i+n+2)){\r\n        puts(&quot;0&quot;);\r\n        return 0;\r\n    }\r\n\r\n    int rk = -2; REP(i, n+2) if (Find(i) == i) ++rk;\r\n    cout &lt;&lt; pow(2, rk) &lt;&lt; endl;\r\n}\r\n<\/pre>\n<p>E:<br \/>\ndp[i][j][k]\uff1a\u8d77\u59cbi\u7ec8\u6b62j\u9700\u89812^k\u6b21\u7684\u6700\u77ed\u957f\u5ea6- &#8211; <\/p>\n<p>\u4f46\u662f SAM \u4e2d\u72b6\u6001\u592a\u591a\u600e\u4e48\u529e\uff1f\u3002\u3002\u3002<br \/>\n\u901a\u8fc7\u9884\u5904\u7406\u51fa\u8d77\u59cb x \u7ec8\u6b62 y \u7684\u6700\u77ed\u4e0d\u5728 SAM \u4e2d\u7684\u4e32\u3002\u3002\u3002\u53ef\u4ee5\u5c06 i, j \u6539\u6210\u5b57\u7b26\u96c6\u3002\u3002\u3002<\/p>\n<h3>External link: <\/h3>\n<p><a href=\"http:\/\/ftiasch.github.io\/blog\/2014\/08\/27\/codeforces-round-263\/\">http:\/\/ftiasch.github.io\/blog\/2014\/08\/27\/codeforces-round-263\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem B. Appleman and Tree Brief description: \u7ed9\u5b9a\u4e00\u68f5\u6709\u6839\u6811\uff0c\u6bcf\u4e2a\u70b9\u6709\u9ed1\u767d\u4e24\u79cd\u989c\u8272\uff0c\u95ee\u6709\u591a\u5c11\u79cd\u6811\u7684\u5212\u5206\u65b9\u6848\uff0c \u4f7f\u5f97\u6bcf\u4e2a\u8054\u901a\u5757\u4e2d\u90fd\u6070\u597d\u6709\u4e00\u4e2a\u9ed1\u8272\u7ed3\u70b9\u3002 Analysis: \u6811 DP\uff0c\u5b50\u6811\u5408\u5e76\u3002\u8bbe\uff1a f[u] \u8868\u793a\u4ee5 u \u4e3a\u6839\u7684\u5b50\u6811\u4e2d\uff0c\u7ecf\u8fc7\u5212\u5206\u8fc7\u540e\uff0c\u4e0e u \u76f8\u8fde\u7684\u8054\u901a\u5757\u6070\u597d\u5305\u542b\u4e00\u4e2a\u9ed1\u8272\u7ed3\u70b9\u7684\u65b9\u6848\u6570\u3002 g[u] \u8868\u793a\u4ee5 u \u4e3a\u6839\u7684\u5b50\u6811\u4e2d\uff0c\u7ecf\u8fc7\u5212\u5206\u8fc7\u540e\uff0c\u4e0e u \u76f8\u8fde\u7684\u8054\u901a\u5757\u3002\u3002\u3002\u4e0d\u5305\u542b\u9ed1\u8272\u7ed3\u70b9\u7684\u65b9\u6848\u6570\u3002 \u8f6c\u79fb\u8ba8\u8bba\u662f\u5426\u5207\u5272 (u, v) \u8fd9\u6761\u8fb9\u5373\u53ef\u3002 void dfs(int u = 0){ ECH(it, adj&#x5B;u]){ dfs(v); f&#x5B;u] = f&#x5B;u]*(f&#x5B;v]+g&#x5B;v]) + g&#x5B;u]*f&#x5B;v]; g&#x5B;u] *= (f&#x5B;v]+g&#x5B;v]); } } http:\/\/codeforces.com\/contest\/461\/submission\/7612452 C: Brief description: \u7ed9\u5b9a\u4e00\u5f20\u7eb8\uff0c\u652f\u6301\u4e24\u4e2a\u64cd\u4f5c\uff1a\u3002 \u3002\u3002\u6cbf\u67d0\u4e2a\u4f4d\u7f6e\u5bf9\u6298\u3002 \u3002\u3002\u8be2\u95ee\u67d0\u4e2a\u533a\u95f4\u7eb8\u5f20\u7684\u4f53\u79ef\u3002 Analysis: \u6811\u72b6\u6570\u7ec4\u3002\u5bf9\u4e8e\u6298\u53e0\u64cd\u4f5c\uff0c\u6211\u4eec\u603b\u662f\u679a\u4e3e\u8f83\u77ed\u7684\u4e00\u90e8\u5206\uff0c\u52a0\u5230\u8f83\u957f\u7684\u4e00\u90e8\u5206\u4e2d\u53bb\u3002 [&hellip;]<\/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":[18,1],"tags":[],"class_list":["post-950","post","type-post","status-publish","format-standard","hentry","category-codeforces","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fk","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/950","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=950"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/950\/revisions"}],"predecessor-version":[{"id":951,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/950\/revisions\/951"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=950"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=950"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=950"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}