洛谷P2693
https://www.luogu.org/problemnew/show/P2693
JDOJ 2375
https://neooj.com:8082/oldoj/problem.php?id=2375
题目描述
农夫约翰的奶牛不停地从他的农场中逃出来，导致了很多损害。为了防止它们再逃出来，他买了一只很大的号码锁以防止奶牛们打开牧场的门。
农夫约翰知道他的奶牛很聪明，所以他希望确保它们不会在简单地试了很多不同的号码组合之后就能轻易开锁。锁上有三个转盘，每个上面有数字1..N (1 <= N <= 100)，因为转盘是圆的，所以1和N是相邻的。有两种能开锁的号码组合，一种是农夫约翰设定的，还有一种“预设”号码组合是锁匠设定的。但是，锁有一定的容错性，所以，在每个转盘上的数字都与一个合法的号码组合中相应的数字相距两个位置以内时，锁也会打开。
比如说，如果农夫约翰的号码组合是(1,2,3)，预设号码组合是(4,5,6)，在转盘被设定为(1,4,5)（因为这和农夫约翰的号码组合足够接近）或(2,4,8)（因为这和预设号码组合足够接近）。注意，(1,5,6)并不会打开锁，因为它与任一号码组合都不够接近。
给出农夫约翰的号码组合和预设号码组合，请计算能够开锁的不同的号码组合的数目。号码是有序的，所以(1,2,3)与(3,2,1)不同。
输入输出格式
输入格式：
第一行：整数N。
第二行：三个以空格分隔的整数，为农夫约翰的号码组合。
第三行：三个以空格分隔的整数，为预设号码组合（可能与农夫约翰的号码组合相同）。
输出格式：
第一行：所有不同的能够开锁的号码组合的总数。
输入输出样例
输入样例#1： 复制
50 1 2 3 5 6 7
输出样例#1： 复制
249
暴力题。
为什么会想到暴力呢？一共三层循环，数据量不超过100，时间不会爆炸，空间更不会。
一开始的思路是模拟密码锁，开一个二倍的数组来模拟圆盘。然后按照下标枚举+标记。
但是没有A，调试了一波。
丑陋的代码就不往外发了，看到题解上有一篇好的做法，在这里为大家解析一下；
本题的难点无非是处理圆盘，我的想法是倍增，把几个连续数列连在一起，但是人家的方法运用了数学思想，先开了一个三维数组（比较容易枚举）然后从a-2到a+2枚举，处理圆盘用了一个很巧妙的方法：i+n再对n取模，这样就保证了从1-n任意的一个数都有对应的数组下标，然后开始枚举，如果这个位置没被打开过就ans++，并补上标记，如果被开过了就是重复情况，最后轻松ac。
大佬就是大佬，不得不服。
Code:
#include<cstdio> #include<algorithm> using namespace std; int n,ans; int a,b,c,x,y,z; int lock[110][110][110]; int main() { scanf("%d",&n); scanf("%d%d%d%d%d%d",&a,&b,&c,&x,&y,&z); for(int i=a-2;i<=a+2;i++) for(int j=b-2;j<=b+2;j++) for(int k=c-2;k<=c+2;k++) if(lock[(i+n)%n][(j+n)%n][(k+n)%n]==0) { ans++; lock[(i+n)%n][(j+n)%n][(k+n)%n]=1; } for(int i=x-2;i<=x+2;i++) for(int j=y-2;j<=y+2;j++) for(int k=z-2;k<=z+2;k++) if(lock[(i+n)%n][(j+n)%n][(k+n)%n]==0) { ans++; lock[(i+n)%n][(j+n)%n][(k+n)%n]=1; } printf("%d",ans); return 0; }