{"id":646,"date":"2013-01-25T20:53:29","date_gmt":"2013-01-25T12:53:29","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=646"},"modified":"2013-01-26T07:17:21","modified_gmt":"2013-01-25T23:17:21","slug":"%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","status":"publish","type":"post","link":"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\/","title":{"rendered":"\u3010\u7b2c\u2468\u6b21 ACdream \u7fa4\u539f\u521b\u7fa4\u8d5b\u3011\u89e3\u9898\u62a5\u544a"},"content":{"rendered":"

\u6bd4\u8d5b\u5730\u5740\uff1ahttp:\/\/www.acdream.net\/contest.php?cid=1019<\/a>
\n\u6570\u636e\u548c\u6807\u7a0b\uff1aACdream-9th.rar<\/a>
\nA[\u4e8c\u6b21\u578b] B[\u4e8c\u7ef4\u6781\u503c\u70b9] C[\u6570\u636e\u7ed3\u6784] D[\u7ef4\u62a4\u51f8\u58f3] E[\u6570\u5b66\u63a8\u7406] F[\u72b6\u6001\u538b\u7f29DP]\u3002\u3002\u3002<\/p>\n

<\/p>\n

Problem A. Yet Another Conic Section Problem<\/h2>\n

Brief description: <\/h3>\n

\uff08\u5224\u5b9a\u4e24\u4e2a\u5706\u9525\u66f2\u7ebf\u662f\u5426\u5168\u7b49\u3002\u3002\u6240\u8c13\u5168\u7b49\u3002\u3002\u3002\u662f\u6307\u5176\u4e2d\u4e00\u4e2a\u53ef\u4ee5\u7ecf\u8fc7\u82e5\u5e72\u6b21\u5e73\u79fb\uff0c\u65cb\u8f6c\uff0c\u53cd\u5c04\u53d8\u6362\u53d8\u6210\u53e6\u4e00\u4e2a\u3002\u3002\uff09<\/p>\n

<\/p>\n

Analysis: <\/h3>\n

[\u4e8c\u6b21\u66f2\u7ebf\u4e0d\u53d8\u91cf]<\/p>\n

\u3002\u3002\u672c\u6765\u60f3\u51fa\u6210\u5224\u65ad\u76f8\u4f3c\u3002\u3002\u3002\u4f46\u662f\u76f8\u4f3c\u4e0d\u53d8\u91cf\u4e0d\u592a\u4f1a\u5f04\u3002\u3002\u5c31\u5148\u5224\u65ad\u5168\u7b49\u3002\u3002
\n\u3002\u4f3c\u4e4e\u6309\u7167 ZJU 3488.<\/a> \u7684\u505a\u6cd5\u4e5f\u53ef\u4ee5\u641e\u3002\u3002\uff08\u5316\u6210\u6807\u51c6\u5f62\u5f0f\u3002\u3002\u5224\u65ad\u66f2\u7ebf\u79cd\u7c7b\u3002\u3002\u8ba1\u7b97\u79bb\u5fc3\u7387\uff08eccentricity\uff09\u3002\u3002<\/p>\n

\r\n\u8bb0\u3002\u3002\r\nI1 = a + c\r\nI2 = ac - bb \uff08\u4e8c\u9636\u4e3b\u5b50\u5f0f\u3002\u3002\r\nI3 = \u884c\u5217\u5f0f\u3002\u3002\r\n\r\nK1 = A(2,2) + A(1,1) ( \u5176\u4e2d A(i,j) \u8868\u793a\u53bb\u6389\u7b2c i \u884c\u7b2c j \u5217\u7684\u4f59\u5b50\u5f0f\u3002\u3002\r\n\u90a3\u4e48\r\n\r\nif ( I2 > 0 ) {\r\n    if ( I1 , I3 \u540c\u53f7 \uff09 \u662f\u865a\u692d\u5706\r\n    if ( I1 , I3 \u5f02\u53f7 \uff09 \u662f\u692d\u5706\r\n    if ( I3 == 0 ) \u662f\u4e00\u4e2a\u70b9\r\n}\r\nif ( I2 < 0 ) {\r\n    if ( I3 == 0 ) \u4e00\u5bf9\u76f8\u4ea4\u7684\u76f4\u7ebf\r\n    if ( I3 != 0 ) \u53cc\u66f2\u7ebf\r\n}\r\nif ( I2 == 0 ) {\r\n    if ( I3 != 0 ) \u629b\u7269\u7ebf\r\n    if ( I3 == 0 ) {\r\n        if ( K1 < 0 ) \u4e00\u5bf9\u5e73\u884c\u7ebf\r\n        if ( K1 > 0 ) \u4e00\u5bf9\u865a\u5e73\u884c\u7ebf\r\n        if ( K1 == 0 ) \u4e00\u5bf9\u91cd\u5408\u7684\u76f4\u7ebf\r\n    }\r\n}\r\n<\/pre>\n
\u3002\u3002\uff08\u3002\u3002\u53ef\u89c1\u5149\u662f\u5224\u65ad\u66f2\u7ebf\u79cd\u7c7b\u3002\u3002\u5c31\u5b58\u5728\u7740\u5927\u91cf\u7684 if-else\u3002\u3002\u3002\uff09
\n\u3002\u3002\u76f8\u6bd4\u4e4b\u4e0b\u3002\u3002\u76f4\u63a5\u5229\u7528\u4e8c\u6b21\u66f2\u7ebf\u4e0d\u53d8\u91cf\u8fdb\u884c\u6bd4\u8f83\u7684\u65b9\u6cd5\u8981\u6613\u4e8e\u64cd\u4f5c\u8bb8\u591a\u3002\u3002<\/p>\n
\r\nstruct Conic{\r\n    DB a, b, c, d, e, f;\r\n    DB I1, I2, I3;\r\n    void input(){\r\n        RF(a, b, c, d, e, f);\r\n        b\/=2, d\/=2, e\/=2;\r\n        I1 = a+c, I2 = a*c - sqr(b);\r\n        I3 = a*c*f+2*b*e*d-c*d*d-a*e*e-f*b*b;\r\n        cout << I1 << " " << I2 << " " << I3 << endl;\r\n    }\r\n    bool operator ==(const Conic&r) const{\r\n        return !sgn(I1, r.I1) && !sgn(I2, r.I2) && !sgn(I3, r.I3);\r\n    }\r\n} C1, C2;\r\n\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("conic03.in", "r", stdin);\r\n    freopen("conic03.out", "w", stdout);\r\n#endif\r\n\r\n    Rush{\r\n        C1.input(), C2.input();\r\n        puts (C1 == C2 ? "Y" : "N");\r\n    }\r\n}\r\n<\/pre>\n
External link: <\/h3>\n
http:\/\/www.spoj.com\/problems\/CONIC\/<\/a>
\n[Weisstein, Eric W. “Conic Section.” From MathWorld–A Wolfram Web Resource.]<\/a>
\n[Se 3 \u7528\u7cfb\u6570\u5224\u522b\u4e8c\u6b21\u66f2\u7ebf\u7c7b\u578b]<\/a>
\nwikipedia, Matrix representation of conic sections<\/a>
\nwikipedia, Positive-definite_matrix<\/a><\/p>\n
Problem B. Minimization<\/h2>\n
Brief description: <\/h3>\n
… ( … \u6c42\u51fa\u3002\u3002\u3002\u5230\u7ed9\u5b9a\u7684k\u4e2a\u70b9\u7684\u8ddd\u79bb\u7684\u548c\/\u5e73\u65b9\u548c\/\u7acb\u65b9\u548c\u6700\u5c0f\u7684\u4e09\u4e2a\u70b9\u3002\u3002\uff09
\n<\/p>\n
Analysis: <\/h3>\n
\u3002\u7c7b\u4f3c\u6a21\u62df\u9000\u706b\u3002\u3002\u3002\u5b9e\u73b0\u7684\u8fc7\u7a0b\u4e2d\u4f7f\u7528 valarray \u53ef\u4ee5\u6781\u5927\u7684\u51cf\u5c11\u4ee3\u7801\u91cf\u3002\u3002\u3002<\/p>\n
\r\n.. .\r\n\t\twhile (L > 1e-9) {\r\n\t\t\tfor (int i = 0; i < k; ++i) {\r\n\t\t\t\tdelta[i] = ps[i] - who;\r\n\t\t\t\tmod[i] = dist(delta[i]);\r\n\t\t\t}\r\n\t\t\tdouble smod = accumulate(mod.begin(), mod.end(), 0.0);\r\n\t\t\tfor (int i = 0; i < k; ++i) {\r\n\t\t\t\tdelta[i] *= pow(mod[i] \/ smod, d - 1);\r\n\t\t\t}\r\n\t\t\tpoint v = accumulate(delta.begin(), delta.end(), point(0.0, n));\r\n\t\t\tv *= L;\r\n\t\t\tdouble t = tryIt(ps, who + v, d + 1);\r\n\t\t\tif (t < ans) {\r\n\t\t\t\tans = t;\r\n\t\t\t\twho += v;\r\n\t\t\t} else {\r\n\t\t\t\tL \/= 2;\r\n\t\t\t}\r\n\t\t}\r\n.. .\r\n<\/pre>\n
Problem C. Crayon<\/h2>\n
Brief description: <\/h3>\n
\u3002\u3002\u52a8\u6001\u7ef4\u62a4\u4e00\u7ec4\u533a\u95f4\uff0c\u652f\u6301\u63d2\u5165\u5220\u9664\u3002\u3002\u8be2\u95ee\u4e0e\u67d0\u4e2a\u533a\u95f4\u81f3\u5c11\u6709\u4e00\u4e2a\u516c\u5171\u70b9\u7684\u533a\u95f4\u6570\u3002\u3002\uff09\u3002\u3002<\/p>\n
Analysis: <\/h3>\n
.\u57fa\u672c\u4e0a\u5c31\u662f\u6821\u8d5b\u6211\u8111\u6b8b\u6ca1\u505a\u51fa\u6765\u7684\u90a3\u9898<\/a>\u3002\u3002 \u5176\u5b9e\u5c31\u662f\u8ba1\u6570\u8865\u96c6\u3002\u3002\u3002\u3002\u5f88\u5178\u578b\u7684\u6b63\u96be\u5219\u53cd\u3002\u3002\u3002\u3002<\/p>\n
External link: <\/h3>\n
http:\/\/www.spoj.com\/problems\/CRAYON\/<\/a><\/p>\n
Problem D. Vision Field<\/h2>\n
Brief description: <\/h3>\n
\u3002\u3002\u3002x \u8f74\u6b63\u534a\u8f74\u4e0a\u5206\u5e03\u7740 n \u4e2a\u697c\u623f (i, Ai)\u3002\u3002\u95ee\u7ad9\u5728 (0, h) \u5f80\u53f3\u53ef\u4ee5\u770b\u5230\u591a\u5c11\u697c\u623f\u3002\u3002\uff09<\/p>\n
Analysis: <\/h3>\n
\u8bbe\u4e00\u5f00\u59cb\u89c6\u70b9\u5904\u5728\u65e0\u7a77\u9ad8\u4f4d\u7f6e\u3002\u3002\u90a3\u4e48\u663e\u7136\u6240\u6709\u697c\u90fd\u80fd\u770b\u5230\u3002\u3002
\n\u3002\u3002\u968f\u7740\u89c6\u70b9\u7684\u4e0b\u964d\u3002\u3002\u4e00\u4e9b\u5efa\u7b51\u5f00\u59cb\u88ab\u906e\u76d6\u3002\u3002<\/p>\n
\u5982\u679c\u6211\u4eec\u80fd\u591f\u9884\u5904\u7406\u51fa\u6bcf\u4e2a\u5efa\u7b51\u88ab\u906e\u76d6\u7684\u65f6\u95f4\u3002\u3002
\n\u90a3\u4e48\u5c31\u53ef\u4ee5 O(logn) \u65f6\u95f4\u5185\u5728\u7ebf\u7684\u56de\u7b54\u6bcf\u4e2a\u8be2\u95ee\u3002\uff08\u4e8c\u5206\u3002\u3002<\/p>\n
\u73b0\u5728\u8003\u8651\u5982\u4f55\u9884\u5904\u7406\u6bcf\u4e2a\u5efa\u7b51\u88ab\u906e\u76d6\u7684\u65f6\u95f4\u3002\u3002
\n\u6734\u7d20\u65b9\u6cd5\u662f\u5bf9\u6bcf\u4e2a\u5efa\u7b51\u548c\u4ed6\u524d\u9762\u7684\u5efa\u7b51\u7684\u9876\u7aef\u8fde\u7ebf\u4e0e y \u8f74\u4ea4\u70b9\u3002
\n\u3002\u5c31\u662f\u5176\u88ab\u906e\u76d6\u7684\u65f6\u95f4\u3002\u3002
\n\u8fd9\u4e2a O(n2) \u7684\u505a\u6cd5\u663e\u7136\u5f31\u7206\u3002\u3002<\/p>\n
\u8003\u5bdf\u76f8\u90bb\u7684\u5efa\u7b51
\n\u53ef\u4ee5\u8bc1\u660e\u3002\u3002\u6700\u65e9\u88ab\u906e\u76d6\u7684\u5efa\u7b51\u4e00\u5b9a\u662f\u4ece\u67d0\u7ec4\u76f8\u90bb\u7684\u5efa\u7b51\u4e2d\u4ea7\u751f\u7684\u3002\u3002
\n\uff08\u7c7b\u4f3c Ural 1010 \u3002\u3002<\/a><\/p>\n
\u6211\u4eec\u7528\u4f18\u5148\u961f\u5217\u7ef4\u62a4\u5f53\u524d\u6240\u6709\u672a\u88ab\u906e\u76d6\u7684\u5efa\u7b51\u3002
\n\u3002\u3002\u5219\u5176\u5173\u952e\u5b57\u4e3a\u4e8e\u5176\u5de6\u8fb9\u7b2c\u4e00\u4e2a\u672a\u88ab\u906e\u76d6\u7684\u5efa\u7b51\u7684\u9876\u7aef\u3002\u3002
\n\u3002\u6240\u5f62\u6210\u7684\u8fde\u7ebf\u4e0e y \u8f74\u4ea4\u70b9\u3002\u3002<\/p>\n
\u590d\u6742\u5ea6 O(nlogn)\u3002
\n\u603b\u7684\u590d\u6742\u5ea6\u4e3a O((n+m)logn)
\n\u3002\u3002\uff08\u3002\u3002\u66f4\u597d\u7684\u65b9\u6cd5\u662f\u7ef4\u62a4\u51f8\u58f3\u3002\u3002\u3002\u9884\u5904\u7406\u7684\u590d\u6742\u5ea6 O(n + nlogn) \uff08\u6392\u5e8f\u3002\u3002<\/p>\n
External link: <\/h3>\n
http:\/\/www.spoj.com\/problems\/VISION\/<\/a><\/p>\n
Problem E. Evil Pu*&le<\/h2>\n
\u3002\u3002\u3002puts(“0”);<\/p>\n
Problem F. Madotsuki\u2018s Pattern<\/h2>\n
Brief description: <\/h3>\n
 .. \u6c42\u6700\u591a\u53ef\u4ee5\u6784\u9020\u591a\u5c11 \u201c\u7a97\u5b50\u82b1\u7eb9\u201d \u548c\uff0c\u4ee5\u53ca\u6709\u591a\u5c11\u53ef\u4ee5\u5f97\u5230\u8fd9\u4e2a\u6700\u4f18\u89e3\u7684\u65b9\u6848\u6570\u3002\u3002\u3002\uff09<\/p>\n
Analysis: <\/h3>\n
\u72b6\u6001\u538b\u7f29 DP\u3002\u3002\u672c\u6765\u60f3\u51fa\u6210\u53ef\u4ee5\u53ef\u4ee5\u8003\u8651\u5de8\u5927\u7a97\u5b50\u82b1\u7eb9\u7684\u3002\u3002
\n\u6bd4\u5982\u4e00\u4e2a 2\u9636\u7a97\u5b50\u3002\u3002\u5c31\u662f<\/p>\n
110011
\n110011
\n001100
\n001100<\/p>\n
\uff08\u5f97\u5206\u5927\u6982\u9700\u8981\u6210\u6307\u6570\u589e\u957f\u3002\u3002\u4f18\u5148\u6784\u9020\u5927\u578b\u7684\u82b1\u7eb9\u3002\u3002\u3002\u4f46\u662f\u53d1\u73b0\u4e0d\u592a\u4f1a\u5f04\u3002\u3002\u5c31\u5148\u8003\u8651 1 \u9636\u7684\u51fa\u51fa\u6765\u4e86\u3002o(\u2267v\u2266)o~~\u3002\u3002\u3002\uff09<\/p>\n
External link: <\/h3>\n
http:\/\/www.spoj.com\/problems\/MDT1\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
\u6bd4\u8d5b\u5730\u5740\uff1ahttp:\/\/www.acdream.net\/contest.php?cid=1019 \u6570\u636e\u548c\u6807\u7a0b\uff1aACdream-9th.rar A[\u4e8c\u6b21\u578b] B[\u4e8c\u7ef4\u6781\u503c\u70b9] C[\u6570\u636e\u7ed3\u6784] D[\u7ef4\u62a4\u51f8\u58f3] E[\u6570\u5b66\u63a8\u7406] F[\u72b6\u6001\u538b\u7f29DP]\u3002\u3002\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":[96],"tags":[],"class_list":["post-646","post","type-post","status-publish","format-standard","hentry","category-acdream"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-aq","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/646","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=646"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/646\/revisions"}],"predecessor-version":[{"id":647,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/646\/revisions\/647"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=646"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=646"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=646"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}