本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2693 [USACO1.3] 号码锁 Combination Lock - 洛谷【题目描述】农夫约翰的奶牛不停地从他的农场中逃出来导致了很多损害。为了防止它们再逃出来他买了一只很大的号码锁以防止奶牛们打开牧场的门。农夫约翰知道他的奶牛很聪明所以他希望确保它们不会在简单地试了很多不同的号码组合之后就能轻易开锁。锁上有三个转盘每个上面有数字 1 ~n因为转盘是圆的所以 1 和n是相邻的。有两种能开锁的号码组合一种是农夫约翰设定的还有一种“预设”号码组合是锁匠设定的。但是锁有一定的容错性所以在每个转盘上的数字都与一个合法的号码组合中相应的数字相距两个位置以内时锁也会打开。比如说如果农夫约翰的号码组合是 1 , 2 , 3 )预设号码组合是 4 , 5 , 6 )在转盘被设定为 1 , 4 , 5)因为这和农夫约翰的号码组合足够接近或 2 , 4 , 8 )因为这和预设号码组合足够接近时可以打开锁。注意( 1 , 5 , 6 并不会打开锁因为它与任一号码组合都不够接近。给出农夫约翰的号码组合和预设号码组合请计算能够开锁的不同的号码组合的数目。号码是有序的所以 1 , 2 , 3 与 3 , 2 , 1 不同。【输入】输入的第一行是一个整数n代表锁上的数字个数。输入的第二行有三个整数x,y,z代表农夫约翰的号码组合。输入的第三行有三个整数a,b,c代表预设的号码组合。【输出】输出一行一个整数代表能够开锁的组合数目。【输入样例】50 1 2 3 5 6 7【输出样例】249【核心思想】问题分析给定三个转盘的数字范围[ 1 , n ] [1, n][1,n]环形相邻1 和n nn相邻以及两个合法号码组合( x , y , z ) (x, y, z)(x,y,z)和( a , b , c ) (a, b, c)(a,b,c)。锁的容错规则为每个转盘上的数字与任一合法组合中对应位置数字的环形距离≤ 2 \leq 2≤2时锁打开。求能开锁的不同号码组合数。算法选择暴力枚举由于n ≤ 100 n \leq 100n≤100三个转盘的三重循环枚举量最大为10 6 10^6106完全可行环形距离计算利用模运算处理环形结构计算两个数字在环上的最短距离容斥思想分别判断是否满足约翰的组合或预设的组合满足任一即可逻辑或关键步骤读入数据n nn数字个数、约翰的组合( x , y , z ) (x, y, z)(x,y,z)、预设组合( a , b , c ) (a, b, c)(a,b,c)三重枚举i , j , k i, j, ki,j,k分别从1 11到n nn枚举三个转盘的数字环形距离判断对单个转盘位置数字p pp与q qq的环形距离( p − q n ) m o d n (p - q n) \bmod n(p−qn)modn或( q − p n ) m o d n (q - p n) \bmod n(q−pn)modn取较小值条件( x − i n ) m o d n ≤ 2 (x - i n) \bmod n \leq 2(x−in)modn≤2或( i − x n ) m o d n ≤ 2 (i - x n) \bmod n \leq 2(i−xn)modn≤2表示i ii与x xx的环形距离≤ 2 \leq 2≤2组合判断满足约翰组合三个转盘分别与( x , y , z ) (x, y, z)(x,y,z)的距离均≤ 2 \leq 2≤2逻辑与满足预设组合三个转盘分别与( a , b , c ) (a, b, c)(a,b,c)的距离均≤ 2 \leq 2≤2逻辑与满足任一即可开锁逻辑或统计答案满足条件的组合数a n s ansans时间/空间复杂度时间复杂度O ( n 3 ) O(n^3)O(n3)三重循环枚举所有组合空间复杂度O ( 1 ) O(1)O(1)仅需常数级变量环形枚举的核心思想模运算处理环形( p − q n ) m o d n (p - q n) \bmod n(p−qn)modn消除了环形结构的边界问题将 1 和n nn的相邻关系统一处理双向距离取小两个方向( p − q n ) % n (p-qn)\%n(p−qn)%n和( q − p n ) % n (q-pn)\%n(q−pn)%n分别表示顺时针和逆时针距离满足其一≤ 2 \leq 2≤2即表示在容错范围内容斥简化无需显式计算并集直接用逻辑或判断满足约翰或满足预设即可小规模暴力可行n ≤ 100 n \leq 100n≤100时n 3 10 6 n^3 10^6n3106在合理范围内无需复杂优化适用于环形结构、小范围枚举、多条件容斥类问题【解题思路】【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;intn,x,y,z,a,b,c,ans0;intmain(){cinn;// 输入ncinxyz;// 输入约翰的号码组合cinabc;// 输入预设的号码组合for(inti1;in;i){// 三个转盘使用三个for循环for(intj1;jn;j){for(intk1;kn;k){if(((x-in)%n2||(i-xn)%n2)((y-jn)%n2||(j-yn)%n2)((z-kn)%n2||(k-zn)%n2)||((a-in)%n2||(i-an)%n2)((b-jn)%n2||(j-bn)%n2)((c-kn)%n2||(k-cn)%n2)){// 满足转盘向上或向下后的移动次数需要小于等于2ans;// 方案数自增1}}}}coutansendl;// 输出结果return0;}【运行结果】50 1 2 3 5 6 7 249