读题点这里

题意简述

小 Y 拥有一个五个拨圈的密码锁,每个拨圈上标有数字 0099。每个拨圈都可以从 0099 循环。小 Y 采用一种锁车方式:从正确密码开始,随机转动密码锁一次,每次只能以某个幅度转动一个拨圈或者同时转动两个相邻的拨圈。现在小 Y 记下了 nn 个状态,这些状态都不是正确密码。要求找出有多少种可能的正确密码,使得每个正确密码都能按照小 Y 的锁车方式产生这 nn 个状态。

思路分析

给定 nn 个状态,我们要找到能产生这些状态的所有可能的正确密码数量。

首先,当 n=1n=1 时,任意一个密码都能满足条件。因为无论哪个密码,只要按照给定的锁车方式进行一次操作,都能得到这个状态。所以,当 n=1n=1 时,答案是 8181

接下来考虑 n>1n>1 的情况:

  1. 枚举所有可能的正确密码:对于每一个错误状态,我们分别枚举单个拨圈和相邻两个拨圈的所有可能的转动情况,并将其保存在 pass 中。

  2. 判断当前密码能否通过所有的错误密码锁状态转动得到:对于每一个可能的正确密码,我们检查是否能通过所有的错误密码锁状态转动得到。如果能够得到,就将计数器 cnt 增加。 cnt 就是最终的答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;

int n,cnt=0;
string tmp,locks[11];
set<string> pass[11];

int main(){
//freopen("lock.in","r",stdin);
//freopen("lock.out","w",stdout);
cin>>n;
if(n==1){
cout<<81<<endl;
return 0;
}
// 读入密码锁的状态
for(int i=1;i<=n;i++){
for(int j=1;j<=5;j++){
int a;
cin>>a;
locks[i]+=(char)(a+'0');
}
}
// 枚举所有可能的正确密码
for(int i=1;i<=n;i++){
// 计算单个拨圈上可以转动到的数字
for(int j=0;j<5;j++){
for(int k=0;k<=9;k++){
if(locks[i][j]-'0' !=k){
// 将当前数字替换成可以转动到的数字
tmp=locks[i].substr(0,j)+(char)(k+'0')+locks[i].substr(j+1);
// 将当前状态加入到 set 中
pass[i].insert(tmp);
}
}
}
// 计算两个相邻拨圈上可以转动到的数字
for(int j=0;j<4;j++){
for(int k=1;k<=9;k++){
char k1=locks[i][j]+k,k2=locks[i][j+1]+k;
if(locks[i][j]+k>'9') k1=locks[i][j]+k-10;
if(locks[i][j+1]+k>'9') k2=locks[i][j+1]+k-10;
// 将两个相邻拨圈上的数字替换成可以转动到的数字
tmp=locks[i].substr(0,j)+k1+k2+locks[i].substr(j+2);
// 将当前状态加入到 set 中
pass[i].insert(tmp);
}
}
}
// 枚举所有可能的正确密码
for(string i:pass[1]){
bool flag=true;
// 判断当前密码是否能够产生所有的密码锁状态
for(int j=2;j<=n;j++){
if(pass[j].find(i)==pass[j].end()){
flag=false;
break;
}
}
if(flag) cnt++;
}
cout<<cnt<<endl;
return 0;
}