第一题：不是字符串问题
题目描述
对于长度为 n 的字符串 t 和整数 k，我们将字符串 f(t, k) 定义为以下内容的连接：
t 的前 k 个字符，按字典序从小到大排序；
t 整串，按字典序从大到小排序；
t 除去前 k 个字符外的剩余字符，按字典序从小到大排序。
现在，对于长度为 n 的字符串 s，你需要取出它的全部长度为 x 的子串，且令 k = x / 2，按照上述步骤进行构造。
请问能构造出多少个互不相同的新字符串？
输入描述
第一行输入一个整数 T 代表数据组数。
对于每组数据：
第一行两个整数 n 和 x，分别代表字符串长度和子串长度。
第二行一个长度为 n 的字符串 s，由大小写字母构成。
输出描述
每组数据输出一个整数，代表构造出的不同新字符串数量。
测试样例
输入
25 4bAbbb7 3nuhhhhh
输出
13
本题的核心在于字符串的局部提取与规则重组。
我们需要遍历原字符串，提取出所有长度为 x 的子串。对于每个子串，根据题目给定的规则（前一半升序、整体降序、后一半升序）进行拼接，得到一个新的长字符串。
由于字符串长度较小，我们可以直接利用哈希集合进行去重，最后统计集合的大小即可。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 第1题
import sys
def count_distinct_reconstructed_strings():
# 读取测试数据组数
input_data = sys.stdin.read().split()
if not input_data:
return
idx = 0
test_cases = int(input_data[idx])
idx += 1
for _ in range(test_cases):
str_len = int(input_data[idx])
sub_len = int(input_data[idx + 1])
idx += 2
original_str = input_data[idx]
idx += 1
unique_results = set()
# 计算截取位置 k
split_point = sub_len // 2
# 遍历所有可能的子串
for i in range(str_len - sub_len + 1):
sub = original_str[i : i + sub_len]
# 部分1：前 split_point 个字符升序
part_a = "".join(sorted(sub[:split_point]))
# 部分2：整个子串降序
part_b = "".join(sorted(sub, reverse=True))
# 部分3：剩余字符升序
part_c = "".join(sorted(sub[split_point:]))
# 组合成新串并加入集合去重
reconstructed = part_a + part_b + part_c
unique_results.add(reconstructed)
print(len(unique_results))
if __name__ == "__main__":
count_distinct_reconstructed_strings()
第二题：字典序
题目描述
给定两个长度均为 n 的单词 A 和 B。
假设每种字母组合（小写字母 a 到 z）都能构成一个单词。
请计算出字典序小于 B 但大于 A，且长度同样为 n 的单词有多少个。
如果 A 的字典序大于或等于 B，则输出 0。
输入描述
第一行输入一个整数 T 代表数据组数。
接下来每组数据包含：
长度 n，以及两个长度为 n 的单词 A 和 B。
输出描述
每行输出一个整数作为答案。
测试样例
输入
41 z a1 a z2 az bb3 bbb bbb
输出
02410
解题思路
两个长度相等的字符串之间的字典序数量，可以等价地看作 26 进制下的数字差值。
我们将字符 a 映射为 0，b 映射为 1，以此类推，z 映射为 25。那么每个长度为 n 的字符串都可以唯一转换为一个 26 进制的大整数。
单词的数量即为：(B 的数值 - A 的数值 - 1)。如果 A 的字典序本身就比 B 大，则返回 0。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 第2题
import sys
def calculate_word_gap():
# 处理所有输入行
lines = sys.stdin.readlines()
if not lines:
return
test_cases = int(lines[0].strip())
# 辅助函数：将字符串转换为 26 进制数值
def convert_to_base26(s):
val = 0
for char in s:
val = val * 26 + (ord(char) - ord('a'))
return val
for i in range(1, test_cases + 1):
data = lines[i].split()
if len(data) < 3:
continue
word_length = int(data[0])
word_start = data[1]
word_end = data[2]
# 如果起始单词字典序更大，直接输出 0
if word_start >= word_end:
print(0)
else:
# 计算两数值之差减一
diff = convert_to_base26(word_end) - convert_to_base26(word_start)
print(diff - 1)
if __name__ == "__main__":
calculate_word_gap()
第三题：小红的红色直线
题目描述
小红有 n 条直线，解析式均为 ax + by + c = 0。
她准备从中选出 k 条直线染成红色。
如果两条红色的直线相交，就会产生一个红点。
小红希望通过合理选择，使得最终产生的红点数量尽可能多。
请计算红点数量的最大值。
输入描述
第一行两个整数 n 和 k。
接下来 n 行，每行三个整数 a, b, c 代表直线参数。
输出描述
输出一个整数，代表最多的红点数量。
测试样例
输入
3 21 1 11 1 21 2 1
输出
1
解题思路：
只要两条直线不平行，它们在平面上就一定会产生一个交点。
如果我们选出的 k 条直线两两都不平行，产生的红点总数将是组合数 C(k, 2) = k * (k - 1) / 2。
然而，如果选出的直线中存在平行线，就会导致交点的损失。每组平行线中，如果已经选了 m 条线，再增加一条同样的平行线，就会额外损失 m 个红点。
因此，我们的目标是最小化平行的总损失。通过统计所有方向相同的直线组，将每组中每多选一次的成本（对应损失数）列出并排序，贪心地选取前 k 个最小成本即可。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 第3题
import sys
import math
def maximize_intersection_points():
# 读取直线总数 n 和需要选取的数量 k
input_lines = sys.stdin.read().splitlines()
if not input_lines:
return
first_line = input_lines[0].split()
total_n = int(first_line[0])
select_k = int(first_line[1])
slope_frequency = {}
# 遍历每条直线的参数
for i in range(1, total_n + 1):
a, b, c = map(int, input_lines[i].split())
# 通过最大公约数简化方向向量 (a, b)
common_div = math.gcd(abs(a), abs(b))
reduced_a, reduced_b = a // common_div, b // common_div
# 统一标准化符号，确保平行线映射到同一个键
if reduced_a < 0 or (reduced_a == 0 and reduced_b < 0):
reduced_a, reduced_b = -reduced_a, -reduced_b
key = (reduced_a, reduced_b)
slope_frequency[key] = slope_frequency.get(key, 0) + 1
parallel_loss_costs = []
# 对于每个平行组，每多选一条线增加的损失分别是 0, 1, 2, ...
for count in slope_frequency.values():
for loss in range(count):
parallel_loss_costs.append(loss)
# 贪心：将所有损失成本排序，选前 k 小的
parallel_loss_costs.sort()
total_parallel_loss = sum(parallel_loss_costs[:select_k])
# 最大红点数 = 理想最大交点数 - 最小损失
ideal_max = select_k * (select_k - 1) // 2
print(ideal_max - total_parallel_loss)
if __name__ == "__main__":
maximize_intersection_points()
10个月宝宝每天需要喝多少奶粉？
