Loading... ### 0x00 审题 这是一个提交答案题，加法和小于两种运算符，算出 $a\times b$，但是没有输入，并不知道 $a,b$ 具体值，所以需要给出一个策略，使得在所有情况下都可以计算出 $a\times b$。 可以发现，唯一能得到关于 $a,b$ 信息的方法只有比较运算符。 ### 0x01 暴力算法 首先需要找出一个 $1$ 放在内存里面，这是一切计算的基础，方法很简单，把 $a+b$ 算出来，再和 $0$ 比较大小，这样就可以得到一个 $1$。这里可以预先做一些简单的转化，小于很对时候没用，需要的是小于等于，那么如何使用小于等于运算符呢？先加一在比较即可。 要计算 $a\times b$ 最容易想的就是，对答案加 $a$ 次 $b$。但是怎么知道 $a$ 多大呢，存一个零时变量，每次加一，然后与 $a$ 比较，存到一个新的变量里，由于不知道 $a$ 的大小，所以直接重复 $10^9$ 次，得到一个长度为 $a$ 的 $1$ 的序列。同理算出 $b$，然后依次枚举 $a,b$ 序列中两个位置，若两位都是 $1$ 则答案加 $1$，但是怎么判断呢？都是 $1$ 说明两个位置加起来大于 $1$，那么把这两个位置加起来，然后比较出与 $1$ 的大小，把结果累加进入答案即可。 ### 0x02 倍增优化 发现这样做很慢，关键原因在于对 $a$ 的拆解每次都只减少了一，可以一次性多减一些。既然提到对整数的拆解，自然会想到二进制，每次尝试找到最大的 $2^{i}\leq a$ 然后把 $a$ 减去 $2^{i}$，这样想法很好，根据思路设计出这样一个策略： 先预处理出来每个 $2^i$ 放在内存中。从高到低枚举 $2^i$ 然后记录几个个临时变量 $x=0,y,z$ 每次把 $y\leftarrow x+2^{i}$，然后 $z\leftarrow \left[y\leq a\right]$，先把 $z$ 记录在内存中一个位置，用来表示 $a$ 的二进制，记为 $A_i$。现在的问题是如何通过 $z$ 的结果，判断是否给 $x$ 加上 $2^{i}$，充分利用 $z$ 这个变量，直接对 $z$ 进行倍增 $i$ 次，每次 $z\leftarrow z+z$，这样若能拆分则 $z\leftarrow 2^i$ 否则$z=0$，直接把 $z$ 累加进 $x$ 即可。这样就在内存中一段位置得到了 $a$ 的二进制。 同理拆分出来 $b$ 后，考虑如何计算答案，既然得到了二进制拆分，计算两个二进制数的乘积最好方法就是竖式乘法。还是和暴力做法一样，$a,b$ 枚举拆分的两位 $i,j$，然后计算这两位是否都是 $1$，判断方法和刚才一样，记录一个临时变量 $z\leftarrow A_i+B_j$，然后 $z\leftarrow \left[z>1\right]$。这样相当于 $z=A_i \& B_j$（位运算或），拆分 $a,b$ 时一样，如何根据 $z$ 判断是否需要对答案加上 $2^{i+j}$ 次方呢，一样的套路倍增 $z$ 变量 $i+j$ 次后累加进答案即可。 这样的总共会用 $\mathcal{O}\left(\log^3 n\right)$ 次操作已经可以通过了。 ### 0x04 继续优化 $\mathcal{O}\left(\log^3 n\right)$ 很好，但是还能更优，这个算法瓶颈在于最后计算 $2^{i+j}$ 部分，相同的倍增会进行很多次，所以考虑把每一次倍增合并计算。枚举 $k$ 然后，把计算多少个 $i+j=k$ 满足 $A_i \& B_j=1$ 累加进临时变量 $z$，最后把 $z$ 一起倍增 $k$ 次，得到 $z\leftarrow 2^k z$，把 $z$ 累加进答案即可。 这样操作复杂度 $\mathcal{O}\left(\log^2 n\right)$ 有了质的变化，空间复杂度 $\mathcal{O}\left(\log n\right)$（指使用了多少个寄存器）。 ### 0x03 代码实现 有一些小问题： 1. 如何清 $0$ 一个变量，把他和某个为 $0$ 的变量比较 2. 若 $a,b$ 都为 $0$，找不出 $1$ 怎么办？这种情况不需要关注，因为接下俩怎么算答案都是 $0$。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} std::vector<std::tuple<char,int,int,int>> res; int mem[1000]; void cmp(int i,int j,int k){ res.push_back({'<',j,k,i}); mem[i]=mem[j]<mem[k]; } void add(int i,int j,int k){ res.push_back({'+',j,k,i}); mem[i]=mem[j]+mem[k]; } void pow2(int pos,int e){ while(e--) add(pos,pos,pos); } void clear(int pos){cmp(pos,pos,95);} int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i,j; // mem[0]=read(); // mem[1]=read(); add(3,0,1); cmp(3,4,3); add(0,0,3),add(1,1,3); //2^{i} mem[i+3] for(i=1;i<=29;++i) add(3+i,3+i-1,3+i-1); /* *93:val *94:digit *95:zero */ //A mem[32+i+1]=A[i] for(i=29;~i;--i){ add(94,93,3+i);//mem[94]=93+2^i cmp(94,94,0); //mem[94]=93+2^i<=A add(32+i+1,32+i+1,94); pow2(94,i); add(93,93,94); } //B mem[62+i+1]=A[i] clear(93); for(i=29;~i;--i){ add(94,93,3+i);//mem[94]=93+2^i cmp(94,94,1); //mem[94]=93+2^i<=B add(62+i+1,62+i+1,94); pow2(94,i); add(93,93,94); } for(i=0;i<=58;++i){ clear(93); for(j=0;j<=std::min(29,i);++j){ if(i-j>29) continue; add(94,32+(i-j)+1,62+j+1);//get A[i-j]+B[j] cmp(94,3,94); //mem[94]=(A[i-j]+B[j]>1)=A[i-j]*B[j]; add(93,93,94); } pow2(93,i); add(2,2,93); } // printf("%d",mem[2]); print(res.size()),putchar('\n'); for(auto tup:res) printf("%c %d %d %d\n",std::get<0>(tup),std::get<1>(tup),std::get<2>(tup),std::get<3>(tup)); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改：2024 年 05 月 28 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏
2 条评论
123