首页 > 代码库 > [ZOJ 1009] Enigma (模拟)
[ZOJ 1009] Enigma (模拟)
题目链接：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
接下来就是链表的事情咯。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <string> 4 #include <iostream> 5 #include <cstring> 6 #include <algorithm> 7 #include <cctype> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <iterator> 12 #include <functional> 13 #include <cmath> 14 #include <numeric> 15 #include <ctime> 16 using namespace std; 17 typedef long long LL; 18 typedef pair<int,int> PII; 19 typedef vector<int> VI; 20 #define PB push_back 21 #define MP make_pair 22 #define SZ size() 23 #define CL clear() 24 #define AA first 25 #define BB second 26 #define EPS 1e-8 27 #define ZERO(x) memset((x),0,sizeof(x)) 28 const int INF = ~0U>>1; 29 const double PI = acos(-1.0); 30 31 int m,n; 32 char r[3][30]; 33 int e[3][30]; 34 const int MAX_N = 30*30*30; 35 int tmp[30]; 36 37 struct CircularNode{ 38 int lst[30]; 39 int num; 40 CircularNode *next; 41 CircularNode(int n){ 42 memset(lst,0,sizeof(lst)); 43 num = n; 44 next = NULL; 45 } 46 ~CircularNode(){ 47 if( next ){ 48 delete next; 49 next = NULL; 50 } 51 } 52 }; 53 54 struct CircularList{ 55 CircularNode *rt,*cur; 56 ~CircularList(){ 57 delete rt; 58 } 59 CircularList(){ 60 rt = NULL; 61 } 62 void push_back(int a[],int m){ 63 if( !rt ) { 64 rt = new CircularNode(m); 65 cur = rt; 66 } else { 67 cur->next = new CircularNode(m); 68 cur = cur->next; 69 } 70 71 for(int j=0;j<m;j++){ 72 cur->lst[a[j]] = j; 73 } 74 } 75 }; 76 77 void mapping(int *r,int st){ 78 int cc[30]; 79 for(int i=0;i<m;i++){ 80 cc[i] = ((tmp[i]+r[(tmp[i]-st+m)%m])%m+m)%m; 81 } 82 for(int i=0;i<m;i++){ 83 tmp[i] = cc[i]; 84 } 85 } 86 87 int main(){ 88 int kase = 1; 89 while(scanf("%d",&m),m){ 90 if(kase!=1) puts(""); 91 printf("Enigma %d:\n",kase++); 92 for(int i=0;i<3;i++) scanf("%s",r[i]); 93 for(int i=0;i<3;i++){ 94 for(int j=0;j<m;j++){ 95 e[i][j] = r[i][j] - ‘A‘ - j; 96 // printf("%d ",e[i][j]); 97 } 98 // puts(""); 99 }100 101 102 CircularList *aCircularList = new CircularList;103 104 105 for(int st1=0;st1<m;st1++){106 for(int st2=0;st2<m;st2++){107 for(int st3=0;st3<m;st3++){108 for(int i=0;i<m;i++) tmp[i] = i;109 mapping(e[0],st3);110 // for(int i=0;i<m;i++) printf("%d ",tmp[i]); puts("");111 mapping(e[1],st2);112 // for(int i=0;i<m;i++) printf("%d ",tmp[i]); puts("");113 mapping(e[2],st1);114 // for(int i=0;i<m;i++) printf("%d ",tmp[i]); puts("");115 aCircularList->push_back(tmp,m);116 // for(int i=0;i<m;i++){117 // printf("%d ",aCircularList->cur->lst[i]);118 // }119 // puts("");120 }121 // exit(0);122 }123 }124 125 scanf("%d",&n);126 getchar();127 int kase = 1;128 while(n--){129 CircularNode *p = aCircularList->rt;130 char c;131 while( (c=getchar())!=‘\n‘ ){132 // printf("%d\n",p->lst[c-‘A‘]);133 putchar(‘a‘+p->lst[c-‘A‘]);134 p = p->next;135 if(!p) p = aCircularList->rt;136 }137 puts("");138 }139 140 delete aCircularList;141 }142 return 0;143 }144 145 /*146 6147 FDBCAE148 ABDEFC149 CDAFEB150 1151 ACE152 */
[ZOJ 1009] Enigma (模拟)