题解：P12601 旷野小计算
六个寄存器，真空指令集。\ 限制卡得紧，一堆子问题。\ 先乘解决除，取负能造一。\ 分支不让用，咋判二的幂。\ 与上零负一，创造新奇迹。\ 数除动分母，官解太诡异。\ 溢出不用急，偶数先右移。\ 一错调一天，这题真猎奇。
先放一个经过微调的 checker，能更好的快速对代码进行测试，分屏放代码和 checker 也可以看完所有数据而不让输入输出混淆。简直是 debug 神器。
#include<iostream>
#include<string>
#include<fstream>
#include<sstream>
#include<vector>
#include<map>
#include<cmath>
#include<bitset>
using namespace std;
#define Reg unsigned long long
map<string,Reg> regs;
int line=0;
void die(string msg){
cout<<"Line "<<line<<": "<<msg<<endl<<endl;
//exit(1);
}
Reg& reg(string id){
if(id=="a"||id=="b"||id=="c"||id=="d")id="r"+id+"x";
if(id=="x")id="rsi";
if(id=="y")id="rdi";
if(regs.find(id)==regs.end())die("accessing invalid register: "+id);
return regs[id];
}
Reg num(const string&str){
Reg n=0;
stringstream ss("");
ss<<str;
ss>>n;
return n;
}
char cases[100];
ostream &XXXXX(cout << "Code file : ");
istream &XXX(cin >> cases);
std::ifstream code(cases);
//#define debug4
#ifdef debug4
Reg ch4x, ch4y, ch4d;
#endif
void initreg(int type){
regs["rax"]=regs["rbx"]=regs["rcx"]=regs["rdx"]=regs["rsi"]=regs["rdi"]=0;
int cnt;
cout << "Input register number : ";
cin >> cnt;
if (cnt) {
cout << "Input " << cnt << " register" << (cnt - 1 ? "s :\n" : " :\n");
} else {
cout << "no input";
}
if (cnt) {
cout << "x = ";
cin >> regs["rsi"];
#ifdef debug4
ch4x = regs["rsi"];
#endif
}
if (cnt >= 2) {
cout << "y = ";
cin >> regs["rdi"];
#ifdef debug4
ch4y = regs["rdi"];
#endif
}
if (cases[0] == '1') {
cout << "need\n" << regs["rsi"] * 4080 << endl;
} else if (cases[0] == '2') {
cout << "need\n" << regs["rsi"] / 4080 << endl;
} else if (cases[0] == '3') {
cout << "need\n" << 4080 << endl;
} else if (cases[0] == '4') {
cout << "need\n" << regs["rsi"] * regs["rdi"] << endl;
} else if (cases[0] == '5') {
cout << "need\n" << regs["rsi"] / regs["rdi"] << endl;
} else if (cases[0] == '6') {
cout << "need\n" << (unsigned long long)sqrtl(regs["rsi"]) << endl;
} else if (cases[0] == '7') {
Reg ans = 1;
while (ans < regs["rsi"]) ans <<= 1;
cout << "need\n" << ans << endl;
}
}
int main(){
string cmd;
initreg(0);
while(getline(code,cmd)){
vector<string> toks;
stringstream ss("");
string tok;
// cout << "code = " << cmd << endl;
if (cmd.substr(0, 5) == "print") {
cout << cmd.substr(6) << endl;
continue;
}
if (cmd == "debug_all") {
cout << "debug_all" << endl;
for (string i : {"a", "b", "c", "d", "x", "y"}) {
cout << i << " = " << reg(i) << endl;
}
continue;
}
if (cmd.substr(0, 12) == "debug_all(b)") {
#ifdef debug4
if (cmd[13] == '*') {
if (ch4x & 1)
{
ch4d += ch4y;
}
ch4x >>= 1;
ch4y <<= 1;
}
#endif
cout << "debug_all(b)" << endl;
for (string i : {"a", "b", "c", "d", "x", "y"}) {
cout << i << " = " << bitset<64>(reg(i)) << endl;
#ifdef debug4
if (i == "d") {
cout << "D = " << bitset<64>(ch4d) << endl;
}
#endif
}
continue;
}
if (cmd == "debug") {
cout << "debug" << endl;
for (string i : {
#if 0
"a", "b", "c",
#endif
"d", "x", "y"
}) {
cout << i << " = " << reg(i) << endl;
}
continue;
}
line++;
for(auto a:cmd)if(a==';')break;else ss<<(a==','?' ':a);
while(ss>>tok)toks.push_back(tok);
if(toks.size()<=0)continue;
if(toks.size()==3-(toks[0]=="!"||toks[0]=="?"||toks[0]=="read"||toks[0]=="write")){
string o=toks[0];
if(o=="+"||o=="add")reg(toks[1])+=reg(toks[2]);
else if(o=="-"||o=="sub")reg(toks[1])-=reg(toks[2]);
else if(o=="^"||o=="xor")reg(toks[1])^=reg(toks[2]);
else if(o=="<"||o=="shl")reg(toks[1])<<=num(toks[2]);
else if(o==">"||o=="shr")reg(toks[1])>>=num(toks[2]);
else if(o=="!"||o=="write") {
// cout << reg(toks[1]) << endl;
printf("%30llu\t", reg(toks[1]));
cout << toks[1] << " = " << bitset<64>(reg(toks[1])) << endl;
}
else if(o=="?"||o=="read")cin>>reg(toks[1]);
else if(o=="="||o=="movabs")reg(toks[1])=num(toks[2]);
else if(o=="*"||o=="mul")reg(toks[1])*=reg(toks[2]);
else if(o=="/"||o=="div")reg(toks[1])/=reg(toks[2]);
else die("unknown instruction");
}
else die("unknown instruction or missing arguments");
}
system("pause");
return 0;
}后文若没有明确说明，所有除法都是向下取整。
A
加法进行赋值，位移处理，减法解决。
+ y x
< y 4
< x 12
- x y
! xB
我们只需要试一遍所有不超过
经过尝试，偷看题解，我们找到了合适的
+ y x
< x 7
+ y x
< x 8
+ y x
< x 8
+ y x
< x 8
+ y x
> y 43
! y这只有 11 条指令，出题人，快点把 16 改小。
C
常数节点，哦对不能用。但是我们可以用官方题解。
想要常数，我们可以先想办法把这个值域很大的
一个很妙的做法就是把这个数取负。
如果 (x>>63)+((-x)>>63) 仅可能为
因为
- y x
> x 63
> y 63
+ x y
- a x
> a 52
+ b a
> a 8
- b a
! b这只有 10 条指令，出题人，快点把 16 改小。
D
定义
根据 A 的思路我们想到可以拆位，拆位可以不断把给定的一个数右移（不妨为
于是我们的思路如下：
for i in range(64) :
if x & (1 << i) != 0 :
cnt += y
y <<= 1循环我们展开，位移，累加都好解决，但是这是旷野小计算，指令集很小，没有分支。
我们偷看题解后发现，其实 cnt += y 等价与 cnt += y * (1 if x & (1 << i) != 0 else 0)。
获取
然后
于是我们的量乘问题，一点都没有解决。（是吗？）
我们发现我们的问题变成了求一个数乘 继续偷看题解发现
最后解决
细节：按位与的加法可能超过数据范围，被忽略掉一个最高位，我们发现我们只需要把需要乘的那个
另一个细节：大常数选手指令条数太多了那不全分。我们可以认真思考自己的代码上一步会让寄存器的变量的值赋为什么，针对上一次的赋值范围适当减少初始化指令次数。
776 行，不知道为什么要放那么迷惑的 1024 行作为限制，我曾经以为我的 1200+ 的解很接近正解了，实际上差得远。
用可读性极差的代码，生成不可读的代码，最后眯着眼睛看根本没有可读性的测试输出。T_T
for (int i = 0; i < 64; i++) {
if (i == 63) {
cout << "^ b b" << endl;
}
cout << "+ b x" << endl;
if (i < 63) {
cout << "< b " << 63 - i << endl;
}
cout << "> b 63" << endl; // b = bool(x & (1 << i))
if (i == 0) {
cout << "- x b" << endl;
}
if (i) {
cout << "^ a a" << endl;
cout << "^ c c" << endl;
}
if (i == 0) {
cout << R"(- a b
> a 1
+ c a
+ c y
^ a y
- c a
> c 1
+ d c
> a 63
+ b a
> b 1
< b 63
+ d b
< y 1
> y 1
)";
} else {
cout << R"(- a b
+ c a
+ c y
^ a y
- c a
+ d c
< y 1
)";
}
}
cout << "! d";这只有 776 条指令，出题人，快点把 1024 改小。
E
官解里写的高级语言代码怪怪的，为什么是 > 不是 >=，为什么是 y -= b 不是 x -= y << i？正确性应当被怀疑？
先自己给出一份高级语言的龟速除代码
x, y = map(int, input().split())
d = 0
print(x // y) # 保证正确答案
for i in range(63, -1, -1) :
b = x >> i
if b >= y :
d += 1 << i
x -= y << i
print(d) # 计算出的答案循环自然是手动展开，b >= y 等价与 b - y 的最高位是 0，换句话说，我们只有在
官解里说什么【有 1 << i 这个表达式，所以需要用 case 3 的办法造出常数 (1<<i)*(b-y>>63) 不是可以写成 b-y>>63<<i 吗？
好吧还是似乎需要造个
这里又遇到了 (y << i) & ... 其中 ... 为 x -= y << i！
// 无脑维护，使劲调试，高达十二分！
cout << R"(+ b y
- c y
> b 63
> c 63
- a b
- a c
> a 63
)"; // 造 1 的代码，a = 1
for (int i = 63; i >= 0; i--) {
cout << "^ b b" << endl;
cout << "^ c c" << endl;
cout << "+ b x" << endl;
if (i != 0) cout << "> b " << i << endl;
cout << "- b y" << endl;
cout << "> b 63" << endl; // b = 0 if x >> i >= y else 1
cout << "^ b a" << endl; // b = 1 if x >> i >= y else 0
// 然后 d += b << i
if (i != 0) cout << "< b " << i << endl;
cout << "+ d b" << endl;
if (i != 0) cout << "> b " << i << endl;
if (i != 0) { // 然后 x -= (y << i) & c
cout << "- c b" << endl; // c = 0xffff if x >> i >= y else 0
cout << "> c 1" << endl; // c = 0x7fff if x >> i >= y else 0
cout << "- x c" << endl;
if (i == 1) {
cout << "- x y" << endl;
cout << "^ c y" << endl;
} else {
cout << "^ b b" << endl;
cout << "+ b y" << endl;
cout << "< b " << i - 1 << endl;
cout << "- x b" << endl;
cout << "^ c b" << endl;
}
cout << "+ x c" << endl;
}
}
cout << "! d";突然发现，题目保证
cout << R"(+ b y
- c y
> b 63
> c 63
- a b
- a c
> a 63
)"; // 造 1 的代码，a = 1
for (int i = 31; i >= 0; i--) {
cout << "^ b b" << endl;
cout << "^ c c" << endl;
cout << "+ b x" << endl;
if (i != 0) cout << "> b " << i << endl;
cout << "- b y" << endl;
cout << "> b 63" << endl; // b = 0 if x >> i >= y else 1
cout << "^ b a" << endl; // b = 1 if x >> i >= y else 0
// 然后 d += b << i
if (i != 0) cout << "< b " << i << endl;
cout << "+ d b" << endl;
if (i != 0) cout << "> b " << i << endl;
if (i != 0) { // 然后 x -= (y << i) & c
cout << "- c b" << endl; // c = 0xffff if x >> i >= y else 0
// cout << "> c 1" << endl; // c = 0x7fff if x >> i >= y else 0
cout << "- x c" << endl;
if (i == 1) {
cout << "- x y" << endl;
cout << "^ c y" << endl;
} else {
cout << "^ b b" << endl;
cout << "+ b y" << endl;
cout << "< b " << i - 1 << endl;
cout << "- x b" << endl;
cout << "^ c b" << endl;
}
cout << "+ x c" << endl;
}
}
cout << "! d";如果被允许看官方题解，感觉难度和乘法差不多。
这只有 570 条指令（因为数据范围小），出题人，快点把 1024 改小。
F
开根，困难。
~作者太菜，不会，全力在研究，出不了几天估计就能补上。~
根据 E 题的传奇官解代码出错行为，F 又没有什么做法解释，抛开官解理论部分自己先研究一下。
手撕平方根？曾经数学老师交过，学案丢了。迅速补一下，推荐这个视频。
容易发现，还是降序枚举位，确定到底能不能再放一个
考虑优化，使用手撕平方根算法。何为手撕平方根算法？
计算乘法的复杂度太高了，假设枚举到第
写出高级语言代码进行检测：
x = int(input())
print(x ** 0.5)
a = 0 # a
b = 0 # S
for i in range(31, -1, -1) :
if b + (a << (i + 1)) + (1 << (2 * i)) <= x :
b += (a << (i + 1)) + (1 << (2 * i))
a += 1 << i
print(a)于是式子是正确的，进行优化：
x = int(input())
print(x ** 0.5)
a = 0 # a
b = 0 # S
c = 1 # 官解用的 c 存储 1，跟官解一样吧
for i in range(31, -1, -1) : # 后面的代码就是依照上面的式子模拟
d = a;
d <<= i + 1
d += c << i * 2
# print(d)
# print((a << (i + 1)) + (1 << (2 * i)))
a += ((b + d - 1 - x) % (1 << 64) >> 63) << i
# 这个东西二进制下只有一个 1，可以直接用 (b+d-1-x>>63)<<i 得到
if b + d <= x :
b += d
print(a)这题也会用到前面的“
写代码的过程中，我们发现我们有可能用“相减再取最高位”的方法会出错，因为这题数据范围太大了。为了解决这个问题，我的方法是这样的：外层枚举
比乘法和除法难得多，但是很有趣。（除了做法名字，这题官解我没看，很高兴。）
// 懒得删调试了
cout << R"(+ a x
- b x
> a 63
> b 63
- c a
- c b
> c 63
^ a a
^ b b
)"; // 造 1 的代码，c = 1
for (int i = 31; i >= 0; i--) {
/*
if (i == 31) { // 作者想对 31 再卡卡，但是 WA 了，懒得调，反正 30 处理对了，31 和 30 一个逻辑一起处理了就多几条指令
cout << "^ d d" << endl;
cout << "+ d x" << endl;
cout << "> d 62" << endl;
cout << "^ a a" << endl;
cout << "- a d" << endl;
cout << "> a 63" << endl;
cout << "+ b a" << endl;
cout << "< b 31" << endl;
cout << "< a 62" << endl;
continue;
}
*/
if (i < 31) cout << "^ d d" << endl;
cout << "+ d a" << endl;
if (i < 30)
cout << "< d " << i + 1 << endl;
else
cout << "< d " << i - 1 << endl;
if (i < 30) {
if (i) cout << "< c " << i * 2 << endl;
} else {
cout << "< c " << i * 2 - 2 << endl;
}
cout << "+ d c" << endl;
if (i < 30) {
if (i) cout << "> c " << i * 2 << endl;
} else {
cout << "> c " << i * 2 - 2 << endl;
}
if (i < 31) cout << "^ y y" << endl;
cout << "+ y b" << endl; // 可能会越界，把所有比较操作先右移
if (i >= 30) cout << "> y 2" << endl;
cout << "+ y d" << endl;
cout << "- y c" << endl;
if (i >= 30) {
// 空间不够，覆盖已经据算掉的 d
cout << "^ d d" << endl;
cout << "+ d x" << endl;
cout << "> d 2" << endl;
cout << "- y d" << endl;
// 然后才计算真实的 d
cout << "^ d d" << endl;
cout << "+ d a" << endl;
cout << "< d " << i + 1 << endl;
cout << "< c " << i * 2 << endl;
cout << "+ d c" << endl;
cout << "> c " << i * 2 << endl;
} else {
cout << "- y x" << endl;
}
// cout << "! y" << endl;
cout << "> y 63" << endl;
// 上面计算好了 d 和分支参数 y
// cout << "print add square size=" << endl;
// cout << "! d" << endl;
// cout << "print if y == 1, can add" << endl;
// cout << "! y" << endl;
if (i) cout << "< y " << i << endl;
cout << "+ a y" << endl;
if (i == 0) {
break;
}
cout << "> y " << i << endl;
// 后续如果 y = 1，那么 b += d，否则 b += 0
// 但是寄存器被用完了
// y 的计算需要 d，但是 d 只需要计算原先的 a，原先的 a 需要 y
// 发现先让 -y 覆盖当前的 d，然后把 -y 倒腾会 y 寄存器
cout << "^ d d" << endl;
cout << "- d y" << endl;
cout << "^ y y" << endl;
cout << "+ y d" << endl;
// 用 d 寄存器计算 2 ^ i * -y ，再加一下当前的 a 可以还原上一步结束的 a
if (i) cout << "< d " << i << endl;
// cout << "! d" << endl;
cout << "+ d a" << endl;
cout << "< d " << i + 1 << endl;
// cout << "print c should be 1" << endl;
// cout << "! c" << endl;
if (i) cout << "< c " << i * 2 << endl;
cout << "+ d c" << endl;
if (i) cout << "> c " << i * 2 << endl;
// 上面重新计算 d
// 让后 b += d & y
// d 是矩形新增面积（看我贴链接的那个视频）
// 因为 i>0 才处理，d 和 y 都提前右移是可以的
cout << "> d 1" << endl;
cout << "> y 1" << endl;
// cout << "! d" << endl;
// cout << "! y" << endl;
cout << "+ b d" << endl;
cout << "+ b y" << endl;
cout << "^ y d" << endl;
cout << "- b y" << endl;
// cout << "! a" << endl;
// cout << "! b" << endl;
}
cout << "! a";1000 行，卡得紧，好险。
update 20250617：做复杂了，这题其实不需要“记录
G
为什么官解里管这个问题叫做容量，不清楚，但是可以很快写出高级语言代码。
x = int(input())
x = x - 1
x |= (x >> 1)
x |= (x >> 2)
x |= (x >> 4)
x |= (x >> 8)
x |= (x >> 16)
x |= (x >> 32)
x = x + 1
print(x);意思是：让 topbit 覆盖全部后方的二进制位，然后加一。
首先我们肯定需要根据
后文规定
中间计算过程中，位移是好实现的，按位或可以拆
cout << R"(+ b x
- c x
> b 63
> c 63
- a b
- a c
> a 63
- x a
)";
for (int i : {1, 2, 4, 8, 16, 32}) {
cout << "^ b b" << endl;
cout << "^ c c" << endl;
if (i != 1) {
cout << "^ d d" << endl;
}
cout << "+ b x" << endl;
cout << "> b " << i << endl;
cout << "+ c b" << endl;
cout << "+ c x" << endl;
cout << "+ d b" << endl;
cout << "^ d x" << endl;
cout << "- c d" << endl;
cout << "> c 1" << endl; // c = x & b
cout << "+ x b" << endl; // x' = x + b
cout << "- x c" << endl; // x' = (x + b) - (x & b) = x | b
}
cout << "+ x a" << endl;
cout << "! x";这只有 87 条指令，出题人，快点把 96 改小。
评价
是一个很有意思的题目，难度不是很高（但我支持它是黑，我的意思是，没有旷野大计算难），但是有点 Educational。
BCDE 的限制卡得不严，让人做出一个自己满意的解后会高兴更久。
里面有几个很有趣的 trick 例如按位与先位移后计算避免先计算后位移的加法溢出。
好题，可是洛谷没有 upvote 功能。
完整答案
完整的答案有点小长，放在这里了。