最近感觉所有要做的题都是在 CF 上的。
然而今天 CF 挂了。
随便点开最近的 AGC。一看,怎么是造计算机题啊。
题意简述
给一个大小为 $N=2\times 10^5$ 的内存池 $a_i$,有两种操作:
+ i j k
,$a_k\gets a_i + a_j$。< i j k
,$a_k\gets [a_i < a_j]$。
注意操作时不需要满足i, j, k
互不相同。
输出一个操作序列使得按序列操作后 $a_2 = a_0\times a_1$。除了 $a_0, a_1$ 外其他元素初始均为 $0$。
记你的操作序列长度为 $Q$,则应保证 $Q\le 2\times 10^5$。
保证非负整数 $a_0,a_1\le 10^9$,所有元素在使用时应保证不大于 $10^{19}$。
主要思路
首先我们会把一个位置 $i$ 设为 $0$:将 $i$ 和某个未使用的位置比较。
其次我们也会把一个位置 $i$ 设为 $1$:将某个未使用的位置和 $a_0 + a_1$ 作比较。
注意到若 $a_0 = a_1 = 0$ 造不出 $1$,但是此时显然无论怎么操作都是 $0$,所以答案也是对的。
其次我们会把一个数左移 $k$ 位:自己加自己 $k$ 次就好了。
那么考虑如何取出一个数 $x$ 的所有二进制位。
先造出所有 $2^k$。
然后从高到低确定每一位即可:
设已经确定的位置的和为 $C$,现在在确定第 $k$ 位。
那么将 $C + 2^k$ 与 $x + 1$ 比较得到 $tmp$ 就是这位是否是 $1$。
最后把 $C\gets C + tmp\times 2^k$ 即可。
于是把 $a_0, a_1$ 的二进制位都取出来,模拟二进制乘法即可。
最终取得了3903
次的答案。感觉还没卡到最优但懒得卡了(
参考代码
1 |
|