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

EP2

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

2.最大平局问题

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

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

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

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

Sol：

1. $<>$，那么两边的手势一定相同，只需要先把中间手势输掉，两边就会相邻，即可贡献 $1$。
2. $<<$，根据石头剪刀布的三环性，可以转化为 $>$
3. $>>$，同理可转化为 $<$
4. $><$，发现直接消去肯定不优，因为只贡献了 $0$，还没有任何转机。

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$ 点。否则无法产生贡献。