{"id":750,"date":"2013-06-23T08:49:43","date_gmt":"2013-06-23T00:49:43","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=750"},"modified":"2013-08-16T04:21:48","modified_gmt":"2013-08-15T20:21:48","slug":"topcoder-open-2013-algorithm-round-3b","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/topcoder-open-2013-algorithm-round-3b\/","title":{"rendered":"TCO 2013 Algorithm Round 3B"},"content":{"rendered":"

\u5f31\u83dc\u53ea\u80fd\u56f4\u89c2\u4e86\u3002\u3002\uff09\u3002\u3002<\/p>\n

250. SimilarSequences<\/h2>\n

Brief description: <\/h3>\n

… \u4e24\u4e2a\u5e8f\u5217\u88ab\u8ba4\u4e3a\u662f\u76f8\u4f3c\u7684\uff0c\u5f53\u524d\u4ec5\u5f53\u4ece\u4e24\u4e2a\u5e8f\u5217\u4e2d\u5404\u5220\u9664\u4e00\u4e2a\u5143\u7d20\u540e\u76f8\u7b49\u3002\uff08\u8fd9\u91cc\u76f8\u7b49\u6307\u76f8\u540c\u4f4d\u7f6e\u4e0a\u7684\u5143\u7d20\u76f8\u540c\u3002\u3002
\n\u3002\u3002\u7ed9\u5b9a\u957f\u5ea6\u4e3a n \u7684\u521d\u59cb\u5e8f\u5217 A \u548c\u4e0a\u754c up\u3002\u3002\u3002\u3002\u95ee\u5b58\u5728\u591a\u5c11\u5e8f\u5217\u4e0e\u4e4b\u76f8\u4f3c\u3002\u3002\uff08\u6bcf\u4e2a\u5143\u7d20\u53d6\u81ea [1, up]…
\n( n <= 40 .. )\n<\/p>\n

Analysis: <\/h3>\n

… \u66b4\u529b\u7f8e\u5b66\u3002\u3002\u3002\u3002
\n\u3002\u679a\u4e3e A<\/code> \u5e8f\u5217\u4e2d\u5220\u9664\u7684\u5143\u7d20\u3002\u3002\u518d\u679a\u4e3e\u8981\u8865\u4e0a\u7684\u5143\u7d20\u4f4d\u7f6e\u3002\uff08\u7528 -1<\/code> \u6807\u8bb0\u4e4b\u3002\u3002\uff09\u3002\u3002\u628a\u8fd9\u4e2a token<\/code> \u653e\u8fdb set<\/code> \u91cc\u3002\u3002\u8bb0\u4e4b h<\/code>\u3002\u3002
\n\u90a3\u4e48\u7b54\u6848\u5c31\u662f SZ(h) * up <\/code>\uff1f\u3002\u3002\u3002<\/p>\n

\u3002\u3002\u3002\u3002\u660e\u663e\u8fd9\u6837\u4f1a\u91cd\u590d\u8ba1\u6570\u3002\u3002\u3002<\/p>\n

\u3002\u3002\u3002\u56e0\u6b64\u6211\u4eec\u7528 SI B(ALL(A))<\/code> \u8bb0\u5f55 A<\/code> \u6570\u7ec4\u4e2d\u51fa\u73b0\u8fc7\u7684\u5143\u7d20\u3002\u3002\u3002
\n\u3002\u3002\u518d\u5efa\u4e00\u4e2a set<\/code> \u3002h2<\/code>\u3002\uff08\u4e4b\u524d\u7684\u73b0\u5728\u8bb0\u4f5c h1<\/code>\u3002\u3002
\n\u3002\u3002\u7528\u4ee5\u4fdd\u5b58\u90a3\u4e9b\u6240\u6709\u53ef\u80fd\u4f1a\u88ab\u91cd\u590d\u8ba1\u6570\u7684 token<\/code> \u3002\u3002(\u65e2\u5728 h1<\/code> \u4e2d\u539f\u5148\u7528 -1<\/code>\u6807\u8bb0\u7684\u90a3\u4e2a\u4f4d\u7f6e\u3002\u3002\u73b0\u5728\u4f9d\u6b21\u7528 B<\/code> \u4e2d\u7684\u5143\u7d20\u586b\u4e0a\u3002\u3002\u3002<\/p>\n

\u90a3\u4e48\u603b\u7684\u7b54\u6848\u5c31\u662f SZ(h1) * (up - SZ(B)) + SZ(h2)<\/code>\u3002\u3002\u3002<\/p>\n

\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nclass SimilarSequences {\r\npublic:\r\n\tint count(vector <int> A, int up) {\r\n\r\n\t    SI B(ALL(A)); set<VI> h1, h2; int n = SZ(A); REP(i, n){\r\n\t        VI AA = A; ERS(AA, i); REP(j, n){\r\n\t            INS(AA, j, -1); h1.insert(AA);\r\n\t            ECH(it, B) AA[j] = *it, h2.insert(AA);\r\n\t            ERS(AA, j);\r\n\t        }\r\n\t    }\r\n\r\n\t    return sum(pdt(SZ(h1), (up - SZ(B))), SZ(h2));\r\n\t}\r\n};\r\n<\/pre>\n
450. AntlerSwapping<\/h2>\n
Brief description: <\/h3>\n
\u3002\u3002\u4e00\u5bf9\u6570\u88ab\u79f0\u4e3a\u662f\u5e73\u8861\u7684\u3002\u3002\u5982\u679c\u5b83\u4eec\u7684\u5dee \uff1c \u7ed9\u5b9a\u7684 cap\u3002
\n… \u7ed9\u5b9a n \u5bf9\u6570\u3002\u3002\u95ee\u81f3\u5c11\u591a\u5c11\u6b21\u4ea4\u6362\u53ef\u4ee5\u4f7f\u5b83\u4eec\u5168\u90e8\u5e73\u8861\u3002\u3002\uff08\u4ea4\u6362\u5728\u67d0\u5bf9\u6570\u7684\u4efb\u610f\u4e00\u9879\u548c\u53e6\u4e00\u5bf9\u6570\u7684\u4efb\u610f\u4e00\u9879\u4e4b\u95f4\u8fdb\u884c\u3002\u3002\u3002
\n..( n <= 16 .. )\n\n\n
Analysis: <\/h3>\n
\u3002\u3002\u5f88\u5bb9\u6613\u60f3\u504f\u3002\u3002\u3002\u4f46\u662f\u8fd9\u4e2a\u6570\u636e\u8303\u56f4\u7684\u8bdd\u4f3c\u4e4e\u5e94\u8be5\u662f SCDP\uff1f\u3002\u3002\u3002<\/p>\n
dp[s] \u8868\u793a\u53ea\u8003\u8651 s \u96c6\u5408\u4e2d\u7684\u6570\u5bf9\u7684\u8bdd\u3002\u3002\u8981\u8ba9\u4ed6\u4eec\u5e73\u8861\u81f3\u5c11\u9700\u8981\u51e0\u6b21\u4ea4\u6362\u3002
\n\u90a3\u4e48\u663e\u7136\u6709…<\/p>\n
\r\n..\r\n\t        REP_SS(i, s) checkMin(dp[s], dp[i] + dp[s^i]);\r\n..\r\n<\/pre>\n
\u8fd9\u91cc REP_SS \u662f\u679a\u4e3e\u5b50\u96c6\u3002\u3002\uff08\u53c2\u89c1 [\u6280\u5de7]\u679a\u4e3e\u5b50\u96c6\u7684\u98d8\u9038\u5199\u6cd5 by \u67ef\u795e\u5c0f\u5929\u4f7f<\/a><\/p>\n
\u3002\u3002\u3002\u8003\u8651\u8d4b\u521d\u503c\u3002\u3002<\/p>\n
\u3002\u3002\u5bf9\u4e8e\u5355\u5143\u7d20\u96c6\u5408\u3002\u3002\u90a3\u4e48\u5982\u679c\u8fd9\u4e24\u4e2a\u5143\u7d20\u7684\u5dee < cap \u90a3\u4e48\u663e\u7136\u4ee3\u4ef7\u662f 0 \u5426\u5219\u662f\u65e0\u7a77\u5927\u3002\u3002\u3002\n\u3002\u3002\u5bf9\u4e8e\u53cc\u5143\u7d20\u96c6\u5408\u3002\u3002\u5982\u679c\u53ef\u4ee5\u51d1\u6210 2 \u5bf9\u7684\u8bdd\u3002\u3002\u3002\u90a3\u4e48\u521d\u503c\u8bbe\u4e3a 1 \u6b21\u3002\u3002\uff08\u3002\u3002\u5f53\u7136\u4e5f\u6709\u53ef\u80fd\u662f 0 \u6b21\u3002\u30020 \u6b21\u7684\u8bdd\u5c06\u4f1a\u7531\u4e0a\u9762\u7684\u8f6c\u79fb\u5f97\u5230\u3002\u3002\u3002\u3002\n\u3002\u3002\u4e00\u822c\u7684\u3002\u3002\u5bf9\u4e8e n \u4e2a\u5143\u7d20\u7684\u96c6\u5408\u3002\u3002\u5982\u679c\u53ef\u4ee5\u51d1\u6210 n \u5bf9\u7684\u8bdd\u3002\u3002\u90a3\u4e48\u521d\u503c\u8bbe\u4e3a n-1\u3002\u3002\uff08\u81f3\u5c11\u53ef\u4ee5\u901a\u8fc7 n-1 \u6b21\u4ea4\u6362\u4f7f\u4e4b\u5e73\u8861\u3002\u3002\u3002\n\n[cpp collapse=\"false\" firstline=\"1\" highlight=\"\"]\n\/\/}\/* .................................................................................................................................. *\/\n\nint dp[1<<16];\nint n;\n\nclass AntlerSwapping {\npublic:\n\tint getmin(vector <int> L, vector <int> R, int C) {\n\n\t    n = SZ(L); FLC(dp, 0x3f); REP_1(s, _U(n)){\n\t        VI A; REP(i, n) if (_1(s, i)) A.PB(L[i]), A.PB(R[i]); SRT(A);\n\t        int j; REP_N(j, SZ(A)){\n\t            if (A[j+1] - A[j] > C) break;\n\t            ++j;\n\t        }\n\t        if (j == SZ(A)) dp[s] = count_bits(s) - 1;\n\t        REP_SS(i, s) checkMin(dp[s], dp[i] + dp[s^i]);\n\t    }\n\t\treturn dp[_U(n)] == INF ? -1 : dp[_U(n)];\n\t}\n};\n[\/cpp]\n\n\n\n
1000. ToastJumping<\/h2>\n
Brief description: <\/h3>\n
\u3002\u3002\u95ee\u4ece (0, 0) \u8df3\u5230 (x, y) \u81f3\u5c11\u9700\u8981\u8df3\u51e0\u6b65\u3002\u3002\u3002
\n\u3002\u3002\u3002\u8df3\u8dc3\u53ea\u80fd\u5728\u6574\u70b9\u4e4b\u95f4\u8fdb\u884c\u3002\u3002\u4e14\u6bcf\u6b21\u8df3\u8dc3\u7684 \u6b27\u51e0\u91cc\u5f97\u8ddd\u79bb^2 \u4e0d\u5f97\u8d85\u8fc7 d\u3002\u3002
\n…<\/p>\n
Analysis: <\/h3>\n
.. \u4e00\u56fe\u6d41\u3002\u3002\u3002
\n
\n\u3002\u3002\u3002k \u6b65\u540e\u7684\u53ef\u8fbe\u533a\u57df\u662f\u51f8\u7684\u3002\u3002\u800c\u4e14\u5c31\u662f 1 \u6b65\u53ef\u8fbe\u533a\u57df\u7684\u90a3\u4e2a\u51f8\u5305\u6bcf\u4e2a\u70b9\u4e58\u4ee5 k\u3002\u3002\u3002\u56e0\u6b64\u7b97\u6cd5\u5c31\u662f\u6784\u9020\u51fa\u6700\u91cc\u5c42\u7684\u90a3\u4e2a\u51f8\u5305\u3002\u3002\u7136\u540e\u679a\u4e3e\u6bcf\u6761\u8fb9\u3002\u3002checkMax \u3002\u3002
\n\u3002\u3002\u5b9e\u9645\u6839\u636e\u5bf9\u79f0\u6027\u3002\u3002\u3002\u6784\u9020\u51fa\u7b2c\u4e00\u8c61\u9650\u7684\u4e00\u534a\u5c31\u591f\u4e86\u3002\u3002<\/p>\n
\r\nconst int N = 50;\r\nVP P;\r\n\r\nint f(int x0, int y0, int dd){\r\n    if (!x0 && !y0) return 0;\r\n\r\n    LL t = sqr((LL)x0)+sqr((LL)y0);\r\n\r\n    CLR(P); int d = sqrt(dd), y = d, x = 0;\r\n#define xx sqr(x)\r\n#define yy sqr(y)\r\n    while(1){\r\n        while (xx+yy>dd) --y; Po p(x, y);\r\n        while (SZ(P)>=2 && dett(P[SZ(P)-2], P.back(), p) >= 0) P.pop_back();\r\n        P.PB(p); if (x>=y) break; ++x;\r\n    }\r\n\r\n    x0 = abs(x0), y0 = abs(y0); if (x0 > y0) swap(x0, y0);\r\n\r\n    int k = 0; Po p0(x0, y0); FOR(i, 1, SZ(P)){\r\n        Po p1(P[i]-P[i-1]); LL p = det(p1, p0), q = det(p1, P[i-1]);\r\n        \/\/cout << p << " " << q << endl;\r\n        checkMax(k, int(ceil(p, q)));\r\n    }\r\n\r\n    return k;\r\n}\r\n\r\nclass ToastJumping {\r\npublic:\r\n    vector <int> minJumps(vector <int> x, vector <int> y, vector <int> d){\r\n        VI res; int n = SZ(x); REP(i, n) res.PB(f(x[i], y[i], d[i]));\r\n        return res;\r\n    }\r\n};\r\n<\/pre>\n
External link: <\/h3>\n
https:\/\/apps.topcoder.com\/wiki\/display\/tc\/TCO+2013+Round+3B<\/a>
\nhttps:\/\/gist.github.com\/lychees\/5843231<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
\u5f31\u83dc\u53ea\u80fd\u56f4\u89c2\u4e86\u3002\u3002\uff09\u3002\u3002 250. SimilarSequences Brief description: … \u4e24\u4e2a\u5e8f\u5217\u88ab\u8ba4\u4e3a\u662f\u76f8\u4f3c\u7684\uff0c\u5f53\u524d\u4ec5\u5f53\u4ece\u4e24\u4e2a\u5e8f\u5217\u4e2d\u5404\u5220\u9664\u4e00\u4e2a\u5143\u7d20\u540e\u76f8\u7b49\u3002\uff08\u8fd9\u91cc\u76f8\u7b49\u6307\u76f8\u540c\u4f4d\u7f6e\u4e0a\u7684\u5143\u7d20\u76f8\u540c\u3002\u3002 \u3002\u3002\u7ed9\u5b9a\u957f\u5ea6\u4e3a n \u7684\u521d\u59cb\u5e8f\u5217 A \u548c\u4e0a\u754c up\u3002\u3002\u3002\u3002\u95ee\u5b58\u5728\u591a\u5c11\u5e8f\u5217\u4e0e\u4e4b\u76f8\u4f3c\u3002\u3002\uff08\u6bcf\u4e2a\u5143\u7d20\u53d6\u81ea [1, up]… ( n<\/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":[17],"tags":[121,120],"class_list":["post-750","post","type-post","status-publish","format-standard","hentry","category-topcoder","tag-121","tag-120"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-c6","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/750","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=750"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/750\/revisions"}],"predecessor-version":[{"id":751,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/750\/revisions\/751"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=750"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=750"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=750"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}