{"id":2938,"date":"2023-05-29T20:25:56","date_gmt":"2023-05-29T12:25:56","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2938"},"modified":"2023-05-30T13:12:23","modified_gmt":"2023-05-30T05:12:23","slug":"facebook-hacker-cup-2022-round-2","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/facebook-hacker-cup-2022-round-2\/","title":{"rendered":"Facebook Hacker Cup 2022 Round 2"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.facebook.com\/codingcompetitions\/hacker-cup\/2022\/round-2\">https:\/\/www.facebook.com\/codingcompetitions\/hacker-cup\/2022\/round-2<\/a><\/li>\n<\/ul>\n<h2>Problem A. Perfectly Balanced<\/h2>\n<p>\u9898\u610f\uff1a\u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u6bcf\u6b21\u8be2\u95ee\u4e00\u4e2a\u5b50\u4e32\uff0c\u95ee\u662f\u5426\u662f\u51e0\u4e4e\u5e73\u8861\u7684\u3002<br \/>\n\u51e0\u4e4e\u5e73\u8861\u7684\u5b9a\u4e49\u662f\uff0c\u4ece\u5b50\u4e32\u4e2d\u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u540e\uff0c\u957f\u5ea6\u4e3a\u5076\u6570\uff0c\u4e14\u524d\u534a\u6bb5\u4e2d\u6bcf\u4e2a\u5b57\u7b26\u7684\u51fa\u73b0\u6b21\u6570\u4e0e\u540e\u534a\u6bb5\u76f8\u7b49\u3002<\/p>\n<p>A1 \u4e2d\u5b57\u7b26\u96c6\u6765\u81ea\u5c0f\u5199\u5b57\u7b26\u3002A2 \u4e2d\u5b57\u7b26\u96c6\u6765\u81ea\u4efb\u610f int\u3002<\/p>\n<p>\u5206\u6790\uff1a\u518d\u8003\u8651\u5f31\u5316\uff0c\u5982\u679c\u5b57\u7b26\u96c6\u53ea\u6709 {0, 1}\uff0c\u90a3\u4e48\u6211\u4eec\u53ea\u8981\u5148\u5224\u65ad\u4e0b\u957f\u5ea6\u662f\u5426\u4e3a\u5947\u6570\uff0c\u7136\u540e\u679a\u4e3e\u4e00\u4e0b\u5220\u54ea\u4e2a\u4f4d\u7f6e\uff0c\u7136\u540e\u6811\u72b6\u6570\u7ec4\u6bd4\u8f83\u4e00\u4e0b\u4e24\u6bb5 1 \u7684\u4e2a\u6570\u662f\u5426\u4e00\u6837\u5373\u53ef\u3002<\/p>\n<p>\u518d\u8003\u8651\u5982\u4f55\u4e0d\u679a\u4e3e\u5220\u54ea\u4e2a\u4f4d\u7f6e\uff0c\u54ea\u4e48\u5c31\u8ba8\u8bba\u4ece\u54ea\u8fb9\u5220\uff0c\u7136\u540e\u770b\u4e24\u8fb9\u7684 diff \u662f\u5426\u662f\u4e00\u5373\u53ef\u3002\u8bbe S(l, r) \u8868\u793a [l, r) \u8fd9\u4e2a\u533a\u95f4\u91cc 1 \u51fa\u73b0\u7684\u6b21\u6570\uff0c\u90a3\u4e48\u5c31\u662f\u6bd4\u8f83\u4e00\u4e0b<\/p>\n<ul>\n<li>S(ml, r) &#8211; S(l, ml) = 1 \u6216\u8005 <\/li>\n<li>S(l, mr) &#8211; S(mr, r) = 1\u3002<\/li>\n<\/ul>\n<p>\u56e0\u6b64\u5bf9\u4e8e A1\uff0c\u6211\u4eec\u53ea\u8981\u5f00 25 \u68f5\u6811\u72b6\u6570\u7ec4\u5c31\u80fd\u901a\u8fc7\u3002\u5bf9\u4e8e\u5b57\u7b26\u96c6\u4efb\u610f\u7684\u60c5\u51b5\uff0c\u6211\u4eec\u628a\u6240\u6709\u6570\u5b57\u6620\u5c04\u6210\u4e00\u4e2a\u968f\u673a uint\uff0c\u7136\u540e\u770b diff \u662f\u5426\u6070\u597d\u662f\u67d0\u4e2a\u5b57\u7b26\u7684\u6620\u5c04\u5373\u53ef\u3002\u4ee3\u7801\u53cd\u800c\u6bd4 A1 \u66f4\u7b80\u5355\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/bitwise&gt;\r\n#include &lt;lastweapon\/fenwicktree&gt;\r\n#include &lt;bits\/stdc++.h&gt;\r\n\r\nusing namespace lastweapon;\r\n\r\nmt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());\r\nuniform_int_distribution&lt;uint64_t&gt; rnd(0, ULLONG_MAX);\r\n\r\nconst int N = int(1e6) + 9;\r\n\r\nmap&lt;int, uLL&gt; H;\r\nset&lt;uLL&gt; inHash;\r\nuLL h(int x) {\r\n    if (!CTN(H, x)) inHash.insert(H&#x5B;x] = rnd(gen));\r\n    return H&#x5B;x];\r\n}\r\n\r\nfenwick_tree&lt;uLL&gt; T;\r\nint a&#x5B;N];\r\nint n;\r\n\r\nint f(int l, int r) {\r\n    if ((r-l)&amp;1) return 0;\r\n    int m = (l+r)\/2;\r\n    uLL L = T.sum(l), R = T.sum(r+1), ML = T.sum(m), MR = T.sum(m+1);\r\n    return CTN(inHash, (MR-L)-(R-MR)) || CTN(inHash, (R-ML)-(ML-L));\r\n}\r\n\r\nint main() {\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    Rush {\r\n        printf(&quot;Case #%d: &quot;, ++Case);\r\n        H.clear(); inHash.clear();\r\n\r\n        RD(n); T = fenwick_tree&lt;uLL&gt;(n+1);\r\n        REP_1(i, n) T.add(i, h(RD(a&#x5B;i])));\r\n\r\n        int z = 0; Rush {\r\n            int cmd, l, r; RD(cmd, l, r);\r\n            if (cmd == 1) {\r\n                T.add(l, h(r) - h(a&#x5B;l]));\r\n                a&#x5B;l] = r;\r\n            } else {\r\n                z += f(l, r);\r\n            }\r\n        }\r\n        printf(&quot;%d\\n&quot;, z);\r\n    }\r\n}\r\n\r\n<\/pre>\n<h2>Problem B. Balance Sheet<\/h2>\n<p>\u6211\u4eec\u628a day \u770b\u6210\u70b9\uff0cclient \u770b\u6210\u8fb9\uff0c\u90a3\u4e48\u663e\u7136\u662f dag dp\u3002<br \/>\n\u5bf9\u4e8e\u5bf9\u4e8e top K \u53ea\u8981\u7528 multiset \u8bb0\u5f55 dp \u503c\u5373\u53ef\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nconst int N = int(1e6) + 9;\r\n\r\ntypedef pair&lt;pair&lt;int, int&gt;, int&gt; rec;\r\n\r\nmultiset&lt;LL&gt; z;\r\n\r\nmap&lt;int, multiset&lt;LL&gt; &gt; c, d;\r\n\r\nvector&lt;rec&gt; e;\r\nint a&#x5B;N],b&#x5B;N],x&#x5B;N],y&#x5B;N];\r\n\r\nint n, k;\r\n\r\nvoid fix(multiset&lt;LL&gt;&amp; x) {\r\n    while (x.size() &gt; k) x.erase(x.begin());\r\n}\r\n\r\nint main() {\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;balance_sheet_input.txt&quot;, &quot;r&quot;, stdin);\r\n    freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    Rush {\r\n        printf(&quot;Case #%d: &quot;, ++Case);\r\n        z.clear(); RD(n, k);\r\n\r\n        c.clear(); d.clear(); e.clear();\r\n        REP_1(i, n) {\r\n            RD(a&#x5B;i],b&#x5B;i],x&#x5B;i],y&#x5B;i]);\r\n            e.PB({{a&#x5B;i], x&#x5B;i]}, -i});\r\n            e.PB({{b&#x5B;i], y&#x5B;i]}, i});\r\n        }\r\n        SRT(e);\r\n\r\n        for (auto&amp; t: e) {\r\n            if (t.se &lt; 0) { \/\/ buy\r\n                int id = -t.se;\r\n                c&#x5B;id].insert(0);\r\n                for (auto i: d&#x5B;a&#x5B;id]]) {\r\n                    c&#x5B;id].insert(i + x&#x5B;id]);\r\n                    fix(c&#x5B;id]);\r\n                }\r\n                for (auto i: c&#x5B;id]) {\r\n                    z.insert(i); fix(z);\r\n                }\r\n\r\n            } else { \/\/ sell\r\n                int id = t.se;\r\n                for (auto i : c&#x5B;id]) {\r\n                    d&#x5B;b&#x5B;id]].insert(i - y&#x5B;id]);\r\n                    fix(d&#x5B;b&#x5B;id]]);\r\n                }\r\n            }\r\n        }\r\n\r\n        Int zz = 0; for (auto&amp; t: z) zz += Int(t);\r\n        cout &lt;&lt; zz &lt;&lt;endl;\r\n    }\r\n\r\n}\r\n<\/pre>\n<h2>Problem C. Balance Scale<\/h2>\n<p>n \u888b\u997c\u5e72\uff0c\u7b2c i \u5f85\u91cc\u6709 C_i \u5757\u91cd W_i \u7684\u997c\u5e72\u3002<br \/>\n\u4ece\u6240\u6709\u7684\u997c\u5e72\u4e2d\u4efb\u53d6 k \u4e2a\uff0c\u95ee\u5176\u4e2d\u6700\u91cd\u7684\u4e00\u5757\u997c\u5e72\uff08\u5982\u679c\u6709\u591a\u4e2a\uff0c\u4efb\u53d6\u5176\u4e00\uff09\u6765\u81ea\u7b2c\u4e00\u888b\u7684\u6982\u7387\u3002<\/p>\n<h2>Problem D. Work-Life Balance<\/h2>\n<p>\u9898\u610f\uff1a\u7ed9\u5b9a\u957f\u5ea6\u4e3a n \u7684\u5e8f\u5217 {Ai}\uff0c\u652f\u6301 m \u6b21\u5355\u70b9\u4fee\u6539\uff0c\u95ee\u6bcf\u6b21\u4fee\u6539\u540e\u81f3\u5c11\u591a\u5c11\u6b21 swap \u64cd\u4f5c\uff0c\u53ef\u4ee5\u8ba9\u5e8f\u5217\u7684\u4e00\u4e2a\u7ed9\u5b9a\u7684\u524d\u7f00\u548c\u7b49\u4e8e\u5269\u4e0b\u90e8\u5206\u7684\u540e\u7f00\u548c\u3002<\/p>\n<ul>\n<li>D1 \u4e2d Ai \u2208 {1,2,3}\uff0c\u53ef\u4ee5\u4ea4\u6362\u4efb\u610f\u4f4d\u7f6e\u3002<\/li>\n<li>D2 \u4e2d Ai \u2208 {1,2}\uff0c\u53ea\u53ef\u4ee5\u4ea4\u6362\u76f8\u90bb\u4f4d\u7f6e\u3002<\/li>\n<\/ul>\n<p>\u5206\u6790\uff1aD1 \u7684\u60c5\u51b5\u663e\u7136\u53ef\u4ee5\u8d2a\u5fc3\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.facebook.com\/codingcompetitions\/hacker-cup\/2022\/round-2 Problem A. Perfectly Balanced \u9898\u610f\uff1a\u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u6bcf\u6b21\u8be2\u95ee\u4e00\u4e2a\u5b50\u4e32\uff0c\u95ee\u662f\u5426\u662f\u51e0\u4e4e\u5e73\u8861\u7684\u3002 \u51e0\u4e4e\u5e73\u8861\u7684\u5b9a\u4e49\u662f\uff0c\u4ece\u5b50\u4e32\u4e2d\u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u540e\uff0c\u957f\u5ea6\u4e3a\u5076\u6570\uff0c\u4e14\u524d\u534a\u6bb5\u4e2d\u6bcf\u4e2a\u5b57\u7b26\u7684\u51fa\u73b0\u6b21\u6570\u4e0e\u540e\u534a\u6bb5\u76f8\u7b49\u3002 A1 \u4e2d\u5b57\u7b26\u96c6\u6765\u81ea\u5c0f\u5199\u5b57\u7b26\u3002A2 \u4e2d\u5b57\u7b26\u96c6\u6765\u81ea\u4efb\u610f int\u3002 \u5206\u6790\uff1a\u518d\u8003\u8651\u5f31\u5316\uff0c\u5982\u679c\u5b57\u7b26\u96c6\u53ea\u6709 {0, 1}\uff0c\u90a3\u4e48\u6211\u4eec\u53ea\u8981\u5148\u5224\u65ad\u4e0b\u957f\u5ea6\u662f\u5426\u4e3a\u5947\u6570\uff0c\u7136\u540e\u679a\u4e3e\u4e00\u4e0b\u5220\u54ea\u4e2a\u4f4d\u7f6e\uff0c\u7136\u540e\u6811\u72b6\u6570\u7ec4\u6bd4\u8f83\u4e00\u4e0b\u4e24\u6bb5 1 \u7684\u4e2a\u6570\u662f\u5426\u4e00\u6837\u5373\u53ef\u3002 \u518d\u8003\u8651\u5982\u4f55\u4e0d\u679a\u4e3e\u5220\u54ea\u4e2a\u4f4d\u7f6e\uff0c\u54ea\u4e48\u5c31\u8ba8\u8bba\u4ece\u54ea\u8fb9\u5220\uff0c\u7136\u540e\u770b\u4e24\u8fb9\u7684 diff \u662f\u5426\u662f\u4e00\u5373\u53ef\u3002\u8bbe S(l, r) \u8868\u793a [l, r) \u8fd9\u4e2a\u533a\u95f4\u91cc 1 \u51fa\u73b0\u7684\u6b21\u6570\uff0c\u90a3\u4e48\u5c31\u662f\u6bd4\u8f83\u4e00\u4e0b S(ml, r) &#8211; S(l, ml) = 1 \u6216\u8005 S(l, mr) &#8211; S(mr, r) = 1\u3002 \u56e0\u6b64\u5bf9\u4e8e A1\uff0c\u6211\u4eec\u53ea\u8981\u5f00 25 \u68f5\u6811\u72b6\u6570\u7ec4\u5c31\u80fd\u901a\u8fc7\u3002\u5bf9\u4e8e\u5b57\u7b26\u96c6\u4efb\u610f\u7684\u60c5\u51b5\uff0c\u6211\u4eec\u628a\u6240\u6709\u6570\u5b57\u6620\u5c04\u6210\u4e00\u4e2a\u968f\u673a uint\uff0c\u7136\u540e\u770b diff \u662f\u5426\u6070\u597d\u662f\u67d0\u4e2a\u5b57\u7b26\u7684\u6620\u5c04\u5373\u53ef\u3002\u4ee3\u7801\u53cd\u800c\u6bd4 A1 \u66f4\u7b80\u5355\u3002 #include &lt;lastweapon\/bitwise&gt; #include &lt;lastweapon\/fenwicktree&gt; [&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-2938","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Lo","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2938","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=2938"}],"version-history":[{"count":9,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2938\/revisions"}],"predecessor-version":[{"id":2951,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2938\/revisions\/2951"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2938"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2938"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2938"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}