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

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

题目分析

几个要点:

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

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

问题转化

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

  1. 11=0,01=1,11=1,01=11 \oplus 1=0,0 \oplus 1=1,1|1=1,0|1=1
  2. 对第一个 11 ,因为前面要不然没有操作符(处在 a1a_1 位),要不然是 00 ,由于 01=1,01=10 \oplus 1=1, 0|1=1 ,所以什么操作符都不影响后续结果为 11
  3. 现在来看 n=2n=2 的情况,1(/)11( \oplus /|)1只有在 111|1 的情况下才为 11 ,所以只能放 |
  4. n=3n=3 的情况, 111=11 \oplus 1 \oplus 1=1 ,可以全部放 \oplus
  5. 继续观察发现 nn 为奇数的情况,操作符可以全部放 \oplusnn 为偶数,至少要 11| 操作符。
  6. 而且因为 11=1,01=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
加载中...