解题思路 这是一个关于幂运算的计数问题。通过分析可以将问题分为两种情况：   当a=c时：  当  时，式子个数为  当 时（），式子个数为  合计：    当a≠c时：   可转化为  需要遍历i，且满足  通过最大公约数来优化计算    代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } long long s...

解题思路 我们需要找到一个无序数组中需要排序的最短子数组的长度。关键在于确定这个子数组的起始和结束位置。 算法步骤：   找到无序的边界：  从左到右遍历数组，找到第一个不满足升序的元素，记为left。 从右到左遍历数组，找到第一个不满足升序的元素，记为right。    确定最小和最大值：  在left和right之间的子数组中，找到最小值和最大值。    扩展边界：  如果最小值小于left位置的元素，更新left。 如果最大值大于right位置的元素，更新right。    计算长度：  返回right - left + 1作为需要排序的最短子数组的长度。    代码   java   ...

解题思路 我们需要找到一个无限长的数字序列，其中数字k在该序列中正好出现k次。序列的前几项如下：  1 2, 2 3, 3, 3 4, 4, 4, 4 5, 5, 5, 5, 5 ...  可以观察到，数字k的最后一个出现位置是1 + 2 + 3 + ... + k = k * (k + 1) / 2。因此，我们可以通过求和公式来确定n项所在的数字。 算法步骤：  确定数字k：通过不断累加k，直到k * (k + 1) / 2大于或等于n。 输出结果：当找到合适的k后，k就是数字序列的第n项。  代码   cpp   java   python   #include <iostream&...

解题思路 我们需要找到一个镇长候选人，满足以下条件：  所有人都认识这个候选人。 这个候选人不认识其他任何人（除了自己）。  为了解决这个问题，我们可以使用图的概念：  将每个人视为图中的一个节点。 将“认识”关系视为有向边。  算法步骤：  构建图：使用两个数组cd和rd来记录每个人的出度和入度。 统计入度和出度：  遍历每个认识关系，更新出度和入度。   寻找候选人：  遍历每个人，找到出度为0且入度为n-1的候选人。    代码   cpp   java   python   #include <iostream> #include <vector> using ...

解题思路 这是一个回文扩展问题。我们需要找到一个最短的回文，使得给定字符串s可以通过在末尾添加字符来形成回文。关键点如下：   回文定义：  回文是指从前往后读和从后往后读是一样的字符串。    最短回文的构造：  我们可以通过找到字符串s的最长回文前缀来确定需要添加的字符。 如果s的前缀是回文的，那么只需在后面添加剩余的字符的反转部分。    算法步骤：  从字符串的末尾开始，检查每个前缀是否是回文。 找到最长的回文前缀后，计算需要添加的字符数。    代码   cpp   java   python   #include <iostream> #include <stri...

解题思路 这是一个查找字符串中第一个只出现一次的字符的问题。我们可以使用哈希表来记录每个字符的出现次数，然后再遍历字符串找到第一个只出现一次的字符。关键点如下：   字符计数：  使用一个哈希表（或数组）来记录每个字符的出现次数。    查找第一个只出现一次的字符：  再次遍历字符串，找到第一个计数为1的字符。    输入输出优化：  由于输入数据量较大，使用快速的输入输出方法。    代码   cpp   java   python   #include <iostream> #include <unordered_map> #include <vector&g...

解题思路 这是一个字符串匹配问题，可以使用动态规划来解决。关键点：   状态定义：   表示字符串  的前  个字符是否能被字符串  的前  个字符匹配。    状态转移：  如果当前字符匹配（ 或 $B[j-1] == '.'），则：     如果  是 '*'，则：   // '*'表示前一个字符出现0次  // '*'表示前一个字符出现1次或多次（前一个字符必须与A[i-1]匹配）      初始化：  ，表示两个空字符串匹配。 处理  中 '*' 的情况，初始化 。    代码   cpp   java   python   #include <iostream> #inc...

解题思路 这是一个博弈论问题，使用动态规划求解。关键点：   状态定义：  a[i][j] 表示在区间 [i, j] 内先手能获得的最大分数 b[i][j] 表示在区间 [i, j] 内后手能获得的最大分数    状态转移：  先手可以选择最左或最右的牌：  选左边：A[i] + b[i+1][j] 选右边：A[j] + b[i][j-1]   后手会选择让先手获得最小值：  min(a[i+1][j], a[i][j-1])      代码   cpp   java   python   class Cards { public: int cardGame(vector<int>...

解题思路 这是一个进制转换和数位和计算问题。关键点：   十进制数位和 ：  对数字  按  取余，累加每一位 如     二进制数位和g(x)：  对数字  按  取余，累加每一位 如 ，    幸运数判断：  遍历  到  的每个数 判断     代码   cpp   java   python   #include <iostream> using namespace std; // 计算十进制数位和 int getDecimalSum(int x) { int sum = 0; while(x > 0) { sum += x % 10; x /= 10; } retu...

解题思路 这是一个逻辑表达式加括号问题。关键点：   预处理：  分离数字和运算符 数字在偶数位，运算符在奇数位    动态规划：   表示区间  得到值  的方案数 枚举分割点，计算所有可能组合    代码   c++   java   python   class Expression { public: int countWays(string exp, int len, int ret) { vector<int> nums((len + 1) / 2); vector<char> ops(len / 2); // 分离数字和运算符 for(int i = 0;...

解题思路 这是一个进制转换和分数计算问题。关键点：   进制转换：  对于每个进制  (2到 ) 将  转换为  进制 计算各位数字之和    分数化简：  总和除以进制个数得到平均值 需要化简为最简分数    最大公约数：  使用辗转相除法求GCD 用于分数化简    代码   cpp   java   python   #include <iostream> using namespace std; // 计算最大公约数 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // 计算一个数在指定进制下各位数字...

解题思路 这是一个字符串混编问题，可以使用动态规划求解。关键点：   动态规划定义：   表示  的前  个字符和  的前  个字符能否混编成  的前  个字符  表示使用了  的前  个字符  表示使用了  的前  个字符    状态转移：  如果当前字符来自 ： 如果当前字符来自 ：    基本判断：  长度必须匹配： 初始状态：    代码   cpp   java   python   class Mixture { public: bool chkMixture(string A, int n, string B, int m, string C, int v) { if(n + m...

解题思路 这是一个集合合并问题。关键点：   数据结构选择：  使用  去重 或使用排序后合并    输出要求：  升序输出 元素间用空格分隔 行末无空格    代码   cpp   java   python   #include <iostream> #include <set> using namespace std; int main() { int n, m; while(cin >> n >> m) { set<int> s; // Input set A for(int i = 0; i < n; i++) { i...

解题思路 这是一个字符串交错组成问题，可以使用动态规划求解。关键点：   动态规划定义：   表示  的前  个字符和  的前  个字符是否能交错组成  的前  个字符  范围：， 范围：    状态转移：  如果 ： 如果 ：    边界条件：   第一行：只用  串匹配 第一列：只用  串匹配    代码   cpp   java   python   class Mixture { public: bool chkMixture(string A, int n, string B, int m, string C, int v) { if(n + m != v) return false...