1. 记忆友好的密码
题面描述
fs 拥有多张银行卡，每张卡的密码均由 6 个数字组成 (可含前导 0)。密码太多不易记忆，他打算进行一次统一改动：选择同一个位置 i，并选择一个数字 d，把所有卡在该位置的数字都改成 d。
改动完成后，得到一批新的 6 位数字密码。fs 希望不同密码的种类数尽可能少。请你计算：完成一次上述改动后，不同密码的最少种类数。
测试用例
输入
35000000 100000 200000 300000 0000003123456 123556 1236563000000 111111 222222
输出
113
解题思路
枚举要统一修改的 6 个位置。
使用哈希集合统计每种情况下删去该位置后的 5 位字符串种类数，取最小值即可。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 题目一：记忆友好的密码import sysdef calculate_min_password_types(passwords): # 初始答案设为密码总数，后面不断取更小值 min_types_count = len(passwords) # 枚举要统一覆盖修改的位置 for pos in range(6): unique_passwords_after_deletion = set() # 删除当前枚举位置的字符后，统计剩下的5位字符串有多少种 for password in passwords: new_password = password[:pos] + password[pos + 1:] unique_passwords_after_deletion.add(new_password) # 更新能够达到的最少密码种类数 min_types_count = min(min_types_count, len(unique_passwords_after_deletion)) return min_types_countdef main(): input_func = sys.stdin.readline test_cases_count = int(input_func().strip()) results = [] for _ in range(test_cases_count): passwords_count = int(input_func().strip()) passwords_list = input_func().strip().split() results.append(str(calculate_min_password_types(passwords_list))) sys.stdout.write("\n".join(results))if __name__ == "__main__": main()
2. 环形二进制串的前缀操作
题面描述
给定一个仅由字符 0 与 1 组成、长度为 n 的环形二进制串 s。
你可以选择一个起点，将环断开并从该位置起按顺时针读出，得到一个线性串 (等价于对 s 进行一次旋转)。
在得到的线性串中，定义其最短 k-前缀长度为：包含恰好 k 个字符 1 的最短前缀的长度。若整个线性串中 1 的总数小于 k，则输出 -1。
你的任务是：在所有可能的旋转中，取上述最短 k-前缀长度的最小值。
若对于任意旋转均不存在包含 k 个 1 的前缀，则输出 -1。
名词解释：字符串的前缀：从字符串的第一个字符开始，向后连续取若干个字符得到的字符串。更具体地，字符串前 i 个字符构成的字符串被称为该字符串的第 i 个前缀。
测试用例
输入
38 3110010015 2010007 100000001
输出
3-11
解题思路
因为寻找的是恰好包含 k 个 1 的最短连续段，因此最优段的左右两边必定都是 1，否则能够继续缩短而不改变 1 的数量。
先扫描一遍找出所有 1 的位置。若不足 k 个，则直接返回 -1。
将记录的所有 1 的位置数组再拼接一份，但是新加进去的位置坐标都需要加上字符串原本的总长度 n，这样就将环形问题展开为线性问题了。
接着依次枚举每个 1 作为区间的开头，寻找往后的第 k 个 1 对应的位置作为区间结尾，计算两者距离。
最后在所有起止距离中取最小的一个即可。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 题目二：环形二进制串的前缀操作import sysdef find_min_prefix_length(total_length, target_ones_count, binary_string): # 记录二进制串中所有字符 1 出现时的索引位置 ones_positions = [] for index, char in enumerate(binary_string): if char == '1': ones_positions.append(index) total_ones_count = len(ones_positions) # 全部的 1 的数量如果不够目标个数，则不可能找到满足条件的旋转片段 if total_ones_count < target_ones_count: return -1 # 为了解决环形的相连特性，我们将原先的位置信息再复制粘贴一份接到末尾 # 第二份的索引位置由于跨越了一轮原字符串，所以要加上原始的字符串长度 extended_positions = ones_positions + [pos + total_length for pos in ones_positions] # 记录能够找到的最短前缀长度（初始设为不可能的最大长度） min_length = total_length + 1 # 遍历每个可能的起点索引。 # 终点则是从当前索引向后数第 target_ones_count 个 1 的位置 for start_idx in range(total_ones_count): # 计算包含指定数量 1 的区间跨度长度 current_length = extended_positions[start_idx + target_ones_count - 1] - extended_positions[start_idx] + 1 # 刷新最短长度记录 if current_length < min_length: min_length = current_length return min_lengthdef main(): input_func = sys.stdin.readline test_cases_count = int(input_func().strip()) results_list = [] for _ in range(test_cases_count): length_info = input_func().split() if not length_info: continue total_length = int(length_info[0]) target_ones_count = int(length_info[1]) binary_string = input_func().strip() results_list.append(str(find_min_prefix_length(total_length, target_ones_count, binary_string))) sys.stdout.write("\n".join(results_list))if __name__ == "__main__": main()
3. 寻找困难不平衡数
题面描述
我们定义一个整数：倘若数字位中奇数数字的个数不等于偶数数字的个数，那么我们称这个整数是一个不平衡数。
现在给定一个由数字 0 到 9 组成的字符串，求解其中有多少子序列满足：这些子序列所代表的数是一个不平衡数，且不包含前导零。
由于答案可能很大，请将答案对 10^9+7 取模后输出。
名词解释：子序列：从原序列中删除任意个，且可以为零或全部元素得到的新的序列。
提示：本题中，如果您需要使用到除法的取模，即计算 A 除以 B 后再对 M 取模的值时，需要使用公式 A 乘 B 的 M-2 次方再对 M 取模得到。例如，计算 1 除以 2 再对 10^9+7 取模的结果。
测试用例
输入
3102
输出
4
输入
6001119
输出
17
输入
70000000
输出
7
解题思路
考虑反向思考，不平衡数总数等于所有不含前导零的子序列总数减去其中平衡的子序列数。
若通过子序列动态规划会有些繁杂。不妨固定子序列产生的第一位。
假设子序列第一位是原序列中第 i 位的数字（不可为 0）。那么此后的所有元素均可以在保留和删除之间二选一。若第 i 位后还有 L 个字符，则以第 i 位为子序列首部的总合法方案数为 2 的 L 次方。
接着考虑减去那些内部奇偶平衡的子序列数量。由于第一位一旦确定为奇或偶，后面的剩余部分，假设通过组合数学去选取奇数和偶数的个数。
借用范德蒙德恒等式可以快速化简：如果是奇数开头，平衡则满足后续奇数选中个数加 1 等于后续偶数选中个数。预处理出组合数及后缀奇数偶数的前缀和统计，即可在线性时间计算每个位置上的合法和非法数目贡献。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 题目三：寻找困难不平衡数import sysMOD_VALUE = 10**9 + 7def initialize_combinations(max_n): # 构建组合数表格以供快速查询 comb_table = [[0] * (max_n + 1) for _ in range(max_n + 1)] for i in range(max_n + 1): comb_table[i][0] = 1 for j in range(1, i + 1): comb_table[i][j] = (comb_table[i-1][j-1] + comb_table[i-1][j]) % MOD_VALUE return comb_tabledef calculate_unbalanced_subsequences(length, num_string): # 预处理组合数 comb_table = initialize_combinations(length + 1) # 预处理2的次幂，计算总方案数时用 powers_of_two = [1] * (length + 1) for i in range(1, length + 1): powers_of_two[i] = (powers_of_two[i-1] * 2) % MOD_VALUE # 从后向前扫描，记录对应点及其之后分别拥有的奇偶数字的个数 suffix_odd_counts = [0] * (length + 1) suffix_even_counts = [0] * (length + 1) for i in range(length - 1, -1, -1): suffix_odd_counts[i] = suffix_odd_counts[i+1] suffix_even_counts[i] = suffix_even_counts[i+1] if int(num_string[i]) % 2 == 1: suffix_odd_counts[i] += 1 else: suffix_even_counts[i] += 1 total_unbalanced = 0 for i in range(length): # 0 不能用作子序列构成的多位数的首位，但单独的 0 亦算作一个长为1的平衡串 # 如果当前位置是 0，只把它当作独单成为串的可能去计入 if num_string[i] == '0': total_unbalanced = (total_unbalanced + 1) % MOD_VALUE continue # 如果以非零这一位开头，后续所有剩余数字有选或者不选两种情况，这是总组合可能 total_subsequences_from_here = powers_of_two[length - i - 1] # 此位置后的奇偶数各自的总库存数 remaining_odd = suffix_odd_counts[i+1] remaining_even = suffix_even_counts[i+1] # 将非法（即平衡的奇偶均衡情况）计算出来并减除 balanced_count = 0 if int(num_string[i]) % 2 == 1: # 第一位选了奇数，剩下还要保证奇数和偶数个数选的数目相差特定的量来抵消 if remaining_even >= 1: balanced_count = comb_table[remaining_odd + remaining_even][remaining_even - 1] else: # 第一位选了偶数的情况 if remaining_odd >= 1: balanced_count = comb_table[remaining_odd + remaining_even][remaining_odd - 1] # 加总并去除非法平衡串数目 total_unbalanced = (total_unbalanced + total_subsequences_from_here - balanced_count) % MOD_VALUE return total_unbalancedif __name__ == "__main__": length = int(sys.stdin.readline().strip()) num_string = sys.stdin.readline().strip() print(calculate_unbalanced_subsequences(length, num_string))
10个月宝宝每天需要喝多少奶粉？
