本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1214 [USACO1.4] 等差数列 Arithmetic Progressions【题目描述】一个等差数列是一个能表示成a , a b , a 2 b , … , a n b ( n ∈ N ) a, ab, a2b, \dots ,anb\space (n \in \mathbb N)a,ab,a2b,…,anb(n∈N)的数列。在这个问题中a aa是一个非负的整数b bb是正整数。写一个程序来找出在双平方数集合{ x ∣ x p 2 q 2 ∧ p , q ∈ N ∩ [ 0 , m ] } \{ x | x p^2 q^2 \wedge p,q \in \mathbb N \cap [0,m]\}{x∣xp2q2∧p,q∈N∩[0,m]}中长度为n nn的等差数列。【输入】第一行一个正整数n nn表示要找的数列长度。第二行一个非负整数m mm表示p , q p,qp,q的上界。【输出】如果没有找到数列输出NONE。如果找到了输出一行或多行每行由二个整数组成a , b a,ba,b。这些行应该以b bb为第一关键字a aa为第二关键字升序排序。所求的等差数列将不会多于10 , 000 10,00010,000个。【输入样例】5 7【输出样例】1 4 37 4 2 8 29 8 1 12 5 12 13 12 17 12 5 20 2 24【核心思想】问题分析给定n nn和m mm在双平方数集合S { p 2 q 2 ∣ 0 ≤ p , q ≤ m } S \{p^2 q^2 \mid 0 \le p, q \le m\}S{p2q2∣0≤p,q≤m}中找出所有长度为n nn的等差数列a , a b , a 2 b , … , a ( n − 1 ) b a, ab, a2b, \ldots, a(n-1)ba,ab,a2b,…,a(n−1)b。要求输出按b bb为第一关键字、a aa为第二关键字升序排列。算法选择筛法标记双平方数用布尔数组f ff标记所有p 2 q 2 p^2 q^2p2q20 ≤ p , q ≤ m 0 \le p, q \le m0≤p,q≤m提取有序集合将所有双平方数按升序存入数组n u m numnum枚举公差和首项外层枚举公差b bb中层枚举首项a aa内层验证连续n nn项是否均为双平方数关键步骤读入n nn数列长度、m mmp , q p, qp,q上界生成双平方数双重循环枚举p , q ∈ [ 0 , m ] p, q \in [0, m]p,q∈[0,m]标记f [ p 2 q 2 ] 1 f[p^2 q^2] 1f[p2q2]1提取有序数组遍历i ii从0 00到N NN若f [ i ] 1 f[i] 1f[i]1则num[cur] i枚举等差数列外层b bb从1 11到num[cur]最大双平方数中层a aa从num[1]到num[cur-1]剪枝若a ( n − 1 ) ⋅ b max_num a (n-1) \cdot b \text{max\_num}a(n−1)⋅bmax_num后续更大的a aa也不可能直接break内层验证k kk从2 22到n nn检查a ( k − 1 ) ⋅ b a (k-1) \cdot ba(k−1)⋅b是否为双平方数若全部n nn项均为双平方数输出a aa和b bb标记flag true输出若flag false输出NONE时间/空间复杂度时间复杂度O ( m 2 max_num ⋅ ∣ S ∣ ⋅ n ) O(m^2 \text{max\_num} \cdot |S| \cdot n)O(m2max_num⋅∣S∣⋅n)筛法O ( m 2 ) O(m^2)O(m2)枚举验证部分取决于双平方数密度空间复杂度O ( N ) O(N)O(N)N 2 m 2 5 N 2m^2 5N2m25布尔标记数组和存储数组枚举验证的核心思想筛法预处理将是否为双平方数的判定预处理为O ( 1 ) O(1)O(1)查询避免每次计算平方和有序集合枚举提取有序数组后按b bb和a aa的顺序自然满足输出排序要求剪枝优化利用a ( n − 1 ) b ≤ max_num a (n-1)b \le \text{max\_num}a(n−1)b≤max_num提前终止不可能的首项枚举验证而非构造不直接构造等差数列而是枚举参数后验证每项的 membership适用于数论集合查询、等差数列枚举、筛法预处理类问题【算法标签】#普及- #数学【代码详解】#includebits/stdc.husingnamespacestd;constintN250*250*25;// 定义数组最大容量m最大250p²q²最大为250²250²125000intn,m;// n为要找的等差数列长度m为p和q的上界intf[N],cur,k;// f[i]标记i是否为双平方数cur记录双平方数的个数k用于循环计数intnum[N];// num数组存储所有双平方数有序boolflag;// flag标记是否找到至少一个等差数列intmain(){cinnm;// 读入数列长度n和p,q的上界m// 第一步生成所有双平方数p²q²其中0≤p,q≤mfor(inti0;im;i)// 枚举pfor(intj0;jm;j)// 枚举qf[i*ij*j]1;// 标记p²q²为双平方数// 第二步将所有双平方数按升序存入num数组for(inti0;iN;i)if(f[i])// 如果i是双平方数num[cur]i;// 加入num数组cur计数加1// 第三步枚举所有可能的等差数列// 外层循环枚举公差ibfor(inti1;inum[cur];i)// 公差i从1到最大双平方数{// 中层循环枚举首项num[j]afor(intj1;jcur-1;j)// 首项从第一个双平方数开始{// 剪枝如果首项加上(n-1)倍公差超过最大双平方数后续更大的首项也不可能直接退出if(num[j](n-1)*inum[cur])break;// 内层循环验证从num[j]开始、公差为i的n项是否都是双平方数for(k2;kn;k)// 验证第2项到第n项if(!f[num[j](k-1)*i])// 如果某项不是双平方数break;// 验证失败退出内层循环// 如果k达到n1说明所有n项都是双平方数找到了一个合法等差数列if(kn1f[num[j](n-1)*i]){coutnum[j] iendl;// 输出首项a和公差bflagtrue;// 标记找到了等差数列}}}// 如果没有找到任何等差数列输出NONEif(!flag)coutNONEendl;return0;}【运行结果】5 7 1 4 37 4 2 8 29 8 1 12 5 12 13 12 17 12 5 20 2 24