感觉有很多神秘交互题.
然后他们的思路和传统题好像截然不同…
CF1354G
最多有1000个位置,每个位置上放了一个石头或者一个礼物.
礼物一定比石头轻,石头一定一个重量.
现在你有一杆秤,每次会告诉你左边重,右边重还是一样重(你能一次选好多个位置上的东西放一起比较).
你有最多50次询问,要求找到一个保证是礼物的位置,礼物数量不会超过 n/2 .
神秘的询问次数.
题解说,我们如果能找到一个必然是石头的位置,那么我们就可以通过倍增在log次数内找到第一个是礼物的位置.
例如:1是石头,找2如果轻说明是礼物,否则也是石头,然后用这俩判断[3,4],递推.
问题在于我们怎么找到这个石头.
观察发现50-log的15还剩35,机会很多,考虑随机化…
我们假设1是石头,在剩下的序列里面随机抽几个位置和1比,如果存在一个大于的就说明不是石头.
因为礼物概率小于1/2,所以正确的概率不低于 (1/2)^t,t是抽查次数.