Yukari的博客

博客

2024ICPC网络赛2 题解

2024-09-23 12:54:07 By Yukari

G

平局对答案没有贡献,不用考虑。如果 x<y,Alice 必须连续赢 k=yx 场,转移到 x>y 状态,概率为 pk0x>y 时,Alice 取胜的方式有两种可能,一种是在输掉 i1 局后,赢下第 i 局,i<yx,概率可以用等比数列求和算出;另一种是连续输掉 k=yx 场,转移到 x<y,概率为 pk1。在两种状态之间相互转移,直到边界,时间复杂度 O(logn)(类比辗转相除法)。

J

vici×W=vici×W,最小化压缩后的体积实际上就是最大化 ci×W,显然是排序 + 贪心。我们可以使用微扰法确定比较函数:相邻的两个箱子 k,k+1 交换位置,只改变了这两个位置的贡献,对上下都没有影响,所以不妨只看这两个箱子。记 W 为两个箱子上方的总重量,则不对换时贡献为 ck×W+ck+1×(W+wk),对换后贡献为 ck+1×W+ck×(W+wk+1),相减得 ck+1×wkck×wk+1,得出比较函数为 wi×cj>wj×ci。时间复杂度 O(nlogn)

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 则无解。

Yukari Avatar