@AC君 在编程这条充满未知与机遇的道路上，刷题宛如一座座待攀的高峰，既考验着我们的知识储备，又磨砺着我们的意志与智慧。每一次的刷题经历，都是一次自我挑战与突破的旅程，让我们在代码的世界里不断成长，遇见更好的自己。 一、初探刷题：困惑与迷茫交织 初入编程刷题之门，我怀揣着既兴奋又忐忑的心情。那些题目，表面看似简单，实则暗藏玄机，常常让我陷入深深的困惑与迷茫之中。 记得初次遇到字符串处理的题目时，题目要求将字符串中的所有字母进行反转，而其他字符的位置保持不变。初看之下，我满心以为这不过是小菜一碟，不就是遍历字符串，然后交换字符位置嘛。然而，真正动手编码时，我才意识到事情远非我想象的那么简单。 我尝试运用双指针法来解决这个问题，一个指针从字符串的起始端出发，另一个指针则从末端向内推进，逐个交换字母的位置。但在实际操作过程中，我却遭遇了诸多难题。比如，当字符串中掺杂着非字母字符时，如何巧妙地跳过它们而不打乱整体的逻辑；又如，当字符串的长度为奇数时，如何妥善处理中间的那个字符，等等。这些问题犹如一座座小山，横亘在我前进的道路上，让我倍感困惑与迷茫，一度想要放弃。 代码示例：字符串反转 cpp复制 #include <iostream> #include <string> using namespace std; void reverseLetters(string& str) { int left = 0, right = str.size() - 1; while (left < right) { if (!isalpha(str[left])) { left++; } else if (!isalpha(str[right])) { right--; } else { swap(str[left], str[right]); left++; right--; } } } int main() { string str = "a-bC-dEf-ghIj"; reverseLetters(str); cout << str << endl; // 输出: "j-Ih-gfE-dCba" return 0; } 二、探索解法：在尝试中寻求突破 面对这些棘手的难题，我没有轻言放弃，而是开启了积极的探索之旅。我广泛查阅各类资料，深入学习不同的算法思想与编程技巧，努力寻找攻克难关的钥匙。 在解决字符串反转问题的过程中，我首先尝试了一种较为简单粗暴的方法——使用额外的空间来存储字母字符，然后再将它们逐一放回原字符串的相应位置。虽然这种方法勉强能够解决问题，但其较高的空间复杂度显然不符合优化的要求。于是，我继续在心中构思更优的解法。 经过反复的思考与无数次的尝试，我终于灵光一闪，找到了一种巧妙的解决方案。我依然采用双指针法，但在遍历字符串的过程中，我会先仔细判断当前字符是否为字母。若是字母，便将其与另一个指针所指向的字母进行交换；若非字母，则果断将指针向前移动一位。凭借这种巧妙的处理方式，我成功地攻克了字符串反转的难题，内心的成就感油然而生，仿佛在黑暗中看到了曙光。 三、总结经验：从困境中汲取养分 每一次的刷题挑战，都是一次难得的学习契机。在接连攻克一个个难题之后，我开始静下心来总结其中的经验与教训，努力探寻其中的规律与方法。 我逐渐领悟到，编程刷题绝非单纯的对知识的检验，更是对思维能力的全方位锻炼。面对复杂繁琐的题目，我们首先要学会冷静地分析问题，将一个大问题巧妙地拆解成若干个小问题，然后逐一击破。同时，我们还要善于灵活运用已掌握的知识与经验，巧妙地调用不同的算法与数据结构，为找到最契合的解决方案而努力。 此外，我还深刻认识到良好编程习惯的重要性。清晰明了的代码注释能够帮助我们更好地理解代码的逻辑脉络；规范严谨的变量命名则能让代码更具可读性与可维护性。在刷题的漫长过程中，我逐渐养成了这些良好的编程习惯，它们不仅显著提升了我的编程水平，更让我在解决实际问题时能够更加得心应手，游刃有余。 四、分享心得：携手他人共成长 在编程刷题的漫漫征途中，我深知单枪匹马的力量是有限的。因此，我十分注重与他人的交流与分享。通过积极参与线上线下的各类编程社区活动，我结识了一群志同道合的朋友。我们一起热烈地讨论各种题目，毫无保留地分享各自的解题思路，互相学习，共同进步。 有一次，在一个编程论坛上，我遇到了一道颇具难度的动态规划题目。那道题目的状态转移方程复杂得令人望而却步，我冥思苦想许久，却始终找不到合适的切入点。无奈之下，我在论坛上发帖求助。没过多久，就有一位热心的网友给予了我回复。他不仅耐心地为我详细讲解了这道题目的解题思路，还慷慨地分享了他的代码实现。通过这次深入的交流，我不仅顺利解决了这道难题，更学到了一种全新的思考问题的方法，拓宽了思维的边界。 我也积极地将自己在刷题过程中的点滴心得与经验分享给他人。每当我取得一些小小的突破时，我都会迫不及待地在社区里发帖分享。看到自己的帖子能够为那些同样在困惑中挣扎的朋友们带来帮助，我的内心充满了无尽的喜悦与满足。这种分享与交流的过程，不仅让我结交了众多志同道合的朋友，更让我在编程的道路上走得更加坚定与自信，步伐愈发稳健。 代码示例：动态规划（背包问题） #include <iostream> #include <vector> using namespace std; int knapsack(int W, int weights[], int values[], int n) { vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= W; j++) { if (j < weights[i - 1]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]); } } } return dp[n][W]; } int main() { int W = 50; int weights[] = {10, 20, 30}; int values[] = {60, 100, 120}; int n = sizeof(values) / sizeof(values[0]); cout << "Maximum value in knapsack = " << knapsack(W, weights, values, n) << endl; return 0; } 五、结语：在刷题中遇见更优秀的自己 编程刷题宛如一场充满挑战与机遇的奇妙旅程。在这条布满荆棘的道路上，我们会遭遇形形色色的难题，经历无数次的困惑与挫折。但正是这些看似艰难的挑战，促使我们不断地成长与蜕变，在困境中突破自我，遇见更优秀的自己。 回首过往的刷题岁月，我感慨万千。那些曾经让我头疼不已的难题，如今都化作了我宝贵的记忆与财富。它们让我深刻地认识到，只要我们坚持不懈，勇于探索，就一定能够在编程的浩瀚世界里创造出属于自己的精彩篇章。 让我们携手共进，在编程刷题的道路上继续奋勇前行，勇敢地迎接每一个挑战，用心地解决每一个问题。相信在不久的将来，我们都能成为更加出色的程序员，用一行行精妙的代码书写出更加美好的未来，开启属于我们的编程新纪元。2025.1.14 我是小码王双井校区的学生以上内容由我独创，如有雷同，纯属巧合。

最近有一件事使我的班主任十分苦恼，许多同学总会在课上交头接耳，为了避免这种情况，我们敬爱的班主任在每周排座位时就会将交头接耳的同学分开。 可是交头接耳的同学人数众多，为了将他们全部分开，班主任每周都要花大量时间排座位。 为了帮助我们可怜的班主任，我决定完成一个程序，帮助班主任排座位 很快我就完成了 （我们班一共31人，学号为1-32，没有19号，座位5X6，座位从左往右第二列有7个人） 虽然排好的座位确实分开了交头接耳的学生，但是我写完代码运行的时候又发现一个很严重的问题，太有序了！ 你运行一些代码就知道我在说什么了 由于是1-32顺序遍历学号并尝试填充，所以只要当前遍历到的学生不是交头接耳的学生，那么座位就是有序的！ 于是我打乱了遍历学号的顺序，代码成了这样 我终于完成了排座位的程序

前言 动态规划(Dynamic Programming)(Dynamic\,Programming)(DynamicProgramming)，简称DPDPDP。仔细想一下，动态规划这个东西不走回头路，有点像贪心和递推的结合体，因此可以成为CSP−JCSP-JCSP−J的考纲范围内的算法知识点。如何学好动态规划？首先就要吃透一道很基本的题目：数字金字塔。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正文 要能够学好动态规划，尤其是到了后面背包等问题，首先要知道状态转移方程式的由来。本文介绍四种数字金字塔的解题思路和方法，望对大家动归的学习路上有帮助。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先，要了解一点：一道题目会有不同的思路和思考方向，这些不同的思路和方向就会带来不同的解题过程和代码。数字金字塔是个很好的例子，它可以从上往下顺着题目要求推出结果，也可以从下往上逆着它的要求来得到正解。 我们先考虑顺推，如法一和法二所示。 方法一：顺推法 在开始之前，先确定一点：设dpdpdp数组，其中dp[i][j]dp[i][j]dp[i][j]表示从顶端走到节点(i,j)(i,j)(i,j)得到的最大的和，并且强制以节点(i,j)(i,j)(i,j)作为终点。 根据题意，节点(i,j)(i,j)(i,j)可以从(i−1,j−1)(i-1,j-1)(i−1,j−1)和(i−1,j)(i-1,j)(i−1,j)走过来。用到贪心的思想，为了得到最大值，我们必须取max⁡(dp[i−1][j−1],dp[i−1][j])\max(dp[i-1][j-1],dp[i-1][j])max(dp[i−1][j−1],dp[i−1][j])，再加上走到了节点(i,j)(i,j)(i,j)时新获得的数据a[i][j]a[i][j]a[i][j]，可以得出转移方程式： dp[i][j]=max⁡(dp[i−1][j−1],dp[i−1][j])+a[i][j]dp[i][j]=\max(dp[i-1][j-1],dp[i-1][j])+a[i][j] dp[i][j]=max(dp[i−1][j−1],dp[i−1][j])+a[i][j] 如果把a[i][j]a[i][j]a[i][j]忽略，改成变量kkk，则应当在双重循环中读入kkk，然后推出dp[i][j]dp[i][j]dp[i][j]，既节省了空间又节省了读入a[1001][1001]a[1001][1001]a[1001][1001]二维数组的时间。 因此，可以写出下列代码： 不过，如果所谓的行数nnn过于大，那么毋庸置疑的是，开二维数组必然会爆空间，你就喜提一个MLE\blue{MLE}MLE了。这时候，就要用一维数组上场替换二维数组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 方法二：一维顺推 如果所谓的行数nnn过大超过大约300030003000的话，由于状态转移方程式中只涉及到dp[i−1][j]dp[i-1][j]dp[i−1][j]和dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]两者，可以考虑只开一维数组（当然也可以开滚动数组），代替二维。 状态转移方程式变为了： dp[j]=max⁡(dp[j−1],dp[j])+kdp[j]=\max(dp[j-1],dp[j])+k dp[j]=max(dp[j−1],dp[j])+k 唯一的麻烦就是如果从左往右存储会发生当m=j+1m=j+1m=j+1时，dp[j]dp[j]dp[j]发生改变后dp[m]=max(dp[m−1],dp[m])+kdp[m]=max(dp[m-1],dp[m])+kdp[m]=max(dp[m−1],dp[m])+k这里dp[m−1]dp[m-1]dp[m−1]已经是更新过后的值了，不符合题意。因此，必须从右往左存储。 这种用一维数组来代替二维数组的方法在背包问题的学习中也很常见，01背包开二维数组开不下时可以考虑开一维数组代替，其原因和上述原因大同小异。而且开了一维数组后完全背包问题会得到简化。如果加上多重背包，那么混合背包使用一维数组确实会更方便。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 每种方法都有它的优点和缺点，而两种不同的方法根据它们优缺点不同，可能会适用于不同场景。说完了顺推，我们再来聊聊逆推，的确逆推有时候会比顺推更有用。 方法三：逆推法 顺推法有优点也有缺点。优点是方法简单容易想到，而且可以优化空间省去数组a[1001][1001]a[1001][1001]a[1001][1001]。 但是缺点是它有多个终点，直接输出dp[n][n]dp[n][n]dp[n][n]明显不是最大值，必须遍历一遍最后一行获得最大值输出。 因此，我们可以考虑设置多个起点出发回到同一个终点。这就是逆推法主要思想。这种思想可能更适用于倒着给出的数字金字塔。 状态转移方程式只不过是把顺推的过程逆过来，还是求最大，因此max⁡\maxmax函数不变，加上的东西也不变。经过改变，状态转移方程式如下： dp[i][j]=max⁡(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j] dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j] 当然，这里需要先输入所有的a[i][j]a[i][j]a[i][j]，再进行逆推过程，不能省去a[1001][1001]a[1001][1001]a[1001][1001]这个二维数组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 方法四：一维逆推 和顺推法一样，逆推法的dp[1001][1001]dp[1001][1001]dp[1001][1001]是二维数组，当所谓的行数nnn超过大约300030003000时，空间就会不够。因此，如果题目给的是倒着的数字金字塔，我们考虑逆推法的一维状态转移方程式。 由逆推法知道，dp[i][j]=max⁡(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]，dp[i][j]dp[i][j]dp[i][j]只取决于dp[i+1][j]dp[i+1][j]dp[i+1][j]和dp[i+1][j+1]dp[i+1][j+1]dp[i+1][j+1]，因此降维操作不影响结果，则状态转移方程式变为： dp[j]=max⁡(dp[j],dp[j+1])+a[i][j]dp[j]=\max(dp[j],dp[j+1])+a[i][j] dp[j]=max(dp[j],dp[j+1])+a[i][j] 令m=j+1m=j+1m=j+1，则先推完dp[j]dp[j]dp[j]，取决于dp[j]dp[j]dp[j]和dp[m]dp[m]dp[m]，而dp[m]dp[m]dp[m]这一轮还没有推；再推dp[m]dp[m]dp[m]，涉及到dp[m]dp[m]dp[m]和dp[m+1]dp[m+1]dp[m+1]，没涉及到dp[j]dp[j]dp[j]。因此，逆推法用一维数组实现，循环不用从后往前，直接从前往后推即可。 不过，对于正着的数字金字塔，逆推用一维数组和用二维数组没什么大的区别，因为你的a[1001][1001]a[1001][1001]a[1001][1001]没办法得到简化。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 后记 每种方法都有各自的优点和缺点。具体情况还需根据题目要求来判断用什么方法。 唯一不变的是吃透数字金字塔很有必要。在后续的LIS和LCS等问题中，状态转移方程式逐渐从具体的意想到的这种变得抽象，必须像这道题一样一眼识破dpdpdp数组每一个位置代表的含义，并推断出状态转移方程式；在以后的背包问题中，一题多解的情况很常见，可以用二维数组，可以优化为一维数组，还可以通过二进制优化成普遍的背包问题。因此，学好了数字金字塔对于以后的问题都很有帮助。

这题我改了三天了还没对 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k, w; cin >> n >> k >> w; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } } 我提交之后他 WA 0ms/3.29m #2 AC 0ms/3.43m #3 AC 1ms/3.41m #4 AC 0ms/3.35m #5 AC 1ms/4.29m #6 AC 0ms/3.30m #7 AC

一、函数的基本定义 A30628.【函数】【入门】哥德巴赫猜想

方法一：顺推法 根据题意，可以得出转移方程式： dp[i][j]=max⁡(dp[i−1][j−1],dp[i−1][j])+a[i][j]dp[i][j]=\max(dp[i-1][j-1],dp[i-1][j])+a[i][j] dp[i][j]=max(dp[i−1][j−1],dp[i−1][j])+a[i][j] 如果把a[i][j]a[i][j]a[i][j]忽略，改成变量kkk，也不会有什么大碍。因此，可以写出下列代码： 方法二：一维顺推 这道题目出题人很善良，所谓的行数rrr满足要求： 1≤r≤1001\leq r\leq100 1≤r≤100 当然，如果所谓的行数rrr过大超过大约300030003000的话，由于状态转移方程式中只涉及到dp[i−1][j]dp[i-1][j]dp[i−1][j]和dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]两者，可以考虑只开一维数组（当然也可以开滚动数组），代替二维。 状态转移方程式变为了： dp[j]=max⁡(dp[j−1],dp[j])+kdp[j]=\max(dp[j-1],dp[j])+k dp[j]=max(dp[j−1],dp[j])+k 唯一的麻烦就是如果从左往右存储会发生当m=j+1m=j+1m=j+1时，dp[j]dp[j]dp[j]发生改变后dp[m]=max(dp[m−1],dp[m])+kdp[m]=max(dp[m-1],dp[m])+kdp[m]=max(dp[m−1],dp[m])+k这里dp[m−1]dp[m-1]dp[m−1]已经是更新过后的值了，不符合题意。因此，必须从右往左存储。 方法三：逆推法 顺推法有优点也有缺点。优点是方法简单容易想到，而且可以优化空间省去数组a[101][101]a[101][101]a[101][101]。 但是缺点是它有多个终点，直接输出dp[n][n]dp[n][n]dp[n][n]明显不是最大值，必须遍历一遍获得最大值输出。 因此，我们可以考虑设置多个起点出发回到同一个终点。这就是逆推法主要思想。 状态转移方程式： dp[i][j]=max⁡(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j] dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j] 当然，这里需要先输入所有的a[i][j]a[i][j]a[i][j]，再进行逆推过程，不能省去a[101][101]a[101][101]a[101][101]这个二维数组。 方法四：一维逆推 和顺推法一样，逆推法的dp[101][101]dp[101][101]dp[101][101]是二维数组，当所谓的行数rrr超过大约300030003000时，空间就会不够。因此，我们考虑逆推法的一维状态转移方程式。 由逆推法知道，dp[i][j]=max⁡(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j]dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]，dp[i][j]dp[i][j]dp[i][j]只取决于dp[i+1][j]dp[i+1][j]dp[i+1][j]和dp[i+1][j+1]dp[i+1][j+1]dp[i+1][j+1]，因此降维操作不影响结果，则状态转移方程式变为： dp[j]=max⁡(dp[j],dp[j+1])+a[i][j]dp[j]=\max(dp[j],dp[j+1])+a[i][j] dp[j]=max(dp[j],dp[j+1])+a[i][j] 令m=j+1m=j+1m=j+1，则先推完dp[j]dp[j]dp[j]，取决于dp[j]dp[j]dp[j]和dp[m]dp[m]dp[m]，而dp[m]dp[m]dp[m]这一轮还没有推；再推dp[m]dp[m]dp[m]，涉及到dp[m]dp[m]dp[m]和dp[m+1]dp[m+1]dp[m+1]，没涉及到dp[j]dp[j]dp[j]。因此，逆推法用一维数组实现，循环不用从后往前，直接从前往后推即可。

1+1=3

文件输入输出 广告： 想加入本团队的点下面 审核必过 前20个加入的都是管理员 蛟龙突击队 文件输出输出是 NOI 系列赛事常见的一种输入输出模式，题目中会写明输入及输出的文件名。 写代码时只需要正常完成后，在 main() 函数的开始加入两行语句即可。 调试时可以先把这两行注释掉，调试成功后提交前取消注释即可。 如果使用 dev-cpp 等 IDE 编写代码，也可以在源代码文件相同的目录下，创建一个输入文件名的同

#include<iostream> #include<conio.h> #include<ctime> //time(0) #include<cstdlib> //rand() #include<windows.h> using namespace std; int main(){ char maze[18][24]= {"************** ",//1 " * * ",//2 " ************ * ** * ",//3 " * **** * ",//4 " ********** * * * ",//5 " ** * * ",//6 " ** ***** ***** * ** ",//7 " * * ",//8 " * ********** ",//9 " * * * * $ ",//10 " **** * * ****** ",//11 " * * * * * * ",//12 " * ****** * ** * * * ",//13 " * * ** * * * ",//14 " ********** ** * ",//15 " * ",//16 "*** *******",//17 "***********************"};//18 //生成i角色 int x,y; srand(time(0)); //随机种子 x = rand()%18; y = rand()%23; while(maze[x][y] != ' '){ x = rand()%18; y = rand()%23; } maze[x][y] = 'i'; }

一、转义字符输出 题目 众所周知，“\”是一个转意字符，它可以转变他后面的字符的功能。 那么问题来了：如何输出一个单独的“\”？ 这个问题看似很难，实则一点都不简单。其实只需要用一个转意字符去转意一个转意字符。听着很绕，其实就是它： Code： 二、28转化 题目 其实就判断一下每个数位上的数字，符合要求就按题目要求操作。为了方便，我们用string：作者第一次顺手写了个int，CE了。 输入，便利，判断，输出： Code： 注意：s.length ()函数返回的是一个double类型的数据，最好强转一下（不转也不是不行），判断的时候要加单引号。（双引号也行）作者第一次没加，WA了。 要是你不会字符串，你就用char输入一个判断一个，直接输出。 Code2： 三、商品降价 题目 看着挺难，先来个输入： 说要给最贵的打折。那就先求一下最大的： 手动算一下样例：发现总共要付的 = a[0] + a[1] + ··· + (最贵的 / 2) = 所有的 - (最贵的 / 2)。 那不就好说了，先求总共的，放同一个循环里吧： 输出： Code： 四、The 2024 ICPC Asia East Continent Final Contest 题目 题目好长～，但全是废话。其实就一个if的事，作者还写了个函数： 注意：题目中的a和b就是函数中的x和y。 有函数了，就直接调用一下就行了。输入，调用，输出： Code： 五、染色问题 题目 这道题硬控作者2个小时，就一道找规律。 造数据！ 当只有一个皮球时，颜色的数量、方案数： m 方案数 2 2 5 5 10 10 不难发现，当n == 1时，方案数就是m，如下： 当有多个皮球时，颜色的数量、方案数： 例：有4个皮球，3种颜色： 皮球编号 可选颜色数量 1 3 2 2 3 2 4 2 有3个皮球，2种颜色： 皮球编号 可选颜色数量 1 2 2 1 3 1 也就是说，第一个有m种，后面都有(m - 1)种，如下： 注意：每次乘完之后都要进行取模，mod是提前定义好的变量，按照题目要求，是：998244353。作者只在最后输出时取模了，WA了。 Code： 六、放烟花啦 题目 第一遍读挺难的，其实就一个输出就能解决。 先写简单的输入： 要求最多能看到的，那就先将小王和小美分别单独能看到的求出来，最后再加起来。 小王： 考虑到第0分钟时会有一根，而且c++种的“\”时向下取整，所以： 才是正确的。这里不加“+1”会WA，作者被硬控了20分钟。 根据小王的，能求出小美的计算公式： 加在一起就是： Code： 注意：代码中的“solve”没有实际上的用途，只是作者顺手写的程序框架。 给个周边吧······

点击跳转比赛 前言 本次竞赛难度T1、T2难度为简单，T3、T4难度为中档，T5、T6难度为困难.各位选手可以通过这次竞赛摸底自己的实力. ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 下面是正文题解部分： T1 这是一种病：字符串模拟 点击跳转 模拟，判断有没有 APT 在其中就行. 时间复杂度：O(∣S∣)O(|S|)O(∣S∣) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 找到最小值：函数化简 点击跳转 推一下式子， F(a,b)=a−c−c−b+2c=a−bF(a,b)=a-c-c-b+2c=a-bF(a,b)=a−c−c−b+2c=a−b，所以函数的值为 a,ba,ba,b 的差，与 ccc 无关. 对于每次询问，时间复杂度：O(1)O(1)O(1). ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3 规律数列：高精递推 点击跳转 显然规律是将上一个数+3,*3,+3,*3... 结果太大了，用 long long 也存不下. 我们可以尝试用数组模拟+3和*3操作. 但是如果每次查询都进行 NNN 次运算就浪费太大了. 我们可以预处理，这样每次查询就只需要直接输出答案了. 对于预处理，时间复杂度：O(N2)O(N^2)O(N2). 对于每次查询，时间复杂度：O(N)O(N)O(N). 总时间复杂度：O(TN+N2)O(TN+N^2)O(TN+N2). ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4 废品回收：贪心策略 点击跳转 贪心，将价值减去价格，每次挑选最大的即可（注意！不需要拿满 kkk 件！如果处理这个废品后的收益小于等于 000 就不要再拿了） 时间复杂度：O(Nlog⁡N)O(N\log N)O(NlogN). 当然，你也可以使用堆来实现在线得出最优解（O(Nlog⁡N)O(N\log N)O(NlogN)），或者用背包DP（O(N×Vi)O(N\times V_i)O(N×Vi )），以下给出背包DP的代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5 计数改良：组合数学 点击跳转 20PTS 深搜，参考下面的代码. 对于每次查询，时间复杂度：O(3N)O(3^N)O(3N). ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 40PTS 我们发现前四个测试点答案也就不超过 151515 种，考虑记忆化. 对于每次查询，时间复杂度：O(1)O(1)O(1) 或 O(3N)O(3^N)O(3N). 总时间复杂度：O(3N)O(3^N)O(3N). ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 100PTS 既然最终答案能记忆化，那能不能每个过程都记忆化一遍呢？ 我们可以记录第 iii 位每种 357357357 出现情况的种类数，分类讨论. 将 357357357 都出现的情况记作 AAA，将 357357357 出现两个的情况记作 BBB，将 357357357 出现一个的情况记作 CCC. AAA： 1. 可以由上一个 AAA 填上 3,5,73,5,73,5,7 获得，情况数 ×3\times 3×3. 2. 可以由上一个 BBB 填上所缺的数获得. BBB： 1. 可以由上一个 BBB 填上 3,5,73,5,73,5,7 中的两个数字获得，情况数 ×2\times 2×2. 2. 可以由上一个 CCC 填上所缺的数获得. CCC： 可以由一个都没有获得. 对于每次查询，时间复杂度：O(1)O(1)O(1). 预处理时间复杂度：O(N)O(N)O(N). 总时间复杂度：O(N)O(N)O(N) . 如果你嫌内存占用太大了，你可以多花费 O(Tlog⁡T)O(T\log T)O(TlogT) 的时间复杂度转离线，把空间复杂度降至 O(1)O(1)O(1). ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 120PTS Macw老师提出来一个快速的办法，理论上可以通过 T=1,N≤10107T=1,N\le 10^{10^7}T=1,N≤10107 的数据！ 首先是随便选取 357357357 中的任意一位，总共有 3N3^N3N 种情况. 然后减去只选择两个数的，即只选 353535 的，只选 373737 的和只选 575757 的，共有 3×2N3\times 2^N3×2N 种情况. 我们发现只选一个数的情况多选了一次，所以需要加回，即将结果 +3+3+3. 这样就可以以 O(log⁡N)O(\log N)O(logN) 的时间复杂度求出答案了！ 我们注意到 109+710^9+7109+7 与 2,32,32,3 均互质，所以对于更大的数可以用费马小定理来将 NNN 降至 109+510^9+5109+5 以内. 对于每次查询，时间复杂度：O(log⁡N)O(\log N)O(logN) . ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6 加固：多维动态规划 点击跳转 这道题得90分的同学大多就是因为没有特判n = 1 的情况，这次也算是提醒了大家看测试点数据的重要性了。 下面给出 222 种对于这道题的解法： AAA：三维动态规划 在这个问题中，我们需要最大化在森林环形结构中小猪家园存活后保留的金币总数。由于家园是环形的，每个小猪有两个邻居，强化一个小猪的家会从其两个邻居那里各拿走 c 个金币。我们的目标是决定哪些小猪的家应该被强化，使得在攻击后幸存的家园中的金币总数最大. 为了解决这个问题，我们可以使用动态规划（DP）。我们需要记录到当前小猪为止，考虑强化或不强化当前小猪时，能够获得的最大金币数。由于问题涉及环形结构，我们可以将其转化为线性问题，通过两次DP处理来解决. 动态规划状态定义 我们使用三维数组 dp[i][j][k] 来表示状态，其中： * i 表示当前考虑到第 i 只小猪. * j 表示第 i-1 只小猪是否被强化（0 表示未强化，1 表示强化）. * k 表示第 i 只小猪是否被强化（0 表示未强化，1 表示强化）. 状态转移方程 * 如果第 i 只小猪不强化 (k = 0)： * 如果第 i-1 只小猪强化 (j = 1)：dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][1][1] - 2*c) * 如果第 i-1 只小猪不强化 (j = 0)：dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1]) * 加上第 i 只小猪的初始金币：dp[i][0][0] += a[i] * 如果第 i 只小猪强化（k = 1）： * 如果第 i-1 只小猪强化 (j = 1)：dp[i][1][0] = max(dp[i-1][1][0] - 2*c, dp[i-1][0][0]) - 2*c * 如果第 i-1 只小猪不强化 (j = 0)：dp[i][1][0] = max(dp[i-1][0][0], dp[i-1][0][1]) - 2*c * 加上第 i 只小猪的初始金币：dp[i][1][0] += a[i] 注意：这里的 dp[i][1][0] 应该是 dp[i][1][1]，因为我们在考虑第 i 只小猪强化的情况. 修正后的状态转移方程为： * dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][0][0]) + a[i] * dp[i][0][1] = max(dp[i-1][1][1] - 2*c, dp[i-1][0][1]) + a[i] * dp[i][1][0] = max(dp[i-1][1][0] - 2*c, dp[i-1][0][0]) - 2*c + a[i] (这种情况实际不会用到，因为 k 表示当前小猪的强化状态) * dp[i][1][1] = max(dp[i-1][1][1] - 2*c, dp[i-1][0][1]) - 2*c + a[i] 由于我们只关心最后一只小猪之前的状态，并且我们最终需要的结果是在第 n 只小猪考虑强化或不强化时的最大值，所以最终答案应该从 dp[n][0][0], dp[n][0][1], dp[n][1][0] (这里实际上不需要考虑，因为最终小猪不能单独强化而不考虑最后一个邻居), dp[n][1][1] - 2*c (如果第 n 只小猪强化，并且考虑从第 1 只小猪不再拿走金币的情况) 中选取. 边界条件 * 初始化 dp[1][...] 时，由于第 0 只小猪不存在（环形结构），我们需要单独处理第一只小猪的情况. 时间复杂度：O(N)O(N)O(N). ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ BBB：二维动态规划 这种解法是我通过观察Macw老师的代码想到的（真是太妙啦！）. 在这个问题中，我们需要最大化在森林环形结构中小猪家园存活后保留的金币总数。由于家园是环形的，每个小猪有两个邻居，且强化一个小猪的家会从其两个邻居那里各拿走 m 个金币（题目中的 c 在此解答中用 m 表示，以与代码一致）。我们的目标是决定哪些小猪的家应该被强化，使得在攻击后幸存的家园中的金币总数最大。 由于问题涉及环形结构，直接应用动态规划（DP）会比较复杂。为了简化问题，我们可以将环形结构拆分为两个线性问题： 1. Case A：假设不强化第1只小猪的家园。 2. Case B：假设强化第1只小猪的家园。 对于每种情况，我们可以使用动态规划来计算到第 n 只小猪时能够获得的最大金币数。 动态规划状态定义 我们使用二维数组 dp[i][j] 来表示状态，其中： * i 表示当前考虑到第 i 只小猪。 * j 表示第 i 只小猪是否被强化（0 表示未强化，1 表示强化）。 状态转移方程 * 如果第i只小猪不强化 (j = 0)： * dp[i][0] = max(dp[i-1][0], dp[i-1][1]) * 如果第i只小猪强化 (j = 1)： * dp[i][1] = max(dp[i-1][0] + a[i], dp[i-1][1] + a[i] - 2*m) 其中，a[i] 表示第 i 只小猪家里初始的金币数。 边界条件 * 对于Case A： * dp[1][0] = 0（不强化第1只小猪） * dp[1][1] = -∞（禁用强化第1只小猪的情况） * 对于Case B： * dp[1][0] = -∞（禁用不强化第1只小猪的情况） * dp[1][1] = a[1]（强化第1只小猪） 考虑环形特性 在 Case B 中，由于我们假设强化了第1只小猪，当计算到第 n 只小猪时，还需要考虑从第 n 只小猪到第1只小猪的额外金币扣除（因为它们是邻居）。但由于我们是线性处理，这个额外的扣除已经在 dp[n][1] 的计算中隐含处理了（即如果第 n 只小猪也强化，那么从 dp[n-1][1] 到 dp[n][1] 的转移已经扣除了 2m）。因此，在最终比较 Case A 和 Case B 的结果时，不需要再额外处理环形特性。 时间复杂度：O(N)O(N)O(N). ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 希望各位能在期末考试中获得一个好成绩！

前言： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这次题难度相比欢乐赛#35和#36略有提升，但还是要比#34及以前的欢乐赛简单。 互动跳转[1] 正式题解： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这是一道很水的题，只要用C++中的cout语句或Python中的print()函数即可。 C++代码： PYTHON代码： T2: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这道题我们第一行先获取到一个测试用例数目T，然后循环T次，之后数位用索引依次累加，最后用 累加结果 mod 2累加结果 \bmod 2累加结果mod2 即可确定数位之和是奇数还是偶数。 C++代码： PYTHON代码： T3: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 因为lcm(a,b)=a×b÷gcd(a,b)lcm(a,b) = a \times b \div gcd(a,b)lcm(a,b)=a×b÷gcd(a,b)，所以这题我们可以使用C++的<algorithm>头文件中的__gcd()函数或Python的math库中的gcd()函数。 C++代码： PYTHON代码： T4: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这题我们可以用C++的for循环去拼接字符，或者用Pythona[-1:0:-1] + a[0]的索引方式将字符串反转字符串 C++代码： PYTHON代码： T5: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先我们用sort()函数对数组进行排序，用 m = (n - 1) // 2 找到中间值的位置。 用 target = a[m] + 1 将中间值提升到比其当前值大的下一个数。 对中间值及其右侧的所有元素进行操作，使这些元素不小于 target，并统计所需的操作次数。 C++代码： PYTHON代码： T6: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先我们要定义 3 × 3 的矩阵 g，表示每个灯的按压次数。 然后创建一个 3 × 3 的数组 r，初始时每个灯的状态为 1（即灯是开启的）。 对于每个灯，计算它和其上下左右相邻灯的按压次数之和，若该和为奇数，则灯的状态变为关闭（0）；若该和为偶数，则灯的状态保持开启（1）。 C++代码: PYTHON代码： 结语： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 上次题解里没写C++代码，这次为了写题解我还特意写了非常难写的C++语言代码...... 请给我点个赞吧！ 互动(来试试能不能看到“XXXX”四个字和“!”符号，能看到的把字发在评论区): ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 想要周边!\color{ffffff}{想要周边!}想要周边! ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 看上面 ↩︎

这次欢乐赛恰逢期末考试，也是抢着时间做完了，然后现在来卷个题解 T1 转义字符输出 输入输出样例： 输入#1 无 输出#1 分析： 这是一道考察基础知识的题，最简单的方法就是用ASCII表 代码： T2 28转化 输入输出样例： 输入#1 12345678 输出#1 18345672 分析： 仅需遍历一遍字符串然后用if就行了 注意要用if（）；else if（）；某鱼当时写了个错误示范if（xxx）；if（xxx）；然后直接wa完 代码： T3 商品降价 输入输出样例： 输入#1 5 10 2 8 4 6 输出#1 25 分析： 最贵的那件商品的价格减半，所以我们只需要先排序然后把最大的减半，然后再相加就行 面对新人：这里我们使用了vector来代替数组，用了algorithm中的sort函数来排序 关于vector 关于sort T4 英文字母 分析：首先多此询问，所以建议封装函数。 简单if判断直接拿下 T5 染色问题 分析：首先多此询问，所以建议封装函数。 然后不难看出这是一个递推，dp[i]=dp[i-1]*(m-1)(dp[0]=m) 哦，注意要取余，由于数据较小，所以可以不用快速幂 代码 T6 放烟花啦 分析：简单分析可得 代码： 最后祝大家期末加油

不会

C20-小心心2 HOMEWORK

输出格式中说将从大到小排序，但样例组和测试点都是从小到大排序

度：节点拥有的子树的数量为节点的度，度为0的节点为叶子节点，度不为0的节点为分支节点。树的度为树的所有节点中度的最大值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ n个结点的树，有且仅有n−1条边n个结点的树，有且仅有n-1条边 n个结点的树，有且仅有n−1条边

本讨论区有效时间时间为 2025.1.1 00:00~2025.1.31 23:59！ 本讨论区为聊天专区，大家可以畅所欲言！ QwQ? 哈？我嘞个畅所欲言，人都没有

一、作业回顾 > 提示：字符串的基本操作 二、扫雷案例 题目链接：A22.[NOIP2015 普及组] 扫雷游戏 三、桶思想练习 题目链接：A318.字母统计 > 桶思想的运用，只不过下标是字符，本质上还是ASCII码，注意数组的范围。