算法笔试-编程练习-M-01-24
t这套题，偏向灵活，更多的考察了数学、贪心
一、质因数
题目描述
小乖对 gcd (最大公约数) 很感兴趣, 他会询问你t次。 每次询问给出一个大于 1 的正整数 n, 你是否找到一个数字m(2 ≤m ≤ n)，使得 gcd(n,m)为素数.
注：原题为给出任意解，本题中请给出最大值作为答案
输入描述
每个测试文件将包含多组测试数据,每组测试数据的第一行包含一个整数 k (2 ≤ k ≤ 10^5), 表示有 k个待测数字.接下来 k 行,每行包含一个整数 n (2 ≤ n ≤ 10^9),表示待测的数字.
输出描述
对于每一组测试数据, 在一行上输出一个整数，代表数字 m。
示例 1
输入
2
114
15
输出
57
5
题目分析
【题目类型：数论、质数】
首先素数和质数是一个概念的两种说法。题目在描述的过程中加了几个拐弯，对于n找到一个m，使gcd(n,m)是素数，求最小的m，其实就是找n的最小质因数m。
这里我们要明确一个概念，所有合数都可以写成若干质数的乘积，所以n的质因数m一定有 m*m<n。这里有两者方案：
1）一种是由于n小于10^9所以可以求出10^5以内所有的质数，然后对于n从小到大遍历。
2）另一种是类似质因数分解的方式，去找n的质因数。
代码：
prime_numbers = []
# 因为 n 小于10^9，则其质因素一定小于10^5
for i in range(2, 100000):find = Falsefor p in prime_numbers:# 一个合数一定有比他小质因数，如果找不到，则该数就是质数if p*p > i: breakif i%p == 0: find = Truebreakif not find:prime_numbers.append(i)k = int(input())
for _ in range(k):n = int(input())flag = Truefor p in prime_numbers:if p*p > n:breakif n % p == 0:print(p)flag = Falsebreakif flag:print(n)# 寻找质因素
def calc(n):factor = 2if n % factor == 0:return factorfactor = 3if n % factor == 0:return factorwhile factor*factor <= n:if n % factor == 0:return factorfactor += 2 # 这里是因为已经确认 n 不会被2整除，所以只遍历奇数就可以（快一点）return n # 能到这里说明没有找到n的质因数，那么n就是素数k = int(input())
for _ in range(k):n = int(input())print(calc(n))补充：
作为补充理解，这里给出gcd和lcm的代码：
def gcd(n, m):while m:n, m = m, n%mreturn ndef lcm(n,m):return n*m//gcd(n,m)n = [1, 12, 6, 10, 30]
m = [3, 18, 15, 21, 20]
for i in range(len(n)):print(n[i], m[i], gcd(n[i], m[i]), lcm(n[i], m[i]))二、极差
题目描述
小乖有一个长度为 n 的数组,每次操作可以选择两个下标i和j,分别减1和加1，小乖想知道最少需要多少次操作，可以使数组极差减小。
数组的极差为数组中最大值和最小值的差
输入描述
第一行输入一个整数 n (2 ≤ n ≤ 10^5), 表示数组的长度 第二行输入n个整数 a_1,a_2,...a_n (1 ≤ a_i ≤ 10^9), 代表数组的元素
输出描述
在一行上输出一个整数,表示最少需要多少次操作。
示例 1
输入
5
1 2 3 4 5
输出
3
题目分析
【题目类型：贪心，数学】
这是一道很直观得平均贪心题目，我们是使用下去取整获得平均数mean，那么只需要让所有数字调整为mean+1 或者mean即可。
由于mean是向下取整得到的，那么原数组中大于mean的数字到mean的差的和，一定大于小于mean的数字到mean的差的和。这个多出来的数值实际上就是mean+1是数量（也就是下面代码中diff = sum(tempList)求得的值）。我们记录大于mean的值的数量为cnt，存在如下两种情况：
1）如果diff >= cnt，那么其实就让所有大于mean的值少减1就可以了。这里的逻辑很直观，就是保证所有原来就大于mean的值为mean+1
2）else cnt>diff，那么就让大于mean的数，少减diff就可以啦。
代码：
n = int(input())
arr = [int(i) for i in input().split()]
mean = sum(arr)//ntempList = []
cnt = 0
ans = 0
for a in arr:temp = a-meanif temp>0:ans += tempcnt += 1tempList.append(temp)diff = sum(tempList)if diff >= cnt:ans -= cnt
elif diff > 1:ans -= diffprint(ans)三、博弈
小乖和小坏在玩一个游戏，游戏中有一个长度为 n 的数组a1,a2,...,an和一个固定的整数k。游戏规则如下，双方都会执行最优策略:
第一步,小乖选择一个非空的区间 [l,r]，将这个区间中的所有数字都乘上 k。
第二步, 小坏选择一个非空的区间 [l,r], 将这个区间中的所有数字都乘上 k。
记sum=整个数组的和，小坏想让sum尽可能小，小乖想让sum尽可能大，你需要求出最后 sum的值。
输入描述
第一行输入两个整数 n 和 k (-
≤ k ≤
第二行输入 n 个整数 a1,a2,...,an(−
输出描述
在一行上输出一个整数表示答案。
示例 1
输入
6 2
-1 -2 -3 1 2 3
输出
0
说明
小乖会选择区间[4,6],数组变成{−1,−2,−3,2,4}；
小坏会选择区间[1,3],数组变成{−2,−4,−6,2,4,6}；
数组总和为 0。
题目分析
【题目类型：最大子序列和，博弈】
对于后手小坏来说，他的决策是贪心的，即为了让sum最小，当k>0时，选择最小子序列和相乘，当k<=0时，选择最大子序列和相乘。而这个问题可以用DP用O(n)的时间复杂度求解，参考算法笔试-编程练习-好题-02-CSDN博客
对于先手小乖来说，难以直接确定如何做可以让sum最大，需要遍历所有情况，检查小坏操作结束后的sum值，选择sum最大的取值。
【注意】博弈问题，通常后手是有贪心解的，但是先手的最优解难以贪心确定。
代码：
import copy
def calc_min(nums_in, k):dp = copy.deepcopy(nums_in)for i in range(1, len(nums_in)):if dp[i-1] < 0:dp[i] += dp[i-1]return sum(nums_in) + (k-1)*min(dp)def calc_max(nums_in, k):dp = copy.deepcopy(nums_in)for i in range(1, len(nums_in)):if dp[i-1] > 0:dp[i] += dp[i-1]return sum(nums_in) + (k-1)*max(dp)def calc_base(nums_in, l, r, k):nums = copy.deepcopy(nums_in)for i in range(l, r+1):nums[i] *= kreturn numsdef main_calc(nums, n, k):if k == 1:return sum(nums)ans = ""for l in range(n):for r in range(l,n):nums_temp = copy.deepcopy(nums)# 小乖：遍历nums_temp = calc_base(nums_temp, l, r, k)# 小坏：贪心if k > 0:# 找最小的区间temp = calc_min(nums_temp, k)else:# 找最大的区间temp = calc_max(nums_temp, k)if ans=="" or temp > ans:ans = tempreturn ansn, k = map(int, input().split())
nums = [int(i) for i in input().split()]
print(main_calc(nums, n, k))