Next Topic

复赛一：密码锁(lock)

信息学奥赛历年真题 2023年CSP提高组真题复赛一：密码锁(lock)

洛谷：P9752
OJ：P5959

这个代码的主要目标是计算出有多少种可能的正确密码，能够通过小 Y 所采用的锁车方式生成输入给出的所有锁车后的密码状态。下面是对代码的详细分析和逻辑解释：

1. 变量定义

n：表示锁车后的状态数。
ans：表示符合条件的正确密码的数量。
ripwd[5]：存储当前遍历到的密码组合。
wrpwd：用于存储输入的所有锁车后的状态，大小为 n×5，其中每一行包含一个密码状态。
cnt：用于存储当前密码和某一个锁车后的密码状态的不同位置。

2. `check()` 函数

这个函数用于判断当前遍历到的 ripwd 密码是否能够通过小 Y 的锁车规则生成所有的锁车状态。具体逻辑如下：

遍历每一个锁车后的状态 wrpwd[i]，通过对比每一个拨圈的位置来计算当前密码 ripwd 与锁车状态 wrpwd[i] 的差异。
如果当前密码和锁车状态 wrpwd[i] 只有一位数字不同，则这个状态可以合法生成，不需要再进一步判断。
如果有两位数字不同，需要确保这两个数字是相邻的拨圈，并且它们的转动幅度必须相同（通过取模运算 (ripwd[x]-wrpwd[i][x]+10)%10 来处理圆形拨圈的性质）。如果两个拨圈的转动幅度不一致，则返回 false。
如果差异的位置超过两位，或者差异的两位数字不相邻，也返回 false。
如果当前密码能够合法生成锁车后的所有状态，则返回 true。

3. `dfs()` 函数

该函数用于遍历所有的可能密码组合。由于密码锁的每个拨圈都有10个数字，因此总共有 10^5 种可能的密码组合。代码通过深度优先搜索（DFS）遍历所有组合，并通过 check() 函数来判断每一个组合是否符合条件。具体步骤为：

递归地对每一位拨圈从 0 到 9 尝试每一个数字，并将其存入 ripwd 数组中。
当递归到第五位时，调用 check() 函数判断当前组合是否能生成所有的锁车状态。
如果符合条件，则将 ans 加 1，表示找到了一个符合条件的密码组合。

4. 主函数 `main()`

首先从输入中读取锁车后的状态数 n 和状态数组 wrpwd。
然后调用 dfs() 函数，遍历所有可能的正确密码组合。
最后输出符合条件的密码组合的数量 ans。

代码逻辑小结

该程序的主要逻辑是通过递归遍历所有可能的密码组合，并使用 check() 函数检查当前密码是否符合小 Y 的锁车规则。根据题意，锁车规则要求每次锁车时，最多只有一个拨圈被转动，或者相邻的两个拨圈被相同幅度地转动。通过深度优先搜索和对每个密码状态的详细检查，程序可以确定有多少种可能的正确密码。

性能分析

由于密码锁的每一位有 10 种可能，总共有 10^5 种密码组合。程序使用递归枚举了所有的密码组合，并且每次检查时需要遍历所有的状态。因此时间复杂度大致为 O(10^5 * n)，其中 n 是锁车后的状态数。在实际中，这样的复杂度应该可以接受。

/**************************************************************** 
 * Description: 2023_CSP_S_复赛第一题
 * Author: Alex Li
 * Date: 2024-07-11 13:01:49
 * LastEditTime: 2024-07-15 17:45:11
****************************************************************/
#include <iostream>
#include <vector>
using namespace std;

const int N=10;
vector< vector<int> >  wrpwd;//动态数组，存n种状态
int n,ans,ripwd[5]; //n是有几种状态，ans是结果，ripwd[5]可行的密码组合

bool check(){
    for(int i=0;i<n;i++){
        vector<int> cnt; //统计对应位数字不同的位置
        for(int j=0;j<5;j++)
            if(ripwd[j]!=wrpwd[i][j])cnt.push_back(j);
        if(cnt.empty()||cnt.size()>2) return false; //不同只能是1位或都2位，其它都不可能。
        //如果只有一位不同，肯定可以匹配，所以不做判断。
        //如果有两位不同需要判断
        if(cnt.size()==2){
            int x=cnt[0], y=cnt[1];
            if(x+1!=y&&y+1!=x) return false;
            int dx=(ripwd[x]-wrpwd[i][x]+10)%10;//因为锁是圆形，需要需要把差值取模
            int dy=(ripwd[y]-wrpwd[i][y]+10)%10;
            if(dx!=dy)return false;  //如果两个位置转动位移不同，不是有效密码
        }
    }
    //   for(int i=0;i<5;i++)cout<<ripwd[i]<<' '; //输出密码
    //  cout<<'\n';
return true;
}

//遍历所有的密码可能行,总共有10^5种
void dfs(int dep){
    if(dep>=5){
        if(check())ans++; //对每种密码组合用check函数做检测
        return;
    }
    for(int i=0;i<=9;i++){
        ripwd[dep]=i;
        dfs(dep+1);
    }
}
int main(){
    cin>>n;
    wrpwd.resize(n,vector<int>(5));  //动态数组初始化。
    //读入n种状态
    for(int i=0;i<n;i++){
        for(int j=0;j<5;j++){
            cin>>wrpwd[i][j];
        }
    }
   //cout<<'\n';
   //搜索所有的可能密码组合
   dfs(0);
  
   cout<<ans<<endl;
}

/*----------------------------------------------------------------
1
0 0 1 1 5
81

2
2 8 3 5 5
2 8 3 5 1
10

2
0 3 7 3 8
0 3 6 7 8
6
*/

Previous Lesson

Back to Lesson

Next Topic

信息学奥赛历年真题