{"id":896,"date":"2014-05-31T05:30:35","date_gmt":"2014-05-30T21:30:35","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=896"},"modified":"2015-07-25T14:35:30","modified_gmt":"2015-07-25T06:35:30","slug":"srm-622","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-622\/","title":{"rendered":"SRM 622"},"content":{"rendered":"

<\/p>\n

250. BuildingRoutes<\/h2>\n

Brief description:<\/h3>\n

\u7ed9\u5b9a\u4e00\u5e45\u5b8c\u5168\u56fe\u3002\u3002\u3002\u3002\u5bf9\u4e8e\u4efb\u610f\u4e24\u70b9\uff0c\u5982\u679c\u5176\u6700\u8fd1\u8def\u5f84\u53ef\u80fd\u7ecf\u8fc7\u67d0\u6761\u9053\u8def\uff0c\u5219\u8fd9\u6761\u9053\u8def\u7684\u62e5\u6324\u5ea6 + 1<\/code>.\u3002
\n\u3002\u95ee\u62e5\u6324\u5ea6 > K<\/code> \u7684\u9053\u8def\u6709\u591a\u5c11\u3002\u3002\u3002<\/p>\n

Analysis:<\/h3>\n

\u3002\u3002\u3002\u76f4\u63a5 Floyd + \u66b4\u529b O(n4) \u679a\u4e3e\u7edf\u8ba1\u3002\u3002\u3002<\/p>\n

500. Ethernet<\/h2>\n

\u7ed9\u5b9a\u4e00\u9897 n<\/code> \u4e2a\u7ed3\u70b9\u7684\u8fb9\u6743\u6811\uff0c\u8981\u6c42\u5c06\u6811\u5212\u5206\u6210\u5c3d\u53ef\u80fd\u5c11\u7684\u5b50\u6811\uff0c\u4f7f\u5f97\u6bcf\u68f5\u5b50\u6811\u7684 diameter<\/code> \u90fd\u4e0d\u5927\u4e8e K<\/code>\u3002<\/p>\n

http:\/\/hi.baidu.com\/thinking610\/item\/afdd261dd5b152068fbde4d2<\/a>
\n\u60f3\u590d\u6742\u4e86\u3002\u3002\u3002\u53ef\u4ee5\u76f4\u63a5 dfs()<\/code> \u8d2a\u5fc3\u7684\u3002\u3002\u3002<\/p>\n

900. FibonacciXor<\/h2>\n

Brief description:<\/h3>\n

\u8bbe g(n)<\/code> \u8868\u793a\u5c06 n<\/code> \u7684 Fibnacci \u5c55\u5f00\u793a\u4e3a\u4e8c\u8fdb\u5236\u6570\u65f6\u7684\u503c\u3002\u3002<\/p>\n

\u2014\u2014\u2014\u2014 \u4f8b\u5982\u3002\u3002
\n 9 = F[4] + F[0] = 8 + 1..
\n g(9) = B(10001) = 17 <\/code><\/p>\n

\u6c42 \\Xor_{i=l}^r g(i)<\/code><\/p>\n

\u3002\u3002\u3002n <= 10^15<\/code> ...<\/p>\n

\r\nconst int FN = 90;\r\nbitset<FN> B[FN], BB;\r\nLL F[FN];\r\n \r\nvoid f(bitset<FN>& b, LL n){\r\n    if (n){\r\n        int t = upper_bound(F, F+FN, n)-F-1;\r\n        if ((n-F[t]+1)&1) b.flip(t);\r\n        f(b, n-F[t]); b ^= B[t]; \/\/f(b, F[t]-1);\r\n    }\r\n}\r\n \r\n \r\nclass FibonacciXor{\r\npublic:\r\n\tint find(long long l, long long r) {\r\n \r\n        REP(i, FN) B[i].reset(); BB.reset();\r\n \r\n        F[0] = 1, F[1] = 2; FOR(i, 2, FN) F[i] = F[i-1] + F[i-2];\r\n        FOR(i, 1, FN) f(B[i], F[i]-1);\r\n \r\n        f(BB, r), f(BB, l-1); int res = 0;\r\n        REP(i, FN) if (BB[i]) INC(res, pow(2, i));\r\n        return res;\r\n\t}\r\n};\r\n \r\n<\/pre>\n
Analysis:<\/h3>\n
\u3002\u3002\u6bd4\u6570\u4f4d DP \u7b80\u5355\u3002\u3002\u76f4\u63a5\u8ba8\u8bba\u9ad8\u4f4d\u662f\u5426\u662f 1\u3002\u53ef\u4ee5\u9012\u5f52\u5230\u4e24\u4e2a\u5b50\u95ee\u9898\u3002\u3002\u3002\u800c\u5176\u4e2d\u4e00\u4e2a\u5fc5\u7136\u662f\u67d0\u4e2a F[i]-1...
\n\u3002\u3002\u4e8e\u662f\u5229\u7528 bitset \u7f13\u5b58\u6240\u6709 F[i]-1 \u4f4d\u7f6e\u7684\u7ed3\u679c\u5373\u53ef\u3002\u3002<\/p>\n
External link:<\/h2>\n
https:\/\/gist.github.com\/lychees\/369d5ead82bbb3253e3d<\/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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[17],"tags":[],"class_list":["post-896","post","type-post","status-publish","format-standard","hentry","category-topcoder"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-es","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/896","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=896"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/896\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=896"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=896"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=896"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}