P9752 [CSP-S 2023] 密码锁 题解

分析

最水 S 组 T1。

每次可以转动一个拨圈，或者转动相邻的两个拨圈，且幅度相同。那么就有一个简单粗暴的思路，枚举修改的方案，用 vector 来储存修改后的方案，存到 map 当中，当然也可以转换为数字存进去。

切记要用两个 map 来储存，一个存方案，下文称为 \(mp\)，一个存这个方案在这个状态下出现过了没有，下文称为 \(vis\)。

• 若这个方案没在这个状态下出现过：将他存入 \(mp\)，他的出现次数增加一次，\(vis\) 标记。
• 若这个方案在这个状态下出现过：跳过。

最后答案统计，将 \(mp\) 遍历一遍，出现次数为 \(n\) 的个数就是答案。

Accepted Code

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int a[N], ans;
map<int, bool> vis;
map<int, int> mp;
vector<int> arr(6);
int up(int k, int n){return (k + n >= 10 ? k + n - 10 : k + n);}//向上转动第 k 个拨圈
int down(int k, int n){return (k - n < 0 ? k - n + 10 : k - n);}//向下转动第 k 个拨圈
int zhnum(vector<int> ar)//转化为数字
{
	int x = 0;
	for (int i = 1; i <= 5; i++)x = x * 10 + ar[i];
	return x;
}
void update(int k){if (vis[k])return; mp[k]++; vis[k] = 1;}//新增密码锁可能性
int main()
{
	int T;
	cin >> T;
	for (int i = 1; i <= T; i++)
	{
		vis.clear();//清空
		for (int i = 1; i <= 5; i++)cin >> a[i];
		//暴力枚举
		for (int i = 1; i <= 5; i++)
		{
			for (int pos = 1; pos <= 5; pos++)
			{
				for (int j = 1; j <= 5; j++)
					if (i == j)arr[j] = down(a[j], pos);
					else arr[j] = a[j];
				int k = zhnum(arr);
				update(k);
			}
			for (int pos = 1; pos <= 5; pos++)
			{
				for (int j = 1; j <= 5; j++)
					if (i == j)arr[j] = up(a[j], pos);
					else arr[j] = a[j];
				int k = zhnum(arr);
				update(k);
			}
		}
		for (int i = 1; i <= 4; i++)
		{
			for (int pos = 1; pos <= 5; pos++)
			{
				for (int j = 1; j <= 5; j++)
					if (i == j)arr[j] = down(a[j], pos);
					else if (i == j - 1)arr[j] = down(a[j], pos);
					else arr[j] = a[j];
				int k = zhnum(arr);
				update(k);
			}
			for (int pos = 1; pos <= 5; pos++)
			{
				for (int j = 1; j <= 5; j++)
					if (i == j)arr[j] = up(a[j], pos);
					else if (i == j - 1)arr[j] = up(a[j], pos);
					else arr[j] = a[j];
				int k = zhnum(arr);
				update(k);
			}
		}
	}
	map<int, int>::iterator it = mp.begin();
	for (; it != mp.end(); it++)
		ans += ((*it).second == T);
	cout << ans;
	return 0;
}