新生杯部分题目解析

未分类

E: $yang12138$的快乐炉石
把操作倒过来看，就是要把$n$变成$1$，$A$法术等价于$n$是偶数时使用，使$n$缩小一半，$B$法术等价于$n$是奇数时使用，使$n$减$一$再除$2$.
显然如果当前$n$是奇数，用$B$法术，如果是偶数就用$A$法术，可以直接调用这样的递归函数计算：

int cal(int n){
    return cal(n/2)+1;
}

时间复杂度$O(logn)$

F: $yang12138$的激烈炉石

注意到单张火球术最高伤害是$10000$，最多使用$4$次就变成了$1$，变成$1$之后就再也不会变少，所以前$4$次操作暴力计算每个数开根号之后的结果，之后的操作可以直接输出$n$.
时间复杂度$O(n).$

G: $yang12138$的妹子

显然

在给定的数据范围内答案最大是$2^{30}$，用$int$型计算组合数即可.
使用递推式$C_n^m = C_{n-1}^{m} + C_{n-1}^{m-1}$可以计算组合数.

时间复杂度$O(n^2).$

H: $yang12138$的随机炉石

首先可以意识到随从的存在是不影响结果的，直接忽略掉随从的存在。
一张炎爆术造成$10$点伤害，对于剩余血量为$n$的英雄来说，最多能承受$\lceil \frac{n}{10} \rceil$次炎爆术.
考虑动态规划，令$dp(n,m)$表示我方能承受$n$次打击，对方能承受$m$次打击时我方的胜率。
初始状态是$dp(0,n)=0,dp(n,0)=1,n \ge 1$
转移方程是$dp(n,m)=\frac{1}{2} dp(n-1,m) + \frac{1}{2}dp(n,m-1)$，其中$n,m \ge 1.$

时间复杂度$O(\frac{n^2}{100}).$