题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1009
题目大意:给你三个转换轮,只有当第一个转换轮转动一圈后第二个才会转,当第二个转动一圈后第三个才会转。转换轮的意思是我按动一个按钮,显示器经过转换轮的转换显示另外一个字母。每按下一个按钮,第一个转换轮都会转动一次。
叉姐说得好,多学习一下思维方法,有些问题都是能够很高效率的想出来的。脑洞什么的全是骗人的。
注意看这张图:
中间转动轮的点, 左右两边是一一对应的。
也就是说,无论转动轮怎么转,都能把左边的keyboard和右边的display一一对应上,不重不漏。
那么,我们给rotor左边的接口依次标号1,2,3,4,5,6 并且根据第一个状态读出对应关系。即1,-1,1,2,0,-3
经过对应关系,我们把keyboard上的标为A集合{a,b,c,d,e,f} 经过对应关系B {1,-1,1,2,0,-3}, 得到 {a+1,b-1,c+1,d+2,e+0,f-3} => {b,a,d,f,e,c}
然后再经过一层对应关系C {0,0,1,1,1,-3} => {b,a,e,f,c,d} ,注意第二个关系是把a+0,b+0,c+1,d+1,f+1,e-3,也就是说不管上一个映射怎么变,这一个还是对abcdef进行映射。
那么,这就可以列出来转移映射关系式了: cc[i] = tmp[i]+r[tmp[i]];
再加上偏移:cc[i] = tmp[i]+r[((tmp[i]-st)%m+m)%m]
再对整个做负数处理:cc[i] = ((tmp[i]+r[((tmp[i]-st)%m+m)%m])%m+m)%m
我就是这里没想好,卡了好久。
到这里,题目就做了一大半。
接下来,我们发现A经过三次映射到了D
那么也就是说我们可以把中间的关系合并起来 A -> D。
表示成f(A) = D
那么求反函数即可g(D) = A
接下来就是链表的事情咯。
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include <functional>
#include <cmath>
#include <numeric>
#include <ctime>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define PB push_back
#define MP make_pair
#define SZ size()
#define CL clear()
#define AA first
#define BB second
#define EPS 1e-8
#define ZERO(x) memset((x),0,sizeof(x))
const int INF = ~0U>>;
const double PI = acos(-1.0); int m,n;
char r[][];
int e[][];
const int MAX_N = **;
int tmp[]; struct CircularNode{
int lst[];
int num;
CircularNode *next;
CircularNode(int n){
memset(lst,,sizeof(lst));
num = n;
next = NULL;
}
~CircularNode(){
if( next ){
delete next;
next = NULL;
}
}
}; struct CircularList{
CircularNode *rt,*cur;
~CircularList(){
delete rt;
}
CircularList(){
rt = NULL;
}
void push_back(int a[],int m){
if( !rt ) {
rt = new CircularNode(m);
cur = rt;
} else {
cur->next = new CircularNode(m);
cur = cur->next;
} for(int j=;j<m;j++){
cur->lst[a[j]] = j;
}
}
}; void mapping(int *r,int st){
int cc[];
for(int i=;i<m;i++){
cc[i] = ((tmp[i]+r[(tmp[i]-st+m)%m])%m+m)%m;
}
for(int i=;i<m;i++){
tmp[i] = cc[i];
}
} int main(){
int kase = ;
while(scanf("%d",&m),m){
if(kase!=) puts("");
printf("Enigma %d:\n",kase++);
for(int i=;i<;i++) scanf("%s",r[i]);
for(int i=;i<;i++){
for(int j=;j<m;j++){
e[i][j] = r[i][j] - 'A' - j;
// printf("%d ",e[i][j]);
}
// puts("");
} CircularList *aCircularList = new CircularList; for(int st1=;st1<m;st1++){
for(int st2=;st2<m;st2++){
for(int st3=;st3<m;st3++){
for(int i=;i<m;i++) tmp[i] = i;
mapping(e[],st3);
// for(int i=0;i<m;i++) printf("%d ",tmp[i]); puts("");
mapping(e[],st2);
// for(int i=0;i<m;i++) printf("%d ",tmp[i]); puts("");
mapping(e[],st1);
// for(int i=0;i<m;i++) printf("%d ",tmp[i]); puts("");
aCircularList->push_back(tmp,m);
// for(int i=0;i<m;i++){
// printf("%d ",aCircularList->cur->lst[i]);
// }
// puts("");
}
// exit(0);
}
} scanf("%d",&n);
getchar();
int kase = ;
while(n--){
CircularNode *p = aCircularList->rt;
char c;
while( (c=getchar())!='\n' ){
// printf("%d\n",p->lst[c-'A']);
putchar('a'+p->lst[c-'A']);
p = p->next;
if(!p) p = aCircularList->rt;
}
puts("");
} delete aCircularList;
}
return ;
} /*
6
FDBCAE
ABDEFC
CDAFEB
1
ACE
*/