Gioush OJ
⌕ 题目搜索注册登录
P1034 · OFFICIAL SOLUTION

P1034 五轮启幽扉 官方题解

Gioush OJ · P1034 五轮启幽扉

五轮启幽扉

【题意简述】

一个密钥包含五个模 1010 意义下的数字。一次试拨可以修改一个转轮，也可以将两个相邻转轮沿相同方向转动相同格数。给出 nn 个试拨后的状态，求可能的原始密钥数量。

【Hint】

【提示】

五个转轮一共只有 10510^5 种状态。枚举原始密钥后，只需判断它与每条记录之间的模差是否对应一次合法试拨。

【数据点 1∼51\sim 51∼5】

特殊性质 A 保证全部记录两两不同，并且只有同一个转轮上的数字发生变化。

若原始密钥还在其他转轮上与记录不同，那么每次试拨都必须同时修改这个转轮和发生变化的转轮。此时两个转轮上的模差应当始终相同，与记录中只有一位变化矛盾。因此，原始密钥的其余四位已经被记录唯一确定。

变化转轮的原始数字可以是 0∼90\sim 9 中任意一个没有在记录中出现的数字。若该数字已经出现，则某条记录会与原始密钥相同，不再对应一次试拨。因此答案为 10−n10-n。

【数据点 6∼106\sim 106∼10】

特殊性质 B 中，全部记录只在一个固定的相邻转轮对上变化，并且两位的变化量始终相同。这些状态位于模 1010 意义下的一条长度为 1010 的轨道上。

原始密钥也必须位于这条轨道上，并且不能等于已经给出的状态。因为记录两两不同，所以答案仍为 10−n10-n。

【数据点 11∼1511\sim 1511∼15】

这一档不再给出满足的是特殊性质 A 还是特殊性质 B。

比较第一条记录与其余记录。若所有非零模差都集中在同一位，则使用单轮轨道；否则寻找唯一的相邻轮对，并检查两个位置的模差是否始终相同，再使用双轮轨道。

一般数据可能同时包含由不同单轮或不同相邻轮对得到的记录，因此无法再把候选限制在同一条轨道上。不过，上述模差判定仍然可以直接用于检查一个给定候选。

【正解】

枚举五个转轮上的数字，得到一个候选原始密钥。对于第 ii 条记录，定义五个模差

dj=(xj−ai,j+10) mod 10,d_j=(x_j-a_{i,j}+10)\bmod 10,

其中 xjx_j 为候选密钥的第 jj 位，ai,ja_{i,j} 为记录的第 jj 位。

令非零模差的数量为 kk：

  • k=0k=0 时，候选密钥与记录相同，没有进行试拨，不合法；
  • k=1k=1 时，恰好修改一个转轮，合法；
  • k=2k=2 时，两个非零模差必须出现在相邻位置，并且数值相同；
  • k>2k>2 时，不可能由一次试拨得到。

一个候选通过全部 nn 条记录的检查时才计入答案。

【正确性证明】

若上述检查通过，则对于每条记录，候选密钥与记录之间恰有一个非零模差，或恰有两个位于相邻位置且相等的非零模差。前者对应一次单轮试拨，后者对应一次相邻双轮同步试拨，因此候选能够产生全部记录。

反过来，若一个原始密钥能够通过一次试拨产生某条记录，那么这次试拨只可能修改一个转轮，或修改两个相邻转轮且变化量相同。它与该记录之间的模差必然满足上述判定。枚举覆盖了全部 10510^5 个密钥，因此算法不会遗漏，也不会重复计算。

特别地，当 n=1n=1 时，单轮试拨共有 5×95\times 9 种反向候选，相邻双轮试拨共有 4×94\times 9 种反向候选，答案为 8181。

【复杂度分析】

共有 10510^5 个候选，每个候选检查 nn 条记录。时间复杂度为 O(105n)\mathcal{O}(10^5n)，空间复杂度为 O(n)\mathcal{O}(n)。

【参考代码】

/*- @Author: Ehundategh- @Date: 2023-10-23 11:49:08- @FilePath: \Code\CSP-S\lock.cpp- @Description: You Steal,I kill */#include <cstdio>#include <cstring>#define MAXN 10using namespace std;int n,Ans=0;int Condition[MAXN][7];bool Try(int a,int b,int c,int d,int e){	for(int i=1;i<=n;i++){		int Da=0,Db=0,Dc=0,Dd=0,De=0,Times=0;		Da=(a-Condition[i][1]+10)%10;		if(Da) Times++;		Db=(b-Condition[i][2]+10)%10;		if(Db) Times++;		Dc=(c-Condition[i][3]+10)%10;		if(Dc) Times++;		Dd=(d-Condition[i][4]+10)%10;		if(Dd) Times++;		De=(e-Condition[i][5]+10)%10;		if(De) Times++;		if(!Times) return false;		if(Times==1) continue;		if(Times==2){			if((Da==Db&&Da!=0)||(Db==Dc&&Db!=0)||(Dc==Dd&&Dc!=0)||(Dd==De&&Dd!=0)) continue;			else return false;		}		if(Times>2) return false;	}	return true;}void Solve(){	scanf("%d",&n);	Ans=0;	for(int i=1;i<=n;i++){		for(int j=1;j<=5;j++){			scanf("%d",&Condition[i][j]);		}	}	if(n==1) printf("81\n");	else{		for(int i=0;i<=9;i++){			for(int j=0;j<=9;j++){				for(int k=0;k<=9;k++){					for(int r=0;r<=9;r++){						for(int o=0;o<=9;o++){							if(Try(i,j,k,r,o)){								Ans++;							}						}					}				}			}		}		printf("%d\n",Ans);	}}int main(){	int c,T;	scanf("%d%d",&c,&T);	while(T-->0) Solve();	return 0;}