原题
题目描述
小 Y 有一把五个拨圈的密码锁，每个拨圈上是从 0 到 9 的数字。每个拨圈都是从 0 到 9 的循环，即 9 拨动一个位置后可以变成 0 或 8，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将密码锁从 00115 转成 11115，但不会转成 12115。所以小 Y 记下了自己锁车后密码锁的 n 个状态，注意这 n 个状态都不是正确密码。为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 n 个状态。
解题思路
首先，由于密码锁只有五位，所以我们可以对正确密码可能的值进行枚举。现在就只需要判断这个密码是否合法了。
那密码怎么会合法呢?第一:与给出的n个状态不相同且不同的位数为1或2。第二:如果不同的位数为2，就进行判断：如果当前位与密码的这一位的值不相等且下一位相等，则肯定不可以。否则，如果下一位与当前位的差转化为0~9与密码的下一位与当前位的差转化为0~9不等，肯定不可以。
最后统计合法密码的数量就可以了。
#include<bits/stdc++.h> using namespace std; int a[20][10]; int n; bool check(string s){ bool bl=1; for(int i=1;i<=n;i++){ int cnt=0; for(int j=1;j<=5;j++){ if(a[i][j]!=s[j-1]-'0'){ cnt++; } } if(cnt==0||cnt>2)return 0;//如果与给定状态相同或不同的位数大于2，则返回不合法 if(cnt==1)continue; //当不同的位数为二 for(int j=1;j<5;j++){ if(s[j-1]-'0'!=a[i][j]){ if(s[j]-'0'==a[i][j+1]){ //如果当前位与密码的这一位的值不相等且下一位相等 return 0; } else if((s[j-1]-'0'+10-a[i][j])%10!=(s[j]-'0'+10-a[i][j+1])%10){ //如果下一位与当前位的差转化为0~9与密码的下一位与当前位的差转化为0~9不等 return 0; } else break; } } } return 1; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; if(n==1){ cout<<81; return 0; } for(int i=1;i<=n;i++){ for(int j=1;j<=5;j++){ cin>>a[i][j]; } } int cnt=0; for(int i=100000;i<=199999;i++){//枚举正确的密码 int t=i; string s; while(t){ s=char(t%10+'0')+s; t/=10; } s.erase(s.begin());//第一位不用管!! if(check(s)){ cnt++;//密码合法。就统计 } } cout<<cnt; return 0; }
