{"id":1002,"date":"2022-04-24T10:03:28","date_gmt":"2022-04-24T02:03:28","guid":{"rendered":"https:\/\/blog.cruciferslab.net\/?p=1002"},"modified":"2022-04-24T10:03:28","modified_gmt":"2022-04-24T02:03:28","slug":"gks-2022-round-b","status":"publish","type":"post","link":"https:\/\/blog.cruciferslab.net\/?p=1002","title":{"rendered":"GKS 2022 Round B"},"content":{"rendered":"\n<p>\u679c\u7136\u65e9\u4e03\u662f\u500b\u56e7\u6642\u9593\u3002\u661f\u671f\u5929\u4e0d\u662f\u500b\u9069\u5408\u65e9\u8d77\u7684\u65e5\u5b50\uff0c\u7761\u5230\u4e03\u9ede\u534a\u8df3\u8d77\u4f86\u53c3\u8cfd\u6240\u4ee5\u524d\u9762\u5403\u4e86\u597d\u4e9b\u5931\u8aa4\u3002\u4e0d\u904e\u6700\u5f8c\u9084\u662f\u5728\u7d50\u675f\u524d\u4e94\u5341\u5206\u9418\u7834\u53f0\u4e86\u3002<\/p>\n\n\n\n<p>\u7167\u4f8b\u5206\u6578\u622a\u5716\u4ee5\u4e0b\u6709\u96f7\uff1b\u6700\u7d42\u6392\u540d\u662f 69 \u540d (Nice!)\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"127\" src=\"https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-1024x127.png\" alt=\"\" class=\"wp-image-1004\" srcset=\"https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-1024x127.png 1024w, https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-300x37.png 300w, https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-150x19.png 150w, https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-768x95.png 768w, https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-1536x190.png 1536w, https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image.png 1843w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<!--more-->\n\n\n\n<h2 class=\"wp-block-heading\">Q1. Infinity Area<\/h2>\n\n\n\n<p>\u5c31\u5f88\u7c21\u55ae\u7684\u6578\u5b78\u8a08\u7b97\u984c\u3002WA \u7684\u539f\u56e0\u662f <code>int64_t<\/code>\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Q2. Palindromic Factors<\/h2>\n\n\n\n<p>\u539f\u672c\u4ee5\u70ba\u6383\u56e0\u6578\u6703\u6162\u7684\uff0c\u4e0d\u904e\u770b\u8d77\u4f86\u597d\u50cf\u9084\u597d\uff0c\u7bc4\u570d\u5167\u6700\u5927\u7684\u9ad8\u5408\u6210\u6578 6983776800 \u53ea\u6709\u5169\u5343\u591a\u500b\u56e0\u6578\uff0c\u76f4\u63a5\u6383 \u221aN \u4ee5\u5167\u7684\u6578\u53bb\u505a\u90fd\u9084\u884c\u3002TLE \u5169\u6b21\u7684\u539f\u56e0\u662f <code>int64_t<\/code>\u3002<\/p>\n\n\n\n<p>\u2026\u2026\u662f\u7684\uff0c\u9019\u5169\u984c\u56e0\u70ba\u65e9\u4e0a\u525b\u8d77\u4f86\u8166\u888b\u6df7\u4e82\uff0c\u5fd8\u8a18\u8003\u616e overflow \u6240\u4ee5\u7e3d\u5171\u6b7b\u4e86\u4e09\u6b21\u3002(\u6240\u4ee5\u65e9\u4e03\u662f\u500b\u56e7\u6642\u9593\u3002)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Q4. Hamiltonian Tour<\/h2>\n\n\n\n<p>\u4ed4\u7d30\u4e00\u60f3\u9019\u984c\u8868\u9762\u4e0a\u662f Hamiltonian Cycle\uff0c\u5be6\u969b\u4e0a\u53ea\u662f DFS \u641c\u5c0b\u7684\u8d70\u8def\u800c\u5df2\u3002(\u61c9\u8a72\u90fd\u770b\u904e\u90a3\u7a2e DFS \u641c\u5c0b\u7684\u6559\u5b78\u88e1\uff0c\u5728\u6a39\u7684\u5916\u76ae\u756b\u4e00\u500b\u5f4e\u5f4e\u66f2\u66f2\u7684\u7bad\u982d\u8868\u793a\u641c\u5c0b\u7684\u9806\u5e8f\u90a3\u73a9\u610f\uff1f\u9019\u984c\u5c31\u662f\u8981\u8f38\u51fa\u90a3\u500b\u7bad\u982d\u3002)<\/p>\n\n\n\n<p>\u56e0\u6b64\u53ea\u8981\u56fa\u5b9a\u597d DFS \u7684\u641c\u5c0b\u9806\u5e8f (\u4f8b\u5982\u5148\u5de6\u8f49\u518d\u76f4\u8d70\u518d\u53f3\u8f49)\uff0c\u5c31\u80fd\u5920\u628a\u8def\u7dda\u8ddf\u8457 DFS \u7684\u904e\u7a0b\u8d70\u904e\u4e00\u6b21\u3002\u4f8b\u5982\u4e0b\u5716\uff0c\u9019\u4e00\u5340\u584a\u5f9e\u5de6\u908a\u4f86\uff0c\u4e0a\u4e0b\u53ef\u8d70\u4f46\u53f3\u908a\u4e0d\u884c\uff1a\u5247\u8def\u7dda\u662f\u9032\u4f86\u5f8c\u5f80\u5317\uff0c\u63a5\u4e0a\u9762\u90a3\u584a\u7684\u8def\u7dda\uff0c\u5b83\u6703\u56de\u5230\u53f3\u4e0a\u683c\uff1b\u53f3\u908a\u4e0d\u80fd\u8d70\u6240\u4ee5\u76f4\u63a5\u5f80\u5357\uff1b\u518d\u5f80\u5357\u9032\u4e0b\u9762\u90a3\u584a\uff0c\u63a5\u4e0b\u9762\u90a3\u584a\u7684\u8def\u7dda\uff0c\u56de\u5230\u5de6\u4e0b\u683c\uff1b\u6700\u5f8c\u5f80\u897f\u8d70\u96e2\u958b\u3002\u7576\u7136\u6709\u4e9b\u7d30\u7bc0\u4f8b\u5982 DFS \u904e\u7684\u4e0d\u80fd\u518d\u8d70\uff0c\u4ee5\u53ca\u958b\u982d\u90a3\u683c\u4e0d\u80fd\u96e2\u958b\u8981\u63a5\u6210\u5708\u7b49\uff0c\u4e0d\u904e\u5927\u81f4\u4e0a\u7684\u6982\u5ff5\u5c31\u662f\u9019\u6a23\u3002<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"366\" height=\"576\" src=\"https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-2.png\" alt=\"\" class=\"wp-image-1005\" srcset=\"https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-2.png 366w, https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-2-191x300.png 191w, https:\/\/blog.cruciferslab.net\/wp-content\/uploads\/2022\/04\/image-2-95x150.png 95w\" sizes=\"auto, (max-width: 366px) 100vw, 366px\" \/><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Q3. Unlock the Padlock<\/h2>\n\n\n\n<p>\u9996\u5148\uff0c\u7531\u65bc\u64cd\u4f5c\u662f\u53ef\u4ea4\u63db\u7684\uff0c\u628a\u984c\u76ee\u7684\u5957\u5a03\u689d\u4ef6\u5012\u904e\u4f86\u6bd4\u8f03\u597d\u505a\u4e8b\uff0c\u4e5f\u5c31\u662f\u5148\u628a\u5927\u7bc4\u570d\u8abf\u597d\u518d\u4f86\u8abf\u5c0f\u7bc4\u570d\u3002\u9019\u6a23\u5c31\u80fd\u770b\u5230\u9019\u984c\u7684\u5b50\u7d50\u69cb\uff1a\u5927\u7bc4\u570d\u53ea\u6709\u5169\u500b\u9078\u9805\uff0c\u8981\u561b\u628a\u6700\u5de6\u908a\u8abf\u6210 0\uff0c\u8981\u561b\u628a\u6700\u53f3\u908a\u8abf\u6210 0\u3002\u4e0d\u904e\u6709\u500b\u554f\u984c\uff1a\u9032\u5230\u540c\u4e00\u500b\u5b50\u554f\u984c\u6642\u9396\u7684\u6578\u5b57\u4e0d\u4e00\u5b9a\u4e00\u6a23\uff0c\u53ef\u80fd\u6703\u5dee\u4e00\u500b\u5e38\u6578\u6b21\u6578\u3002<\/p>\n\n\n\n<p>\u4f8b\u5982\u984c\u76ee\u7684 0~9 \u7684\u9396\uff0c1 1 2 2 3 3 \u7684\u6578\u5b57\u4f86\u8aaa\u597d\u4e86\u3002\u53d6\u5230\u4e2d\u9593\u7684 [1]~[4] \u7684\u4f4d\u7f6e\u6642\uff0c\u53ef\u80fd\u56e0\u70ba\u5148\u5de6\u518d\u53f3\uff0c\u5b83\u6210\u4e86 8 9 9 0\uff1b\u4e5f\u53ef\u80fd\u56e0\u70ba\u5148\u53f3\u518d\u5de6\uff0c\u5b83\u6210\u4e86 0 1 1 2\u3002\u5982\u679c\u628a\u9019\u5169\u7a2e\u72c0\u614b\u770b\u6210\u5169\u7a2e\u7684\u8a71\uff0c\u90a3\u5176\u5be6\u5e7e\u4e4e\u6c92\u6709\u91cd\u758a\u5230\u5b50\u554f\u984c (\u56e0\u70ba\u6bcf\u500b\u7bc4\u570d\u6709 D \u7a2e\u53ef\u80fd\u4f4d\u7f6e)\uff1b\u5c31\u7b97\u76f4\u63a5\u7b46\u8a18\u6cd5\u5beb\u4e0b\u53bb\u4e5f\u6703\u9700\u8981\u770b 2^N \u500b\u5b50\u554f\u984c\uff0c\u5c0d N&lt;=400 \u9019\u500b\u7bc4\u570d\u986f\u7136\u4e0d\u53ef\u884c\u3002<\/p>\n\n\n\n<p>\u9019\u88e1\u7684\u95dc\u9375\u5c31\u5728\u65bc\uff0c\u96d6\u7136\u9032\u4f86\u6642\u7684\u72c0\u6cc1\u4e0d\u540c\uff0c\u4f46\u6211\u53ef\u4ee5\u7d00\u9304\u9032\u4f86\u4e4b\u5f8c\u5982\u679c\u6211\u9078\u5de6\u908a\u8abf\u6210 0 \u5f8c\u9084\u8981\u5e7e\u6b65\uff0c\u4ee5\u53ca\u9078\u53f3\u908a\u8abf\u6210 0 \u5f8c\u9084\u8981\u5e7e\u6b65\u3002\u8981\u54ea\u4e00\u908a\u8abf\u6210 0 \u9019\u4ef6\u4e8b\u6bcf\u6b21\u9032\u4f86\u770b\u73fe\u5728\u72c0\u6cc1\u5982\u4f55\u518d\u7b97\u5c31\u597d\uff0c\u4f46\u4e4b\u5f8c\u9084\u8981\u5e7e\u6b65\u9019\u56de\u4e8b\u9700\u8981\u6c42\u5b50\u554f\u984c\uff0c\u6240\u4ee5\u5c31\u5148\u7b97\u597d\u8a18\u8d77\u4f86\u3002\u9019\u6a23\u4e00\u4f86\u6bcf\u500b\u7bc4\u570d\u5c31\u7b97\u5dee\u4e86\u5e38\u6578\u6b21\u6578\u4e5f\u53ef\u4ee5\u5171\u7528\u540c\u4e00\u500b\u5b50\u554f\u984c\u8a08\u7b97\u7d50\u679c\u3002\u4e0d\u904e\u56e0\u70ba\u8166\u888b\u5927\u6982\u53ea\u6e05\u9192\u4e00\u534a\uff0c\u611f\u89ba\u7b46\u8a18\u6cd5\u6bd4\u8f03\u597d\u5beb\u6240\u4ee5\u5c31\u9084\u662f\u5beb\u4e86\u7b46\u8a18\u6cd5\uff0c\u4e0d\u7136\u7406\u8ad6\u4e0a\u61c9\u8a72\u662f\u53ef\u4ee5\u5beb\u6210 DP \u7684\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u5c0f\u7d50<\/h2>\n\n\n\n<p>\u2026\u2026\u679c\u7136\u65e9\u4e03\u9084\u662f\u500b\u56e7\u6642\u9593\u3002(\u56e0\u70ba\u5f88\u91cd\u8981\u6240\u4ee5\u8981\u8aaa\u4e09\u6b21)<\/p>\n\n\n\n<p>\u9019\u5834\u610f\u5916\u7684\u7834\u53f0\u7684\u4eba\u6578\u4e0d\u591a (\u53ea\u6709\u7d04\u4e00\u767e\u4eba)\uff0c\u770b\u8d77\u4f86\u662f Q4 \u5927\u6e2c\u8cc7\u5728\u5b88\u9580\uff1bQ4 \u5c0f\u6e2c\u8cc7\u56e0\u70ba\u662f\u898f\u5247\u5716\u5f62\uff0c\u53ef\u4ee5\u8b49\u660e\u4e00\u5b9a\u6709\u89e3\uff0c\u89e3\u4e5f\u5f88\u597d\u5beb\uff1b\u4f46\u5927\u6e2c\u8cc7\u6c92\u6709\u898f\u5247\uff0c\u6240\u4ee5\u8981\u771f\u7684\u627e\u51fa\u5b83\u8ddf DFS \u641c\u5c0b\u9806\u5e8f\u7684\u95dc\u9023\u518d\u4f86\u5beb\u624d\u6703\u904e\u3002<\/p>\n\n\n\n<p>\u63a5\u4e0b\u4f86\u662f 5\/14 \u7684 GCJ R2\uff0c\u4ee5\u53ca 5\/22 \u7684 GKS Round C\u3002\u4e0b\u6b21\u898b\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u679c\u7136\u65e9\u4e03\u662f\u500b\u56e7\u6642\u9593\u3002\u661f\u671f\u5929\u4e0d\u662f\u500b\u9069\u5408\u65e9\u8d77\u7684\u65e5\u5b50\uff0c\u7761\u5230\u4e03\u9ede\u534a\u8df3\u8d77\u4f86\u53c3\u8cfd\u6240\u4ee5\u524d\u9762\u5403\u4e86\u597d\u4e9b\u5931\u8aa4\u3002\u4e0d\u904e\u6700\u5f8c\u9084\u662f\u5728\u7d50\u675f\u524d [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,4],"tags":[],"class_list":["post-1002","post","type-post","status-publish","format-standard","hentry","category-gcj","category-programming"],"_links":{"self":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/1002","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1002"}],"version-history":[{"count":1,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/1002\/revisions"}],"predecessor-version":[{"id":1006,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/1002\/revisions\/1006"}],"wp:attachment":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1002"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1002"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1002"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}