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输入 11 0 0 1 1 5输出 181说明/提示【样例 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∼31 11无4 ∼ 5 4\sim 54∼52 22无6 ∼ 8 6\sim 86∼88 88A9 ∼ 10 9\sim 109∼108 88无特殊性质 A保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的n nn个状态。思路分析这是一个密码锁推理问题。我们需要找到所有可能的初始正确密码使得这些密码可以通过恰好一次操作变为给定的n个状态。核心思路问题转化给定n个状态每个状态都是由正确密码通过一次操作得到的。我们需要找出所有可能的正确密码。操作类型转动一个拨圈5个位置每个位置可以向上/向下转动1~9步模10运算同时转动两个相邻拨圈4组相邻对每组可以向上/向下转动1~9步幅度相同逆向思维与其枚举所有可能密码10^5100000种然后检查是否能变为所有n个状态不如从给定的状态反向推导可能的正确密码。算法设计对于每个给定状态我们可以枚举所有可能的逆操作单拨圈逆操作对每个位置反向转动1~9步双拨圈逆操作对每对相邻位置反向转动相同的1~9步这样对每个状态我们可以得到最多5×9×2 4×9×2 162个可能的原密码。由于n很小≤8我们可以对第一个状态生成所有可能的原密码集合S1对每个后续状态生成可能的原密码集合Si求所有Si的交集同时满足所有状态过滤掉与给定状态相同的密码时间复杂度最多8个状态每个状态最多162个可能原密码求交集复杂度不高总计算量约100万次操作完全可行代码实现#includebits/stdc.husingnamespacestd;intn,cnt;inta[10][5];// 存储n个状态intcur[5];// 当前尝试的密码setints,ans;// s用于去重ans存储最终答案// 将5位密码编码为整数intencode(intx[5]){intres0;for(inti0;i5;i){resres*10x[i];}returnres;}// 检查当前密码cur是否满足所有状态boolcheck(){// 对每个给定状态检查能否通过一次操作从cur得到它for(inti0;in;i){boolokfalse;// 检查单拨圈操作for(intj0;j5;j){intdiff(a[i][j]-cur[j]10)%10;// 转动步数if(diff0)continue;// 不能不动// 其他位置必须相同boolsametrue;for(intk0;k5;k){if(kj)continue;if(a[i][k]!cur[k]){samefalse;break;}}if(same){oktrue;break;}}if(ok)continue;// 检查双拨圈操作for(intj0;j4;j){intdiff1(a[i][j]-cur[j]10)%10;intdiff2(a[i][j1]-cur[j1]10)%10;if(diff10||diff1!diff2)continue;// 其他位置必须相同boolsametrue;for(intk0;k5;k){if(kj||kj1)continue;if(a[i][k]!cur[k]){samefalse;break;}}if(same){oktrue;break;}}if(!ok)returnfalse;}returntrue;}// 生成所有可能密码voiddfs(intp){if(p5){intcodeencode(cur);// 避免重复计算同一个密码if(s.find(code)!s.end())return;s.insert(code);// 检查是否满足所有状态if(check()){ans.insert(code);}return;}// 枚举当前位置的数字0-9for(inti0;i10;i){cur[p]i;dfs(p1);}}intmain(){cinn;for(inti0;in;i){for(intj0;j5;j){cina[i][j];}}// 生成所有可能密码并检查dfs(0);// 输出结果coutans.size()endl;return0;}功能分析1. 密码编码encode()函数将5位数组编码为整数便于存储和去重2. 深度优先搜索dfs()函数枚举所有00000~99999的密码使用集合s去重虽然实际上不会重复因为dfs顺序枚举对每个密码调用check()验证3. 验证函数check()核心验证逻辑对每个给定状态检查能否通过恰好一次操作从当前密码cur得到该状态单拨圈检查遍历5个位置检查是否只有该位置不同且差值为1-9双拨圈检查遍历4对相邻位置检查是否只有这两个位置不同且差值相同1-9必须满足所有n个状态4. 去重与存储使用setint ans存储所有有效密码自动去重最终输出ans.size()得到答案数量各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}