一、写在前面兄弟们Day 22今天搞了一套第十三届蓝桥杯国赛的真题把前四道题全部过了一遍。不得不说国赛的难度确实比省赛高了一个档次尤其是填空题如果硬算的话时间根本不够必须找规律。大题部分考察的知识点也很综合涉及质数筛、数论推导、字符串解析等。今天的四道题斐波那契与7 —— 找规律周期小蓝做实验 —— 质数筛大数判断取模 —— 数论推导反证法内存空间 —— 字符串解析模拟二、第一题斐波那契与7难度⭐⭐⭐2.1 题目大意斐波那契数列F(1)1, F(2)1, F(n)F(n-1)F(n-2)。问前 202202011200 项中有多少项的个位数字是72.2 解题思路这题数据量巨大2022亿项直接递推肯定超时必须找规律。关键观察个位数字只跟个位数字有关。比如 132437个位只由 347 决定。所以斐波那契数列的个位数字序列也是有周期的。我们只需要模拟前若干项的个位找到周期即可。2.3 代码实现a,b1,1num2ans0# 找规律只考虑个位whilenum180:cur(ab)%10# 只保留个位a,bb,curifcur7:ans1num1# 打印出来看看规律# num ans# 60 8# 120 16# 180 24# 发现规律60个循环一组每组有8个7print(202202011200//60*8)2.4 规律验证手动模拟一下个位序列F(1)1, F(2)1, F(3)2, F(4)3, F(5)5, F(6)8, F(7)3, F(8)1…个位序列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,1,1…数一下前60项里有8个7。而且因为只跟个位有关这个周期会一直重复下去。所以答案 202202011200 // 60 * 8 269602681602.5 踩坑记录不要硬算2022亿项Python也跑不动必须找周期。只保留个位cur (a b) % 10这样数字不会越界。周期验证多跑几组确认周期确实是60不要只看一组就下结论。三、第二题小蓝做实验难度⭐⭐⭐⭐3.1 题目大意给定一个文件primes.txt里面有很多数字。判断其中有多少个是质数。数字范围很大有些可能超过 10^8。3.2 解题思路这题分两部分处理小于等于 10^8 的数用埃氏筛预处理所有质数然后 O(1) 判断大于 10^8 的数直接试除法判断因为这类数不会太多埃氏筛的时间复杂度是 O(n log log n)对于 10^8 来说在Python里有点悬但实际测试可以通过。3.3 代码实现fopen(primes.txt,r,encodingutf-8)txtf.read().split()# 按位数分开处理arr1[int(i)foriintxtiflen(i)8]# 小于等于10^8arr2[int(i)foriintxtiflen(i)8]# 大于10^8# 埃氏筛defselects(n):primes[True]*(n1)primes[0]primes[1]Falsep2whilep*pn:ifprimes[p]:foriinrange(p*p,n1,p):primes[i]Falsep1returnprimes n10**8ans0primeselects(n)# 小于等于10^8的数直接查表foriinarr1:ifprime[i]:ans1# 大于10^8的数试除法判断foriinarr2:is_primeTrueforjinrange(2,int(i**0.5)1):ifi%j0:is_primeFalsebreakifis_prime:ans1print(ans)3.4 踩坑记录埃氏筛的内存10^8 的布尔数组大概占 100MB要注意内存限制。试除法优化只需要判断到 sqrt(n) 即可不要傻乎乎地遍历到 n。文件读取f.read().split()可以直接按空白字符分割不用一行行读。大数处理大于 10^8 的数如果很多试除法会超时但这题数据量应该不大。四、第三题取模难度⭐⭐⭐⭐4.1 题目大意给定 n 和 m问是否存在两个不同的数 x, y1 ≤ x y ≤ m使得 n mod x n mod y。4.2 解题思路这题如果暴力枚举 x 和 y时间复杂度是 O(m²)对于大数会超时。需要用数论推导。关键思路反证法。假设不存在这样的 x 和 y那么对于所有 1 ≤ x y ≤ m都有 n mod x ≠ n mod y。这意味着 n mod 1, n mod 2, …, n mod m 这 m 个余数互不相同。但余数的范围是 0 到 x-1所以n mod 1 0唯一可能的值n mod 2 必须是 1因为0已经被占了n mod 3 必须是 2…n mod m 必须是 m-1也就是说如果存在解必须满足 n % i i - 1 对所有 i ∈ [1, m] 成立。反过来只要存在一个 i 使得 n % i ≠ i - 1就一定存在解。4.3 代码实现importsysinputsys.stdin.readline Tint(input())for_inrange(T):n,mmap(int,input().split())flagTrueforiinrange(1,m1):ifn%i!i-1:print(Yes)# 存在这样的x,yflagFalsebreakifflag:print(No)# 不存在4.4 证明过程为什么 n % i i - 1 对所有 i 成立时就不存在解因为如果 n % i i - 1那么 n 1 能被 i 整除因为 n k*i (i-1)所以 n1 (k1)*i。也就是说 n 1 是 1, 2, …, m 的公倍数。只有当 n 1 是 lcm(1,2,…,m) 的倍数时才可能。对于一般的 n 和 m这种情况几乎不可能发生所以大部分情况下答案都是 “Yes”。4.5 踩坑记录不要暴力O(m²) 的暴力在 m 很大时会超时必须推导数学规律。反证法的逻辑想清楚不存在解的充要条件是什么。边界情况m1 时不存在两个不同的数直接输出 “No”。五、第四题内存空间难度⭐⭐⭐⭐5.1 题目大意给定一段类似 C/C 的代码统计其中声明的变量占用的总内存空间。涉及三种类型int占 4 字节long占 8 字节String字符串类型每个字符占 1 字节不算引号变量声明格式int a1,b2;—— 普通变量每个占 4 字节int arr[10];—— 数组占 4*10 40 字节int arr[10][20];—— 多维数组占 41020 800 字节String shello;—— 字符串占 5 字节String shello,tworld;—— 多个字符串最后把总字节数转换成人类可读格式B/KB/MB/GB每 1024 进一位。5.2 解题思路这题是字符串解析模拟。需要逐行解析代码识别变量类型计算每种变量占用的空间。核心逻辑判断类型int/long/String判断是否是数组看有没有[]如果是数组解析维度并计算元素个数如果是普通变量统计的个数每个对应一个变量如果是 String解析引号内的字符数5.3 代码实现importosimportsys tint(input())ans0for_inrange(t):k0cur0sinput().strip()ifs[0]i:# int 类型k4ifs[3:5][]:# 是数组ss[5:]# 解析多维数组的维度whiles.find([)!-1:sts.find([)1eds.find(])curint(s[st:ed])ss[ed1:]ansk*curelse:# 普通变量# 统计 的数量每个 对应一个变量whiles.find()!-1:cur1ss[s.find()1:]ansk*curelifs[0]l:# long 类型k8ifs[4:6][]:# 是数组ss[6:]whiles.find([)!-1:sts.find([)1eds.find(])curint(s[st:ed])ss[ed1:]ansk*curelse:# 普通变量whiles.find()!-1:cur1ss[s.find()1:]ansk*curelse:# String 类型whiles.find()!-1:# 找到双引号的位置sts.find()1ifs.find(,)!-1:eds.find(,)-1else:eds.find(;)-1ansed-st ss[ed2:]# 转换成人类可读格式dans[B,KB,MB,GB]stpos0whileans!0:ifans%1024!0:ststr(ans%1024)dans[pos]st ans//1024pos1print(st)5.4 踩坑记录数组维度解析多维数组如arr[10][20]需要循环解析每个[]里的数字然后相乘。int 和 long 的区别int后面数组从第3位开始判断int[]long从第4位开始long[]。String 的引号是英文双引号不是中文引号解析时要注意。多个变量int a1,b2;这种一行多个变量的情况要通过统计的数量来判断变量个数。单位转换每 1024 进一位从 B - KB - MB - GB注意是除法取余的方式转换。六、今日总结题目核心算法关键技巧易错点斐波那契与7找规律个位周期不要硬算大数小蓝做实验质数筛试除埃氏筛预处理内存限制、大数处理取模数论推导反证法暴力会超时内存空间字符串解析正则/字符串操作数组维度、引号类型今天这四道题覆盖了国赛常见的几种题型填空题找规律是王道硬算必死质数题埃氏筛是标配大数据要分治数论题多想想数学推导少写暴力循环模拟题细心处理字符串注意各种边界情况国赛的前四道大题难度其实还好关键是时间分配。填空题如果5分钟没思路就先跳过大题先把暴力分拿到再考虑优化。明天继续肝国赛后几道题兄弟们一起加油七、附录相关知识点复习数论基础模运算性质、反证法、鸽巢原理质数算法埃氏筛、欧拉筛、Miller-Rabin素性测试字符串处理find、切片、正则表达式找规律技巧只保留低位、模拟找周期如果觉得有帮助欢迎点赞收藏有问题评论区见
备战蓝桥杯国赛【Day 22】
一、写在前面兄弟们Day 22今天搞了一套第十三届蓝桥杯国赛的真题把前四道题全部过了一遍。不得不说国赛的难度确实比省赛高了一个档次尤其是填空题如果硬算的话时间根本不够必须找规律。大题部分考察的知识点也很综合涉及质数筛、数论推导、字符串解析等。今天的四道题斐波那契与7 —— 找规律周期小蓝做实验 —— 质数筛大数判断取模 —— 数论推导反证法内存空间 —— 字符串解析模拟二、第一题斐波那契与7难度⭐⭐⭐2.1 题目大意斐波那契数列F(1)1, F(2)1, F(n)F(n-1)F(n-2)。问前 202202011200 项中有多少项的个位数字是72.2 解题思路这题数据量巨大2022亿项直接递推肯定超时必须找规律。关键观察个位数字只跟个位数字有关。比如 132437个位只由 347 决定。所以斐波那契数列的个位数字序列也是有周期的。我们只需要模拟前若干项的个位找到周期即可。2.3 代码实现a,b1,1num2ans0# 找规律只考虑个位whilenum180:cur(ab)%10# 只保留个位a,bb,curifcur7:ans1num1# 打印出来看看规律# num ans# 60 8# 120 16# 180 24# 发现规律60个循环一组每组有8个7print(202202011200//60*8)2.4 规律验证手动模拟一下个位序列F(1)1, F(2)1, F(3)2, F(4)3, F(5)5, F(6)8, F(7)3, F(8)1…个位序列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,1,1…数一下前60项里有8个7。而且因为只跟个位有关这个周期会一直重复下去。所以答案 202202011200 // 60 * 8 269602681602.5 踩坑记录不要硬算2022亿项Python也跑不动必须找周期。只保留个位cur (a b) % 10这样数字不会越界。周期验证多跑几组确认周期确实是60不要只看一组就下结论。三、第二题小蓝做实验难度⭐⭐⭐⭐3.1 题目大意给定一个文件primes.txt里面有很多数字。判断其中有多少个是质数。数字范围很大有些可能超过 10^8。3.2 解题思路这题分两部分处理小于等于 10^8 的数用埃氏筛预处理所有质数然后 O(1) 判断大于 10^8 的数直接试除法判断因为这类数不会太多埃氏筛的时间复杂度是 O(n log log n)对于 10^8 来说在Python里有点悬但实际测试可以通过。3.3 代码实现fopen(primes.txt,r,encodingutf-8)txtf.read().split()# 按位数分开处理arr1[int(i)foriintxtiflen(i)8]# 小于等于10^8arr2[int(i)foriintxtiflen(i)8]# 大于10^8# 埃氏筛defselects(n):primes[True]*(n1)primes[0]primes[1]Falsep2whilep*pn:ifprimes[p]:foriinrange(p*p,n1,p):primes[i]Falsep1returnprimes n10**8ans0primeselects(n)# 小于等于10^8的数直接查表foriinarr1:ifprime[i]:ans1# 大于10^8的数试除法判断foriinarr2:is_primeTrueforjinrange(2,int(i**0.5)1):ifi%j0:is_primeFalsebreakifis_prime:ans1print(ans)3.4 踩坑记录埃氏筛的内存10^8 的布尔数组大概占 100MB要注意内存限制。试除法优化只需要判断到 sqrt(n) 即可不要傻乎乎地遍历到 n。文件读取f.read().split()可以直接按空白字符分割不用一行行读。大数处理大于 10^8 的数如果很多试除法会超时但这题数据量应该不大。四、第三题取模难度⭐⭐⭐⭐4.1 题目大意给定 n 和 m问是否存在两个不同的数 x, y1 ≤ x y ≤ m使得 n mod x n mod y。4.2 解题思路这题如果暴力枚举 x 和 y时间复杂度是 O(m²)对于大数会超时。需要用数论推导。关键思路反证法。假设不存在这样的 x 和 y那么对于所有 1 ≤ x y ≤ m都有 n mod x ≠ n mod y。这意味着 n mod 1, n mod 2, …, n mod m 这 m 个余数互不相同。但余数的范围是 0 到 x-1所以n mod 1 0唯一可能的值n mod 2 必须是 1因为0已经被占了n mod 3 必须是 2…n mod m 必须是 m-1也就是说如果存在解必须满足 n % i i - 1 对所有 i ∈ [1, m] 成立。反过来只要存在一个 i 使得 n % i ≠ i - 1就一定存在解。4.3 代码实现importsysinputsys.stdin.readline Tint(input())for_inrange(T):n,mmap(int,input().split())flagTrueforiinrange(1,m1):ifn%i!i-1:print(Yes)# 存在这样的x,yflagFalsebreakifflag:print(No)# 不存在4.4 证明过程为什么 n % i i - 1 对所有 i 成立时就不存在解因为如果 n % i i - 1那么 n 1 能被 i 整除因为 n k*i (i-1)所以 n1 (k1)*i。也就是说 n 1 是 1, 2, …, m 的公倍数。只有当 n 1 是 lcm(1,2,…,m) 的倍数时才可能。对于一般的 n 和 m这种情况几乎不可能发生所以大部分情况下答案都是 “Yes”。4.5 踩坑记录不要暴力O(m²) 的暴力在 m 很大时会超时必须推导数学规律。反证法的逻辑想清楚不存在解的充要条件是什么。边界情况m1 时不存在两个不同的数直接输出 “No”。五、第四题内存空间难度⭐⭐⭐⭐5.1 题目大意给定一段类似 C/C 的代码统计其中声明的变量占用的总内存空间。涉及三种类型int占 4 字节long占 8 字节String字符串类型每个字符占 1 字节不算引号变量声明格式int a1,b2;—— 普通变量每个占 4 字节int arr[10];—— 数组占 4*10 40 字节int arr[10][20];—— 多维数组占 41020 800 字节String shello;—— 字符串占 5 字节String shello,tworld;—— 多个字符串最后把总字节数转换成人类可读格式B/KB/MB/GB每 1024 进一位。5.2 解题思路这题是字符串解析模拟。需要逐行解析代码识别变量类型计算每种变量占用的空间。核心逻辑判断类型int/long/String判断是否是数组看有没有[]如果是数组解析维度并计算元素个数如果是普通变量统计的个数每个对应一个变量如果是 String解析引号内的字符数5.3 代码实现importosimportsys tint(input())ans0for_inrange(t):k0cur0sinput().strip()ifs[0]i:# int 类型k4ifs[3:5][]:# 是数组ss[5:]# 解析多维数组的维度whiles.find([)!-1:sts.find([)1eds.find(])curint(s[st:ed])ss[ed1:]ansk*curelse:# 普通变量# 统计 的数量每个 对应一个变量whiles.find()!-1:cur1ss[s.find()1:]ansk*curelifs[0]l:# long 类型k8ifs[4:6][]:# 是数组ss[6:]whiles.find([)!-1:sts.find([)1eds.find(])curint(s[st:ed])ss[ed1:]ansk*curelse:# 普通变量whiles.find()!-1:cur1ss[s.find()1:]ansk*curelse:# String 类型whiles.find()!-1:# 找到双引号的位置sts.find()1ifs.find(,)!-1:eds.find(,)-1else:eds.find(;)-1ansed-st ss[ed2:]# 转换成人类可读格式dans[B,KB,MB,GB]stpos0whileans!0:ifans%1024!0:ststr(ans%1024)dans[pos]st ans//1024pos1print(st)5.4 踩坑记录数组维度解析多维数组如arr[10][20]需要循环解析每个[]里的数字然后相乘。int 和 long 的区别int后面数组从第3位开始判断int[]long从第4位开始long[]。String 的引号是英文双引号不是中文引号解析时要注意。多个变量int a1,b2;这种一行多个变量的情况要通过统计的数量来判断变量个数。单位转换每 1024 进一位从 B - KB - MB - GB注意是除法取余的方式转换。六、今日总结题目核心算法关键技巧易错点斐波那契与7找规律个位周期不要硬算大数小蓝做实验质数筛试除埃氏筛预处理内存限制、大数处理取模数论推导反证法暴力会超时内存空间字符串解析正则/字符串操作数组维度、引号类型今天这四道题覆盖了国赛常见的几种题型填空题找规律是王道硬算必死质数题埃氏筛是标配大数据要分治数论题多想想数学推导少写暴力循环模拟题细心处理字符串注意各种边界情况国赛的前四道大题难度其实还好关键是时间分配。填空题如果5分钟没思路就先跳过大题先把暴力分拿到再考虑优化。明天继续肝国赛后几道题兄弟们一起加油七、附录相关知识点复习数论基础模运算性质、反证法、鸽巢原理质数算法埃氏筛、欧拉筛、Miller-Rabin素性测试字符串处理find、切片、正则表达式找规律技巧只保留低位、模拟找周期如果觉得有帮助欢迎点赞收藏有问题评论区见
