洛谷P9752题解

wangzelin · 2023-11-22 11:46:40 · 个人记录

题目链接

题目链接

题目解法

题目中这种奇怪的数据范围都是在提示题目的解法。

本题中数据范围为 n \le 8，我们发现每个密码都只有5位数，因此我们可以枚举每一种密码，再分别判定能否产生产生锁车后的全部 n 个状态。

时间复杂度为 O(kn)，其中 k = 8\times10^5。

AC代码

#include<bits/stdc++.h>
using namespace std;

int n,a[9][6],sec[6]={-1,-1,-1,-1,-1,-1},ans;

bool check()
{
    int p,q,k;
    for(int i=1;i<=n;i++) //判定能否产生锁车后的每种状态。
    {
        p=-1,q=-1,k=0;
        for(int j=1;j<6;j++) if(a[i][j]==sec[j]) k++;
        if(k<3||k==5) return false;
        if(k==4) continue;
        for(int j=1;j<6;j++)
        {
            if(p==-1&&a[i][j]!=sec[j]) p=j;
            else if(p!=-1&&q==-1&&a[i][j]!=sec[j]) q=j;
        }
        int x=(a[i][p]-sec[p]+10)%10,y=(a[i][q]-sec[q]+10)%10;
        if(p!=q-1||x!=y) return false;
     }
     return true; 
}
void dfs(int k) //搜索每种可能的密码排列
// k 为当前枚举到第 k 位。
{
    if(k>5)
    {
        if(check())
        {
            ans++;
        }
        return ;
    }
    for(int i=0;i<10;i++)
    {
        sec[k] = i;
        dfs(k+1);
        sec[k] = -1;
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<6;j++) cin>>a[i][j];
    dfs(1);
    cout<<ans;
    return 0;
}