{"id":818,"date":"2013-09-07T20:19:37","date_gmt":"2013-09-07T12:19:37","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=818"},"modified":"2014-10-23T21:37:13","modified_gmt":"2014-10-23T13:37:13","slug":"srm-508","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-508\/","title":{"rendered":"SRM 508"},"content":{"rendered":"

<\/p>\n

250. DivideAndShift<\/h2>\n

Brief description:<\/h3>\n

\u3002\u3002\u6c42\u6ee1\u8db3\u4ee5\u4e0b\u9012\u5f52\u5173\u7cfb\u7684\u67d0\u51fd\u6570\u7684\u503c\u3002\u3002
\nf(n, 0) = 1<\/code>
\nf(n, m) = f(n, m%n)<\/code>
\nf(n, m) = min(f(n, m-1), f(n, m+1), f(n\/d, m%(n\/d))<\/code><\/p>\n

Analysis:<\/h3>\n

\u3002\u3002\u663e\u7136\u653e\u7f29\u603b\u662f\u5b89\u6392\u5728\u6eda\u52a8\u7684\u524d\u9762\u6bd4\u8f83\u79d1\u5b66\u3002\u3002\u3002\u4e8e\u662f\u679a\u4e3e\u7ea6\u6570\u5c31\u884c\u4e86\u3002\u3002\u653e\u7f29\u6b21\u6570\u7b49\u4e8e\u7d20\u56e0\u5b50\u4e2a\u6570\u3002\u3002<\/p>\n

\r\nint fact(int x){\r\n    int z = 0; REP(i, SZ(P)){\r\n        while (x % P[i] == 0) ++z, x \/= P[i];\r\n        if (x == 1) break;\r\n    }\r\n    if (x != 1) ++z;\r\n    return z;\r\n}\r\n\r\nclass DivideAndShift {\r\npublic:\r\n\tint getLeast(int n, int m) {\r\n        sieve(); --m; int res = INF; REP_1(d, n) if (n % d == 0){\r\n            int nn = n \/ d, mm = m % nn;\r\n            checkMin(res, fact(d) + min(mm, nn-mm));\r\n        }\r\n        return res;\r\n\t}\r\n};\r\n<\/pre>\n
500. YetAnotherORProblem<\/h2>\n
Brief description:<\/h3>\n
\u3002\u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a n \u7684\u6570\u7ec4 a[]\u3002\u3002\u6c42\u6709\u591a\u5c11\u6ee1\u8db3\u6761\u4ef6\u7684\u6570\u7ec4 b[]\u3002\u3002\u4f7f\u5f97\u3002\u3002b[i] <= a[i]\u3002\u3002\u3002\u4e14 b \u7684\u548c\u7b49\u4e8e\u4f4d\u6216\u3002\u3002<\/p>\n
Analysis:<\/h3>\n
\u3002\u3002\u548c\u7b49\u4e8e\u4f4d\u6216\u3002\u3002\u663e\u7136\u5c31\u662f\u6bcf\u4e2a\u4f4d\u4e0a\u81f3\u591a\u6709\u4e00\u4e2a\u4e00\u3002\u3002\u4e8e\u662f\u663e\u7136\u548c\u67d0\u9898<\/a>\u4e00\u6837\u3002\u3002\u53ef\u4ee5\u4ece\u9ad8\u4f4d\u5230\u4f4e\u4f4d DP\u3002\u3002\u3002
\ndp[k][s]: \u8868\u793a\u5f53\u524d\u7b2c k \u4f4d\u3002\u3002s \u8868\u793a\u5f53\u524d\u5df2\u7ecf\u4e0d\u53d7\u9650\u5236\u7684\u96c6\u5408\u3002\u3002\u3002\u679a\u4e3e 0 \u548c \u6070\u597d\u6709\u4e00\u4e2a 1 \u8fd9\u4e24\u79cd\u51b3\u7b56\u3002\u8bb0\u5fc6\u5316\u641c\u7d22\u5373\u53ef\u3002\u3002\u3002<\/p>\n
\r\nconst int N = 10;\r\nint dp[61][1&lt;&lt;N]; vector&lt;long long&gt; R;\r\nint n;\r\n\r\nint f(int k, int s){\r\n\r\n    if (k &lt; 0) return 1;\r\n\r\n    int &amp;res = dp[k][s]; if (res == -1){\r\n        int ss = s; REP(i, n) if (_1(R[i], k)) ss |= _1(i);\r\n        res = f(k-1, ss); \/\/ 0 .. .\r\n\r\n        REP(i, n) if (_1(s, i) || _1(R[i], k)){ \/\/ 1 .. .\r\n            int ss = s; REP(j, n) if (j != i &amp;&amp; _1(R[j], k)) ss |= _1(j);\r\n            INC(res, f(k-1, ss));\r\n        }\r\n    }\r\n    return res;\r\n}\r\n\r\nclass YetAnotherORProblem {\r\npublic:\r\n\tint countSequences(vector&lt;long long&gt; R){\r\n\t    ::R = R; n = SZ(R); FLC(dp, -1);\r\n\t\treturn f(60, 0);\r\n\t}\r\n};\r\n<\/pre>\n
1000. BarbarianInvasion2<\/h2>\n
Brief description:<\/h3>\n
\u3002\u3002\u4e00\u4e2a n<\/code> \u4e2a\u70b9\u7684\u51f8\u5305\u5185\u90e8\u5206\u5e03\u7740 m<\/code> \u4e2a\u70b9\u3002\u3002\u3002\u8981\u6c42\u5c06\u51f8\u5305\u7684\u8f6e\u5ed3\u5206\u5272\u6210\u7b49\u957f\u7684 m<\/code> \u6bb5\u6d4b\u5ea6\u3002\u3002\uff08\u3002\u6ce8\u610f\u6bcf\u6bb5\u4e0d\u8981\u6c42\u5728\u8fb9\u754c\u4e0a\u8fde\u7eed\u5206\u5e03\u3002\u3002\uff09\u3002\u3002\u3002\u5c06\u8fd9\u4e9b\u6d4b\u5ea6\u548c\u5185\u90e8\u7684\u70b9\u505a\u5339\u914d\u3002\u3002\u3002\u6700\u5c0f\u5316\u6700\u8fdc\u7684\u6d4b\u5ea6\u5230\u70b9\u7684\u8ddd\u79bb\u3002\u3002\u3002(m = 5<\/code>)<\/p>\n
Analysis:<\/h3>\n
\u3002\u3002\u9996\u5148\u4e8c\u5206\u7b54\u6848\u3002\u3002<\/p>\n
\"\"<\/a><\/p>\n
\u3002\u3002\u663e\u7136\u5bf9\u51f8\u5305\u4e0a\u7684\u6bcf\u4e00\u6761\u8fb9\u3002\u3002\u6211\u4eec\u9700\u8981\u505a\u7ebf\u6bb5\u548c\u5706\u6c42\u4ea4\u3002\u3002\u7136\u540e\u626b\u63cf\u7ebf\u3002\u3002\u641e\u51fa\u6bcf\u4e2a\u5c0f\u6bb5\u53ef\u4ee5\u4ece\u5c5e\u7684\u5706\u7684\u96c6\u5408\u3002\u3002\u3002
\n\u3002\u3002\u4e4b\u540e\u8981\u5224\u65ad\u5408\u6cd5\u3002\u3002\u5b9e\u9645\u4e0a\u5c31\u5f97\u5230\u4e86\u4e00\u4e2a\u5b8c\u5907\u5339\u914d\u7684\u95ee\u9898\u3002\u3002\u3002\u4f3c\u4e4e\u53ef\u4ee5\u8dd1\u7f51\u7edc\u6d41\u3002\u3002\u4f46\u662f\u56f0\u96be\u4e4b\u5904\u5728\u4e8e\u3002\u3002\u6b64\u9898\u4e2d\u7684\u5bb9\u91cf\u4e0d\u662f\u6574\u6570\u3002\u3002\u3002\u3002
\n\u3002\u3002\u6ce8\u610f\u5230\u3002m \u975e\u5e38\u5c0f\u3002\u3002\u800c\u4e14\u6211\u4eec\u53ea\u8981\u5224\u65ad\u5b8c\u5907\u5339\u914d\u7684\u5b58\u5728\u6027\u3002\u3002\u6240\u4ee5\u53ef\u4ee5\u66b4\u529b\u4f7f\u7528 Hall’s marriage theorem<\/a>\u3002\u3002\u3002<\/p>\n
\r\nconst int M = 5;\r\nVP B; Po C[M]; DB T; DB S[1&lt;&lt;M];\r\nint n, m;\r\n\r\nbool f(DB r){\r\n\r\n    RST(S); REP(i, n){\r\n\r\n        Seg l(B[i], B[i+1]); DB ln = l.len(); vector&lt;DB&gt; D; D.PB(0), D.PB(ln);\r\n\r\n        REP(j, m){\r\n\r\n            Circle c(C[j], r); if (!~c.sgn(l)) continue;\r\n            Po p0, p1; VP P = c*l; ECH(p, P) D.PB(dist(*p, B[i]));\r\n\r\n            \/*DB b= 2*dot(B[i]-C[j],l.d()._1()), c = (B[i]-C[j]).len2() - sqr(r);\r\n            DB d = sqr(b) - 4*c; if (d &lt; 0) continue;\r\n            d=sqrt(d); DB d0 = (-b-d)\/2, d1 = (-b+d)\/2;\r\n            if (0&lt;d0&amp;&amp;d0&lt;ln) D.PB(d0); if (0&lt;d1&amp;&amp;d1&lt;ln) D.PB(d1);*\/\r\n        }\r\n\r\n        SRT(D); FOR(j, 1, SZ(D)){\r\n            Po p = l.a + l.d()._1()*(D[j]+D[j-1])\/2;\r\n            int s = 0; REP(k, m) if (~sgn(r*r, dist2(p, C[k]))) s |= _1(k);\r\n            S[s] += D[j] - D[j-1];\r\n        }\r\n    }\r\n\r\n    FOR(s, 1, _1(m)){\r\n        DB p = 0, q = T * count_bits(s);\r\n        FOR(ss, 1, _1(m)) if (s &amp; ss) p += S[ss];\r\n        if (sgn(p, q) &lt; 0) return 0;\r\n    }\r\n    return 1;\r\n}\r\n\r\nclass BarbarianInvasion2 {\r\npublic:\r\n\tdouble minimumTime(vector &lt;int&gt; bX, vector &lt;int&gt; bY, vector &lt;int&gt; cX, vector &lt;int&gt; cY) {\r\n\r\n\t    n = SZ(bX), m = SZ(cX); B.resize(n+1);\r\n\t    REP(i, n) B[i] = Po(bX[i], bY[i]); B[n] = B[0]; T = getPeri(B) \/ m;\r\n\t    REP(i, m) C[i] = Po(cX[i], cY[i]);\r\n\r\n\t\tDB l = 0, r = 1e5; DO(233){\r\n\t\t    DB m = (l+r) \/ 2;\r\n\t\t    if (f(m)) r = m;\r\n\t\t    else l = m;\r\n\t\t}\r\n\t\treturn l;\r\n\t}\r\n};\r\n<\/pre>\n
External link:<\/h3>\n
https:\/\/apps.topcoder.com\/wiki\/display\/tc\/SRM+508<\/a>
\nhttps:\/\/gist.github.com\/lychees\/6475006<\/a>
\nwww.cnblogs.com\/zbwmqlw\/archive\/2011\/06\/03\/2070534.html<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"","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":[],"class_list":["post-818","post","type-post","status-publish","format-standard","hentry","category-topcoder"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-dc","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/818","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=818"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/818\/revisions"}],"predecessor-version":[{"id":893,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/818\/revisions\/893"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=818"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=818"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=818"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}