{"id":2041,"date":"2022-11-08T02:48:19","date_gmt":"2022-11-07T18:48:19","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2041"},"modified":"2022-11-09T22:55:05","modified_gmt":"2022-11-09T14:55:05","slug":"codeton-round-3","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/codeton-round-3\/","title":{"rendered":"CodeTON Round 3"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/codeforces.com\/contest\/1750\">https:\/\/codeforces.com\/contest\/1750<\/a><\/li>\n<\/ul>\n<h2>Problem D. Count GCD<\/h2>\n<p>\u4f3c\u4e4e\u662f <a href=\"https:\/\/www.codechef.com\/submit\/PGCDS\">\u9694\u58c1\u539f\u9898<\/a>&#8230;<\/p>\n<h2>Problem E. Bracket Cost<\/h2>\n<ul>\n<li><a href=\"https:\/\/zhuanlan.zhihu.com\/p\/581182890\">https:\/\/zhuanlan.zhihu.com\/p\/581182890<\/a><\/li>\n<\/ul>\n<p>\u6ca1\u505a\u51fa\u6765\u4f3c\u4e4e\u662f\u56e0\u4e3a <a href=\"https:\/\/t.me\/algorithm_daily_of_minako\/7141\">\u8bfb\u9519\u4e86\u9898&#8230;<\/a><\/p>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u62ec\u53f7\u5e8f\u5217\uff0c\u95ee\u6240\u6709\u5b50\u5e8f\u5217\u7684\u5e73\u8861\u4ee3\u4ef7 f() \u7684\u548c\u3002 f() \u5b9a\u4e49\u4e3a\uff0c\u7528\u6700\u5c11\u7684 shift \u548c insert \u64cd\u4f5c\uff0c\u4f7f\u8be5\u5e8f\u5217\u5e73\u8861\u3002<br \/>\n\u6ce8\u610f shift \u64cd\u4f5c\u53ef\u4ee5\u4efb\u9009\u4e00\u4e2a\u5b50\u4e32\u8fdb\u884c&#8230;<\/p>\n<h2>Problem F. Majority<\/h2>\n<p>\u95ee\u6709\u591a\u5c11\u957f\u5ea6\u4f4d n (n&lt;=5000) \u7684 0-1 \u5e8f\u5217\uff0c\u6ee1\u8db3\u8be5\u5e8f\u5217\u53ef\u4ee5\u6267\u884c\u4efb\u610f\u6b21\u8fde\u63a5\u64cd\u4f5c\u53d8\u4e3a\u5168 1. \u8fde\u63a5\u64cd\u4f5c\u5b9a\u4e49\u4e3a\uff0c\u9009\u62e9\u4e00\u4e2a\u533a\u95f4 i,j, \u6ee1\u8db3 si = sj = 1\uff0c\u5c06 [i,j] \u5168\u90e8\u53d8\u4e3a 1\uff0c\u8981\u6c42\u64cd\u4f5c\u524d\u533a\u95f4\u4e2d 1 \u7684\u6570\u76ee >= 0 \u7684\u6570\u76ee\u3002<\/p>\n<p>dp[i][j] \u8868\u793a\u6700\u7ec8\u72b6\u6001\u957f\u5ea6\u4e3a i\uff0c\u4e14\u5de6\u8fb9\u6709\u8fde\u7eed j \u4e2a 1\uff08\u5f62\u5982 111100..001\uff09\u7684\u65b9\u6848\u6570\u3002<\/p>\n<h2>Problem G. Doping<\/h2>\n<p>\u5148\u4e0d\u8003\u8651\u5b57\u5178\u5e8f\u7684\u95ee\u9898\uff0c\u90a3\u4e48\u662f\u67d0\u79cd\u5bf9\u6392\u5217\u7684\u5212\u5206\u3002\u3002\u3002<br \/>\n\u8fd9\u7c7b\u9898\u76ee\u6709\u5f88\u591a\uff0c\u6bd4\u5982 <a href=\"http:\/\/121.40.196.125\/p\/1931?view=classic\">[Shoi2007] Permutation \u6709\u5e8f\u7684\u8ba1\u6570<\/a>..\uff08\u8fd9\u4e24\u4e2a\u9898\u76ee\u8fd8\u786e\u5b9e\u633a\u6709\u5173\u8054\u7684\u3002\u3002\u3002\uff09<br \/>\n\u9700\u8981\u5148 dp \u51fa\u8fd9\u4e2a\u4e1c\u897f\uff0c\u7136\u540e\u8003\u8651\u5b57\u5178\u5e8f\u53ea\u8981\u679a\u4e3e\u524d\u7f00\u5373\u53ef\u3002<\/p>\n<p>\u9519\u4f4d\u6392\u5217<br \/>\nhttps:\/\/en.wikipedia.org\/wiki\/Derangement<br \/>\nhttp:\/\/oeis.org\/A000166<\/p>\n<pre>\n1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, ...\n<\/pre>\n<p>k \u4e0d\u52a8\u70b9\u6392\u5217<br \/>\nhttps:\/\/en.wikipedia.org\/wiki\/Rencontres_numbers<\/p>\n<pre>\n1                               \n0   1                           \n1   0   1                       \n2   3   0   1                   \n9   8   6   0   1               \n44  45  20  10  0   1           \n265 264 135 40  15  0   1       \n1854    1855    924 315 70  21  0   1   \n14833   14832   7420    2464    630 112 28  0   1\n<\/pre>\n<p>http:\/\/oeis.org\/A134830<br \/>\n\u7b2c\u4e00\u4e2a\u4e0d\u52a8\u70b9\u5728\u4f4d\u7f6e k \u7684\u6392\u5217<br \/>\n\uff08\u6709 k \u4e2a\u5bf9\u8c61\u6709\u540e\u7ee7\u7684\u6392\u5217\uff0c\u4f7f\u5f97\u6392\u5217\u4e2d\u6ca1\u6709\u8fde\u7eed\u6570\u5b57\uff09<\/p>\n<pre>\n1\n1 0\n2 1 1\n6 4 3 2\n24 18 14 11 9\n120 96 78 64 53 44\n720 600 504 426 362 309 265\n5040 4320 3720 3216 2790 2428 2119 1854\n40320 35280 30960 27240 24024 21234 18806 16687 14833\n362880 322560 287280 256320 229080 205056 183822 165016 148329 133496\n414233 51353 2943360 2656080 2399760 2170680 1965624 1781802 1616786 1468457 1334961\n<\/pre>\n<p>\u80fd\u88ab\u5206\u6210 k \u6bb5\u7684\u6392\u5217\uff08\u6bcf\u6bb5\u90fd\u662f\u8fde\u7eed\u6570\u5b57\uff09<\/p>\n<pre>\n0\n1 0\n1 2 2\n1 3 9 10\n1 4 18 44 52\n1 5 30 110 265 308\n1 6 45 220 795 1854 2118\n1 7 63 385 1855 6489 14833 16686\n1 8 84 616 3710 17304 59332 133496 148328\n1 9 108 924 6678 38934 177996 600732 1334961 1468456\n<\/pre>\n<p>\u6700\u957f\u8fde\u7eed\u6bb5\u957f\u5ea6\u4e3a k \u7684\u6392\u5217\uff1f<\/p>\n<p>\u73af\u7684\u6570\u76ee<br \/>\nhttp:\/\/oeis.org\/A008275<\/p>\n<pre>\n1\n1 1\n2 3 1\n6 11 6 1\n24 50 35 10 1\n120 274 225 85 15 1\n720 1764 1624 735 175 21 1\n5040 13068 13132 6769 1960 322 28 1\n40320 109584 118124 67284 22449 4536 546 36 1\n362880 1026576 1172700 723680 269325 63273 9450 870 45 1\n<\/pre>\n<p>\u6700\u957f\u73af<br \/>\nhttp:\/\/oeis.org\/A126074<\/p>\n<pre>\n1\n1 1\n1 3 2\n1 9 8 6\n1 25 40 30 24\n1 75 200 180 144 120\n1 231 980 1260 1008 840 720\n1 763 5152 8820 8064 6720 5760 5040\n1 2619 28448 61236 72576 60480 51840 45360 40320\n1 9495 162080 461160 653184 604800 518400 453600 403200 362880\n<\/pre>\n<p>\u6700\u77ed\u73af<br \/>\nhttp:\/\/oeis.org\/A145877<\/p>\n<pre>\n1\n1 1\n4 0 2\n15 3 0 6\n76 20 0 0 24\n455 105 40 0 0 120\n3186 714 420 0 0 0 720\n25487 5845 2688 1260 0 0 0 5040\n229384 52632 22400 18144 0 0 0 0 40320\n2293839 525105 223200 151200 72576 0 0 0 0 362880\n<\/pre>\n<h2>Problem H. BinaryStringForces<\/h2>\n<p>\u4e5f\u662f 0-1 \u5e8f\u5217\uff0c\u4efb\u610f\u6267\u884c\u64cd\u4f5c\uff0c\u8fd9\u91cc\u9996\u5148\u628a\u5e8f\u5217\u6309\u7167\u8fde\u7eed\u7684 01 \u5206\u6210\u82e5\u5e72\u7aef\uff0c\u6bcf\u6b21\u64cd\u4f5c\u5b9a\u4e49\u4e3a\u9009\u62e9\u76f8\u90bb\u7684\u4e24\u6bb5\uff0c\u5c06\u8f83\u5c11\u7684\u989c\u8272\u67d3\u6210\u8f83\u591a\u7684\uff08\u76f8\u7b49\u65f6\u67d3\u8272\u6210 1\uff09\u3002<br \/>\n\u95ee\u7ed9\u5b9a\u7684\u957f\u5ea6\u4e3a n \u7684\u5b57\u7b26\u4e32\uff0c\u6709\u591a\u5c11\u5b50\u4e32\uff0c\u6ee1\u8db3\u53ef\u4ee5\u6267\u884c\u4efb\u610f\u6b21\u64cd\u4f5c\u540e\u5168\u90e8\u67d3\u8272\u6210 1\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/codeforces.com\/contest\/1750 Problem D. Count GCD \u4f3c\u4e4e\u662f \u9694\u58c1\u539f\u9898&#8230; Problem E. Bracket Cost https:\/\/zhuanlan.zhihu.com\/p\/581182890 \u6ca1\u505a\u51fa\u6765\u4f3c\u4e4e\u662f\u56e0\u4e3a \u8bfb\u9519\u4e86\u9898&#8230; \u7ed9\u5b9a\u4e00\u4e2a\u62ec\u53f7\u5e8f\u5217\uff0c\u95ee\u6240\u6709\u5b50\u5e8f\u5217\u7684\u5e73\u8861\u4ee3\u4ef7 f() \u7684\u548c\u3002 f() \u5b9a\u4e49\u4e3a\uff0c\u7528\u6700\u5c11\u7684 shift \u548c insert \u64cd\u4f5c\uff0c\u4f7f\u8be5\u5e8f\u5217\u5e73\u8861\u3002 \u6ce8\u610f shift \u64cd\u4f5c\u53ef\u4ee5\u4efb\u9009\u4e00\u4e2a\u5b50\u4e32\u8fdb\u884c&#8230; Problem F. Majority \u95ee\u6709\u591a\u5c11\u957f\u5ea6\u4f4d n (n&lt;=5000) \u7684 0-1 \u5e8f\u5217\uff0c\u6ee1\u8db3\u8be5\u5e8f\u5217\u53ef\u4ee5\u6267\u884c\u4efb\u610f\u6b21\u8fde\u63a5\u64cd\u4f5c\u53d8\u4e3a\u5168 1. \u8fde\u63a5\u64cd\u4f5c\u5b9a\u4e49\u4e3a\uff0c\u9009\u62e9\u4e00\u4e2a\u533a\u95f4 i,j, \u6ee1\u8db3 si = sj = 1\uff0c\u5c06 [i,j] \u5168\u90e8\u53d8\u4e3a 1\uff0c\u8981\u6c42\u64cd\u4f5c\u524d\u533a\u95f4\u4e2d 1 \u7684\u6570\u76ee >= 0 \u7684\u6570\u76ee\u3002 dp[i][j] \u8868\u793a\u6700\u7ec8\u72b6\u6001\u957f\u5ea6\u4e3a i\uff0c\u4e14\u5de6\u8fb9\u6709\u8fde\u7eed [&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":[1],"tags":[],"class_list":["post-2041","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wV","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2041","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=2041"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2041\/revisions"}],"predecessor-version":[{"id":2042,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2041\/revisions\/2042"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2041"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2041"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2041"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}