2023信奥赛C++提高组csp-s复赛真题及题解：密码锁
2023信奥赛C++提高组csp-s复赛真题及题解：密码锁
题目描述
小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从0 00到9 99的数字。每个拨圈都是从0 00到9 99的循环，即9 99拨动一个位置后可以变成0 00或8 88，
因为校园里比较安全，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。
当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将密码锁从0 0 1 1 5 \tt{0\;0\;1\;1\;5}00115转成1 1 1 1 5 \tt{1\;1\;1\;1\;5}11115，但不会转成1 2 1 1 5 \tt{1\;2\;1\;1\;5}12115。
时间久了，小 Y 也担心这么锁车的安全性，所以小 Y 记下了自己锁车后密码锁的n nn个状态，注意这n nn个状态都不是正确密码。
为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部n nn个状态。
输入格式
输入的第一行包含一个正整数n nn，表示锁车后密码锁的状态数。
接下来n nn行每行包含五个整数，表示一个密码锁的状态。
输出格式
输出一行包含一个整数，表示密码锁的这n nn个状态按照给定的锁车方式能对应多少种正确密码。
输入输出样例 1
输入 1
1 0 0 1 1 5输出 1
81说明/提示
【样例 1 解释】
一共有81 8181种可能的方案。
其中转动一个拨圈的方案有45 4545种，转动两个拨圈的方案有36 3636种。
【数据范围】
对于所有测试数据有：1 ≤ n ≤ 8 1 \leq n \leq 81≤n≤8。
| 测试点 | n ≤ n\leqn≤ | 特殊性质 |
|---|---|---|
| 1 ∼ 3 1\sim 31∼3 | 1 11 | 无 |
| 4 ∼ 5 4\sim 54∼5 | 2 22 | 无 |
| 6 ∼ 8 6\sim 86∼8 | 8 88 | A |
| 9 ∼ 10 9\sim 109∼10 | 8 88 | 无 |
特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的n nn个状态。
思路分析
这是一个密码锁推理问题。我们需要找到所有可能的初始正确密码，使得这些密码可以通过恰好一次操作变为给定的n个状态。
核心思路
问题转化：给定n个状态，每个状态都是由正确密码通过一次操作得到的。我们需要找出所有可能的正确密码。
操作类型：
- 转动一个拨圈：5个位置，每个位置可以向上/向下转动1~9步（模10运算）
- 同时转动两个相邻拨圈：4组相邻对，每组可以向上/向下转动1~9步（幅度相同）
逆向思维：与其枚举所有可能密码（10^5=100000种），然后检查是否能变为所有n个状态，不如从给定的状态反向推导可能的正确密码。
算法设计
对于每个给定状态，我们可以枚举所有可能的逆操作：
- 单拨圈逆操作：对每个位置，反向转动1~9步
- 双拨圈逆操作：对每对相邻位置，反向转动相同的1~9步
这样对每个状态，我们可以得到最多5×9×2 + 4×9×2 = 162个可能的原密码。
由于n很小（≤8），我们可以：
- 对第一个状态，生成所有可能的原密码集合S1
- 对每个后续状态，生成可能的原密码集合Si
- 求所有Si的交集（同时满足所有状态）
- 过滤掉与给定状态相同的密码
时间复杂度
- 最多8个状态
- 每个状态最多162个可能原密码
- 求交集复杂度不高
- 总计算量约100万次操作，完全可行
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,cnt;inta[10][5];// 存储n个状态intcur[5];// 当前尝试的密码set<int>s,ans;// s用于去重，ans存储最终答案// 将5位密码编码为整数intencode(intx[5]){intres=0;for(inti=0;i<5;i++){res=res*10+x[i];}returnres;}// 检查当前密码cur是否满足所有状态boolcheck(){// 对每个给定状态，检查能否通过一次操作从cur得到它for(inti=0;i<n;i++){boolok=false;// 检查单拨圈操作for(intj=0;j<5;j++){intdiff=(a[i][j]-cur[j]+10)%10;// 转动步数if(diff==0)continue;// 不能不动// 其他位置必须相同boolsame=true;for(intk=0;k<5;k++){if(k==j)continue;if(a[i][k]!=cur[k]){same=false;break;}}if(same){ok=true;break;}}if(ok)continue;// 检查双拨圈操作for(intj=0;j<4;j++){intdiff1=(a[i][j]-cur[j]+10)%10;intdiff2=(a[i][j+1]-cur[j+1]+10)%10;if(diff1==0||diff1!=diff2)continue;// 其他位置必须相同boolsame=true;for(intk=0;k<5;k++){if(k==j||k==j+1)continue;if(a[i][k]!=cur[k]){same=false;break;}}if(same){ok=true;break;}}if(!ok)returnfalse;}returntrue;}// 生成所有可能密码voiddfs(intp){if(p==5){intcode=encode(cur);// 避免重复计算同一个密码if(s.find(code)!=s.end())return;s.insert(code);// 检查是否满足所有状态if(check()){ans.insert(code);}return;}// 枚举当前位置的数字0-9for(inti=0;i<10;i++){cur[p]=i;dfs(p+1);}}intmain(){cin>>n;for(inti=0;i<n;i++){for(intj=0;j<5;j++){cin>>a[i][j];}}// 生成所有可能密码并检查dfs(0);// 输出结果cout<<ans.size()<<endl;return0;}功能分析
1. 密码编码
encode()函数将5位数组编码为整数，便于存储和去重
2. 深度优先搜索
dfs()函数枚举所有00000~99999的密码- 使用集合
s去重（虽然实际上不会重复，因为dfs顺序枚举） - 对每个密码调用
check()验证
3. 验证函数check()
- 核心验证逻辑：对每个给定状态，检查能否通过恰好一次操作从当前密码
cur得到该状态 - 单拨圈检查：遍历5个位置，检查是否只有该位置不同且差值为1-9
- 双拨圈检查：遍历4对相邻位置，检查是否只有这两个位置不同且差值相同（1-9）
- 必须满足所有n个状态
4. 去重与存储
- 使用
set<int> ans存储所有有效密码，自动去重 - 最终输出
ans.size()得到答案数量
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}