致所有集训营的同学

码上开聊VOL.3 未来无限-王子翾

码上开聊 欢迎来到码上开聊！这是一个属于编程少年的花式聊天角，带你一起解锁大佬们的神仙操作、逆袭时刻和刷题“翻车”故事！在这里，每一个代码少年都在用青春和坚持“码”出自己的高光时刻！ 🎉 欢迎来到「码上开聊」Vol.3！在本期访谈中，我们将走近年仅初二、编程经验丰富的王子翾（社区昵称：Sanssssss），聆听他如何在小学二年级便踏上了编程之旅，并一路收获奖项的成长故事。让我们一起了解这位充满活力的同学吧！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 码上开聊VOL.3 未来无限-王子翾 > 个人档案 * 姓名：王子翾 * 社区昵称：Sanssssss * 年级：初二 * 校区：成都牛市口校区 * 编程起点：小学二年级学Scratch，三年级学Python与C++ * 兴趣：编程、游戏设计、信息安全 * 社区主页：ACGO个人主页 * 获奖经历： * 2024年：CSP-J 一等奖（第二轮）、CSP-S 三等奖（第一轮）、蓝桥杯C++省二 * 2023年：CSP-J 二等奖（第一轮）、第五届四川省青少年创意编程与智能设计比赛决赛一等奖 * 2022年：CSP-J 二等奖 （第一轮）、蓝桥杯Python省赛二等奖 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 高能访谈 Q1 你是从什么时候开始学编程的？ 王子翾 ：我从小学二年级开始学Scratch，现在初二，三年级学的Python，过了一年才开始学C++。 Q2 从小就喜欢编程么？ 王子翾 ：小时候觉得编程挺好玩，主要是图形化编程很有意思。现在更多的是刷题成功后觉得很有成就感，像是一种“能力变强”的感觉。我觉得既然花了很多时间学编程，不坚持下去感觉会浪费掉之前的努力。 Q3 你从PYTHON过渡到C++难吗？是怎么克服的？ 王子翾 ：一开始确实有点难，特别是动态规划的部分，刚开始一直搞不懂。后来听了同龄人的思路，再刷几道类似的题，慢慢就理解了。 Q4 平常都怎么安排刷题时间？在哪些平台刷题？ 王子翾 ：每周日我会给自己半天时间刷题，除非有事一般都会刷。周一到周五看作业进度，有空就上ACGO打比赛。一开始是在洛谷，最近在ACGO上打比赛。 Q5 有什么印象深刻的题么？ 王子翾 ：ACGO挑战赛8的第五题A27805.宏量运算 ，我想了三天才做出来。 Q6 你参加了几次集训营？有什么感受？ 王子翾 ：参加过多次集训营，我觉得集训营能把大家聚在一起，都是热爱编程的同龄人，能一起学，也能交流做题的技巧，还能查缺补漏，对我帮助挺大的。虽然我是在成都学习的，不过每年都会去杭州参加集训。我觉得杭州是总部，教得更扎实。 Q7 集训营里有没有特别难忘的事情？ 王子翾 Q8 用一句话形容自己的性格？ 王子翾 ：我觉得我的性格像水一样吧，因为我从小到大就没有真正生气过，所以我觉得我的性格像水。 Q9 学习C++过程中有什么难忘的经历吗？ 王子翾 ：最难忘的一件事是在刚入门的时候发现万能头文件，因为只需要这一个头文件就可以顶替其他大部分头文件，所以当时特别激动。后来，我还将一些想法写成了《我重生异世界，觉醒最强系统》系列。 王子翾文章：我重生异世界，觉醒最强系统（2） Q10 有什么编程经验可以分享给刚入门的选手？ 王子翾 ：就是不要轻易放弃，然后遇到对你来说特别困难，完全没有思路的不要死磕，因为如果连思路都没有就几乎不可能做对，这时候就可以问问老师或同学，也可以去社区问问大佬，很多都是很乐意教萌新的。 来源：通义万象 本人照片图生图 Q11 未来编程学习上有什么计划？有考虑什么职业方向吗？ 王子翾 ：明年想冲一下S组的奖，然后尝试争取进省队。希望高中阶段能够继续提高吧。职业的话 可能会考虑游戏设计或者信息网络安全这一块吧，两个方向都挺感兴趣的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 访谈结语 如果你也对编程有兴趣，欢迎和他一起加入ACGO，刷题、讨论、交流经验，一起在编程的世界里不断进步吧！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 往期访谈 VOL.1-镇站之宝Macw VOL.2-勤勉笃行吴泽均

关于欢乐赛#33的举报

原举报 惩罚 当事人发言： 首先让我们捋一捋，竞赛结尾有标明：首次作弊禁言15天并取消奖励，但这边很明确的能看到只禁言3天。如果真的是作弊，为什么只有3天？再者，公告曰：T5、T6与AI相似度达100%。AI的随机方式都不能保证达到与AI100%相似度，诸位仍然觉得这是使用AI吗？又如，如果在排位赛作弊会降低排位分，即使不在评分范围内也应有相对应在排位分上的惩罚，主页信息却不见#33有掉分。综上所述，此计不过是AC君为避免事态扩大与老师演的苦肉计罢了 所以说AC君有自己的反作弊系统，有的时候如果存在其他合理且合规的可能性不用先写举报帖，直接私聊向AC君汇报/核对情况。如果闹了乌龙对谁都不好。 有大佬点赞了，帮帮忙吧（点个赞发个顶都可以） 从12.4以后 处罚更为酌情处理

故事接龙-重开

以前那个没用了，全被他们的图片占了！ 这次来重新接龙！！ 如果发图片，联系AC君 另外禁止给评论点赞！ https://www.acgo.cn/application/1815726290803429376👈团队

互动#8｜如果转生异世界写代码

🚀互动#8 ：如果转生异世界写代码 😎 hi，要是转生到异世界，你会怎样？ 你能利用代码知识干啥？ 快来一起脑洞大开吧！ 🎤脑洞分享区 分享你在异世界运用代码的奇思妙想，职业规划、冒险策略等都可。 🎁 话题奖励 * 奖励设置：选 3 位 最强脑洞送 ACGO 2周年贴纸。 * 参与方式：在评论区畅抒己！ ⏰ 活动时间 * 结束时间: 12月15日 * 奖励公告 ：12月16日 🎁获奖名单 ID 昵称 4326909 天之神_ZDZL_复仇者_6. 2771152 AC是我的0.o 2454098 复仇者_燃烬

一文讲清动态规划的本质

一文讲清动态规划的本质 动态规划 Dynamic Programming (DP) 是算法领域的核心思想之一，却同时也是让许多学习者感到棘手的难点之一。动态规划的难点在于它不是简单的数学推导，也不单纯考验人们的程序设计能力，而更像是一种从思维方式到问题建模的一次深刻训练。 本文将从动态规划的定义出发，深入探讨动态规划的本质、应用场景、核心特点、解题思路以及如何逐步提升解决动态规划问题的能力。 动态规划的定义和应用：将大问题分解成许多小问题 动态规划的核心思想可以被概括为一句话：将一个复杂的问题分解成多个简单的子问题，并通过保存子问题的解来避免重复计算，从而提高求解效率。 换句话说，动态规划适用于解决以下两类问题： 1. 最优子结构问题：所谓的最优子结构问题，就是一个最优解可以通过其子问题的最优解而构成。 2. 子问题重叠问题：多个子问题在递归的过程中会重复出现，并且会被多次计算到。 E.G. 01 - 斐波那契数列 I\MATHRM{I}I 我们都知道斐波那契的通项公式是 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)。以计算斐波那契数列的第五项 F(5)F(5)F(5) 为例，很显然，F(5)F(5)F(5) 就是我们需要求解的大问题，而这个大问题可以被逐步分解为两个小问题，即 F(4)F(4)F(4) 和 F(3)F(3)F(3) 。只要我们知道了 F(4)F(4)F(4) 和 F(3)F(3)F(3)，那么我们就可以将这两项相加来得到最终的结果。这个就是最优子结构的体现。 那什么时候会出现子问题重叠呢？我们不妨用代码来实现斐波那契数列： 这是一个很简单的递归算法。通过模拟递归算法我们可以画出一个递归图： 通过观察这个图可以发现，在计算 F(5)F(5)F(5) 的时候，F(3)F(3)F(3) 被 F(5)F(5)F(5) 调用过一次，同时又被 F(4)F(4)F(4) 调用一次。相同地，F(2)F(2)F(2) 被 F(3)F(3)F(3) 调用了两次，被 F(4)F(4)F(4) 也调用了一次。我们可以发现这个图中有很多的重复计算，这会大大浪费程序的运行时间。然而这就是所谓的子问题重叠问题。 针对这类型的问题，有什么解决方案呢？最直接的方法就是把已经计算过的答案保存下来，下次再调用的时候直接获取结果就可以了，这种方法就是大家常说的“记忆化”。记忆化搜索的代码如下： 这个代码与普通斐波那契数列唯一的区别就是增加一个 memo 数组，判断某一个值是否已经被计算过。如果已经被计算过就直接返回，而不需要继续递归来消耗时间。 而另一种解决办法就是“递推“，我们可以从小到大，先计算 F(0)F(0)F(0) 和 F(1)F(1)F(1) 并把答案保存下来，计算 F(2)F(2)F(2) 的时候就可以立刻通过将 F(0)F(0)F(0) 和 F(1)F(1)F(1) 相加得到结果。这种递推的做法就是所谓的动态规划思想。而这么做的代码也更加简洁： 因此，动态规划的核心思想就是通过 记录 和 重用 子问题的解，避免重复计算，从而提高求解效率。动态规划是一种典型的 拿空间换时间 的思想（毕竟现在的社会，时间成本比空间成本高太多了）。 > 动态规划与分治思想的主要区别就是分治算法主要应用于子问题不重叠的问题，而针对子问题重叠的问题，动态规划是一个更好的选择。 动态规划的性质 动态规划的三个基本性质是：最优子结构、子问题重叠 以及 无后效性。前两个性质已经在第一部分提及过了，本部分主要讲解无后效性。 无后效性，又称马尔可夫性，这意味着某阶段的状态一旦确定，就不接受该状态之后决策的影响。即，某状态以后的过程不会影响之前的状态，只与当前的状态有关。用一句话概括就是“过去的事情不会影响未来，只关注当前的状态”。 除了无后效性，动态规划的另一个核心在于 最优性原理，即一个最优解包含其子问题的最优解。这一原理是由理查德·贝尔曼（Richard Bellman）提出。最优性原理是动态规划思想的理论基石。 E.G. 02 - 斐波那契数列 II\MATHRM{II}II 回到原本斐波那契数列场景，当计算 F(5)F(5)F(5) 时，答案只依赖于当前状态 F(4)F(4)F(4) 和 F(3)F(3)F(3) 的值，与更早的历史状态无关。这就是为什么，我们在计算 F(5)F(5)F(5) 的时候可以直接使用 F(3)F(3)F(3) 和 F(4)F(4)F(4) 之前被计算出来的结果相加得到答案，而不是从 F(1)F(1)F(1) 和 F(0)F(0)F(0) 开始重新计算。 与此同时，在具有无后效性的场景中，一旦某一个状态的值已经被计算下来并可以转移到下一个状态时，这个状态将不会再被改变。换句话说，某状态以后的过程不会影响以前计算出来的状态，只与当前的状态有关。 无后效性是避免重复计算子问题的前提条件。 动态规划和递归的关联 在看到这里，你会发现动态规划和递归这两个思想有着异曲同工之妙。事实上，大多数的动态规划问题都可以使用记忆化搜索（递归）来解决。动态规划和暴力递归的关键区别如下： * 递归：通过函数自调用，将问题分解为子问题，直到达到基本情况。递归可能导致大量重复计算，效率较低。 * 动态规划：通过记录已解决的子问题的解，避免重复计算。动态规划通常采用自底向上的方式，效率更高。 因此广义而言。带有记忆化搜索的递归算法也可以被称之为是动态规划。 解决动态规划问题的基本思路 解决动态规划问题的基本思路如下： 步骤一：确定不同的阶段和变量 根据题目的特性，我们可以把一个问题拆解成小问题，将一个小问题拆分成一个个次小问题，以此类推。那么在这之中，每一个需要解决的问题就被称之为一个阶段（状态）。因此对于动态规划问题，第一步需要做的就是尝试如何把大问题分解成许多个有关联的问题。同时，我们需要找到每一个阶段之间都是通过什么变量关联起来的。在斐波那契数列问题中，变量就是斐波那契数列的项数。 步骤二：确定状态转移方程式 在动态规划中，我们把每一个“阶段”称之为一个状态。例如，F(5)F(5)F(5) 就可以被称之为是一个状态。我们需要搞清楚大问题的状态和小问题的状态之间的关联。 在斐波那契数列中，这个关联就是：序列的第 iii 项为序列的第 i−1i-1i−1 和第 i−2i-2i−2 项的和。用数学表示就是 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)。在其他的例子中（更加现实一点的），状态转移方程往往与决策有着密不可分的关系（例子请参考【E.g. 03 - 数楼梯】）。 在设计状态转移方程式时，你需要包括所有可能涉及到的变量。以确保能在后续的程序实现步骤中保留所有的可能性。 步骤三：确定初始状态和边界条件 将问题分解成不能够再被分解的问题，这些问题被称之为最小问题。对于每一个最小问题，应当可以做到直接得出答案，而不需要通过计算。 例如在斐波那契数列中，所谓的最小问题就是 F(0)F(0)F(0) 和 F(1)F(1)F(1) 的值。这两个值的计算不需要依赖于任何的递推式子，而是根据定义或者逻辑直接给出的。 因此我们需要设置 F(0)F(0)F(0) 和 F(1)F(1)F(1) 的初始值，并且将这两个状态设置成边界条件。 E.G. 03 - 数楼梯 题目描述 一个楼梯有 NNN 级台阶，上楼可以一步上一阶，也可以一步上二阶。请你编写一个程序，计算走到第 NNN 级台阶共有多少种不同的走法。 解题思路 这是一道动态规划的经典例题，对于初学者而言可能对这道题目没有任何的头绪，让我们按照【解决动态规划问题的基本思路】一步一步来解决这道题。 首先确定不同的阶段，对于这道题而言，很显然不同的的阶段就是走到不同阶数的方案数，而当前楼梯的阶级就是唯一的变量。每上一层楼梯，这个变量就会增加。我们不妨定义 dpidp_idpi 表示走到第 iii 阶楼梯的方案数。 接下来确定变量和状态转移方程，在这个场景中，我们思考每一个状态之间的关联。假设我们要知道走到第十级台阶的方案数，但是我们知道想要走到第十级台阶，我们只有两个可能性（决策）： 1. 从第九级台阶迈一步走到第十级台阶。 2. 从第八级台阶迈两步走到第十级台阶。 除了这两种方法，我们没有选择。换句话说，走到某一级台阶的方案数只跟走到这之前一级和之前两级台阶的方案数有关系（无后效性），并且方案数就是这两种可能性相加的和（逻辑上也是这样子的）。用一个更宽泛的式子来描述就是： dpi=dpi−1+dpi−2\large{dp_i = dp_{i-1} + dp_{i-2}} dpi =dpi−1 +dpi−2 而这个式子就是所谓的状态转移方程式。 因此，在设计状态转移方程式的时候我们着重观察“可能性”和“决策”这两个关键点。 最后就是确定初始状态和边界条件了，根据题目要求，状态的边界条件在 1≤i≤n1\le i \le n1≤i≤n： 1. 当只有一级台阶的时候，只有一种可能性，就是从初始平台迈一步来到第一级台阶。因此 dp1=1dp_1 = 1dp1 =1。 2. 当有两级台阶的时候，有两种可能，一种是从初始平台迈两步直接来到第二级台阶，另外一种就是连续走两步走到第二级台阶。因此 dp2=2dp_2 = 2dp2 =2。 3. 到了第三级台阶，套用公式可以得到 dp3=dp1+dp2dp_3 = dp_1 + dp_2dp3 =dp1 +dp2 ，因此不再需要继续计算初始条件了。 最后，本题的 C++ 标准代码如下： E.G. 04 - 最长公共子序列 题目描述 给定两个字符串 X 和 Y，求出这两个字符串的最长公共子序列 LCS 的长度。注意，这里的子序列不要求连续，但必须保持顺序。 样例输入输出： 解题思路 这道题相比较前面的题目难度有一定的提升，我们依旧按照前文提到的基本思路来一步一步地解决这个动态规划问题。 首先来确定不同的状态（阶段），我们的目标是找出两个字符串 X 和 Y 的最长公共子序列。为了将问题分解，我们可以定义阶段和变量如下： * 阶段： 我们考察两个字符串的前缀，分别为 X[0:i] 和 Y[0:j]（即 X 的前 i 个字符和 Y 的前 j 个字符）。 * 变量： 两个变量 i 和 j 用于表示字符串 X 和 Y 的子问题范围。 在每个阶段，我们的任务是确定 X[0:i] 和 Y[0:j] 的最长公共子序列的长度。这就将整个问题分解为多个规模更小的子问题。 因此，我们考虑用 dpi,jdp_{i, j}dpi,j 来表示字符串 X[0:i] 和 Y[0:j] 的最长公共子序列的长度。 看到这里，很多人会有些许疑问（其实我当初也对这个状态的定义感到困惑，但在经过大量的实践后我发现这确实是最好的状态定义方法。事实上，我认为状态的定义在某种程度上确实是一种玄学，如果实在没有办法搞懂为什么这么定义的话就直接理解就行，不需要刨根问底。但我依然准备了几点理由）： 为什么定义阶段为 X[0:i] 和 Y[0:j]？ 原因 1：递归思想的启发 公共子序列的性质决定了大问题可以由小问题递归构建： * 假如我们已经知道了 X[0:i-1] 和 Y[0:j-1] 的最长公共子序列，那么我们可以根据 X[i-1] 和 Y[j-1] 的关系推导出 X[0:i] 和 Y[0:j] 的结果。 * 这表明，将大问题划分为较短的前缀问题是自然的。 原因 2：易于表示动态变化 通过前缀的定义，我们可以在任意时刻只关注子字符串 X[0:i] 和 Y[0:j]： * 当前阶段的解法只需要依赖之前的阶段，而不用考虑整个字符串。 * 动态规划的核心是利用阶段间的状态关系来避免重复计算，通过子问题的答案逐步推导出最终答案。 为什么选择子字符串的前缀？ 原因 1：动态规划的自底向上特性 动态规划要求我们从最小的问题开始求解，而前缀是自然的分解方式： * 对于 X[0:i] 和 Y[0:j]，最小的子问题是 i=0 或 j=0，即两个字符串中任意一个为空时，公共子序列长度为 0。 * 从空字符串到完整字符串的逐步扩展非常符合动态规划的思路。 原因 2：控制问题规模 通过逐步扩展前缀，我们可以在二维表格 dp[i][j] 中用已知的小问题结果构造更大的问题： * 如果我们随机考察 X 和 Y 的任意部分（如子序列中间），那么问题之间的关联关系会变得复杂，动态规划就难以实施。 * 而利用前缀作为阶段，每次只需要看最后一个字符的关系，并结合已有的子问题结果，问题变得简单而清晰。 接下来就到了第二步，确定状态转移方程式。通过考察字符串 X 和 Y 的最后一个字符，我们先把所有的可能性的找出来： 【情况一】当 X[i-1] == Y[j-1] 时（即两个字符串的最后一个字符相同）： 这意味着这两个字符可以成为最长公共子序列的一部分。因此，我们可以将这两个字符加入到之前计算的最长公共子序列中。因此可得 dpi,j=dpi−1,j−1dp_{i, j} = dp_{i-1, j-1}dpi,j =dpi−1,j−1 。 这里的 dp[i][j] 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。 dp[i-1][j-1] 表示在不考虑这两个最后字符的情况下，字符串 X 的前 i-1 个字符和字符串 Y 的前 j-1 个字符的最长公共子序列的长度。由于 X[i-1] 和 Y[j-1] 相同，我们将这两个字符加入到子序列中，因此长度增加了 1。 【情况二】当 X[i-1] != Y[j-1] 时（即两个字符串的最后一个字符不同）： 由于最后一个字符不同，我们无法同时将它们加入到公共子序列中。因此，我们需要决定是排除 X 的最后一个字符还是排除 Y 的最后一个字符，以找到更长的公共子序列。因此可得 dpi,j=max⁡(dpi−1,j,dpi,j−1)dp_{i, j} = \max(dp_{i-1, j}, dp_{i, j-1})dpi,j =max(dpi−1,j ,dpi,j−1 )。 dp[i-1][j] 表示排除 X 的最后一个字符后，字符串 X 的前 i-1 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。 dp[i][j-1] 表示排除 Y 的最后一个字符后，字符串 X 的前 i 个字符和字符串 Y 的前 j-1 个字符的最长公共子序列的长度。 我们取这两者中的较大值，确保选择了能够形成最长子序列的路径。 最后就是处理边界了和初始条件了，当其中一个字符串为空时（即 i==0 || j == 0），则公共子序列的长度为零。 最后，本题的 C++ 代码如下： E.G. 05 - 最长上升子序列 题目描述 给定一个长度为 NNN 的序列 S=a1,a2,⋯ ,anS = a_1, a_2, \cdots, a_nS=a1 ,a2 ,⋯,an ，请求求出这个序列的最长上升子序列。子序列不要求连续，但每一个元素出现的顺序需要与原序列中元素出现的顺序对应。 解题思路 按照相同的方法，我们先尝试把这个大问题分解成小问题。通过观察题目，注意到长度为 NNN 的序列的最长上升子序列一定是由一个更短的序列添加一个元素得来的，因此我们只需要计算将这个元素拼接到哪一个更短的序列中可以得到一个更长的上升子序列即可。因此可以定义 dpidp_idpi 为以第 iii 个元素为结尾的最长上升子序列的长度。 接下来是状态转移方程，根据上述的定义可以得到 dpi=max⁡Sj<Si,1≤j<i(dpj+1)dp_i = \max_{S_j < S_i, 1\le j < i}(dp_j + 1)dpi =maxSj <Si ,1≤j<i (dpj +1)。该如何理解呢？ 为了计算 dpidp_idpi ，我们需要分析以 SiS_iSi 为结尾时，最长上升子序列的可能性。对于每一个 SiS_iSi ，我们需要考虑之前所有的元素（即 S1S_1S1 到 Si−1S_{i-1}Si−1 ），是否可以成为 SiS_iSi 的前驱： * 如果 Sj<SiS_j < S_iSj <Si 且 j<ij < ij<i，说明 SiS_iSi 可以接在以 SjS_jSj 为结尾的最长上升子序列后面，构成一个更大的上升子序列。 * 那么这个更大的上升子序列的长度就可以表示为： dpi=max⁡(dpj+1)，对于所有j满足Sj<Si且j<idp_i = \max(dp_j + 1)，对于所有 j 满足 S_j < S_i 且 j < i dpi =max(dpj +1)，对于所有j满足Sj <Si 且j<i 以上就是状态转移方程的推导。因此在设计状态转移方程的时候，了解并分类讨论每一个“可能性”是至关重要的。 最后就是初始值了，我们需要一开始把 dp 数组中的所有元素都设置为 111，因为无论如何，数组中的任意一个元素都可以自成一个长度为 111 的上升子序列。 最后 C++ 代码如下： E.G. 06 - 钞票问题 题目描述 Macw 在一个神奇的国家，这个国家的货币只有 111 元，555 元， 111111 元三种面值的钞票，现在 Macw 想购买一个价值为 nnn 元的物品，请问 Macw 最少需要准备多少张钞票刚好能够凑够 nnn 元？ 解题思路 这道题也是动态规划问题的经典题型。依旧按照上述动态规划“三步曲”，我们先来将问题分解出来，既然我们不知道凑够 nnn 元最少需要的钞票数量，但是与【E.g. 03 - 数楼梯】类似，我们可以将问题分解为凑够 n−1,n−2,n−3,⋯ ,1n-1, n-2, n-3, \cdots, 1n−1,n−2,n−3,⋯,1 元钱所需要的钞票数量，并从小到大来解决。因此我们定义状态 dpidp_idpi 为凑够 iii 元钱所需要的最少钞票数量。 接下来找状态转移方程，依旧寻找可能的可能性。假设我们现在有 iii 元钱，我不知道凑够 iii 元钱所需要的钞票，但是我们知道： 1. 我只需要在 i−1i- 1i−1 元钱所需要的最少面额下增加一张面额为 111 的钱即可凑到 iii 元钱。 2. 我只需要在 i−5i- 5i−5 元钱所需要的最少面额下增加一张面额为 555 的钱即可凑到 iii 元钱。 3. 我只需要在 i−11i- 11i−11 元钱所需要的最少面额下增加一张面额为 111111 的钱即可凑到 iii 元钱。 以上就是三种选择性，我们只需要找到所需钞票数量最少的那一个组合就好了，即： dpi=max⁡(dpi−1+1,dpi−5+1,dpi−11+1)\large{dp_i = \max(dp_{i-1} + 1, dp_{i-5} + 1, dp_{i-11} + 1)} dpi =max(dpi−1 +1,dpi−5 +1,dpi−11 +1) 化简可得： dpi=max⁡(dpi−1,dpi−5,dpi−11)+1\large{dp_i = \max(dp_{i-1}, dp_{i-5}, dp_{i-11}) + 1} dpi =max(dpi−1 ,dpi−5 ,dpi−11 )+1 相同地，由于一开始我们不知道凑够某一个特定面值所需要的最少钞票数量，因此我们将 dpidp_idpi 全部赋值为 ∞\infty∞。而对于 dp0dp_0dp0 我们知道凑够 000 元钱不需要任何一张钞票，因此我们特设 dp0=0dp_0 = 0dp0 =0 作为我们的初始值。 最后，我们的 C++ 代码如下： 以上就是一些基础的动态规划问题的解决方案。实际上，动态规划问题是算法和程序设计竞赛中的非常一大块内容，难度较高的动态规划问题通常与其他算法一起出现，也有许多不同的优化方法降低动态规划的时间复杂度和空间复杂度（例如线段树优化 DP、斜率优化 DP、单调队列优化 DP 等）。 我对动态规划问题学习的建议 说句实话，在我刚学习动态规划问题的时候也是一知半解，一直是一个一知半解的状态，许多题目也都是凭感觉做的。但随着刷题量越来越多，我也渐渐发现部分动态规划是有迹可循的，大部分题目都可以套类似的状态的定义和状态转移方程。毕竟动态规划这个思想本身也特别难懂，还是得需要自己去多练习才可以发现规律和找到解题技巧。 总而言之，动态规划是一种强大的算法设计方法，适用于具有最优子结构、无后效性和子问题重叠性质的问题。该思想通过将复杂问题分解为子问题，记录并重用子问题的解，动态规划能够高效地求解多阶段决策问题。理解并掌握动态规划的本质，对于解决复杂问题和优化算法性能具有重要意义。 REFERENCES GeeksforGeeks. (n.d.). Dynamic Programming. Retrieved from https://www.geeksforgeeks.org/dynamic-programming/ Gupta, R. (2023). Mastering Dynamic Programming: A Step-by-Step Guide. Medium. Retrieved from https://medium.com/@connectto.guptaraghav/mastering-dynamic-programming-a-step-by-step-guide-741d9d7d142 Stanford University. (n.d.). Dynamic Programming. Retrieved from https://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf Stanford University. (2013). Dynamic Programming Lecture Notes (CS161). Retrieved from https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/16/Small16.pdf Bellman, R. (1966). Dynamic Programming. Science, 153(3731), 34–37. doi:10.1126/science.153.3731.34

32场信奥讲座#2 主讲人：黄敬文

🚀 #32场信奥讲座# 第2期 | 主讲人：黄敬文 🌟 编程界的心理压力？我们帮你轻松应对！ 🎉 本周五，加入黄敬文老师的编程情绪管理与心理健康必修课！ 👨‍🏫 黄敬文老师，将带你探索竞赛背后的情绪管理秘诀，让你在编程的世界里游刃有余！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌈 主讲人风采 * NOI全国银牌得主，编程界的佼佼者； * 冬令营金牌，青少年编程的领军人物； ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点此了解32场硬核信奥讲座>>

【游戏】四字词语接龙

大家好，我是【编程爱好者】。 接下来我们来玩个游戏： 每人说一个四字词语，要求第一个字和前一个词语最后一个字相同。（必须遵守） 注：我的这个游戏参考了【一株寒冰射手-lcepea】的论坛【游戏】故事接龙。 广告： 邀请大家参加C➕➖✖➗团队！审核必过！ 点我加入C➕➖✖➗团队

互动#9｜2024结果清单

🚀本周互动：2024结果清单 😎2024 年的进度条即将拉满，这一年里你收获了怎样的结果清单呢？ 🎤成果剖析区 列出清单：列出清单：无论是友情、掌握的学识或技能、习惯养成、看过的书……皆可一一罗列。 🎁 话题奖励 抽取三人获得ACGO随机周边 ⏰ 话题时间 截止时间 12月29日 获奖公布12月30日 快来晒出你的 2024 成果清单，与大家一同见证成长与收获！😎

ACGO 巅峰赛#15 - 题目解析

ACGO 巅峰赛#15 - 题目解析 > 间隔四个月再战 ACGO Rated，鉴于最近学业繁忙，比赛打得都不是很频繁。虽然这次没有 AK 排位赛（我可以说是因为周末太忙，没有充足的时间思考题目…（好吧，其实也许是因为我把 T5 给想复杂了））。 > > 本文依旧提供每道题的完整解析（因为我在赛后把题目做出来了）。 T1 - 高塔 题目链接跳转：点击跳转 > 插一句题外话，这道题的题目编号挺有趣的。 没有什么特别难的点，循环读入每一个数字，读入后跟第一个输入的数字比较大小，如果读入的数字比第一个读入的数字要大（即 ai>a1a_i > a_1ai >a1 ），直接输出 iii 并结束主程序即可。 本题的 C++ 代码如下： 本题的 Python 代码如下： T2 - 营养均衡 题目链接跳转：点击跳转 也是一道入门题目，没有什么比较难的地方，重点是把题目读清楚了。 我们设置一个数组 arr\tt{arr}arr，其中 arri\tt{arr_i}arri 表示种营养元素还需要的摄入量。那么，如果 arri≤0\tt{arr_i} \le 0arri ≤0 的话，就表示该种营养元素的摄入量已经达到了 “健康饮食” 的所需标准了。按照题意模拟一下即可，最后遍历一整个数组判断是否有无法满足的元素。换句话说，只要有任意的 ∀i\forall i∀i，满足 arri>0\tt{arr_i} > 0arri >0 就需要输出 No。 本题的 C++ 代码如下： 本题的 Python 代码如下： T3 - ^_^ 还是 :-( 题目链接跳转：点击跳转 > 一道简单的思维题目，难度定在【普及-】还算是合理的。不过 USACO 的 Bronze 组别特别喜欢考这种类似的思维题目。 普通算法 考虑采用贪心的思路，先把序列按照从大到小的原则排序。暴力枚举一个节点 iii，判断是否有可能满足选择前 iii 个数字 −1-1−1，剩下的数字都至少 +1+1+1 的情况下所有的数字都大于零。 那么该如何快速的判断是否所有的数字都大于零呢？首先可以肯定的是，后 n−in - in−i 个数字一定是大于零的，因为这些数字只会增加不会减少。所以我们把重点放在前 iii 个数字上面。由于数组已经是有序的，因此如果第 iii 个数字是大于 111 的，那么前 iii 个数字在减去 111 之后也一定是正整数。 由于使用了排序算法，本算法的单次查询时间复杂度在 O(Nlog⁡2N)O(N \log_2 N)O(Nlog2 N) 级别，总时间复杂度为 O(N2log⁡2N)O(N^2 \log_2 N)O(N2log2 N)，可以在 1s\tt{1s}1s 内通过所有的测试点。 本题的 C++ 代码如下： 本题的 Python 代码如下： 二分答案优化 注意到答案是单调的，因此可以使用二分答案的算法来适当优化。虽然效果微乎其微，但在整体时间运行上表现良好。 优化后的 C++ 代码如下： 优化后的 Python 算法如下： T4 - AZUSA的计划 题目链接跳转：点击跳转 这道题的难度也不是很高，稍微思考一下即可。 任何事件时间 ttt 对 (a+b)(a + b)(a+b) 取模后，事件可以映射到一个固定的周期内。这样，问题就转化为一个固定长度的区间检查问题。 因此，在读入数字后，将所有的数字对 (a+b)(a + b)(a+b) 取模并排序，如果数字分布（序列的最大值和最小值的差值天数）在 aaa 范围内即可满足将所有的日程安排在休息日当中。但需要注意的是，两个日期的差值天数不能单纯地使用数字相减的方法求得。以正常 777 天为一周作为范例，周一和周日的日期差值为 111 天，而不是 7−1=67 - 1 = 67−1=6 天。这也是本题最难的部分。 如果做过 区间 DP 的用户应该能非常快速地想到如果数据是一个 “环状” 的情况下该如何解决问题（参考题目：石子合并（标准版））。我们可以使用 “剖环成链” 的方法，将环中的元素复制一遍并将每个数字增加 (a+b)(a + b)(a+b)，拼接在原数组的末尾，这样一个长度为 nnn 的环就被扩展为一个长度为 2n2n2n 的线性数组。 最后只需要遍历这个数组内所有长度为 nnn 的区间 [i,n+i−1][i, n + i - 1][i,n+i−1]，判断是否有任意一个区间的最大值和最小值的差在 aaa 以内即可判断是否可以讲所有的日程安排都分不在休息日中。 本题的时间复杂度为 O(Nlog⁡2N)O(N \log_2 N)O(Nlog2 N)。 本题的 C++ 代码如下： 本题的 Python 代码如下： T5 - 前缀和问题 题目链接跳转：点击跳转 > 我个人认为这道题比最后一道题要难，也许是因为这类题目做的比较少的原因，看到题目后不知道从哪下手。 使用分类讨论的方法，设置一个阈值 SSS，考虑暴力枚举所有 b>Sb > Sb>S 的情况，并离线优化 b≤Sb \le Sb≤S 的情况。将 SSS 设置为 N\sqrt{N}N ，则有： 1. 对于大步长 b>Sb > Sb>S，任意一次查询只需要最多遍历 550550550（即 N\sqrt{N}N ）次就可以算出答案，因此暴力枚举这部分。 2. 对于小步长 b≤Sb \le Sb≤S，按 bbb 分组批量离线查询。 对于大步长部分，每一次查询的时间复杂度为 O(N)O(\sqrt{N})O(N )，在最坏情况下总时间复杂度为 O(N×N)O(N \times \sqrt{N})O(N×N )。对于小步长的部分，每一次查询的时间复杂度约为 O(n)O(n)O(n)，在最坏情况下的时间复杂度为 O(N×N)O(N\times \sqrt{N})O(N×N )，因此本题在最坏情况下的渐进时间复杂度为： O(N×N)\large{O(N \times \sqrt{N})} O(N×N ) 最后，本题的 C++ 代码如下： 本题的 Python 代码如下（不保证可以通过所有的测试点）： T6 - 划分区间 题目链接跳转：点击跳转 一道线段树优化动态规划的题目，难度趋近于 CSP 提高组的题目和 USACO 铂金组的中等题。一眼可以看出题目是一个典型的动态规划问题，但奈何数据量太大了，O(N2)O(N^2)O(N2) 的复杂度肯定会 TLE。但无论如何都是 “车到山前必有路”，看到数据范围不用怕，先打一个暴力的动态规划再优化。 按照一位 OI 大神的说法：“所有的动态规划优化都是在基础的代码上等量代换”。 与打家劫舍等线性动态规划类似，对于本题而言，设状态的定义为 dpidp_idpi 表示对 [1,i][1, i][1,i] 这个序列划分后可得到的最大贡献。通过暴力遍历 j,(1≤j<i)j, (1 \le j < i)j,(1≤j<i)，表示将 (j,i](j, i](j,i] 归位一组。另设 A(j,i)A(j, i)A(j,i) 为区间 (j,i](j, i](j,i] 的贡献值。根据以上信息可以得到状态转移方程： dpi=max⁡0≤j<i(dpj+A(j,i))\large{dp_i = \max_{0 \le j<i}{(dp_j + A(j, i))}} dpi =0≤j<imax (dpj +A(j,i)) 接下来就是关于 A(j,i)A(j, i)A(j,i) 的计算了。设前缀和数组 SiS_iSi 表示从区间 [1,i][1, i][1,i] 的和，那么 (j,i](j, i](j,i] 区间的和可以被表示为 S[i]−S[j]S[i] - S[j]S[i]−S[j]。根据不同的 S[i]−S[j]S[i] - S[j]S[i]−S[j]，则有以下三种情况： 1. 当 S[i]−S[j]>0S[i] - S[j] > 0S[i]−S[j]>0 时，证明该区间的和是正数，贡献为 i−ji - ji−j。 2. 当 S[i]−S[j]=0S[i] - S[j] = 0S[i]−S[j]=0 时，该区间的和为零，贡献为 000。 3. 当 S[i]−S[j]<0S[i] - S[j] < 0S[i]−S[j]<0 时，证明该区间的和是负数，贡献为 −(i−j)=j−i- (i - j) = j - i−(i−j)=j−i。 综上所述，可以写出一个暴力版本的动态规划代码： 接下来考虑优化这个动态规划，注意到每一次寻找 max\tt{max}max 都非常耗时，每一次都需要遍历一遍才能求出最大值。有没有一种方法可以快速求出某一个区间的最大值呢？答案就是线段树。线段树是一个非常好的快速求解区间最值问题的数据结构。 > 更多有关区间最值问题的学习请参考：[# 浅入线段树与区间最值问题](# 浅入线段树与区间最值问题) 综上，我们可以通过构建线段树来快速求得答案。简化三种情况可得： 因此我们构造三棵线段树，分别来维护这三个区间： 1. max⁡0≤j<idpj\max_{0\le j < i} dp_jmax0≤j<i dpj 2. max⁡0≤j<i(dpj−j)\max_{0\le j < i} (dp_j - j)max0≤j<i (dpj −j) 3. max⁡0≤j<i(dpj+j)\max_{0\le j < i} (dp_j + j)max0≤j<i (dpj +j) 然而我们的线段树不能仅仅维护这个区间，因为这三个的最大值还被 A(j,i)A(j, i)A(j,i) 的三种状态所限制着，因此，我们需要找的是满足 Si−SjS_i - S_jSi −Sj 在特定条件下的最大值。这样就出现了另一个严重的问题，SiS_iSi 的值可能非常的大，因此我们需要对前缀和数组离散化一下（坐标压缩：类似于权值线段树的写法）才可以防止内存超限。 这样子对于每次寻找最大值，都可以在 O(log⁡2N)O(\log_2N)O(log2 N) 的情况下找到。本算法的总时间复杂度也控制在了 O(N×log⁡2N)O(N \times \log_2N)O(N×log2 N) 级别。 本题的 C++ 代码如下： 本题的 Python 代码如下（由于 Python 常数过大，因此没有办法通过这道题所有的测试点，但是代码的正确性没有问题）： 当然也可以用树状数组来写，速度可能会更快一点： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 更新日志： Dec. 3, 2024：修改了错别字和时间复杂度的解析错误；优化了代码的变量名；T6 增加了树状数组解法。

巅峰赛 #16 全题解！！！

T4的题解有误，现已重写. 我们帅童玩家也是站起来了好吧（澄清一下，榜三不是我小号） 报一下个入难度：红 橙 橙/黄 黑蓝 绿 绿. T1 用 map 记录每个数字出现的次数，然后按题意判断. T2 每次取出第一个字符放到最后一个，判断是不是回文即可. string没有pop_front有点烦…… T3 我们可以用一种新型的记录方法，也可以记录到所有的子串. 例如 abcadcbabcadcbabcadcb： 遍历到第 111 个字符，l=1,r=1l=1,r=1l=1,r=1：将 aaa 加入字符串，并增加 111 个子串： aaa. 遍历到第 222 个字符，l=1,r=2l=1,r=2l=1,r=2：将 bbb 加入字符串，并增加 222 个子串：b,abb,abb,ab. 遍历到第 333 个字符，l=1,r=3l=1,r=3l=1,r=3：将 ccc 加入字符串，并增加 333 个子串：c,bc,abcc,bc,abcc,bc,abc. 遍历到第 444 个字符，r=4r=4r=4：由于已经出现过了 aaa，所以第 111 个字符就不能要了，令 l=2l=2l=2. 此时可新增 333 个子串：a,ca,bcaa,ca,bcaa,ca,bca. 遍历到第 555 个字符，l=2,r=5l=2,r=5l=2,r=5：将 ddd 加入字符串，并增加 444 个子串：d,ad,cad,bcadd,ad,cad,bcadd,ad,cad,bcad. 遍历到第 666 个字符，r=6r=6r=6：由于已经出现过了 ccc，所以第 2,32,32,3 个字符就不能要了，令 l=4l=4l=4. 此时可新增 333 个子串：c,dc,adcc,dc,adcc,dc,adc . 遍历到第 777 个字符，l=4,r=7l=4,r=7l=4,r=7：将 bbb 加入字符串，并增加 444 个子串：b,cb,dcb,adcbb,cb,dcb,adcbb,cb,dcb,adcb. ∴\therefore∴ 共有 202020 个不含有重复字符的子串. 翻译成代码如下： T4 为了方便表示，我将以 xxx 开头，yyy 结尾的子串数量称为 {x,y}\{x,y\}{x,y}，数组 aaa 中大于数 xxx 的个数称为 a.LB(x)a.LB(x)a.LB(x)，即lower bound. 个人认为本次巅峰赛最难的一题！ 认真读题，可发现题目实际让我们找的是如下的代码： 首先，我想到两个块合并只需要把左右两个块的 {x,y}\{x,y\}{x,y} 相加再加上第一个块内 xxx 的数量乘第二个块内 yyy 的数量即可. 于是我轻松地打了个线段树代码： 然后内存爆了. 后来我尝试用分块做，TLE了. 最后我使劲想想想，终于想出来了： 我们不需要维护整个线段树，真正需要维护的只是 676676676 个结果. 我们可以换个角度考虑，如aababbaababbaababb，将第 555 个字符改成 aaa： 先统计负贡献： 1. 在前四个字符与第五个字符的关系中，{a,b}−=3\{a,b\}-=3{a,b}−=3，{b,b}−=1\{b,b\}-=1{b,b}−=1. 2. 在第六个字符与第五个字符的关系中，{b,b}−=1\{b,b\}-=1{b,b}−=1. 再统计正贡献： 1. 在前四个字符与第五个字符的关系中，{a,a}+=3\{a,a\}+=3{a,a}+=3，{b,a}+=1\{b,a\}+=1{b,a}+=1. 2. 在第六个字符与第五个字符的关系中，{a,b}+=1\{a,b\}+=1{a,b}+=1. 我们发现，如果把这个字符串拆开，分为 aaa 字符串与 bbb 字符串： 那么贡献就与 555 在 aaa 字符串与 bbb 字符串的相对位置，即 ∑i∈ba.LB(i)\sum\limits_{i\in b} a.LB(i)i∈b∑ a.LB(i) 有关. 其它的字符串也有这个性质，自行验证. 可以亮代码了……吗？ 等等，还有两件事没讲清楚. 1.如何快速求 a.LB(x)a.LB(x)a.LB(x): 如果按正常的数组处理的话，修改时间复杂度就得退化至 O(n)O(n)O(n)； 而 setsetset 只会给你返回迭代器，转换成数值又得花费 O(n)O(n)O(n) 的时间. 怎么办呢？ 机智的我想到了用树状数组模拟数组！只要每次加入元素在该元素的下标增加 111，删除元素在该元素的下标增加 −1-1−1，那么查询某个下标的结果就是 a.LB(x)a.LB(x)a.LB(x)！ 使用这种方法也可以以 O(nlog⁡n)O(n\log n)O(nlogn) 的时间复杂度求得一个数组的逆序对. 2.初始化时间复杂度问题： 确实，通过上面的办法可以让修改变为 O(log⁡n)O(\log n)O(logn)，查询变为 O(1)O(1)O(1)，但是要初始化. 而如果按照上面的代码初始化，时间复杂度是 O(n2)O(n^2)O(n2)！ 没关系，稍微推导一下，就可以推出 {x,y}=∑i∈yx.LB(i)+(i∈x)\{x,y\}=\sum\limits_{i\in y} x.LB(i)+(i\in x){x,y}=i∈y∑ x.LB(i)+(i∈x). 该题代码如下： T5 模板题，参考区间根号题. 我们发现最多只会运算 350350350 次，所以 O(350n)O(350n)O(350n) 是完全可以的. 具体做法：维护一个线段树，记录区间内 111 的个数，修改时如果发现有一个子树内的元素都为 111 就不搜了；查询直接按普通线段树做. 由于这个算法是自顶而下的，所以就不能用重口味线段树了. T6 一开始没读题就0帧起手，写了个bfs找环+Floyd算法. 直到我看到了：不会重复经过同一个车站. 天塌了70+行的代码白写了 但是这个提示也带给我了一个好消息：消耗的时间最多也不会超过 151515. 这就让我想到了最短Hamilton路径的解法：状压DP. 巧了，在这题也同样适用！ 我们弄个dp，dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示从 iii 出发，第 kkk 个状态，最后一个点为 jjj 是否可能实现. 然后枚举每个时间和所有点，判断当时间为 iii，选取 jjj 点作为车站是否可行.