$$\huge\color{red}{密码锁——看了就懂!}$$
题目大意
给出$2$组答案,如果一种方案中每一个数字都和答案给出的数字中的每一个都相差不到$2$格,那么称之为合法方案,求所有合法方案数量的总和。具体情况如下:
解释:此时$n=8$,在$1$号轮盘上的答案为$8$,则在$1$号轮盘上,$1,2,6,7,8$号均合法(暖色标识),而$3,4,5$号均不合法(冷色标识)。
题解解法
由于$n$范围极小,可以使用$O(n^3)$级别的暴力。(备注:一般$O(n^3)$数据量不超过$10^8$是不会超时的)
算法步骤:
第一步:封装一个函数,判断任意一环上的任意一个数字是否合法。如下所示:
bool close (int x,int y){//x和y是否能匹配,其中y代表标准答案,x代表被判断的数字
if (abs(x-y)<=2 or abs(x-y)>=n-2) return 1;//如果离标准答案不超过两个数字的差距,那么符合要求
return 0;//(否则)不符合
}
第二步:封装一个函数,判断任意一个方案是否合法。如下所示:
bool OK (int a1,int a2,int a3,int b1,int b2,int b3){//判断可行性
return close(a1,b1) and close(a2,b2) and close(a3,b3);//b1,b2,b3表示答案
}
第三步:暴力枚举,注意$(i,j,k)$组成的是有序数对,所以类似$(1,2,3)$,$(2,3,1)$这种的算是不同的方案。代码如下所示:
int ans=0;//枚举方案+判断可行性
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
for (int k=1;k<=n;++k)//枚举所有可能的方案
if (OK(i,j,k,ans1[1],ans1[2],ans1[3]) or OK(i,j,k,ans2[1],ans2[2],ans2[3]))
++ans;
易错点分析
- 在写$close()$函数时忘记考虑绝对值大于等于$n-2$这种情况(即没有考虑到这些密码组成了一个环);
- 在写$OK()$函数时没有用按位与$and$符号(即没有考虑到这些条件要一并满足);
- 在写暴力枚举时忘记$(i,j,k)$是有序数对,少计算了。
$AC$代码
#include <bits/stdc++.h>
using namespace std;
int n,ans1[5],ans2[5];//定义
bool close (int x,int y){//x和y是否能匹配
if (abs(x-y)<=2 or abs(x-y)>=n-2) return 1;//如果离标准答案不超过两个数字的差距,那么符合要求
return 0;//(否则)不符合
}
bool OK (int a1,int a2,int a3,int b1,int b2,int b3){//判断可行性
return close(a1,b1) and close(a2,b2) and close(a3,b3);
}
int main () {
cin>>n;//输入数据
for (int i=1;i<=3;++i) cin>>ans1[i];
for (int i=1;i<=3;++i) cin>>ans2[i];
int ans=0;//枚举方案+判断可行性
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
for (int k=1;k<=n;++k)//枚举所有可能的方案
if (OK(i,j,k,ans1[1],ans1[2],ans1[3]) or OK(i,j,k,ans2[1],ans2[2],ans2[3]))
++ans;
cout<<ans;//输出答案
return 0;
}
声明
本蒟蒻写的题解可能有误,不喜勿喷!(作者:陆修远)