Codeforces Round #370 (Div. 2)
E.Memory and Crow
题意
- 有(N(N le 10^5))个赌场。
- Memory在第(i)个赌场有(p_i)的概率获胜并走向(i+1)个赌场。
- 有(Q(Q le 10^5))次操作，操作有两种：
- 1 i a b，把第(i)个赌场到胜率设为(p_i=frac{a}{b})
- 2 l r，求Memory从赌场(l)开始，最后获胜走到(r+1)的概率。
思路
D.Memory and Scores
题意
- 两个人玩一个游戏，轮流进行，每个玩家每回合随机获得([-k,k])中的一个分数，其中(1 le k le 1000)。
- 已知两个人的起始分数，求进行(t(t le 100))轮游戏（(2t)个回合）后，第一个玩家的分数严格大于第二个玩家的方案数，modulo (10^9+7)。
思路
- 两个玩家的得分相互独立，所以单独考虑一个玩家最后的得分即可。
- 根据题目条件，最后的总得分最值为(pm 10^5)，用(f(i,j))表示进行(i)回合后玩家得分为(j)的方案数，转移：$$f(i,j)=sum_{l=j-k}^{j+k}{f(i-1,l)}$$每次转移可以维护一个长度为(k)的区间和，时间复杂度为(O(kt^2))
C.Memory and De-Evolution
题意
- 给一个长为(x)的正三角形，每次可以改变三角形的一条边，使得新的三条边仍构成三角形，最后变成一个长为(y)的正三角形，求最少的步数。
- 题目保证(x gt y)
思路
- 考虑从正三角形(y)变成正三角形(x)。
- 每次改变边长时，都尽量让最短的边变最长。
- 假设当前的边长为(a le b le c)，则令(a=min(x, c - b + 1))。