关于t2的构造方法
  • 板块灌水区
  • 楼主隐藏人物001
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/11/26 22:12
  • 上次更新2023/10/27 01:19:02
查看原帖
关于t2的构造方法
233394
隐藏人物001楼主2022/11/26 22:12

通过2n-2的方法的启发,我们不妨理想能空出一个栈,关于2n-1时,我们可以预处理当前出现次数为奇数次的数的块,他们在当时一定会出现在栈里。显然在这些数量在2n-2内,2n-2的方法是适用的,当出现2n-1时,我们考虑下个入栈的数在之前的位置,如果其能在之前被放在底下,我们可以把2n-1放在下个出现数字的另一块的栈内,这样我们空出一个栈,利用操作2后依旧满足之前的性质。如果这个块强制被放到了我们利用的空栈上,我们考虑将2n-1放在一个只有一个块的栈上,然后下个与之前块相同的进入第n个栈,这样最后一个栈也是空栈。同样满足之前的性质。 这种方案在任何情况都是可行的,也就是说,只要满足任何相同的块是偶数块,栈数为2n-1时肯定有解。

2022/11/26 22:12
加载中...