2020-2021:teams:hotpot:200718-200724

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:hotpot:200718-200724 [2020/07/24 16:03]
misakatao 更新
+++ 2020-2021:teams:hotpot:200718-200724 [2020/07/24 16:43] (当前版本)
misakatao 更新
@@ 行 130: / 行 130: @@
 陶吟翔：
+===Codeforces Round 652 D - TediousLee===
+题目大意：初始为一个点，每次操作，每个点如果没有儿子，就多一个儿子，如果有儿子就多2个儿子，有3个儿子就不会再改变，每一步的时候每个不满足的点都会改变，问第$n$种状态不重复最多找几个爪子，爪子的形状如下图
+{{:2020-2021:teams:hotpot:26.png?400|}}
+数据范围：多组数据，$T \le 10^4$，$1 \le n \le 2 \times 10^6$
+解题思路：显然$n=1$或$n=2$时答案是0，从$n=3$时开始往后递推，每次上一个所在的爪子下移一位，上上次的每个爪子的两边会各出现一个爪子，并且每向下移动三次最顶上就会多一个爪子，所以递推式是$f[i] = f[i-1] + 2 \times f[i-2] + 4 \times (i\ mod\ 3==0)$
+推荐理由：一道不错的递推思维题，把前几个状态在哪里选爪子标出来就能发现规律，但发现规律的过程也并不容易，需要对题目给出的变化方式进行总结，锻炼了做题者的总结思维和观察能力。
 郭衍培：

2020-2021/teams/hotpot/200718-200724.1595577788.txt.gz · 最后更改: 2020/07/24 16:03 由 misakatao