{"id":1051,"date":"2024-02-03T23:18:49","date_gmt":"2024-02-03T15:18:49","guid":{"rendered":"http:\/\/ggapa.net:81\/?p=1051"},"modified":"2024-02-21T11:51:40","modified_gmt":"2024-02-21T03:51:40","slug":"%e5%81%9a%e9%a2%98%e7%ac%94%e8%ae%b0cesc","status":"publish","type":"post","link":"http:\/\/ggapa.net:81\/2024\/02\/03\/%e5%81%9a%e9%a2%98%e7%ac%94%e8%ae%b0cesc\/","title":{"rendered":"\u505a\u9898\u7b14\u8bb0(CSES)"},"content":{"rendered":"<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-1075\">CSES - 1075 Permutations II<\/a><\/h3>\n<p>\u52a8\u6001\u89c4\u5212\u597d\u9898\u3002<\/p>\n<h4>\u89e3\u6cd5\u4e00\uff08recommend)<\/h4>\n<p>\u5b9a\u4e49 $F(i, j, k)$ $1$ \u8868\u793a\u5728 1 \u5230 $i$ \u7684\u6392\u5217\u4e2d\uff0c\u6ee1\u8db3\u6709 $j$ \u5bf9\u76f8\u90bb\u7684 $&lt;i$ \u7684\u5dee\u4e3a $1$\uff0c$k = 1$ \u6216 $0$ \u5206\u522b\u5bf9\u5e94 $i$ \u548c $i - 1$ \u662f\u5426\u76f8\u90bb\u7684\u6392\u5217\u4e2a\u6570\uff0c\u6613\u5f97 $F(1, 0, 0) = 1$\uff0c$F(2, 0, 1) = 2$\u3002\u8bbe\u5f53\u524d\u5df2\u7ecf\u5904\u7406\u5b8c\u4e86\u524d $i$ \u4e2a\u6392\u5217\u7684\u60c5\u51b5\uff0c\u6211\u4eec\u8003\u8651 $i + 1$ \u653e\u7f6e\u7684\u4f4d\u7f6e\u3002<\/p>\n<ul>\n<li>\u5982\u679c $i$ \u548c $i - 1$ \u4e0d\u76f8\u90bb\uff0c\u5c06 $i + 1$ \u653e\u5230 $i$ \u65c1\u8fb9\u6709\u4e24\u79cd\u9009\u62e9\uff0c$F(i + 1, j, 1) += 2F(i, j, 0)$\u3002<\/li>\n<li>\u5982\u679c $i$ \u548c $i - 1$ \u76f8\u90bb\uff0c\u5c06 $i$ \u63d2\u5165\u5230 $i$ \u7684\u4e24\u4fa7\u6709\u4e24\u79cd\u60c5\u51b5\uff1a\n<ol>\n<li>\u6dfb\u52a0\u5230 $i$ \u548c $i - 1 $ \u5916\u4fa7\uff0c\u6b64\u65f6\u4ea7\u751f\u4e86\u4e00\u4e2a\u65b0\u7684\u76f8\u5dee\u4e3a $1$ \u7684\u76f8\u90bb\u5143\u7d20\uff0c$F(i + 1, j + 1, 1) += F(i, j, 1)$\u3002<\/li>\n<li>\u6dfb\u52a0\u5230 $i$ \u548c $i - 1$ \u4e2d\u95f4\uff0c\u6b64\u65f6\u76f8\u5dee\u4e3a 1 \u7684\u76f8\u90bb\u5143\u7d20\u6570\u91cf\u5e76\u6ca1\u6709\u6539\u53d8\uff0c$F(i + 1, j, 1) += F(i\uff0cj, 1)$<\/li>\n<\/ol>\n<\/li>\n<li>\u5982\u679c\u5c06 $i$ \u52a0\u5165\u5230\u539f\u672c\u76f8\u5dee $1$ \u7684\u4e24\u4e2a\u5143\u7d20($&lt;i$)\u4e2d\uff0c \u76f8\u5dee\u7684\u5143\u7d20\u4f1a\u51cf\u5c11\u4e00\u5bf9\uff0c\u6b64\u65f6\u4f9d\u7136\u5206\u4e24\u79cd\u60c5\u51b5\uff1a\n<ol>\n<li>$i$ \u548c $i - 1$ \u662f\u76f8\u90bb\u7684\uff0c$F(i + 1, j, 0) += j \\times F(i, j, 1)$ \u3002<\/li>\n<li>$i$ \u548c $i - 1$ \u4e0d\u76f8\u90bb\uff0c\u6b64\u65f6\u4f1a\u4f7f $j$ \u51cf\u5c11 $1$ \uff0c$F(i + 1, j - 1, 0) += j \\times F(i, j, 0)$\u3002<\/li>\n<\/ol>\n<\/li>\n<li>\u5982\u679c\u5c06 $i + 1$ \u653e\u5230\u5e8f\u5217\u7684\u5176\u4ed6\u4f4d\u7f6e\uff08\u4e0d\u80fd\u653e\u5728 $i$ \u548c $i - 1$ \u4e4b\u95f4\uff0c\u4e0a\u6587\u5df2\u7ecf\u8ba8\u8bba\u8fc7\u4e86\u8fd9\u79cd\u60c5\u51b5\uff09\uff0c\u6b64\u65f6\u6709 $i - j - 1$ \u4e2a\u4f4d\u7f6e\u53ef\u4ee5\u7528\uff0c\u8fd8\u662f\u5206\u4e24\u79cd\u60c5\u51b5\uff1a\n<ol>\n<li>\u82e5 $i$ \u548c $i - 1$ \u4e0d\u76f8\u90bb\uff0c$F(i + 1, j, 0) += (i- j- 1) \\times F(i, j, 0)$ \u3002<\/li>\n<li>\u82e5 $i$ \u548c $i - 1$ \u662f\u76f8\u90bb\u7684\uff0c$F(i + 1, j + 1, 0) += (i - j - 1) \\times F(i, j, 1)$\u3002<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n<p>\u81f3\u6b64\uff0c\u6211\u4eec\u5df2\u7ecf\u5206\u6790\u5b8c\u4e86\u6240\u6709\u7684\u60c5\u51b5\uff0c\u6700\u7ec8\u7684\u6240\u6c42\u7b54\u6848\u4e3a $F(n, 0, 0)$ \uff0c\u65f6\u95f4\u590d\u6742\u5ea6 $O(n^2)$\u3002<\/p>\n<h4>\u89e3\u6cd5\u4e8c \u2753<\/h4>\n<p>\u8fd9\u73a9\u610f\u662f\u6709\u89c4\u5f8b\u7684\uff0c\u8be6\u89c1 <a href=\"https:\/\/oeis.org\/A002464\">OEIS - A002464<\/a> \uff0c\u600e\u4e48\u63a8\u51fa\u6765\u7684\u7b49\u6211\u53bb\u95ee\u95ee\u5927\u4f6c\u3002<\/p>\n<p><a href=\"https:\/\/vjudge.net\/solution\/49146336\">AC code by CYR<\/a><\/p>\n<h4>\u603b\u7ed3<\/h4>\n<p>\u4e00\u5f00\u59cb\u505a\u8fd9\u9053\u9898\u7684\u65f6\u5019\u5e76\u6ca1\u6709\u60f3\u51fa\u6765\u8fd9\u9053\u9898\u662f\u52a8\u6001\u89c4\u5212\uff0c\u6211\u8fd8\u4ee5\u4e3a\u662f\u6570\u5b66\u9898\uff0c\u751a\u81f3\u90fd\u5df2\u7ecf\u53d1\u73b0\u4e86\u524d\u540e\u4e24\u79cd\u72b6\u6001\u4e4b\u95f4\u7684\u5173\u7cfb\uff0c\u82e5\u6709\u5f88<strong>\u660e\u663e\u7684\u5173\u7cfb<\/strong>\uff0c\u9996\u5148\u8981\u8003\u8651\u7684\u5c31\u662f<strong>\u52a8\u6001\u89c4\u5212\u6216\u7ec4\u5408\u9012\u63a8<\/strong>\u3002<\/p>\n<p>\u5173\u4e8e\u72b6\u6001\u7684\u8bbe\u8ba1\uff0c\u9700\u8981\u627e\u5230\u591a\u4e2a\u4f1a\u5f71\u54cd\u7684\u7ef4\u5ea6\uff0c\u5927\u6982\u5c31\u662f\u4ee5\u4e0b\u51e0\u70b9\uff1a<\/p>\n<ol>\n<li>\u524d $i$ \u4e2a\u5143\u7d20\u6240\u6c42\u5f97\u7684\u7b54\u6848\u3002<\/li>\n<li>\u4f1a\u5bf9\u540e\u7eed\u5185\u5bb9\u4ea7\u751f\u5f71\u54cd\u7684 $j$ \u3002<\/li>\n<li>\u4ee5\u53ca\u662f\u5426\u5b58\u5728\u67d0\u4e9b\u7279\u6b8a\u60c5\u51b5\u4f1a\u5bfc\u81f4\u89c4\u5f8b\u4e0d\u9002\u7528\u7684\u5e03\u5c14\u503c $k$ \u3002<\/li>\n<\/ol>\n<h3>CSES-1077 Sliding Window Cost<\/h3>\n<h4>\u9898\u76ee\u5927\u610f<\/h4>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u5305\u542b $n$ \u4e2a\u6574\u6570\u7684\u6570\u7ec4\u3002\u4f60\u7684\u4efb\u52a1\u662f\u8ba1\u7b97\u6bcf\u4e2a\u7531 $k$ \u4e2a\u5143\u7d20\u7ec4\u6210\u7684\u7a97\u53e3\uff0c\u4ece\u5de6\u5230\u53f3\uff0c\u4f7f\u6240\u6709\u5143\u7d20\u76f8\u7b49\u7684\u6700\u5c0f\u603b\u6210\u672c\u3002<\/p>\n<p>\u4f60\u53ef\u4ee5\u7528\u6210\u672c\u4e3a $x$ \u589e\u52a0\u6216\u51cf\u5c11\u6bcf\u4e2a\u5143\u7d20\uff0c\u5176\u4e2d $x$ \u662f\u65b0\u503c\u548c\u539f\u59cb\u503c\u4e4b\u95f4\u7684\u5dee\u503c\u3002\u603b\u6210\u672c\u662f\u8fd9\u4e9b\u6210\u672c\u7684\u603b\u548c\u3002<\/p>\n<h4>\u89e3\u9898\u601d\u8def<\/h4>\n<p>\u662f\u6ed1\u52a8\u7a97\u53e3\uff0c\u6211\u4eec\u5b9a\u4e49\u4e24\u4e2a\u96c6\u5408 $lq$ \u548c $rq$ \u5206\u522b\u4ee3\u8868\u5c0f\u4e8e\u7b49\u4e8e\u548c\u5927\u4e8e\u4e2d\u4f4d\u6570\u7684\u5143\u7d20\uff0c\u5176\u4e2d $lq$ \u7684\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u5c31\u662f\u533a\u95f4\u5185\u7684\u4e2d\u4f4d\u6570\u3002\u5b9a\u4e49 $m$ \u8868\u793a\u533a\u95f4\u5185\u7b2c $m$ \u4e2a\u6570\u4e3a\u4e2d\u4f4d\u6570\u3002<\/p>\n<p>\u5728\u8fdb\u884c\u7a97\u53e3\u6ed1\u52a8\u65f6\uff0c\u8003\u8651\u5982\u4f55\u66f4\u65b0 $lq$ \u548c $rq$\uff1a<\/p>\n<ul>\n<li>\u82e5 $|lq| &lt; m$ \uff0c\u5e94\u5f53\u5148\u5728 $rq$ \u4e2d\u63d2\u5165\u5f53\u524d\u5143\u7d20\uff0c\u63a5\u7740\u5c06 $rq$ \u4e2d\u6700\u5c0f\u7684\u5143\u7d20\u8f6c\u79fb\u5230 $lq$ \u4e2d\u3002<\/li>\n<li>\u5426\u5219\uff0c\u5e94\u5f53\u5728 $lq$ \u4e2d\u63d2\u5165\u5f53\u524d\u5143\u7d20\uff0c\u63a5\u7740\u5ac1\u7ed9\u4f60 $lq$ \u4e2d\u7684\u6700\u5927\u5143\u7d20\u8f6c\u79fb\u5230 $rq$ \u4e2d\u3002<\/li>\n<\/ul>\n<p>\u4e3a\u4e86\u8ba1\u7b97\u5f53\u5f53\u524d\u533a\u95f4\u7684\u6700\u5c0f\u6210\u672c\uff0c\u6211\u4eec\u5b9a\u4e49\uff1a<\/p>\n<ul>\n<li>$ls$ \u4ee3\u8868 $lq$ \u4e2d\u5143\u7d20\u7684\u603b\u548c\u3002<\/li>\n<li>$rs$ \u4ee3\u8868 $rq$ \u4e2d\u5143\u7d20\u7684\u603b\u548c\u3002<\/li>\n<li>$med$ \u4ee3\u8868\u4e2d\u4f4d\u6570\uff0c\u4e5f\u5c31\u662f $ls$ \u4e2d\u6700\u5927\u7684\u5143\u7d20\u3002<\/li>\n<\/ul>\n<p>\u90a3\u4e48\u53ef\u4ee5\u5f97\u5230\u533a\u95f4\u6700\u5c0f\u603b\u6210\u672c\u4e3a\uff1a$(med\\cdot lc - ls) + (rs - med\\cdot rc)$ \u3002<\/p>\n<p><a href=\"https:\/\/vjudge.net\/solution\/49062009\/yGEPyhEqMlS9FX0yr1ND\">AC code<\/a><\/p>\n<h4>\u603b\u7ed3<\/h4>\n<p>\u5bf9\u4e8e\u533a\u95f4\u6ed1\u52a8\u7a97\u53e3\u4e2d\u4f4d\u6570\u95ee\u9898\uff0c\u53ef\u4ee5\u8003\u8651\u5efa\u7acb\u4e24\u4e2a\u96c6\u5408\uff0c\u6765\u8fdb\u884c\u6c42\u89e3\u3002\u5bf9\u4e8e\u6ed1\u52a8\u7a97\u53e3\u95ee\u9898\uff0c<code>set<\/code> \u662f\u4e00\u4e2a\u5f88\u597d\u7684\u9009\u62e9\u3002<\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-1093\">CSES - 1093 Two Sets II<\/a><\/h3>\n<p>\u9996\u5148\u8003\u8651\u65e0\u89e3\u7684\u60c5\u51b5\uff0c\u8bb0 $N = \\sum_{1}^{n}$\uff0c\u6613\u5f97\u82e5 $2|n$ \u5219\u4e00\u5b9a\u6709\u89e3\u3002<\/p>\n<p>\u8fd9 $n$ \u4e2a\u6570\u7684\u548c\u4e3a $\\frac{n(n +1)}{2}$ \uff0c\u90a3\u4e48\u6bcf\u4e00\u90e8\u5206\u7684\u7684\u548c\u4e3a $\\frac{n(n +1)}{4}$\uff0c\u9898\u76ee\u4e2d $n$ \u7684\u8303\u56f4\u8f83\u5c0f\uff0c \u8fd9\u6697\u793a\u4e86\u7528 01 \u80cc\u5305\u6765\u89e3\u51b3\u95ee\u9898\u3002<\/p>\n<p>\u6211\u4eec\u4ee4 $\\texttt{dp}{[i][j]}$ \u4ee3\u8868\u5728\u524d $1-i$ \u4e2a\u6570\u4e2d\uff0c\u7ec4\u6210\u548c\u4e3a $j$ \u7684\u6570\u91cf\uff0c\u53ef\u4ee5\u5f97\u5230\u8f6c\u79fb\u65b9\u7a0b\u4e3a $\\texttt{dp}{[i][j]} = \\texttt{dp}{[i-1][j]} + \\texttt{dp}[i-1][j - i]$\uff0c\u589e\u6dfb\u6216\u8005\u4e0d\u589e\u6dfb\u7684\u60c5\u51b5\u3002<\/p>\n<p><a href=\"https:\/\/vjudge.net\/solution\/48920960\/rxrommxRnKl5flEe4y9b\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-1194\/origin\">CSES - 1194 Monsters<\/a><\/h3>\n<p>\u8fd9\u9053\u9898\u5f88\u660e\u663e\u7528 BFS\uff0c\u95ee\u9898\u5728\u4e8e\u8ff7\u5bab\u4e2d\u51fa\u73b0\u4e86\u602a\u7269\uff0c\u6211\u4eec\u7684\u52c7\u58eb\u4e0d\u80fd\u548c\u602a\u7269\u63a5\u89e6\uff0c\u8f6c\u6362\u4e00\u4e0b\u5c31\u662f\uff0c\u52c7\u58eb\u4e0d\u80fd\u5230\u8fbe\u602a\u7269\u53ef\u80fd\u6240\u5728\u7684\u533a\u57df\u3002<\/p>\n<p>\u5728\u8f6c\u6362\u4e00\u4e0b\uff0c\u602a\u7269\u6c38\u8fdc\u6bd4\u52c7\u58eb\u5148\u8d70\u4e00\u6b65\uff0c\u52c7\u58eb\u4e0d\u80fd\u8d70\u5230\u602a\u7269\u6240\u8d70\u8fc7\u7684\u9762\u79ef\uff0c\u8003\u8651\u628a\u602a\u7269\u548c\u52c7\u58eb\u5728\u4e00\u8d77\u8fdb\u884c BFS\uff0c\u5c06\u602a\u7269\u5148\u5165\u961f\uff0c\u8fd9\u4fdd\u8bc1\u4e86\u602a\u7269\u603b\u662f\u6bd4\u52c7\u58eb\u5148\u8d70\u3002<\/p>\n<p>\u6ce8\u610f\uff1a\u4e0d\u8981\u5fd8\u8bb0\u7279\u5224\u8fb9\u754c\u6761\u4ef6\uff01<\/p>\n<p>\u603b\u7ed3\uff1a\u8c03\u8bd5\u4f18\u5148\u68c0\u67e5\u8fb9\u754c\u6761\u4ef6\uff0c\u505a\u9898\u65f6\u53ef\u4ee5\u8003\u8651\u4e0d\u540c\u7684\u5165\u961f\u987a\u5e8f\u8fbe\u5230\u6240\u9700\u8981\u7684\u7ed3\u679c<\/p>\n<p><a href=\"https:\/\/vjudge.net\/solution\/49008108\/271sCw0fKPFv5Da33vZq\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-1203\">CSES - 1203 Visiting Cities<\/a><\/h3>\n<p>\u53cc\u5411\u6700\u77ed\u8def\u548c\u5927\u6570\u5224\u65ad\u76f8\u7b49\u64cd\u4f5c\uff0c<\/p>\n<p>\u82e5\u4e00\u4e2a\u70b9 $i$ \u4e00\u5b9a\u5904\u4e8e $1$ \u5230 $n$ \u7684\u6700\u77ed\u8def\u4e0a\uff0c\u90a3\u4e48\uff1a<\/p>\n<ul>\n<li>$dis(1, i) + dis(i, n) = dis(1,n)$\u3002<\/li>\n<li>$way(1,i)\\times way(i, n) = way(i ,n)$ \u3002<\/li>\n<\/ul>\n<p>\u5176\u4e2d\u6211\u4eec\u5b9a\u4e49 $dis(u, v)$ \u4ee3\u8868\u8282\u70b9 $u$ \u81f4\u8282\u70b9 $v$ \u7684\u6700\u77ed\u8ddd\u79bb\uff0c $way(u, v)$ \u4ee3\u8868\u8282\u70b9 $u$ \u5230 $v$ \u7684\u6700\u77ed\u8def\u6570\u91cf\u3002<\/p>\n<p>\u8003\u8651\u4ee4\u8d77\u70b9\u5206\u522b\u4e3a $1$ \u548c $n$ \uff0c\u8dd1\u4e24\u6b21 <code>Dijkstra<\/code>\uff0c\u63a5\u7740\u5c31\u80fd\u89e3\u51b3\u4ee5\u4e0a\u7684\u5224\u65ad\u3002\u4f46\u662f\u4f1a\u6709\u4e00\u4e2a\u95ee\u9898\uff0c\u6700\u77ed\u8def\u7684\u6570\u91cf\u53ef\u80fd\u4f1a\u8d85\u8fc7 <code>long long <\/code> \u6240\u627f\u53d7\u7684\uff0c\u53c8\u56e0\u4e3a\u6b64\u4e0d\u8981\u6c42\u8f93\u51fa\u6700\u7ec8\u7684\u6570\u503c\uff0c\u53ea\u9700\u8981\u5224\u65ad\u662f\u5426\u76f8\u7b49\uff0c\u6211\u4eec\u53ef\u4ee5\u6311\u9009\u4e24\u4e2a\u5927\u8d28\u6570\uff0c\u5206\u522b\u5bf9\u4e24\u4e2a\u6570\u7ec4\u8fdb\u884c\u64cd\u4f5c\uff0c\u82e5\u6700\u540e\u7ed3\u679c\u76f8\u540c\u7684\u6982\u7387\u662f\u975e\u5e38\u5c0f\u7684\u3002<\/p>\n<p>\u8fd9\u79cd\u65b9\u6cd5\u662f\u7528\u4e8e\u5224\u65ad\u5927\u6570\u662f\u5426\u76f8\u540c\u7684\u5e38\u7528\u5957\u8def\uff0c\u6211\u4eec\u5e94\u5f53\u79ef\u7d2f\u5e38\u7528\u8d28\u6570\uff1a<\/p>\n<ul>\n<li>998244353\u30011e9 + 7\u30011e8 + 7\u30011e9 + 9<\/li>\n<\/ul>\n<p>\u7531\u4e8e\u8fd9\u9053\u9898\u5361 9982444353 \u4e0d\u80fd\u7528\u3002<br \/>\n<a href=\"https:\/\/vjudge.net\/solution\/49114207\/R3p5cDqmTNJRrdImTm8t\">AC code<\/a><\/p>\n<p>####123123123<\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-1625#author=GPT_zh\">CSES - 1625 Grid Paths<\/a><\/h3>\n<p>\u4e00\u9053\u975e\u5e38\u597d\u7684\u641c\u7d22\u9898<\/p>\n<h4>\u6734\u7d20\u7b97\u6cd5<\/h4>\n<p>\u6211\u4eec\u7b80\u5355\u7684\u4f7f\u7528\u56de\u6eaf\u6cd5\u8fdb\u884c\u7206\u641c\uff0c\u5e76\u8ba1\u7b97\u8fd9\u6837\u7684\u8def\u5f84\u6570\u91cf\u3002<\/p>\n<p>\u8fd0\u884c\u65f6\u95f4\uff1a483s<\/p>\n<p>\u9012\u5f52\u8c03\u7528\u6b21\u6570\uff1a760\u4ebf<\/p>\n<h4>\u4f18\u53161<\/h4>\n<p>\u5982\u679c\u5728\u8bbf\u95ee\u4e86\u6240\u6709\u7684\u65b9\u683c\u524d\u5c31\u5230\u8fbe\u4e86\u7ec8\u70b9\uff0c\u53c8\u6216\u8005\u662f\u6b65\u6570\u5df2\u7ecf\u8fbe\u5230\u4e86\u6307\u5b9a\u6b65\u6570\u5374\u8fd8\u6ca1\u6709\u5230\u3002\u6ee1\u8db3\u4efb\u610f\u4e00\u4e2a\u5c31\u53ef\u4ee5\u9000\u51fa\u641c\u7d22\u3002<\/p>\n<p>\u8fd0\u884c\u65f6\u95f4\uff1a119s<\/p>\n<p>\u9012\u5f52\u8c03\u7528\u6b21\u6570\uff1a200\u4ebf<\/p>\n<h4>\u4f18\u53162<\/h4>\n<p>\u5982\u679c\u78b0\u5230\u4e86\u65b9\u683c\u8fb9\u7f18\uff0c\u5219\u4f1a\u628a\u6574\u4e2a\u5730\u56fe\u5206\u6210\u4e24\u4e2a\u90e8\u5206\uff0c\u82e5\u5176\u4e2d\u5305\u542b\u8fd8\u672a\u8bbf\u95ee\u8fc7\u7684\u65b9\u683c\uff0c\u5219\u4e00\u5b9a\u65e0\u89e3\uff0c\u9000\u51fa\u9012\u5f52\u5373\u53ef\u3002<\/p>\n<p>\u8fd0\u884c\u65f6\u95f4\uff1a1.8s<\/p>\n<p>\u9012\u5f52\u8c03\u7528\u6b21\u6570\uff1a2.21\u4ebf<\/p>\n<h4>\u4f18\u53163<\/h4>\n<p>\u8003\u8651\u5bf9\u4f18\u5316 2 \u8fdb\u884c\u62d3\u5c55\uff0c\u82e5\u5728\u641c\u7d22\u65f6\u65e0\u6cd5\u7ee7\u7eed\u524d\u8fdb\uff0c\u9700\u8981\u5411\u5de6\u6216\u8005\u5411\u53f3\u8f6c\uff0c\u7f51\u683c\u5c31\u4f1a\u5206\u6210\u4e24\u4e2a\u90e8\u5206\uff0c\u82e5\u4e24\u8005\u4e2d\u5305\u542b\u672a\u88ab\u8bbf\u95ee\u8fc7\u7684\u65b9\u683c\u3002\u5f88\u660e\u663e\uff0c\u6b64\u65f6\u4e00\u5b9a\u65e0\u89e3\u3002<\/p>\n<p>\u8fd0\u884c\u65f6\u95f4\uff1a0.6s<\/p>\n<p>\u9012\u5f52\u8c03\u7528\u6b21\u6570\uff1a6900\u4e07<\/p>\n<hr \/>\n<p>\u7ecf\u8fc7\u4e86\u4f18\u5316\u4e09\u7684\u4f18\u5316\u4e4b\u540e\uff0c\u6211\u4eec\u5df2\u7ecf\u53ef\u4ee5\u901a\u8fc7\u672c\u9898\uff0c\u4e3a\u4e86\u8fbe\u5230\u4f18\u5316\u4e09\uff0c\u6211\u4eec\u9700\u8981\u63d0\u524d\u5c06\u65b9\u683c\u7684\u8fb9\u7f18\u5305\u56f4\u8d77\u6765\uff0c\u4fd7\u8bdd\u8bf4\u5c31\u662f\u5c06\u8fb9\u7f18\u7684 <code>vis<\/code> \u6570\u7ec4\u6807\u8bb0\u4e3a <code>true<\/code> \u3002<\/p>\n<blockquote><p>In backtracking, the search tree is usually large and even simple observations can effectively prune the search. Especially useful are optimizations that occur during the first steps of the algorithm, i.e., at the top of the search tree.<\/p>\n<p>\u5728\u8fdb\u884c\u56de\u6eaf\u7b97\u6cd5\u65f6\uff0c\u641c\u7d22\u6811\u901a\u5e38\u4f1a\u975e\u5e38\u5e9e\u5927\uff0c\u5373\u4f7f\u662f\u8fdb\u884c\u7b80\u5355\u7684\u89c2\u5bdf\u4e5f\u80fd\u6709\u6548\u7684\u526a\u679d\u3002\u5c24\u5176\u662f\u5728\u56de\u6eaf\u7b97\u6cd5\u7684\u524d\u51e0\u6b65\u975e\u5e38\u6709\u6548\u679c\uff0c\u4e5f\u5c31\u662f\u641c\u7d22\u6811\u7684\u9876\u7aef\u3002<\/p>\n<p>\u2014\u2014<a href=\"https:\/\/usaco.guide\/problems\/cses-1625-grid-paths\/solution\">USACO Guide<\/a><\/p><\/blockquote>\n<p><a href=\"https:\/\/vjudge.net\/solution\/49021389\/iDroLWx5FiFH4LSgSuHY\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-1757#author=GPT_zh\">CSES - 1757 Course Schedule II <\/a><\/h3>\n<p>\u4e92\u76f8\u6709\u5148\u540e\u5173\u7cfb\uff0c\u8fde\u8fb9\u8dd1\u62d3\u6251\u6392\u5e8f\u7684\u7ecf\u5178\u95ee\u9898\uff0c\u672c\u8d28\u4e0a\u5c5e\u4e8e\u8d2a\u5fc3\u3002<\/p>\n<p>\u6ce8\u610f\uff1a<\/p>\n<ul>\n<li>\u9700\u8981\u6ce8\u610f\u8fb9\u4e0e\u8fb9\u4e4b\u95f4\u7684\u65b9\u5411\uff0c\u6ce8\u610f\u8f93\u51fa\u7684\u65b9\u5f0f\uff0c\u53ef\u4ee5\u8003\u8651\u901a\u8fc7\u4f18\u5148\u961f\u5217\u6765\u7ef4\u62a4<\/li>\n<\/ul>\n<p><a href=\"https:\/\/vjudge.net\/solution\/49117315\/AuUcWmbwfUkyhrIrAsGU\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-2179\">CSES - 2179 Even Outdegree Edges<\/a><\/h3>\n<p>\u56fe\u8bba<\/p>\n<p>\u8003\u8651\u5728\u8fdb\u884c DFS \u751f\u6210\u6811\u65f6\u76f4\u63a5\u8d2a\u5fc3\u6784\u9020\u3002<\/p>\n<p>\u9519\uff1a<\/p>\n<ul>\n<li>\u5728\u8fdb\u884c\u5ea6\u6570\u4fee\u6539\u65f6\u628a\u590d\u6742\u64cd\u4f5c\u76f4\u63a5\u8fc7\u4e8e\u7b80\u5355\u5316\uff0c\u76f4\u63a5\u5c06\u5ea6\u6570\u7684\u6807\u8bb0\u76f4\u63a5\u89c4 0\uff0c\u5e76\u6ca1\u6709\u8003\u8651\u591a\u4e2a\u513f\u5b50\u5bf9\u7b54\u6848\u9020\u6210\u7684\u5f71\u54cd\u3002<\/li>\n<\/ul>\n<p>\u603b\u7ed3\uff1a<\/p>\n<ul>\n<li>\u56fe\u8bba\u9898\u53ef\u4ee5\u5148\u53bb\u4e00\u822c\u5316\uff0c\u5148\u8f6c\u6362\u6210\u6811\u4e0a\u95ee\u9898\uff0c\u83ca\u82b1\u56fe\uff0c\u94fe\u6761\u6765\u5206\u6790\u9898\u76ee\u3002<\/li>\n<li>\u8fb9\u5904\u7406\u8fb9\u64cd\u4f5c\uff0c\u8d2a\u5fc3\u5c40\u90e8\u89e3\u8f6c\u5316\u4e3a\u5168\u90e8\u89e3\uff0c\u5bf9\u4e8e\u8fd8\u9700\u8981\u5224\u65ad\u6709\u6ca1\u6709\u89e3\u51b3\u65b9\u6848\u7684\u95ee\u9898\uff0c\u5f80\u5f80\u53ef\u4ee5\u4ece\u5c40\u90e8\u5230\u5168\u5c40\uff0c\u82e5\u5c40\u90e8\u5408\u6cd5\u4f46\u662f\u5168\u5c40\u4e0d\u5408\u6cd5\uff0c\u90a3\u4e48\u5c31\u662f\u65e0\u89e3\u7684\u3002\u6240\u4ee5\u8bf4\u5728\u8003\u8651\u8d2a\u5fc3\u7684\u65f6\u5019\u5f80\u5f80\u4e0d\u9700\u8981\u592a\u5728\u610f\u65e0\u89e3\u7684\u60c5\u51b5\uff0c\u81ea\u7136\u800c\u7136\u7684\u5c31\u80fd\u5192\u51fa\u6765\u65e0\u89e3\u7684\u60c5\u51b5\u3002<\/li>\n<li>\u4f46\u662f\u8fd9\u5e76\u4e0d\u4ee3\u8868\u6211\u4eec\u4e0d\u5206\u6790\u65e0\u89e3\u60c5\u51b5\uff0c\u5f80\u5f80\u65e0\u89e3\u7684\u60c5\u51b5\u4f1a\u662f\u4e00\u4e9b\u9898\u76ee\u7684\u7a81\u7834\u53e3\u53ef\u4ee5\u5e2e\u52a9\u6211\u4eec\u89e3\u9898\uff0c\u4f46\u4e0d\u5e94\u8be5\u88ab\u65e0\u89e3\u60c5\u51b5\u9650\u5236\u4e86\u601d\u8def\uff0c\u4ece\u800c\u4e0d\u6562\u8003\u8651\u8d2a\u5fc3<\/li>\n<\/ul>\n<p><a href=\"https:\/\/vjudge.net\/solution\/49104109\/wYuu0QxmINTb1G2dUiTh\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-2228#author=0\">CSES - 2228<\/a><\/h3>\n<p>\u9996\u5148\u4e0d\u8003\u8651\u9898\u76ee\u4e2d\u7684\u9650\u5236\u6761\u4ef6\uff0c\u65b9\u6848\u6570\u5e94\u8be5\u4e3a\uff1a$k^n$\uff0c\u90a3\u4e48\u5982\u679c\u53ea\u7f3a\u4e86\u4e00\u4e2a\u6570\u5b57\u5462\uff1f\u5982\u679c\u7f3a\u4e86\u4e00\u4e2a\u6570\u5b57\u6240\u6784\u6210\u7684\u65b9\u6848\u4e3a\uff1a$(k - 1)^n \\times \\binom 1k$ \u3002<\/p>\n<p>\u5982\u4f55\u7406\u89e3\uff1f\u4e58\u53f7\u5de6\u8fb9\u4ee3\u8868\u7684\u5269\u4e0b\u7684 $k - 1$ \u4e2a\u6570\u5b57\u586b\u5165 $n$ \u4e2a\u7a7a\u4f4d\u7684\u65b9\u6848\u6570\uff0c\u800c\u4e58\u53f7\u53f3\u8fb9\u5219\u4ee3\u8868\u7740\uff0c\u4ece $k$ \u4e2a\u6570\u5b57\u4e2d\u6311\u9009 1 \u4e2a\u6240\u9700\u8981\u7684\u65b9\u6848\u6570\u3002<\/p>\n<p>\u6211\u4eec\u7c7b\u6bd4\uff0c\u5982\u679c\u7f3a\u4e86 $i$ \u4e2a\u6570\u5b57\uff0c\u6784\u6210\u7684\u65b9\u6848\u6570\u4e3a$(k - i)^n \\times \\binom ik$ \uff0c\u4f46\u662f\u5462\uff0c\u7531\u4e8e\u4e00\u5b9a\u7f3a\u5c11\u4e00\u4e2a\u6570\u5b57\u7684\u60c5\u51b5\uff0c\u5df2\u7ecf\u5305\u542b\u4e86\u4e00\u5b9a\u7f3a\u5c11\u4e24\u4e2a\u6570\u5b57\u7684\u60c5\u51b5\uff0c\u6240\u4ee5\u8bf4\u6211\u4eec\u8981\u7528\u5bb9\u65a5\u539f\u7406\u3002<\/p>\n<p>\u6700\u7ec8\u7684\u7b54\u6848\u4e3a\uff1a<\/p>\n<p>$$k^n - \\sum_{i = 1}^{k - 1} (k - i)^n \\times\\binom ik$$<\/p>\n<p>\u603b\u7ed3\uff1a\u5bf9\u4e8e\u65b9\u6848\u6570\u95ee\u9898\u53ef\u4ee5\u4f18\u5148\u8003\u8651\u5bb9\u65a5\u539f\u7406\uff1b\u5e76\u4ece\u6ca1\u6709\u9650\u5236\u5f80\u6709\u9650\u5236\u8fdb\u884c\u601d\u8003\u3002<\/p>\n<p><a href=\"https:\/\/vjudge.net\/solution\/48845881\/5Km8tJ8PuokMY3UyeHff\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-2414\">CSES - 2414 List of Sums<\/a><\/h3>\n<p>\u8003\u8651\u5e8f\u5e8f\u5217 A \u662f\u5355\u8c03\u9012\u589e\uff0c\u5c06 B \u4ece\u5c0f\u5230\u5927\u6392\u5e8f\u3002\u6211\u4eec\u53ef\u4ee5\u63a8\u51fa\u4ee5\u4e0b\u7ed3\u8bba\uff1a<\/p>\n<ul>\n<li>$A_0 + A_1 = B_0$<\/li>\n<li>$A_0 + A_2 = B_1$<\/li>\n<\/ul>\n<p>\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\uff1a<\/p>\n<ul>\n<li>$A_2 - A_1 = B_1 - B_0$<\/li>\n<\/ul>\n<p>\u8003\u8651 $A_1 + A_2$ \uff0c\u5b83\u7684\u503c\u4e00\u5b9a\u662f $B_i,i \\in [2, n]$\uff0c\u8fd9\u4e2a\u8bf4\u660e\u4e86\uff0c $A_0$ \u53ea\u6709 $n - 2$ \u79cd\u53ef\u80fd\u3002<\/p>\n<p>\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\uff1a$A_1 = \\frac{B_i - B_1 + B_0}{2}$ \uff0c$A_0 = \\frac{B_1 + B_0 - B_i}2$\uff0c\u90a3\u4e48\u6211\u4eec\u5c31\u53ef\u4ee5\u4fbf\u5229\u6bcf\u4e00\u4e2a $A_0$ \u7136\u540e\u5224\u65ad\u5b83\u80fd\u4e0d\u80fd\u4f7f B \u6210\u7acb\uff0c\u5982\u4f55\u6d4b\u8bd5\uff1f<\/p>\n<p>\u5bf9\u4e8e\u6bcf\u4e00\u8f6e\u6d4b\u8bd5\uff0c$A\\i$ \u5c31\u7b49\u4e8e $B{\\min} - A_i$\uff0c\u4e4b\u540e\u4ece B \u4e2d\u5224\u65ad $A_j + A_i(j &lt; i)$ \u662f\u5426\u5728 B \u4e2d\u5e76\u5220\u9664\u3002<\/p>\n<p><a href=\"https:\/\/vjudge.net\/solution\/48810705\/lpNKpEsYGnYwVRZe8VQh\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-2421\">CSES - 2421 Counting Reorders <\/a><\/h3>\n<p>\u4fd7\u8bdd\u8bf4\u201c\u6b63\u96be\u5219\u53cd\u201d\uff0c\u56e0\u4e3a\u76f4\u63a5\u6c42\u5408\u6cd5\u7684\u60c5\u51b5\u5f88\u660e\u663e\u975e\u5e38\u96be\uff0c\u6240\u4ee5\u8003\u8651\u53cd\u7740\u6765\u3002\u6211\u4eec\u5c06\u4e00\u4e2a\u5b57\u7b26\u4e32\u5206\u6210\u82e5\u5e72\u4e2a\u533a\u95f4\uff0c\u4f7f\u5f97\u6bcf\u4e2a\u533a\u95f4\u91cc\u9762\u7684\u5b57\u6bcd\u90fd\u76f8\u540c\u3002<\/p>\n<p>\u5c06\u6240\u6709\u7684\u5b57\u6bcd\u5206\u6210 $x$ \u4e2a\u533a\u95f4\u7684\u65b9\u6848\u6570\u4e3a $A(x)$\uff0c\u5219\u5bf9\u4e8e\u521d\u59cb\u5b57\u7b26\u4e32\u5168\u90e8\u91cd\u65b0\u6392\u5217\u7684\u60c5\u51b5\u6570\u4e3a $A(n)$\uff0c\u4e00\u5b9a\u6709\u4e24\u4e2a\u76f8\u90bb\u5b57\u7b26\u91cd\u590d\u7684\u6570\u76ee\u5c31\u662f $A(n - 1)$\uff0c\u6b64\u65f6\u4e00\u5b9a\u6709\u4e00\u4e2a\u957f\u5ea6\u4e3a 2 \u7684\u533a\u95f4\u4e2d\u5b57\u6bcd\u76f8\u540c\uff0c\u5269\u4f59\u7684 $n - 1$ \u4e2a\u533a\u95f4\u4efb\u610f\u6392\u5217<\/p>\n<p>\u76f8\u4f3c\u7684\uff0c\u4e00\u5b9a\u6709 $i$ \u4e2a\u5b57\u6bcd\u8fde\u7eed\u76f8\u540c\u7684\u6570\u76ee\u662f $A(n - i)$\uff0c\u56e0\u4e3a $A(n)$ \u4e2d\u5df2\u7ecf\u5305\u542b\u4e86 $A(n - 1)$ \u7684\u60c5\u51b5\uff0c\u800c $A(n - 1)$ \u4e2d\uff0c\u540c\u6837\u4e5f\u5305\u542b\u4e86 $A(n - 2)$ \u7684\u60c5\u51b5\uff0c\u6240\u4ee5\u8bf4\u8003\u8651\u5bb9\u65a5\u539f\u7406\uff0c\u6700\u7ec8\u7684\u7b54\u6848\u4e3a:<\/p>\n<p>$$\\sum_{i = 0}^{n} A(n - i) \\times(-1)^n$$<\/p>\n<p>\u4f46\u662f\u8be5\u5982\u4f55\u8ba1\u7b97 $A(x)$ \u5462\uff1f\u5b9a\u4e49 $D(i, j)$ \u4ee3\u8868\u524d $i$ \u4e2d\u5b57\u7b26\uff0c\u5206\u6210 $j$ \u4e2a\u533a\u95f4\u7684\u65b9\u6848\u6570\uff0c\u90a3\u4e48 $A(n) = D(26,n)$\uff0c\u663e\u7136 $D(0, 0) = 1$\uff0c\u8bb0\u7b2c $i$ \u4e2d\u5b57\u7b26\u51fa\u73b0\u7684\u6b21\u6570\u4e3a $c$\uff0c\u663e\u7136\u5f53 $c = 0$ \u65f6\uff0c$D(i, j) = D(i - 1, j)$\u3002\u5426\u5219\uff0c\u8fd9 $c$ \u4e2a\u5b57\u7b26\u5c31\u8981\u5206\u6210 $k \\in [1, c]$\uff0c\u4e2a\u90e8\u5206\u548c\u5df2\u6709\u7684 $j$ \u4e2a\u533a\u95f4\u6df7\u5408\uff0c\u53ef\u4ee5\u5f97\u5230\uff1a<\/p>\n<p>$$D(i, j + k) \\gets D(i, j + k)+D(i - 1,j)\\cdot \\binom {j+k}{k}\\cdot \\binom{c - 1}{k - 1} $$<\/p>\n<p>\u5982\u4f55\u7406\u89e3\u4ee5\u4e0a\u7684\u5f0f\u5b50\u5462\uff1f\u5176\u4e2d $\\binom {j+k}{k}$\uff0c\u8868\u793a\u5c06 $k$ \u4e2a\u533a\u95f4\u63d2\u5165\u539f\u6765\u7684 $j$ \u4e2a\u533a\u95f4\u4e2d\uff0c\u5c31\u662f\u5728 $j + k$ \u4e2a\u533a\u95f4\u4e2d\u9009\u62e9 $k$ \u4e2a\uff0c\u800c $\\binom{c - 1}{k - 1}$ \u53ef\u4ee5\u901a\u8fc7\u63d2\u677f\u6cd5\u7406\u89e3\u3002<\/p>\n<p>\u603b\u7ed3\uff1a<\/p>\n<ol>\n<li>\u5bf9\u4e8e\u6b63\u7740\u6c42\u6bd4\u8f83\u56f0\u96be\u7684\u7ec4\u5408\u6570\u5b66\u9898\u76ee\uff0c\u53ef\u4ee5\u8003\u8651\u53cd\u7740\u6c42\u89e3\u3002<\/li>\n<li>\u5bf9\u4e8e\u9898\u76ee\u6027\u8d28\u8fdb\u884c\u5206\u6790\uff0c\u6784\u9020\u51fa\u73b0\u4e0d\u540c\u60c5\u51b5\u7684\u6982\u7387\uff0c\u5e76\u8003\u8651\u5bb9\u65a5<\/li>\n<li>\u627e\u5230\u5f53\u524d\u6b65\u9aa4\u548c\u4e0a\u4e00\u6b65\u9aa4\u7684\u5173\u7cfb\uff0c\u8fdb\u884c\u9012\u63a8\u3002<\/li>\n<\/ol>\n<p><a href=\"https:\/\/vjudge.net\/solution\/48862105\/77NzMr61ETRcPBZecWyq\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-2425#author=GPT_zh\">CSES-2425 Stack Weights<\/a><\/h3>\n<p>\u67d0\u4f4d\u9ad8\u4eba\u66fe\u7ecf\u8bf4\u8fc7\uff1a\u5bf9\u4e8e\u627e\u5145\u8981\u6761\u4ef6\u7684\u9898\u76ee\uff0c\u90a3\u5c31\u628a\u5b83\u6240\u6709\u7684\u5fc5\u8981\u6761\u4ef6\u5168\u90e8\u5217\u51fa\u6765\u3002<\/p>\n<p>\u90a3\u4e48\u6211\u4eec\u5c31\u8003\u8651\u5217\u51fa\u5145\u5206\u6761\u4ef6\uff0c\u7ecf\u8fc7\u5927\u91cf\u7684\u6f14\u7b97\u7b97\u6211\u4eec\u53d1\u73b0\uff1a<\/p>\n<ul>\n<li>\u5982\u679c\u5806 1 \u7684\u91cd\u91cf\u5927\u4e8e\u5806 2 \u7684\u91cd\u91cf\uff0c\u90a3\u4e48 $\\forall i \\in [1,n]$ \uff0c\u5b9a\u4e49 $l_i$ \u8868\u793a\u5806 1 \u7f16\u53f7\u5927\u4e8e $i$ \u7684\u781d\u7801\u6570\uff0c$r_i$ \u4ee3\u8868\u5806 2 \u7f16\u53f7\u5927\u4e8e $i$ \u7684\u781d\u7801\u6570\uff0c\u90fd\u6709 $l_i &gt; r_i$\u3002<\/li>\n<\/ul>\n<p>\u5bf9\u4e8e\u5806 2 \u540c\u7406\uff0c\u95ee\u9898\u5c31\u8f6c\u5316\u6210\u4e86\u6c42\u89e3\u80fd\u5426\u5728\u67d0\u4e00\u65f6\u523b\uff0c\u5806 1 \u3001\u5806 2 \u90fd\u80fd\u6ee1\u8db3\u4ee5\u4e0a\u6761\u4ef6\u3002<\/p>\n<p>\u53ef\u4ee5\u901a\u8fc7\u8bb0\u5f55\u524d\u7f00\u548c\u6765\u5feb\u901f\u5224\u65ad\u6761\u4ef6\u662f\u5426\u6210\u7acb\uff1a<\/p>\n<ul>\n<li>\u82e5\u6700\u5c0f\u503c\u4e0d\u5c0f\u4e8e 0\uff0c\u5219\u5806 1 \u4e00\u5b9a\u91cd\u4e8e\u5806 2<\/li>\n<li>\u6700\u5927\u503c\u4e0d\u5927\u4e8e 0\uff0c\u5219\u5806 2 \u4e00\u5b9a\u91cd\u4e8e\u5806 1<\/li>\n<li>\u82e5\u4ee5\u4e0a\u6761\u4ef6\u5747\u4e0d\u6ee1\u8db3\uff0c\u8fd4\u56de\u4f60\u5bc4\u4e86<\/li>\n<\/ul>\n<p>\u53ef\u4ee5\u8003\u8651\u901a\u8fc7\u7ebf\u6bb5\u6811\u8fdb\u884c\u533a\u95f4\u6700\u5927\u6700\u5c0f\u503c\u7ef4\u62a4\uff0c\u5176\u4ed6\u6570\u636e\u7ed3\u6784\u5e94\u8be5\u4e5f\u53ef\u4ee5\uff0c\u4f46\u662f\u6211\u592a\u83dc\u4e86\u4e0d\u4f1a\u3002<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6 $O(n \\log n)$ \uff0c\u5e94\u8be5\u6ca1\u6709\u9519\u5427\u3002<\/p>\n<p><a href=\"https:\/\/vjudge.net\/solution\/48801685\/Y0FQLG49NbJKhS7CsXR0\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-2426\">CSES - 2426 Programmers and Artists<\/a><\/h3>\n<p>\u666e\u901a\u7684\u679a\u4e3e\u65f6\u95f4\u590d\u6742\u5ea6 $O(n^2)$ \u4f1a\u8d85\u65f6\uff0c\u8003\u8651\u7528\u8d2a\u5fc3\u4f18\u5316\u3002<\/p>\n<p>\u5c06\u6bcf\u4e2a\u4eba\u6309\u7167 $x - y$ \u9012\u51cf\u6392\u5e8f\uff0c\u8003\u8651\u7ef4\u62a4\u4e24\u4e2a\u6570\u7ec4 $suf[i]$ \u548c $pre[i]$\uff0c\u5206\u522b\u8868\u793a\u540e $i$ \u4e2a\u4eba\u8fdb\u884c\u7684\u8d21\u732e\u548c\u524d $i$ \u4e2a\u4eba\u8fdb\u884c\u7684\u8d21\u732e\u3002\u679a\u4e3e\u65f6\u5c31\u8003\u8651 $pre[i] + suf[i + 1]$\uff0c\u597d\u50cf\u53ef\u4ee5\u79f0\u4f5c\u4e2d\u9014\u76f8\u9047\uff1f<\/p>\n<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/P7913\">[CSP-S 2021] \u5eca\u6865\u5206\u914d<\/a> \u4e5f\u662f\u4e00\u9053\u7c7b\u4f3c\u7684\u9898\u76ee\uff0c\u628a\u6bcf\u4e00\u79cd\u53ef\u80fd\u60c5\u51b5\u679a\u4e3e\u51fa\u6765\uff0c\u63a5\u7740\u901a\u8fc7\u4e2d\u9014\u76f8\u9047\u6765\u505a\u3002<\/p>\n<p>\u603b\u7ed3:<\/p>\n<ul>\n<li>\u4ec0\u4e48\u9898\u76ee\u53ef\u4ee5\u901a\u8fc7\u4e2d\u9014\u76f8\u9047\u6765\u505a\uff1f\n<p>\u6709\u4e24\u4e2a\u96c6\u5408 $A$\u3001$B$\uff0c\u6709\u4e00\u5143\u7d20 $i$\uff0c\u82e5 $i \\in A$ \u4e3a\u771f\uff0c\u90a3\u4e48 $i\\in B$ \u4e00\u5b9a\u4e3a\u5047\uff0c\u53cd\u4e4b\u4ea6\u7136\u3002\u63a5\u7740\u6211\u4eec\u5c31\u53ef\u4ee5\u901a\u8fc7\u67d0\u4e9b\u624b\u6bb5\u9884\u5904\u7406(\u6392\u5e8f)\uff0c\u63a5\u7740\u5728\u8ba1\u7b97\u51fa $A$ \u548c $B$ \u5728\u4e0d\u540c\u5927\u5c0f\u7684\u4e0d\u540c\u7b54\u6848\u3002\u63a5\u7740\u901a\u8fc7\u4e00\u4e2a $O(n)$ \u7684\u679a\u4e3e\u53bb\u7edf\u8ba1\u7b54\u6848\u5373\u53ef\u3002<\/li>\n<\/ul>\n<p><a href=\"https:\/\/vjudge.net\/solution\/49116012\/9kTBWeMcuoIZbbUDN2Dz\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/CSES-2430\">CSES - 2430 Binary Subsequences<\/a><\/h3>\n<p>\u6784\u9020\u795e\u9898\uff0c\u4f9d\u7136\u662f\u7ecf\u5178\u7684\u53cd\u7740\u6765\uff0c\u6211\u4eec\u5148\u8003\u8651\u6b63\u7740\u63a8\uff0c\u8bb0 $x$ \u548c $y$ \u5206\u522b\u4ee3\u8868\u4ee5 0 \u7ed3\u5c3e\u548c\u4ee5 1 \u7ed3\u5c3e\u7684\u5b50\u5e8f\u5217\u4e2a\u6570\uff0c\u5982\u679c\u63a5\u4e0b\u6765\u53c8\u662f 0\uff0c\u5219 $ x = x + y + 1$\uff0c\u5982\u679c\u4e0b\u4e00\u4f4d\u662f 1 \u90a3\u4e48 $y = x + y + 1$\u3002<\/p>\n<p>\u7531\u4e8e $x + y = n$ \uff0c\u6211\u4eec\u53ef\u4ee5\u4f9d\u6b21\u679a\u4e3e $x$ \u548c $y$\uff0c\u7136\u540e\u53cd\u63a8\u51fa\u5bf9\u5e94\u7684 01 \u4e32\uff0c\u6709\u70b9\u7c7b\u4f3c\u4e8e\u8f97\u8f6c\u76f8\u9664\u6cd5\u3002<\/p>\n<p>\u5747\u644a\u65f6\u95f4\u590d\u6742\u5ea6 $O(n\\log n)$<\/p>\n<p><a href=\"https:\/\/vjudge.net\/solution\/49155238\">AC code<\/a><\/p>\n<h3><a href=\"https:\/\/vjudge.net\/problem\/OpenJ_Bailian-2356#author=GPT_zh\">OpenJ_Bailian - 2356 Find a multiple<\/a><\/h3>\n<p>\u5b9a\u4e49 $s<em>i$ \u4ee3\u8868 $\\sum<\/em>{i=1}^{n} a_i$ \uff0c\u82e5 $N|s_i$ \uff0c\u5219\u8f93\u51fa $a_j,\\forall j[1,i]$ \u5373\u53ef\u3002<\/p>\n<p>\u82e5 $s_i\\equiv s_j\\mod{N}(i&lt;j)$ \uff0c\u5219\u8f93\u51fa $a_k,\\forall k\\in[i,j]$ \u5373\u53ef<\/p>\n","protected":false},"excerpt":{"rendered":"<p>CSES &#8211; 1075 Permutations II \u52a8\u6001\u89c4\u5212\u597d\u9898\u3002 \u89e3\u6cd5\u4e00\uff08recommend) \u5b9a\u4e49 $ [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[33],"_links":{"self":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/1051"}],"collection":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/comments?post=1051"}],"version-history":[{"count":46,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/1051\/revisions"}],"predecessor-version":[{"id":1145,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/1051\/revisions\/1145"}],"wp:attachment":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/media?parent=1051"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/categories?post=1051"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/tags?post=1051"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}