{"id":86,"date":"2010-12-19T07:59:16","date_gmt":"2010-12-18T23:59:16","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=86"},"modified":"2012-03-03T07:59:33","modified_gmt":"2012-03-02T23:59:33","slug":"srm-491","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-491\/","title":{"rendered":"SRM 491"},"content":{"rendered":"<p>500 :<br \/>\n\u95ee\u9898\u63cf\u8ff0\uff1a\u8ba1\u6570\u95ee\u9898\uff0c\u6ee1\u8db3\u4e0b\u5217\u6761\u4ef6\u7684\u516d\u9762\u4f53\u9ab0\u5b50\u7684\u6570\u76ee\u3002\u3002<br \/>\n1\uff1a\u6570\u5b57\u8303\u56f4\u5728[1\uff0cN]\u4e4b\u95f4\u4e14\u4e24\u4e24\u4e0d\u76f8\u540c\u3002<br \/>\n2\uff1a\u5bf9\u9762\u6570\u5b57\u548c\u76f8\u7b49\u4e14 >= k\u3002<br \/>\n3\uff1a\u7ecf\u8fc7\u65cb\u8f6c\u76f8\u540c\u7684\u7b5b\u5b50\u88ab\u770b\u4f5c\u662f\u7b49\u4ef7\u7684\u3002<br \/>\n&#8230;<br \/>\n\u7b97\u6cd5\u5206\u6790\uff1a \u679a\u4e3e\uff0c\u53ea\u8981\u8ba4\u8bc6\u5230\uff08\u54ea\u5c3c\uff09\uff0c&#8221; \u4efb\u4f553\u5bf9\u6570\uff0c\u53ea\u4f1a\u4ea7\u751f\u4e24\u7ec4\u672c\u8d28\u4e0d\u540c\u7684\u89e3 &#8221; \u5c31\u53ef\u4ee5\u4e86\u3002<br \/>\n\uff08room \u91cc\u6709\u4eba\u7528DP?.. \u662f\u600e\u4e48DP\u7684\u5462\uff1f\uff09<\/p>\n<p>1000 :<br \/>\n\u95ee\u9898\u63cf\u8ff0\uff1a\u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a N \u7684\u6570\u8f74\uff0c\u8f93\u5165 M \u4e2a\u4e09\u5143\u7ec4 (l, r, d) \uff0c\u7834\u574f\u6240\u6709 [l, r] \u4e2d\uff0c\u88ab d \u6574\u9664\u7684\u4f4d\u7f6e\uff1f\u95ee\u4e00\u5171\u88ab\u7834\u574f\u4e86\u591a\u5c11\u4e2a\u4f4d\u7f6e\u3002<br \/>\n\u7b97\u6cd5\u5206\u6790\uff1a\u4ecb\u4e8e M \u503c\u8f83\u5c0f\uff0c\u53ef\u4ee5\u7528\u5bb9\u65a5\u539f\u7406\u505a\u3002\uff08\u7ebf\u6bb5\u6811\u53ef\u4ee5\u9a6c\uff1f\uff09<\/p>\n<pre lang=\"cpp\" file=\"500.cpp\">\r\n#include <iostream>\r\nusing namespace std;\r\n\r\nint Cn3(int n){\r\n\tif (n < 3) return 0;\r\n\treturn n * (n-1) * (n-2) \/ 6;\r\n}\r\n\r\n\r\nclass FoxMakingDiceEasy{\r\npublic:\r\n\t\tint theCount(int n, int k){\t\t\t\r\n\t\t\tint res = 0, MAX = n * 2 - 5;\r\n\t\t\t\/\/ i: \u4e3a\u4e86\u8ba1\u7b97\uff0c\u679a\u4e3e\u6b63\u53cd\u4e24\u9762\u7684\u6570\u5b57\u548c - 1 \u7684\u503c\u3002                      \r\n\t\t\tfor (int i=k-1;i<MAX;i++){\r\n\t\t\t\tif (i <= n){\r\n\t\t\t\t\tres += Cn3(i\/2);\r\n\t\t\t\t}\r\n\t\t\t\telse {                                                 \r\n\t\t\t\t\tres += Cn3(n - i\/2);\r\n\t\t\t\t}\t\t\t\t\r\n\t\t\t}\r\n\t\t\treturn res * 2;\r\n\t\t}\r\n};\r\n<\/pre>\n<pre lang=\"cpp\" file=\"1000.cpp\">\r\n#include <iostream>\r\n#include <vector>\r\nusing namespace std ;\r\n\r\nclass BottlesOnShelf\r\n{\r\n\tpublic :\r\n\t\tlong long  gcd( long long a , long long b ) { if ( b == 0 ) return a ; return gcd(b , a%b) ; }\r\n\t\tlong long  lcm( long long a , long long b ) { long long c = gcd(a , b) ; return a * b \/ c ; }\r\n\t\t\r\n\t\tint getNumBroken(int N, vector <int> L, vector <int> R, vector <int> D)\r\n\t\t{\r\n\t\t\tint M = L.size() , p , ll , rr , ans ;\r\n\t\t\tlong long w , c ;\r\n\r\n\t\t\tans = 0 ;\r\n\t\t\tfor ( int i = 1 ; i < (1 << M) ; i ++ )\r\n\t\t\t{\r\n\t\t\t\tp = 0 ;\r\n\t\t\t\tfor ( int j = 0 ; j < M ; j ++ ) if ( ( i >> j ) & 1 ) p ++ ;\r\n\t\t\t\t\r\n\t\t\t\tll = 1 ; rr = N ; w = -1 ;\r\n\t\t\t\tfor ( int j = 0 ; j < M ; j ++ ) if ( ( i >> j ) & 1 )\r\n\t\t\t\t{\r\n\t\t\t\t\tif ( L[j] > ll ) ll = L[j] ;\r\n\t\t\t\t\tif ( R[j] < rr ) rr = R[j] ;\r\n\t\t\t\t\tif ( w == -1 ) w = D[j] ; else w = lcm(w , (long long)D[j]) ;\r\n\t\t\t\t}\r\n\t\t\t\t\r\n\t\t\t\tc = (long long)(rr \/ w) - (long long)((ll-1) \/ w) ;\r\n\t\t\t\tif ( p % 2 == 1 ) ans += c ; else ans -= c ;\r\n\t\t\t}\r\n\t\t\treturn ans ;\r\n\t\t}\r\n} ;\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>500 : \u95ee\u9898\u63cf\u8ff0\uff1a\u8ba1\u6570\u95ee\u9898\uff0c\u6ee1\u8db3\u4e0b\u5217\u6761\u4ef6\u7684\u516d\u9762\u4f53\u9ab0\u5b50\u7684\u6570\u76ee\u3002\u3002 1\uff1a\u6570\u5b57\u8303\u56f4\u5728[1\uff0cN]\u4e4b\u95f4\u4e14\u4e24\u4e24\u4e0d\u76f8\u540c\u3002 2\uff1a\u5bf9\u9762\u6570\u5b57\u548c\u76f8\u7b49\u4e14 >= k\u3002 3\uff1a\u7ecf\u8fc7\u65cb\u8f6c\u76f8\u540c\u7684\u7b5b\u5b50\u88ab\u770b\u4f5c\u662f\u7b49\u4ef7\u7684\u3002 &#8230; \u7b97\u6cd5\u5206\u6790\uff1a \u679a\u4e3e\uff0c\u53ea\u8981\u8ba4\u8bc6\u5230\uff08\u54ea\u5c3c\uff09\uff0c&#8221; \u4efb\u4f553\u5bf9\u6570\uff0c\u53ea\u4f1a\u4ea7\u751f\u4e24\u7ec4\u672c\u8d28\u4e0d\u540c\u7684\u89e3 &#8221; \u5c31\u53ef\u4ee5\u4e86\u3002 \uff08room \u91cc\u6709\u4eba\u7528DP?.. \u662f\u600e\u4e48DP\u7684\u5462\uff1f\uff09 1000 : \u95ee\u9898\u63cf\u8ff0\uff1a\u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a N \u7684\u6570\u8f74\uff0c\u8f93\u5165 M \u4e2a\u4e09\u5143\u7ec4 (l, r, d) \uff0c\u7834\u574f\u6240\u6709 [l, r] \u4e2d\uff0c\u88ab d \u6574\u9664\u7684\u4f4d\u7f6e\uff1f\u95ee\u4e00\u5171\u88ab\u7834\u574f\u4e86\u591a\u5c11\u4e2a\u4f4d\u7f6e\u3002 \u7b97\u6cd5\u5206\u6790\uff1a\u4ecb\u4e8e M \u503c\u8f83\u5c0f\uff0c\u53ef\u4ee5\u7528\u5bb9\u65a5\u539f\u7406\u505a\u3002\uff08\u7ebf\u6bb5\u6811\u53ef\u4ee5\u9a6c\uff1f\uff09 #include using namespace std; int Cn3(int n){ if (n < 3) return 0; return n * (n-1) * (n-2) [&hellip;]\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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-86","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1o","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/86","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=86"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/86\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=86"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=86"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=86"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}