hzy 和zsl 的生存挑战 (签到)
我还是要吐槽一下,题目都说了两人没有交流还怎么能推出一个人相同一个人不相同,如果两个人都相同呢?
1 | puts("1.00\n1.00\n1.00\n1.00"); |
人类史上最大最好的希望事件 (矩阵快速幂求fib前缀平方和)
思路
斐波那契数列前n项和答案为$F_{N}*F_{N+1}$
1 |
|
超级无敌简单题 (规律)
思路
发现如果出现4就会出现死循环
1 |
|
免费送气球 (权值线段树)
思路
对于每个数存一个数量和val 然后判断数量是否大于查询数量,
1 |
|
简单数学题 (数学题)
思路
$F(n) = \sum_{i=1}^n (i \times \sum_{j=i}^n C_j^i)$
->$F(n)=\sum_{i=1}^{n}\sum_{j=i}^{n} i \times C_{j}^{i} $
其中$ \sum C_{j}^{i}$ 是杨辉三角的一条斜线
然后把i乘入这个斜线中,发现杨辉三角变成一个新的少了一维的杨辉三角
发现新的杨辉三角是之前的杨辉三角每一层的元素乘上层号
然后就是变成求$\sum_{i=1}^{n} i\times 2^{i-1}$
$1\times 2+2 \times2^1 +3 \times 2^2+\dots n \times2^{n-1}$
然后拆项为
根据等比数列$s_n=\frac{a_1(1-a_n)}{1-q}=\frac{a_nq-a_1}{q-1}$
整理
第一行变成$2^n-2^0$ 第二行变成$2^n-2^1$ 第n行变成$2^n-2^{n-1}$
再整理变成$n\times2^n-(2^n-1)=(n-1)\times2^n+1$
1 |
|
zyb的面试 (原题)
1 |
|
Count (矩阵快速幂)
思路
考虑矩阵快速幂 考虑要从前一项得到后一项的$n^3$
根据公式$(n+1)^3=n^3+3n^2+3n+1$
推出$f(n)=f(n-1)+2f(n-2)+n^3+3n^2+3*n+1$
所以构造一个矩阵就行了
1 |
|