实在是不会改了,我把每个公式和字母数字周围都加了空格,还是过不了审核。麻烦有经验的同学帮忙看看,找找BUG。(代码略)
题目分析
几个要点:
- 二进制某一位上做位操作不影响其他位。
- 1⊕0=1,0⊕0=0,1∣0=1,0∣0=0,即 0 前任意数配任意操作符出来的结果还是前数。
- 结合以上两点,每个操作符可认为只影响其后的那个数,即可以把问题归类。
由此以上分析,影响结果 bi 位的只和数列中的 bi 项及前面的操作符有关。
问题转化
我们把所有 bi 项都提取出来,问题转换成共有 n 个 1 的式子 0(⊕/∣)1(⊕/∣)1(⊕/∣)1...(⊕/∣)1=?
,我们的目标是让结果等于 1 。
- 1⊕1=0,0⊕1=1,1∣1=1,0∣1=1。
- 对第一个 1 ,因为前面要不然没有操作符(处在 a1 位),要不然是 0 ,由于 0⊕1=1,0∣1=1 ,所以什么操作符都不影响后续结果为 1 。
- 现在来看 n=2 的情况,1(⊕/∣)1只有在 1∣1 的情况下才为 1 ,所以只能放 ∣ 。
- n=3 的情况, 1⊕1⊕1=1 ,可以全部放 ⊕。
- 继续观察发现 n 为奇数的情况,操作符可以全部放 ⊕ ;n 为偶数,至少要 1 个 ∣ 操作符。
- 而且因为 1∣1=1,0∣1=1 ,所以如果想要最后结果为 1 ,最后 1 个操作符为 ∣ 即可,前面就可以任意放。
形成算法
根据以上的分析发现可以用贪心算出最优解,具体如下:
- 从大的 bi 开始,依次满足计算结果为 1 ,如果 bi 的个数为奇数就不管,是偶数就要在最后一个 bi 位置前放 ∣ 操作符。
- 若全都弄完了,还有剩下的 ∣ 没放置,那就从每个不同的 bi 位置从后往前放,因为最后 1 个操作符为 ∣ 即可,前面就可以任意放。
实际做的过程中,“最后1个操作符为 ∣ 即可”这点我到最后 15 分钟才想到,其实这点很明显。但因为没想到,致使我花了很多时间在设计如何放置操作符上。