这是本文档旧的修订版!
给定 $n$ 个磁体,编号 $1\sim n$。磁体有三种类型 $S,N,-$,其中 $-$ 代表无磁性。允许 $n+\lfloor \log n\rfloor$ 次询问。
每次询问选择若干磁体,分成两组,然后用装置测量两组磁体之间的受力。
其中,设第 $i$ 组有 $s_i$ 个 $S$ 型磁体,$n_i$ 个 $N$ 型磁体,则受力为 $s_1s_2+n_1n_2-s_1n_2-s_2n_1$,若受力超过 $n$ 则测量装置损坏。
要求在不损坏装置的前提下在允许询问次数内找到所有无磁性磁体。
数据保证至少有两个有磁性的磁体和一个无磁性的磁体。
每次询问 $1\sim i-1$ 和 $i$ 号磁体两组之间的受力,当受力不为 $0$ 时 $i$ 号磁体一定有磁性,$1\sim i-1$ 中一定恰有一个有磁性磁体。
考虑二分找到 $1\sim i-1$ 中的有磁性磁体,然后用第 $i$ 号磁体检验 $i+1\sim n$ 磁体的磁性。查询次数 $n-1+\lceil \log n\rceil$。
给定 $n$ 枚硬币,初始时 $i$ 号硬币位于位置 $a_i$ 且正面朝上。每次操作可以交换两枚硬币位置同时将两枚硬币翻面。
要求给出方案在至多 $n+1$ 次操作内将所有硬币归位( $i$ 号硬币位于位置 $i$ 且正面朝上)。
首先发现对一个循环,当循环中有两枚硬币反面朝上时,