本文主要是介绍24.4.20 蚂蚁笔试(开发)a1.09,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
只是个人记录,玻璃心请大佬轻喷,如果有幸能得到大佬的指教那就更好啦~
若干单选和多选,感觉没有太难。下面是三个算法题(记不住具体的题目了,)
题目1
大致题意:数组a有n个元素,让求数组a的权值(权值计算方式:正数元素个数-负数元素个数)。现在对其中k个元素取反(取其相反数),求现在数组a的权值最大为多少?
输入描述:
第一行 n代表数组元素个数,k代表修改的元素个数
第二行 数组a,元素以空格隔开
题解:一定不要忘记0 让k先对负数取反,可能的话,剩下的取反施加再0上面,最后不得已再施加在正数上面。
伪码:
x=正数个数
y=负数个数
z=0的个数
if k <y:
print(x+k-y)
elif k==y:
print(x+k)
else:
if k<=z+y:
print(x+y)
else:
print(x+y-(k-y-z)-(k-y-z))
题目2
大致题意:构造数字x=x*k,x初始为1,k是由1或2组成的数字(满足条件的k如2,12,121,22221等),求x最少成几次能够变成n. 输入描述:一个数字n(n最大为2*1e5)代表x终点,输出描述:y代表最少次数
输入描述:
第一行 n代表构造目标
输出描述:
第一行 代表最少次数
题解: 随便输出的,过了4%. 不太会
事后和同学讨论,也许可以先打表,因为n最大并不是很大。然后dfs.
result =[]
ans = 18
def find_numbers():numbers = []for i in range(1, 200001):if all(digit in ['1', '2'] for digit in str(i)):numbers.append(i)return numbers
def check(n,res,cur):global result,ansif cur==len(result):returnif n==1:ans = min(ans,res)returnfor i in range(len(result)):if n%result[i]==0:check(n/result[i],res+1,i+1)result = find_numbers()
result.sort(reverse=True)
#print(result)
myset = (1,2,4,6,8)
t = int(input())
for i in range(t):n = int(input())if n%10 not in myset:print(-1)continueif n==1:print(0)continueans = 18 ##log2*1e5<18check(n,0,0)if ans == 18:ans = -1print(ans)
题目3
大致题意:数组a每个元素代表硬币金额,数组p代表取出第i个硬币的概率(具体概率这样计算p[i]/sum(p数组)),现在求取出硬币的和不小于x的期望。
输入:
第一行n,x分别代表数组元素个数和目标
第二行 就是数组a
第三行 是数组p
(数组a元素大小最大为500,n,x最大也是500)
输出:
期望模mod=1e9+7(期望可以由有理数x/y表示,要求输出(x/y%mod))它提示:对分数取模可以这样算,在[1,p-1]区间内找一个k,满足k*y%mod==x,这个k就是要的结果。
样例,
输入
2 5
3 6
2 4
样例解释:3取2次才不小于5,概率是1/3,6取一次满足不小于5,概率为2/3.期望就是2/3 *2 + 2/3*1=4/3,最后输出4/3模mod,结果为:333333337.
题解:用python的pow函数过了5%,但是感觉没什么问题不知道为啥了。事后讨论:前面计算期望简单,分数取模那里,使用扩展欧几里得求逆元的思想:参考以下
def modinv(x, mod):# 扩展的欧几里德算法求解模数逆元def egcd(a, b):if a == 0:return (b, 0, 1)else:g, y, x = egcd(b % a, a)return (g, x - (b // a) * y, y)gcd, x_inv, _ = egcd(x, mod)if gcd != 1:raise Exception('Modular inverse does not exist')else:return x_inv % mod
###k*y%mod ==x 利用逆元(x*x'%mod=1,则x'即为x%mod的逆元)的思想,把右边化为1
###k*y*x'%mod ==1 x’是x%mod的逆元
###k*(y*x')%mod ==1 最后也就是求(y+x')%mod的逆元
x = 4
mod = pow(10,9)+7
x_inv = modinv(x, mod)
y = 3
x = x_inv*y
x_inv = modinv(x,mod)
print("逆元是:", x_inv)
这篇关于24.4.20 蚂蚁笔试(开发)a1.09的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!