试题A：斐波那契与7
题意分析
- 题目中问有多少项个位是7，而能让个位发生变化的也只有个位相加减，所以只考虑个位就行，不用在考虑其他位，即结果只保留个位就行
对于这种题，肯定有规律，我们只需要找到找个规律，题目差不多就解决了
f1 = 0 f2 = 1 f3 = 1 c = 0 # 统计出现的次数 for i in range(60): print(f3, end=' ') # 斐波那契数列中的数字 f3 = (f1+f2)%10 if f3 ==7: c+=1 f1 = f2 f2 = f3 # 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0 # 经过验证，60个一循环 每个循环里面有8个个位为7的数字 print() print(c) print(202202011200//60) # 一共3370033520次循环 print((202202011200//60)*8) # 26960268160
答案：26960268160
试题 B: 小蓝做实验
利用埃氏筛法解题，埃氏筛法的效率非常高 关于埃氏筛法看这个
答案：342693
# 运用埃氏筛法进行解题 # 因为只有少部分的数据大于10**8,将数据分为两部份，小于10**8的，大于10**8 f = open(r'primes.txt','r',encoding='utf-8') txt = f.read().split() # 讲文件内的东西转化为列表 arr1 = [int(i) for i in txt if len(i)<=8] # 根据长度分，然后在转换为整型 arr2 = [int(i) for i in txt if len(i)>8] # 长度为170，所以单独判断花费的时间并不长 # 先默认所有的都为质数(这部分可以看我质数筛的文章) # 埃氏筛选法效率非常高2分42秒能够找出10*8以内的质数 nums = [True for i in range(10**8+1)] for i in tqdm(range(3,10**8+1)): if nums[i]: for j in range(i+i,10**8,i): nums[j] = False c=0 # 记录次数 for i in arr1: # 根据列表里面的值判断是否为质数 if nums[i]: c+=1 for i in arr2: # 对大于10**8的数进行判断 for j in range(2,int(i**0.5)+1): if i%j == 0: break else: c+=1 print(c)
试题 C: 取模
# 暴力 t = int(input()) nums = [] for i in range(t): n,m = input().split() n = int(n) m = int(m) f = False for j in range(1,m+1): if f: break for k in range(j+1,m+1): if n%j==n%k: f = True nums.append('Yes') break else: nums.append('No') for i in nums: print(i)
试题 D: 内存空间
思路
- 观察题意我们可以根据每句的前几个字符进行分类，详细可以分为5类，我们对不同的类，进行不同的处理，具体的处理方法见代码
- 占用空间的大小先用B为单位，最后再根据转换的规则转换成题目要求的形式
t = int(input()) zong = 0 # 总大小，单位B for i in range(t): s_lst = input().split() if s_lst[0] == 'int': # 根据不同的输入情况进行分类 st1 = s_lst[1].split(',') zong+=len(st1)*4 elif s_lst[0] == 'long': st1 = s_lst[1].split(',') zong+=len(st1)*8 elif s_lst[0] == 'String': st1 = s_lst[1].split(',') num = 0 for item in st1: num+=len(item.split('=')[1])-2 zong+=num-1 elif s_lst[0] == 'int[]': num = 0 for it in range(1,len(s_lst)): if 'long' in s_lst[it] and ';' not in s_lst[it]: num += int(s_lst[it][4:-1]) elif 'long' in s_lst[it] and ';' in s_lst[it]: num += int(s_lst[it][4:-2]) zong+=num*4 elif s_lst[0] == 'long[]': num = 0 for it in range(1,len(s_lst)): if 'long' in s_lst[it] and ';' not in s_lst[it]: num += int(s_lst[it].split(',')[0][5:-1]) elif 'long' in s_lst[it] and ';' in s_lst[it]: num += int(s_lst[it][5:-2]) zong+=num*8 z = [0,0,0,0] # B，KB，MB，GB 前的数值 for i in range(4): z[i]=zong%1024 zong = zong//1024 if zong <=0: break result = '' result_st = ['GB','MB','KB','B'] for i in range(1,len(z)+1): if z[4-i] != 0: result+=f'{z[4-i]}{result_st[i-1]}' print(result)
试题 E: 近似 GCD
解题思路
- 题目的意思就是求，数组A中的长度大于1的子数组，有多少个满足近似GCD的值为g
- 本题主要采用的方法，双指针法
- 算法主要分为两部分
- 判断子数组是否满足条件，
- 指针的移动几种情况
n,g = map(int,input().split()) nums = [int(i) for i in input().split()] import math l = 0 r = 2 c = 0 while r<=len(nums): arr = nums[l:r] flag = False for i in range(len(arr)): s = g for j in range(len(arr)): if i == j: # 跳过本身，也就是相当于将本身修改为 g continue else: s = math.gcd(s,arr[j]) # 利用math库中的gcd方法求解质数 if s == g: c += 1 flag = True break if flag: r+=1 else: if r-l>3: # 长度大于3 r-=1 l+=1 elif r-l==3: # 长度等于3 l+=1 else: # 长度等于2 r+=1 l+=1
