蓝桥杯备战日志(Python)19-阅兵方阵&删除字符-(平方和频次统计&字符串字典序)

阅兵方阵

原题

X 国要参加同盟阅兵活动。

主办方要求每个加盟国派出的士兵恰好能组成 2 个方阵。

X 国发现弱小的 Y 国派出了130 人的队伍，他们的士兵在行进中可以变换 2 种队形：

X 国君很受刺激，觉得 X 国面积是 Y 国的 6 倍，理应变出更多队形。 于是他发号施令： 我们要派出一支队伍，在行进中要变出 12种队形！！！

手下人可惨了，要忙着计算至少多少人才能组成 12 种不同的双方阵。 请你利用计算机的优势来计算一下，至少需要多少士兵。

分析

本题题意清楚，求平方和等于同一个数res的情况，这里已知有12种情况，求res这个数的最小值。解题思路是，求出1~n (这里取n=1000)内的平方，然后枚举不同的平方组合得到平方和，同时统计各平方和的值的频次，最后在出现频次等于12的平方和的数中选择最小的那个数即为所求。

源码

n = 1000
An = [i*i for i in range(1,n)]
num_fre_dict = dict()
for i in range(1,n-1):
    for j in range(i,n-1):
        nums = An[i] + An[j]
        t = num_fre_dict.get(nums)
        if t is None:
            num_fre_dict[nums] = 1
        else:
            num_fre_dict[nums] = t + 1

res = min( num for num,fre in num_fre_dict.items() if fre == 12)
print(res)

删除字符

原题

分析

本题转换一下角度就很容易求解，给定一个字母字符串，可求其长度为length,需要删除t个字母，即在字母字符串中按顺序选择 num (num=length - t) 个字母。解题的关键点在于字典序最小，首先要理解计算机中字母字符串的字典序的比较：逐一比较两个字符串str1何str2的第i个字符(i = 0, 1, 2, ..., n-1, n为最短字符串的长度)，若str1[i] < str2[i]，则字典序：str1 < str2。下图两个例子加深理解：

本题的解题思想是贪心策略，选择第i个字母时，在保证最后还有num-i个字母可供选择的条件下，在未选择的字母中选择一个字典序最小的字母。然后再选择第i+1个字母时需要从上一个已选择的字母后面选择，依次类推，具体实现见“源码”。

源码

str_input = input()
t = int(input())

num = len(str_input) - t
str_selected = ''

# 选择num个字符
for i in range(1,num+1):
    # 当前选择第i个字符，然后还需选择 num-i 个字符
    # 在除去已选字符前面的字符和后面num-i个字符后的前面所有字符中选择一个字典序最小的
    char_ = str_input[0]
    index = 0
    for j in range(1,len(str_input)-num+i):
        if str_input[j] < char_:
            char_ = str_input[j]
            index = j
    str_selected += char_
    str_input = str_input[index+1:]  # 删除选择的字符char_前面的字符

print(str_selected)

上一篇：​​蓝桥杯备战日志(Python)18-第几个幸运数字-(枚举只含某些因子的整数)​​