G

平局对答案没有贡献，不用考虑。如果 $x< y$，Alice 必须连续赢 $k = \lfloor\dfrac{y}{x} \rfloor$ 场，转移到 $x>y$ 状态，概率为 $p_0^k$。$x>y$ 时，Alice 取胜的方式有两种可能，一种是在输掉 $i-1$ 局后，赢下第 $i$ 局，$i< \lfloor\dfrac{y}{x} \rfloor$，概率可以用等比数列求和算出；另一种是连续输掉 $k = \lfloor \dfrac{y}{x} \rfloor$ 场，转移到 $x< y$，概率为 $p_1^k$。在两种状态之间相互转移，直到边界，时间复杂度 $O(\log n)$（类比辗转相除法）。

J

$\sum v_i-c_i\times W = \sum v_i - \sum c_i\times W$，最小化压缩后的体积实际上就是最大化 $\sum c_i\times W$，显然是排序 + 贪心。我们可以使用微扰法确定比较函数：相邻的两个箱子 $k,k+1$ 交换位置，只改变了这两个位置的贡献，对上下都没有影响，所以不妨只看这两个箱子。记 $W$ 为两个箱子上方的总重量，则不对换时贡献为 $c_k\times W + c_{k+1}\times (W+w_k)$，对换后贡献为 $c_{k+1}\times W + c_k\times (W+w_{k+1})$，相减得 $c_{k+1}\times w_k - c_k\times w_{k+1}$，得出比较函数为 $w_i\times c_j > w_j\times c_i$。时间复杂度 $O(n\log n)$。

I

考虑从 $n$ 的二进制表示转换到平衡三进制表示，我们的构造方法是，把二进制数分成若干以 1 结尾的小段，比如 1202 = 010010110010 = 01 001 01 1 001 0。把这些形如 00...01 的段变成 1Z...ZZ，比如上面的 1202 变成 1Z 1ZZ 1Z 1 1ZZ 0。如果最后有 1 个 0，直接输出；有 2 个及以上的 0 则无解。