F&S:Apocalypse 未详写游戏解析

· · 个人记录

EP2

1.练习日Aranda给Z出的问题「数字比较」

待更新

2.最大平局问题

X 给 Avantoge 的贪心法练习题，镜头有拍到

有 n 个人站成一排玩石头剪刀布，每个人只会出一种固定的手势。定义一次操作为：

  • 选择任意的相邻两人，让他们玩石头剪刀布，将败者移除。若平局，则任意移除一人。然后，其余的人会补上空位。

已知当双方手势不同时，石头可以战胜剪刀，剪刀可以战胜布，布可以战胜石头；若一局中双方手势相同，则该局游戏为平局。

你需要不断执行操作直到只剩下一个人，最大化操作造成的平局次数。

Sol：

原漫画旁边有Avantoge给出的答案，但字太小了看不清，只能模糊看出 > 和 < 样式的符号，以下答案就按照此设定给出。

考虑手势之间的关系。设 < 的意义为右侧手势被左侧手势击败，> 反之。

将初始就相邻的手势消去肯定不劣，因此可以将所有连续相同的手势消到只剩一个，这样就能将一个手势序列转化为一个只含 > 和 < 的序列。

手动模拟一下可以发现，对于相邻两个字符只有四种操作：

  2. <<$，根据石头剪刀布的三环性，可以转化为 $>
  3. >>$，同理可转化为 $<

现在考虑挖掘更深入的性质。

  1. 首先如果出现了 <>，直接消去肯定不劣，因为它是唯一可以直接贡献 1 的操作。于是接下来默认所有的 <> 都已被消去。
  2. 对于 >>>，可以先转化为 <> 再消去，消耗 3 个符号获得 1 点贡献。<<< 也同理。且由于最左侧和最右侧符号相同，因此消去后不影响其他的符号方向。
  3. 考虑如果两个相邻的符号不同，一定是 ><（因为 <> 可以直接被消去），且不会出现两个以上的 ><，不然总会形如 ><>< ，可消掉中间的 <> 变为单个 ><。
  4. 所以把能消掉的都消了之后的串形如 >>><<<<，由 u 个 > 和 v 个 < 构成。
  5. 考虑怎么消最大化贡献。注意到中间的 >><< 可以被转化为 <> 后消去，但这样需要花费 4 个符号获得 1 点贡献。没有 3 个符号优，根据贪心策略，应优先考虑消去 >>> 和 <<<。

至此，得到最大平局问题的构造策略。

  1. 先让相邻且平局的人两两游戏，计算贡献，使得序列只含有 < 和 >。
  2. 消掉所有存在的 <>（表现为中间人会被两边人战胜），计算贡献。可证明最后一定剩下左侧 u 个 >，右侧 v 个 <。
  3. 当 u\ge 3 时，将连续的三个 > 消去（表现为石头布剪刀石头、布剪刀石头布、剪刀石头布剪刀），计算贡献。当 v\ge 3 时，将连续的三个 < 消去（表现为石头剪刀布石头、布石头剪刀布、剪刀布石头剪刀），计算贡献。最后得到的 u,v 满足 u,v\le 2。
  4. 当且仅当 u=v=2 时，即出现 >><< 时，可再消去，贡献 1 点。否则无法产生贡献。