2020-2021:teams:hotpot:200718-200724
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200718-200724 [2020/07/24 14:30] 喝西北风 |
2020-2021:teams:hotpot:200718-200724 [2020/07/24 16:43] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| 2020.7.20 [[2020nowcoder4|2020牛客暑假多校训练营（第四场）]] ''prob:4/5/10'' ''rank:46/1111'' | 2020.7.20 [[2020nowcoder4|2020牛客暑假多校训练营（第四场）]] ''prob:4/5/10'' ''rank:46/1111'' | ||
| + | |||
| + | 2020.7.23 [[2020supplementarytraining1|2020-2021 BUAA ICPC Team Supplementary Training 01]] ''prob: 2/2/11'' | ||
| ======林星涵====== | ======林星涵====== | ||
| =====专题===== | =====专题===== | ||
| + | |||
| + | 本周无 | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.7.21 [[codeforces658div2|Codeforces Round #658]] ''prob:4/5/6'' ''rank:599'' | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | *Codeforces Round 658 D - Unmerge | ||
| + | *分类：贪心 | ||
| + | *题目大意：给你一个 &2*n& 的序列，问你能否将其分为两个长度为 $n$ 的序列，令其归并后的序列和原序列相同。 | ||
| + | *数据范围：多组数据，$t \le 1000$，$1 \le n \le 2000$ | ||
| + | *解题思路：我们可以发现，一个数后面如果连续出现比他小的数，那么他们必定是被分到一个序列中的，利用这个性质我们将大区间拆成多个长度不等的小区间做 0，1 背包看能否构成 $n$ 长度的序列即可。 | ||
| + | *Comment：利用归并性质进行贪心的题，思路较好。 | ||
| ======陶吟翔====== | ======陶吟翔====== | ||
| 行 49: | 行 62: | ||
| =====专题===== | =====专题===== | ||
| + | |||
| + | 本周无 | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.7.21 [[codeforces658div2|Codeforces Round #658]] ''prob:5/5/6'' ''rank:42'' | ||
| =====题目===== | =====题目===== | ||
| 行 79: | 行 96: | ||
| *题目大意：求长度为k，包含子序列s的，仅由小写字母构成的字符串个数。 | *题目大意：求长度为k，包含子序列s的，仅由小写字母构成的字符串个数。 | ||
| *数据范围：$1 \le |s|,k-|s| \le 2\times 10^6$ | *数据范围：$1 \le |s|,k-|s| \le 2\times 10^6$ | ||
| - | *解题思路：设|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：很好的数学题，不好想，方法事实上很简洁。 | *Comment：很好的数学题，不好想，方法事实上很简洁。 | ||
| 行 99: | 行 116: | ||
| 林星涵： | 林星涵： | ||
| + | |||
| + | ===Codeforces Round 658 C2 - Prefix Flip (Hard Version)=== | ||
| + | |||
| + | 题目大意：给两个0，1串 $a,b$ ，能进行的操作是将一个前缀的0，1交换并前后翻转，求从 $a$ 到 $b$ 的操作数不超过 $2*n$ 的序列。 | ||
| + | |||
| + | 数据范围：$ n \le 100005 $ | ||
| + | |||
| + | 解题思路：此题构造思路较为清晰，如果原本相同，便不做改动，如果不同则看第一位是否相同，不同则直接翻转，否则先翻转第一位再翻转。 | ||
| + | |||
| + | 难点在于如何维护，涉及到区间翻转比较直接的想法是splay,但实际上由于该翻转操作的特殊性只要记录首尾进行交换等操作即可。 | ||
| + | |||
| + | 推荐理由：构造思路清晰，维护方式巧妙简洁。（而且我数组开小fst了。。。） | ||
| 陶吟翔： | 陶吟翔： | ||
| - | 郭衍培： | + | ===Codeforces Round 652 D - TediousLee=== |
| - | ====题目大意==== | + | 题目大意：初始为一个点，每次操作，每个点如果没有儿子，就多一个儿子，如果有儿子就多2个儿子，有3个儿子就不会再改变，每一步的时候每个不满足的点都会改变，问第$n$种状态不重复最多找几个爪子，爪子的形状如下图 |
| - | 求长度为k，包含子序列s的，仅由小写字母构成的字符串个数。 | + | {{:2020-2021:teams:hotpot:26.png?400|}} |
| - | ====数据范围==== | + | 数据范围：多组数据，$T \le 10^4$，$1 \le n \le 2 \times 10^6$ |
| - | $1 \le |s|,k-|s| \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)$ |
| + | |||
| + | 推荐理由：一道不错的递推思维题，把前几个状态在哪里选爪子标出来就能发现规律，但发现规律的过程也并不容易，需要对题目给出的变化方式进行总结，锻炼了做题者的总结思维和观察能力。 | ||
| + | |||
| + | 郭衍培： | ||
| - | ====解题思路==== | + | 题目大意：求长度为k，包含子序列s的，仅由小写字母构成的字符串个数。 |
| - | 设|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即可。 | + | 数据范围：$1 \le |s|,k-|s| \le 2\times 10^6$ |
| - | ====Comment==== | + | 解题思路：设|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即可。 |
| - | 很好的数学题，不好想，方法事实上很简洁。这种题做起来确实很舒爽。 | + | 推荐理由：很好的数学题，不好想，方法事实上很简洁。这种题做起来确实很舒爽。 |
2020-2021/teams/hotpot/200718-200724.1595572201.txt.gz · 最后更改: 2020/07/24 14:30 由 喝西北风
