[CSP-S 2023] 密码锁

原题链接

题目描述

小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从 $0$ 到 $9$ 的数字。每个拨圈都是从 $0$ 到 $9$ 的循环，即 $9$ 拨动一个位置后可以变成 $0$ 或 $8$，

因为校园里比较安全，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。

当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将密码锁从 $00115$ 转成 $11115$，但不会转成 $12115$。

时间久了，小 Y 也担心这么锁车的安全性，所以小 Y 记下了自己锁车后密码锁的 $n$ 个状态，注意这 $n$ 个状态都不是正确密码。

为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 $n$ 个状态。

输入格式

输入的第一行包含一个正整数 $n$，表示锁车后密码锁的状态数。

接下来 $n$ 行每行包含五个整数，表示一个密码锁的状态。

输出格式

输出一行包含一个整数，表示密码锁的这 $n$ 个状态按照给定的锁车方式能对应多少种正确密码。

样例 #1

样例输入 #1

1
0 0 1 1 5

样例输出 #1

81

提示

【样例 1 解释】

一共有 $81$ 种可能的方案。

其中转动一个拨圈的方案有 $45$ 种，转动两个拨圈的方案有 $36$ 种。

【样例 2】

见选手目录下的 lock/lock2.in 与 lock/lock2.ans。

【数据范围】

对于所有测试数据有：$1\le n\le 8$。

测试点	$n\le$	特殊性质
$1\sim 3$	$1$	无
$4\sim 5$	$2$	无
$6\sim 8$	$8$	A
$9\sim 10$	$8$	无

特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 $n$ 个状态。

【解析】
部分分，已知当n为1时，答案为81，30分到手。
正解是通过每组数据得到81个可能的正确排列，，统计其中重复的，如果数量为n，即为一个可能的正确排列。
时间复杂度为O（595n）。
代码使用桶排序，对于这个数据量（最大881）任何排序都没问题。
详见代码：

#include <bits/stdc++.h>
using namespace std;
int a[100005];//对可能的正确排列做桶排序
int b[6];//一组数据
int n;
int ans=0;
int main (){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=5;j++){
            cin>>b[j];
        }
        for(int j=1;j<=5;j++){//对第j个数，第j和j+1个数进行还原
            for(int k=1;k<=9;k++){
                int t=0;//用五位整数表示还原的排列
                int d=0;//同时改两个位置的
                for(int m=1;m<=5;m++){
                    if (m==j){
                        t=t*10+(b[m]+k)%10;
                    }else{
                        t=t*10+b[m];
                    }
                    if (j!=5&&(m==j||m==j+1)){
                        d=d*10+(b[m]+k)%10;
                    }else{
                        d=d*10+b[m];
                    }
                }
                a[t]++;
                a[d]++;
            }
        }
    }
    for(int i=0;i<=99999;i++){
        if(a[i]==n){
            ans++;
        }
    }
    cout<<ans;
	return 0;
}