这几天在蔡老板的带领下学习到了很多有趣(shui)的题,挑几道印象深刻的分享一下。

自闭的游戏

题目描述

小 A 和小 B 在玩一个游戏,游戏一开始有 n 张卡牌,第 i 张卡牌上面的值为 a[i],且有一个关键数字 M。

两个玩家轮流操作,小 A 先手。每轮每个玩家可以移除任意一张卡牌,假设卡牌上的数字为 x ,则关键数字 M 会变成 $⌊\dfrac M x⌋$
如果某位玩家操作后,关键数字变成 0 了,那么游戏结束,最后操作的玩家输。

小 B 玩了几天后输得有点自闭,所以他想问你,对于给定的 n 张牌 a[1..n],有多少 $x∈[L,R]$,满足关键数字为 x 时后手必胜。

保证 $∏_{i=1}^{n}a[i]>R$,这样永远都不会出现没有牌了但是游戏还未结束的情况。

数据范围

对于 100% 的数据,有 $1≤n≤10$,$1≤a[i]≤1000$,$1≤L≤R≤10^{18}$,$\prod\limits_{i=1}^{n}a[i]>R$

思路

首先我们不要管 $L,R$ 的范围,思考一下对于一个确定的 M 如何快速求得答案。。。然后会发现无法快速求得答案。。。

这个时候观察发现 $n$ 不管什么时候都很小,考虑一下是不是可以暴搜判断胜负。

枚举两个人在某个时刻选择了哪张牌,发现最后的胜负是取决于选出来的牌的数字之积(废话)。由于 M 是被整除,所以对于一个数字之积,对应的一段连续 M 的答案是相同的。所以只要判断每段 M 中的一个就行。一共 $2^n$ 个选择数字方案,可以轻松地 40ms 出答案。

代码

强壮的游戏

题目描述

小 A 在玩一个很好玩的游戏,这个游戏的地图由 n 个房间组成,游戏的流程是这样的:

一开始小 A 的血量为 1,任何时候当小 A 的血量降到 0 小 A 就死了,在游戏刚开始时,小 A 可以任选一个房间,然后进入那个房间,房间一共有三种:

  • 金币房:进入后可以获得一个金币

  • 怪物房:进入后血量减一

  • 续命房:进入后血量加一

在进入一个房间且按照房间的类型结算完效果后,小 A 有两种选择:立刻结束游戏,收益为当前金币个数;或者假设当前在第 i 个房间,则进入第 i+1 个房间(如果存在的话)

注意,如果小 A 中途死掉的话,那么收益就为0
现在给出这个游戏的地图,求小 A 的最大收益

思路

这道题有很多二分、单调栈之类的神仙做法,我都没想到。这里提供一种 $O(n)$ 模拟的无脑做法,并且证明为什么这是对的。

直接开两个变量 $hp,score$,从第一个房间开始,完全按题意模拟,死掉了就重置 $hp=1,score=0$。答案不断对 $score$ 取最大值即可。

下面证明为什么这是对的。

考虑从 $i$ 到 $j$ 是模拟算法中合法的一段。在 $i$ 处进入,$j$ 处死掉。那么假设我们从 $i,j$ 中的另一个点 $k$ 处进入,那么我们一定不能到达比 $j$ 更远的地方以获得更多的金币。因为从 $i$ 到 $j$ 保证了 $k$ 点的血量大于等于 1,一定不比直接从 $k$ 进入劣。金币只增不减,那就是活得越久越好。

代码

真得很容易,出题人表示他一开始没想到这个模拟是对的,不然就不会把它放在 T2 了。。。