2020-2021:teams:hotpot:200718-200724
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200718-200724 [2020/07/24 16:02] misakatao 更新 |
2020-2021:teams:hotpot:200718-200724 [2020/07/24 16:43] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 127: | 行 127: | ||
| 难点在于如何维护，涉及到区间翻转比较直接的想法是splay,但实际上由于该翻转操作的特殊性只要记录首尾进行交换等操作即可。 | 难点在于如何维护，涉及到区间翻转比较直接的想法是splay,但实际上由于该翻转操作的特殊性只要记录首尾进行交换等操作即可。 | ||
| - | Comment：构造思路清晰，维护方式巧妙简洁。（而且我数组开小fst了。。。） | + | 推荐理由：构造思路清晰，维护方式巧妙简洁。（而且我数组开小fst了。。。） |
| 陶吟翔： | 陶吟翔： | ||
| + | |||
| + | ===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)$ | ||
| + | |||
| + | 推荐理由：一道不错的递推思维题，把前几个状态在哪里选爪子标出来就能发现规律，但发现规律的过程也并不容易，需要对题目给出的变化方式进行总结，锻炼了做题者的总结思维和观察能力。 | ||
| 郭衍培： | 郭衍培： | ||
| 行 139: | 行 151: | ||
| 解题思路：设|s|=n。考虑字符串中字典序最小的s。设最后一位是第m位。之前的n-1位有$C_{m-1}^{n-1}$种，除这n-1个位置以外，其余m-n个位置，每个位置有25种选择（不能是它后面的那个字母，否则违反字典序最小）。而第m位往后的位置，每个位置有26种选择。因此最后一位是m的字符串有$C^{n-1}_{m-1}25^{m-n}26^{k-m}$种。枚举m即可。 | 解题思路：设|s|=n。考虑字符串中字典序最小的s。设最后一位是第m位。之前的n-1位有$C_{m-1}^{n-1}$种，除这n-1个位置以外，其余m-n个位置，每个位置有25种选择（不能是它后面的那个字母，否则违反字典序最小）。而第m位往后的位置，每个位置有26种选择。因此最后一位是m的字符串有$C^{n-1}_{m-1}25^{m-n}26^{k-m}$种。枚举m即可。 | ||
| - | Comment：很好的数学题，不好想，方法事实上很简洁。这种题做起来确实很舒爽。 | + | 推荐理由：很好的数学题，不好想，方法事实上很简洁。这种题做起来确实很舒爽。 |
2020-2021/teams/hotpot/200718-200724.1595577766.txt.gz · 最后更改: 2020/07/24 16:02 由 misakatao
