2022/7/28 蔚来算法岗笔试
有一说一，这么短的答题时间出这么难的题目真变态啊...
1.NOIP 2011提高组 原题 （一个笔试这么短的时间搞个提高组的题目，实在无语啊。。。没做过原题的吃大亏）
代码就不放了，直接点链接可以看题解
2.对于一个序列，牛牛每次可以将序列中任意一个位置上的数乘上任意一个质数。现在他想知道至少需要多少次操作才能使得该序列中的任意两个不同位置的数相乘都为完全平方数。
统计质因子出现重数为奇数的次数
统计质因子出现重数为奇数的次数
from collections import defaultdict from math import ceil n=int(input()) a=list(map(int,input().split())) ans=0 cnt=defaultdict(int) for v in a: if int(v**0.5)**2==v: continue x=v for i in range(2,min(ceil(v**0.5)+1,v)): if v%i==0: temp=0 while x%i==0: temp+=1 x//=i if temp&1: cnt[i]+=1 if x!=1: cnt[x]+=1 for v in cnt.values(): ans+=min(v,n-v) print(ans)3. 51nod首尾排序法的升级版 （允许有重复数字）
不会做有重复数字的情况，直接当没有重复数字做的，过了80%
n=int(input()) a=list(map(int,input().split())) idx=[i for i in range(n)] idx.sort(key=lambda x:(a[x],x)) dp=[1]*n for i in range(1,n): if idx[i]>idx[i-1]: dp[i]=dp[i-1]+1 print(n-max(dp))
类似资料：