这道题目真的是。。。
赛时的时候想完全证明出来发现不行,其实根本不用,这种题目主打的就是一个感性理解,官方题解也没给出证明。。在这道题目卡了1h完大蛋,最后剩20min做D,然而D也只做了30min。。。
我们手玩几组样例就会发现,他是想要在任意本金经历了无论多少场(\(≤x\))输之后,下一场赢至少会比最开始的本金多\(1\)元(否则的话我就按照这种情况无限循环下去,本金要么根本不变要么减少);赢的场次根本不用关心
下面的分析都假设没有超过\(x\)场连输
由于本金有限,我们对于输的第一场,选择投\(1\)元,然后我们一直尝试投\(1\)元(假设一直输),直到多久不投\(1\)元了呢?直到我们再投一次\(1\)元后,这一场我们赢了,但是却无法弥补前面输的总金额
稍微计算就可以知道,最多放\(k-1\)个\(1\),第\(k\)场输就要放\(2\)或以上了
其实说白了,就是假设我们前面连输的总金额是\(cnt\),那么我们接下来投的钱是\(num\),如果我们这一场赢了,必须有\((k-1)\cdot num>cnt\),我们解出num就好了,如果这一场输入就把解出的\(num\)累加到\(cnt\)里面,继续考虑下一场
我中间花费的一个小时完全是因为去推导数学公式了(可以看看我的代码),但实际上\(x\)只有\(100\),直接一轮一轮循环也没关系
然后注意,中途完全可以爆long long,但没关系,某一时刻的\(cnt\)比\(a\)大直接结束循环就好了
标签:cnt,题目,Casino,long,Sasha,num,本金,我们 From: https://www.cnblogs.com/dingxingdi/p/18021643