【求助】题解改格式
  • 板块学术版
  • 楼主moshouiii3
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/8/10 11:05
  • 上次更新2023/10/27 16:09:42
查看原帖
【求助】题解改格式
753903
moshouiii3楼主2022/8/10 11:05

实在是不会改了,我把每个公式和字母数字周围都加了空格,还是过不了审核。麻烦有经验的同学帮忙看看,找找BUG。(代码略)

题目分析

几个要点:

  1. 二进制某一位上做位操作不影响其他位。
  2. 1⊕0=1,0⊕0=0,1∣0=1,0∣0=01 \oplus 0=1,0 \oplus 0=0,1|0=1,0|0=0,即 00 前任意数配任意操作符出来的结果还是前数。
  3. 结合以上两点,每个操作符可认为只影响其后的那个数,即可以把问题归类。

由此以上分析,影响结果 bib_i 位的只和数列中的 bib_i 项及前面的操作符有关。

问题转化

我们把所有 bib_i 项都提取出来,问题转换成共有 nn 个 11 的式子 0(⊕/∣)1(⊕/∣)1(⊕/∣)1...(⊕/∣)1=?0( \oplus /|)1( \oplus /|)1( \oplus /|)1...( \oplus /|)1=? ,我们的目标是让结果等于 11 。

  1. 1⊕1=0,0⊕1=1,1∣1=1,0∣1=11 \oplus 1=0,0 \oplus 1=1,1|1=1,0|1=1。
  2. 对第一个 11 ,因为前面要不然没有操作符(处在 a1a_1 位),要不然是 00 ,由于 0⊕1=1,0∣1=10 \oplus 1=1, 0|1=1 ,所以什么操作符都不影响后续结果为 11 。
  3. 现在来看 n=2n=2 的情况,1(⊕/∣)11( \oplus /|)1只有在 1∣11|1 的情况下才为 11 ,所以只能放 ∣| 。
  4. n=3n=3 的情况, 1⊕1⊕1=11 \oplus 1 \oplus 1=1 ,可以全部放 ⊕\oplus 。
  5. 继续观察发现 nn 为奇数的情况,操作符可以全部放 ⊕\oplus ;nn 为偶数,至少要 11 个 ∣| 操作符。
  6. 而且因为 1∣1=1,0∣1=11|1=1,0|1=1 ,所以如果想要最后结果为 11 ,最后 11 个操作符为 ∣| 即可,前面就可以任意放。

形成算法

根据以上的分析发现可以用贪心算出最优解,具体如下:

  1. 从大的 bib_i 开始,依次满足计算结果为 11 ,如果 bib_i 的个数为奇数就不管,是偶数就要在最后一个 bib_i 位置前放 ∣| 操作符。
  2. 若全都弄完了,还有剩下的 ∣| 没放置,那就从每个不同的 bib_i 位置从后往前放,因为最后 11 个操作符为 ∣| 即可,前面就可以任意放。

实际做的过程中,“最后1个操作符为 ∣| 即可”这点我到最后 15 分钟才想到,其实这点很明显。但因为没想到,致使我花了很多时间在设计如何放置操作符上。

2022/8/10 11:05
加载中...