{"id":539,"date":"2012-10-25T18:05:42","date_gmt":"2012-10-25T10:05:42","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=539"},"modified":"2012-10-27T08:36:53","modified_gmt":"2012-10-27T00:36:53","slug":"coci-20122013-round-1","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/coci-20122013-round-1\/","title":{"rendered":"COCI 2012\/2013 Round #1"},"content":{"rendered":"

Brief description: <\/h3>\n

Problem A. Dom<\/h5>\n

… \u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u4e32\u4e2d\u7684\u6240\u6709\u7684 \u201cCAMBRIDGE\u201d \u4e2d\u7684\u5b57\u7b26\u3002\u3002<\/p>\n

\r\nimport re\r\nprint re.sub("[CAMBRIDGE]","",raw_input())\r\n<\/pre>\n
Problem B. F7<\/h5>\n
\u3002\u3002n \u4e2a\u4eba\u53c2\u52a0\u4e00\u4e2a\u6bd4\u8d5b\uff0c\uff08\u6ca1\u6709\u5e76\u5217\u3002\u3002
\n\u3002\u3002\u5176\u4e2d\u7b2c i \u540d \u83b7\u5f97 n-i+1 \u5206\u3002\u3002
\n\u73b0\u5728\u7ed9\u5b9a n \u4e2a\u4eba\u4e00\u4e2a\u521d\u59cb\u5206\u6570\uff0c\u95ee\u6700\u540e\u6709\u591a\u5c11\u4eba\u53ef\u80fd\u83b7\u5f97\u603b\u5206\u7b2c\u4e00\uff1f\uff08\u5e76\u5217\u7b2c\u4e00\u4e5f\u53ef\u4ee5\u3002\u3002<\/p>\n
\r\nI = lambda: map(int, raw_input().split())\r\n\r\nn = input() \r\na = [0] * n\r\nfor i in range(0, n):\r\n\ta[i] = input()\r\n\r\na.sort()\r\n\r\ni = n\t\t\r\nbest = 0\r\n\r\nwhile i>=0:\t\r\n\ti -= 1\r\n\tif (a[i]+n < best): break\t\r\n\tif (a[i]+n-i > best): best = a[i]+n-i\r\nprint n-i-1\t\r\n<\/pre>\n
\uff08\u8d2a\u5fc3\u3002\u3002Python \u540e\u4e09\u4e2a\u70b9\u8d85\u65f6\u3002\u3002<\/p>\n
\u3002\u3002\u3002<\/p>\n
Problem C. Koncert<\/h5>\n
\u3002\u3002\u3002\u6211\u8fd9\u4e2a\u8822\u98de\u4e86\u554a\u3002\u8fd9\u4e2a\u7b80\u76f4\u5c31\u662f bug \u554a\u3002
\n\u3002\u3002\u3002\u8fdb\u53bb\u4f1a\u573a\u91cc\u9762\u8fd8\u80fd\u5e26\u7968\u51fa\u6765\u7ed9\u522b\u4eba\u3002\u8dea\u8dea\u8dea\u3002\u3002\u3002
\n\u3002\u6a21\u62df\u3002\u3002<\/a><\/p>\n
Problem D. Ljubomora<\/h5>\n
\u3002\u3002n \u4e2a\u4eba m \u5806\u77f3\u5b50\uff0c\u7b2c i \u5806\u77f3\u5b50\u6709 ai \u4e2a\u3002\u3002\u73b0\u5728\u8981\u628a\u8fd9 m \u5806\u77f3\u5b50\u5206\u7ed9\u8fd9 n
\n \u4e2a\u4eba\uff0c\u8981\u6c42\u6bcf\u4e2a\u4eba\u62ff\u5230\u7684\u77f3\u5b50\u5fc5\u987b\u6765\u81ea\u540c\u4e00\u5806\u3002\u3002\u3002\u6c42\u65b9\u6848\u4f7f\u5f97\u62ff\u5230\u77f3\u5b50\u6700\u591a\u7684\u4eba\u62ff\u5230\u7684\u6700\u5c11\u3002\u3002
\n\u4e8c\u5206\u7b54\u6848\u5224\u5b9a\u3002\u3002\uff08\u5047\u8bbe\u7b54\u6848\u4e3a x\uff0c\u82e5\u6ee1\u8db3 \" \sum_{i=1}^n \lceil \frac{a_i}{x} \rceil \leq n \" \u5219\u5408\u6cd5\u3002\u3002<\/p>\n
Problem E. Snaga<\/h5>\n
\u5b9a\u4e49  K(x) \u4e3a\u6700\u5c0f\u7684\u4e0d\u80fd\u6574\u9664 x \u7684\u6570\uff0c\u5b9a\u4e49 \"strength(x) = strength(K(x)) + 1 \" ( \" strength(2) = 0  \"\u3002\u3002
\n\u6c42 \" \sum_{i=A}^B strength(i) \"\u3002<\/p>\n
Problem F. Mars<\/h5>\n
\u8981\u6c42\u6784\u9020\u4e00\u4e2a 2^k \u9636\u7684\u6392\u5217\u3002\u3002
\n\u6ee1\u8db3\u4ee5\u6b64\u6392\u5217\u6784\u9020\u7684\u6ee1\u4e8c\u53c9\u6811\u7684\u6bcf\u4e2a\u7ed3\u70b9\uff0c\uff08\u6bcf\u4e2a\u7ed3\u70b9\u662f\u4e00\u4e2a\u96c6\u5408\uff0c\u4ee5 ai \u4f4d\u7f6e\u7684\u6570\u4e3a\u53f6\u5b50\uff0c\u7136\u540e\u6bcf\u4e2a\u7ed3\u70b9\u7531\u5176\u5de6\u53f3\u5b50\u6811\u5408\u5e76\u800c\u6210\u3002\u3002
\n\u3002\u90fd\u662f\u4e00\u6bb5\u8fde\u7eed\u7684\u6570\u5b57\u3002\u3002\u5df2\u77e5\u6bcf\u5bf9\u6570\u5b57\u4e4b\u95f4\u5b58\u5728\u4e00\u4e2a\u65a5\u529b\u3002\u3002
\n\u6700\u5c0f\u5316\u6392\u5217\u76f8\u90bb\u6570\u5b57\u4e4b\u95f4\u7684\u65a5\u529b\u548c\u3002\u3002\u3002<\/p>\n
<\/p>\n
Analysis: <\/h3>\n
Problem E. Snaga<\/h5>\n
\u6ce8\u610f\u5230  \"K(x) \" \u7684\u503c\u5f88\u5c0f\uff08\u5927\u6982\u4e0d\u8d85\u8fc7 100 \u3002\u3002\u3002
\n\u4e8e\u662f\u66b4\u529b\u5373\u53ef\u3002\u3002<\/p>\n
Problem F. Mars<\/h5>\n
F[i][j] \u8868\u793a\u524d i \u4e2a\u6570\uff0c\u6700\u540e\u4e00\u4e2a\u662f j\u3002\u6211\u4eec\u6ce8\u610f\u5230\u80fd\u8f6c\u79fb\u5230\u8fd9\u4e2a\u72b6\u6001\u7684\u72b6\u6001\uff0c\u65f6\u4e00\u4e2a\u957f\u5ea6\u4e3a low_bit(i) \u7684\u533a\u95f4\u3002
\n\u6ce8\u610f\u5230\u6211\u4eec\u53ef\u4ee5\u7528\u795e\u4f4d\u8fd0\u7b97\u76f4\u63a5\u5f97\u5230\u8fd9\u4e2a\u533a\u95f4\u3002\u3002\u8fd9\u6837\u66b4\u529b\u7684\u8bdd\u590d\u6742\u5ea6\u5c31\u662f O(n^2logn) \u3002\u3002\u3002\u3002<\/p>\n
\r\nconst int N = 1029;\r\n\r\nint f[N][N], a[N][N];\r\nint n, z;\r\n\r\nint main(){\r\n\r\n    n = _1(RD()); REP_2(i, j, n, n) RD(a[i][j]);\r\n\r\n    FLC(f, 0x3f), RST(f[0]); FOR(i, 1, n) REP(j, n){\r\n        int s = (j - j % low_bit(i)) ^ low_bit(i), e = s + low_bit(i);\r\n        FOR(k, s, e) checkMin(f[i][j], f[i-1][k] + a[j][k]);\r\n    }\r\n\r\n    OT(*min_element(f[n-1], f[n-1]+n));\r\n}\r\n<\/pre>\n
\u3002\u52a8\u6001\u89c4\u5212\uff0c\u4f4d\u8fd0\u7b97\u3002\u3002<\/a><\/p>\n
External link: <\/h3>\n
http:\/\/evaluator.hsin.hr\/index.php<\/a>
\nhttp:\/\/www.codeforces.com\/blog\/entry\/5585<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description: Problem A. Dom … \u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u4e32\u4e2d\u7684\u6240\u6709\u7684 \u201cCAMBRIDGE\u201d \u4e2d\u7684\u5b57\u7b26\u3002\u3002 import re print re.sub("[CAMBRIDGE]","",raw_input()) Problem B. F7 \u3002\u3002n \u4e2a\u4eba\u53c2\u52a0\u4e00\u4e2a\u6bd4\u8d5b\uff0c\uff08\u6ca1\u6709\u5e76\u5217\u3002\u3002 \u3002\u3002\u5176\u4e2d\u7b2c i \u540d \u83b7\u5f97 n-i+1 \u5206\u3002\u3002 \u73b0\u5728\u7ed9\u5b9a n \u4e2a\u4eba\u4e00\u4e2a\u521d\u59cb\u5206\u6570\uff0c\u95ee\u6700\u540e\u6709\u591a\u5c11\u4eba\u53ef\u80fd\u83b7\u5f97\u603b\u5206\u7b2c\u4e00\uff1f\uff08\u5e76\u5217\u7b2c\u4e00\u4e5f\u53ef\u4ee5\u3002\u3002 I = lambda: map(int, raw_input().split()) n = input() a = [0] * n for i in range(0, n): a[i] = input() a.sort() i = n best = 0 […]<\/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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[24],"class_list":["post-539","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-24"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-8H","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/539","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=539"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/539\/revisions"}],"predecessor-version":[{"id":540,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/539\/revisions\/540"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=539"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=539"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=539"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}