为什么考场上一大堆人读错题了啊。顺便祝提高组出题人身体健康。
解法
注意到密码锁只有 $5$ 个拨圈，所以正确密码只有 $00000$ 到 $99999$ 这 $10^5$ 种可能，对于每种可能的正确密码，我们只需要 $\mathcal{O}(n)$ 进行判断就可以了。
我们设我们枚举到的正确密码状态是 $now$，其中 $now_i(i\in[1,5])$ 表示每个拨圈的状态。我们分别验证 $now$ 可不可以拨到每种锁车后的状态。验证方法如下：
- 如果当前状态和当前锁车后的状态有至少 $3$ 个拨圈不相同，则因为转动密码锁仅一次，所以不能当前状态不可能是正确密码。
- 如果当前状态和当前锁车后的状态相同，则因为这 $n$ 个状态都不是正确密码，所以当前状态不可能是正确密码。
- 如果当前状态和当前锁车后的状态有 $2$ 个拨圈不相同，那么如果两个状态不相同的拨圈位置相邻且拨动幅度相同，则当前状态可能是正确密码（还要看是否满足其他锁车后的状态），否则一定不是正确密码。
- 如果当前状态和当前锁车后的状态有 $1$ 个拨圈不相同，则当前状态可能是正确密码（还要看是否满足其他锁车后的状态）。
考场代码
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
int a[100][10],now[10],sub[10];
inline bool judge()
{
for(int i=1,cnt;i<=n;i++)
{
cnt=0;
for(int j=1;j<=5;j++) sub[j]=(a[i][j]-now[j]+10)%10;
if(sub[1]==0 && sub[2]==0 && sub[3]==0 && sub[4]==0 && sub[5]==0) return false;
for(int j=1;j<=5;j++)
{
if(sub[j]==0) continue;
cnt++;
if(cnt>=3) return false;
if(cnt==2)
{
if(sub[j]!=sub[j-1]) return false;
}
}
}
return true;
}
inline void dfs(int dep)
{
if(dep==6)
{
if(judge()) ans++;
return;
}
for(int i=0;i<=9;i++) now[dep]=i,dfs(dep+1);
}
int main()
{
// freopen("lock.in","r",stdin);
// freopen("lock.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=5;j++) cin>>a[i][j];
dfs(1);
cout<<ans;
return 0;
}
