此题翻译有误
  • 板块CF698C LRU
  • 楼主yijan
  • 当前回复13
  • 已保存回复13
  • 发布时间2021/3/23 11:55
  • 上次更新2023/11/5 01:42:58
查看原帖
此题翻译有误
63398
yijan楼主2021/3/23 11:55

大概是 2018 年的翻译,然后这个翻译让我对一个错题搞了半个早上

正确翻译:

nn 种物品和一个大小为 kk 的队列,有 pip_i 的概率会选择第 ii 种物品放入队列,如果队列已经有 ii将队列中的 ii 移到队尾

对着这个假题意做了很久,怎么看这个东西直接做 dpdp 都不对,于是看了几篇题解还是觉得有锅,即使倒着考虑这个问题,例如类似 duyi 博客中的这个序列 5 2 1 5 3 4 ,如果直接倒着做会发现第二个 55 并不在当前集合中,但是却不能往集合里面加入 55 ,因为按照题意来正着做会让 55 本身存在于队列中的,也就是说序列上前面的数会对后面造成影响。

但是如果用正确题意来做,会发现它前面是否存在 55 并不影响这个位置把 55 放到队尾,所以只需要反着考虑,就不会产生前面对后面的影响,就可以变成题解中说的问题(即如果选到当前选择过的数就不管,继续操作下去,选择到新的数直接加入序列)

感觉可能主要是除了 duyi 的题解都缺少理性说明(但是duyi的题解好像也忽略了这种情况),导致这个错翻译一直未被修正。。

2021/3/23 11:55
加载中...