3 solutions
-
3
这题非常难,其他的两篇题解使用了cout或者printf的高级算法,这里介绍一个基础的做法——手搓 64 位 0.5MB 内存的机器码虚拟机。
这是虚拟机框架:
#include<bits/stdc++.h> using namespace std; #define int long long #define ull unsigned int #define N 65536 int memory[N]; ull code[N] = { }; /* 0 Input 1 Output 2 Write 3 Copy 4 Calculate (& | ~ ^ << >>) 5 Calculate (+ - * / %) 6 Goto 7 If-goto 8 x++ 9 x-- f Exit */ signed main() { for(int i=0;;i=(i+1)%N) { int op=code[i]>>60; if(op==0) //Input { int p=code[i]&65535; cin >> memory[ (code[i]>>56)&1 ? memory[p] : p ]; } else if(op==1) //Output { int p=code[i]&65535, val = memory[ (code[i]>>56)&1 ? memory[p] : p ]; if((code[i]>>57)&1) { cout<<char(val&127); } else { cout<<val; } } else if(op==2) //Write { int p = (code[i]>>32)&65535, val = code[i]&((1ll<<32)-1); memory[ (code[i]>>56)&1 ? memory[p] : p ] = val; } else if(op==3) //Copy { int pf = (code[i]>>16)&65535, pt = code[i]&65535; int val = memory[ (code[i]>>55)&1 ? memory[pf] : pf ]; memory[ (code[i]>>56)&1 ? memory[pt] : pt ] = val; } else if(op==4) //Calculate (& | ~ ^ << >>) { int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535; int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ], val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3; int op2 = (code[i]>>52)&15; if(op2==0) { val3=val1&val2; } else if(op2==1) { val3=val1|val2; } else if(op2==2) { val3=~val2; } else if(op2==3) { val3=val1^val2; } else if(op2==4) { val3=((val2>>6)?0:val1<<val2); } else { val3=((val2>>6)?0:val1>>val2); } memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3; } else if(op==5) //Calculate (+ - * / %) { //想要乘方的建议自己写一个快速幂, 应该是能写的 int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535; int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ], val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3; int op2 = (code[i]>>52)&15; if(op2==0) { val3=val1+val2; } else if(op2==1) { val3=val1-val2; } else if(op2==2) { val3=val1*val2; } else if(op2==3) { val3=(val2?val1/val2:0); } else { val3=(val2?val1%val2:0); } memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3; } else if(op==6) //Goto { int p=code[i]&65535; i = (code[i]>>56)&1 ? memory[p] : p; i = (i+N-1)%N; } else if(op==7) //If-goto (> < == >= <= !=) { int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535; int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ], val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ]; int op2 = (code[i]>>52)&15; bool flag; if(op2==0) { flag=(val1>val2); } else if(op2==1) { flag=(val1<val2); } else if(op2==2) { flag=(val1==val2); } else if(op2==3) { flag=(val1>=val2); } else if(op2==4) { flag=(val1<=val2); } else { flag=(val1!=val2); } if(flag) { i = (code[i]>>56)&1 ? memory[p3] : p3; i = (i+N-1)%N; } } else if(op==8) //x++ { int p=code[i]&65535; memory[ (code[i]>>56)&1 ? memory[p] : p ]++; } else if(op==9) //x-- { int p=code[i]&65535; memory[ (code[i]>>56)&1 ? memory[p] : p ]--; } else if(op==15) //Exit { break; } else { cout<<"\n\nError: Invalid code\n\n"; } } return 0; }
这是这题的实现:
// 将其复制进代码的第 8 行即可 0x2000000000000048, 0x1200000000000000, //H 0x2000000000000065, 0x1200000000000000, //e 0x200000000000006c, 0x1200000000000000, //l 0x200000000000006c, 0x1200000000000000, //l 0x200000000000006f, 0x1200000000000000, //o 0x200000000000002c, 0x1200000000000000, //, 0x2000000000000057, 0x1200000000000000, //W 0x200000000000006f, 0x1200000000000000, //o 0x2000000000000072, 0x1200000000000000, //r 0x200000000000006c, 0x1200000000000000, //l 0x2000000000000064, 0x1200000000000000, //d 0x2000000000000021, 0x1200000000000000, //! 0x200000000000000a, 0x1200000000000000, //[\n] 0xf000000000000000 //exit
拓展阅读:
将 code 数组设为 0x0000000000000000, 0x0000000000000001, 0x5000000000010002, 0x1000000000000002, 0xf000000000000000 即可达到 A+B Problem 的要求。逐行解析:
0x0000000000000000:输入一个整数,将其存放于内存的 0 号位置; 0x0000000000000001:输入一个整数,将其存放于内存的 1 号位置; 0x5000000000010002:将内存的 0,1 号位置的数相加,并将结果存放在内存的 2 号位置; 0x1000000000000002:将 2 号位置的数以数字形式输出; 0xf000000000000000:退出程序。
Information
- ID
- 11909
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 1
- Tags
- # Submissions
- 56
- Accepted
- 31
- Uploaded By