Jeremy's Blog

数字倍数问题问题描述小U对数字倍数问题很感兴趣，她想知道在区间 $[l, r]$ 内，有多少个数是 $a$ 的倍数，或者是 $b$ 的倍数，或者是 $c$ 的倍数。你需要帮小U计算出这些数的个数。 解题思路本题要求统计区间内能被给定的多个数中的至少一个整除的整数个数，是典型的容斥原理应用。 容斥原理容斥原理用于计算多个集合的并集的基数，其公式为： |A \cup B| = |A| + |B| - |A \cap B|对于三个集合，有： |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|应用到解题 集合定义： 令 $A$、$B$、$C$ 分别表示能被 $a$、$b$、$c$ 整除的整数集合。 目标： 计算 $|A \cup B \cup C|$，即在区间内能被 $a$、$b$ 或 $c$ 整除的整数个数。 计算步骤 计算单个集合的基数： 计算能被 $a$、$b$、$c$ 整除的整数个数，分别记为 $N_a$、$N_b$、$N_c$。 计算集合的交集的 ...

数组元素最小操作次数问题问题描述小U有一个数组，她可以通过选择一个元素并将其除以2（向下取整）的操作来改变数组。小U想知道，最少需要多少次这样的操作才能使得所有数组元素相等。 解题思路本题要求通过对数组中的元素进行除以 $2$ 的操作，使得所有元素相等，并求出最小的操作总次数。 具体思路如下： 记录每个元素能够通过多少次操作达到哪些值： 对于数组中的每个元素，模拟其不断除以 $2$ 的过程，记录它能够到达的所有值以及到达每个值所需的操作次数。 使用哈希表（如 unordered_map 来存储每个可能的目标值对应的操作次数列表。 汇总所有元素可达到的公共值： 遍历哈希表，对于每个可能的目标值，检查是否所有元素都能够通过某些操作达到该值（即操作次数列表的长度是否等于数组长度 n ）。 如果是，则计算将所有元素变为该值所需的操作总次数。 求最小的操作总次数： 在所有可能的目标值中，选择操作总次数最小的值，即为所求答案。 代码实现12345678910111213141516171819202122232425262728293031323334353637#include ...

最少字符串操作次数问题描述小U得到一个只包含小写字母的字符串 S 。她可以执行如下操作：每次选择字符串中两个相同的字符删除，然后在字符串未尾添加一个任意的小写字母。小U想知道，最少需要多少次操作才能使得字符串中的所有字母都不相同？ 解题思路要使每个字符的出现次数唯一，我们可以分三步处理： 统计字符频率和未使用字符：遍历字符串，统计每个字符出现的次数，并记录未在字符串中出现的字符（从 a 到 z 共 26 个）。 优先替换操作：对于频率大于 1 的字符，优先使用未使用的字符进行替换。每次替换操作，可以将两个相同的字符替换为一个新字符，这样可以同时减少重复字符的数量和引入新的字符。 删除多余字符：如果没有未使用的字符可供替换，或者字符频率仍然大于 1，则需要通过同字符+2 -1的操作，相当于删除一个字符来减少重复字符。 代码实现123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>using namespace std;int so ...

二进制之和问题描述给定两个二进制字符串，返回它们的和（用十进制字符串表示）。输入为非空字符串且只包含数字 1 和 0，需要考虑大数问题。时间复杂度不得超过 $O(n^2)$ ，其中 $n$ 是二进制字符串的最大长度。 解题思路本题要求将两个二进制字符串相加，以十进制字符串的形式输出，同时需要考虑大数问题，不能使用内置的数据类型直接转换，核心在于通过字符串来模拟大数的四则运算，我们分两步来解决： 二进制字符串相加：模拟二进制加法，得到两个二进制字符串的和，结果也是一个二进制字符串。 二进制转十进制字符串：将得到的二进制和转换为十进制字符串，模拟大数乘法和加法。 具体步骤： 二进制加法：从最低位开始逐位相加，注意进位。 大数乘法和加法：在将二进制转换为十进制时，无法使用内置类型直接计算，需要模拟大数乘法（乘以 2）和大数加法（加上当前位的值）。 代码实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#incl ...