CSP-S 2023 密码锁

原文链接：CSP-S 真题第一讲：密码锁

说明：CSDN和公众号文章同步发布，需要第一时间收到最新内容，请关注公众号【比特正传】。

一、题目背景

题目来源：CSP-J 2023年 T2

题目考察点：模拟、枚举

题目链接：[CSP-S 2023] 密码锁 - 洛谷

题意：
旋转规则：1、只能旋转一次；2、只能旋转一个或相邻两个同一方向和同一幅度；

通过以上【旋转规则】可以得到题目给的n个状态，则为正确密码，求解正确密码的数量，

二、题目分析

本题密码锁共5位，每位10个取值，因此密码的总个数为 $10^{5}$ ，可以枚举出所有的密码的可能，然后check一下当前枚举的状态是否可能是正确密码，如果可能，cnt+1，否则忽略即可。

枚举很简单，用5层循环或者dfs搜索都可以，枚举出来后，如何check是不是正确密码呢？

题目提到旋转后的可能状态有n个，本题n<=8，所以可以遍历这n个状态，看是否可以用当前枚举状态A通过上面提到的【旋转规则】得到，再详细一点：对当前枚举状态和n个可能状态分别做差，得到的差数组sub，如果满足1️⃣全为0（如sub=[0,0,0,0,0]）；2️⃣有一个非零，其他全为0（如sub=[0,0,3,0,0]）；3️⃣两个连续相等的非零值，其他全为0（如sub=[0,2,2,0,0]）；满足以上3个中的任意一个即可，如果都不满足，则一定为非正确密码。（如[1,0,1,0,0], [0,0,5,4,0], [1,2,1,5,0]等均为非正确的密码）

三、AC code

结合代码回看上面的分析，更易消化

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

const int N = 10;
int n, a[N][N], cnt = 0;
int cur[N], sub[N];

bool check() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=5; j++) {
			sub[j] = (cur[j]-a[i][j]+10) % 10;	
		}
		if(sub[1]==0 && sub[2]==0 && sub[3]==0 && sub[4]==0 && sub[5]==0) return false;  // 两个密码相等
		int unZero = 0;  // 两个密码对应位置不相等的个数
		for(int j=1; j<=5; j++) {
			if(sub[j] == 0) continue;
			unZero++;
			if(unZero >= 3) return false;  // 大于等于3，转一次肯定无法得到a[i]，因此直接返回false
			if(unZero == 2) {
				if(sub[j-1] != sub[j]) return false;  // 两个不一样，但是这两个没有相连，也不行，返回false
			}
		}
	}
	
	return true;
}

void dfs(int idx) {
	if(idx == 6) {  //共5个密码位
		if(check()) cnt++;   // 此时枚举到了一个状态，check
		return;
	}
	for(int i=0; i<=9; i++) {
		cur[idx]= i;
		dfs(idx+1);
	}
}

int main() {
	cin >> n;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=5; j++) {
			cin >> a[i][j];
		}
	}
	dfs(1);  // 通过dfs搜索所有状态
	cout << cnt << endl;
}

#include "bits/stdc++.h"
using namespace std;
const int N = 10;
int n, a[N][N], cnt = 0;
int cur[N], sub[N];
bool check() {
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=5; j++) {
      sub[j] = (cur[j]-a[i][j]+10) % 10;
    }
    if(sub[1]==0 && sub[2]==0 && sub[3]==0 && sub[4]==0 && sub[5]==0) return false;  // 两个密码相等
    int unZero = 0;  // 两个密码对应位置不相等的个数
    for(int j=1; j<=5; j++) {
      if(sub[j] == 0) continue;
      unZero++;
      if(unZero >= 3) return false;  // 大于等于3，转一次肯定无法得到a[i]，因此直接返回false
      if(unZero == 2) {
        if(sub[j-1] != sub[j]) return false;  // 两个不一样，但是这两个没有相连，也不行，返回false
      }
    }
  }
  
  return true;
}

int main() {
  cin >> n;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=5; j++) {
      cin >> a[i][j];
    }
  }
  for(int i=0; i<10; i++) {
    cur[1] = i;
    for(int j=0; j<10; j++) {
      cur[2] = j;
      for(int k=0; k<10; k++) {
        cur[3] = k;
        for(int t=0; t<10; t++) {
          cur[4] = t;
          for(int x=0; x<10; x++) {
            cur[5] = x;
            if(check()) cnt++;
          }
        }
      }
    }
  }
  cout << cnt << endl;
  return 0;
}