2020-2021:teams:running_chicken:2020_summer_week2_report
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week2_report [2020/07/24 17:02] chenjiyuan3 [比赛] |
2020-2021:teams:running_chicken:2020_summer_week2_report [2020/07/31 21:34] (当前版本) selia [todolist（补题）] |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| 2020牛客暑期多校训练营（第三场）cjy J/K xx **H** zrx I | 2020牛客暑期多校训练营（第三场）cjy J/K xx **H** zrx I | ||
| - | Codeforces Round #657 xx F zrx **E** | + | Codeforces Round #657 xx **F** zrx **E** |
| - | 2020牛客暑期多校训练营（第四场）cjy E/J xx A zrx I | + | 2020牛客暑期多校训练营（第四场）cjy E/J xx **A** zrx I |
| - | Codeforces Round #658 xx C zrx D cjy E | + | Codeforces Round #658 xx **C** zrx D cjy E |
| + | |||
| + | BUAA ICPC 2020-2021 cjy A/E xx B/C zrx E/K | ||
| =====CJY===== | =====CJY===== | ||
| 行 29: | 行 31: | ||
| 2020.07.18 Topcoder Parallel 2B | 2020.07.18 Topcoder Parallel 2B | ||
| - | 2020.07.19 Codeforces Round #657 (Div. 2) | + | 2020.07.19 Codeforces Round #657 |
| + | |||
| + | 2020.07.22 Codeforces Round #658 | ||
| - | 2020.07.22 Codeforces Round #658 (Div. 1) | ||
| ====题目==== | ====题目==== | ||
| + | |||
| + | 2020牛客暑期多校训练营（第三场）K | ||
| =====ZRX===== | =====ZRX===== | ||
| 行 70: | 行 75: | ||
| ====题目==== | ====题目==== | ||
| + | 2020牛客多校第三场 H | ||
| + | |||
| + | 2020牛客多校第四场 A | ||
| ======本周推荐====== | ======本周推荐====== | ||
| =====zrx===== | =====zrx===== | ||
| - | Codeforces Round #657 zrx E | + | Codeforces Round #657 E |
| - | 考虑构造题的时候，可以多考虑特殊种类的树，如毛毛虫，菊花图等，例如本题要求两个孩子深度差最大，毛毛虫显然是一种极优方案。 | + | 题意：构造一科有n个点的满二叉树，且恰好有k个点两个儿子最深的长度 一个是另一个的两倍 |
| + | |||
| + | 题解：考虑毛毛虫，这样构造出来的一定是最多的，对于一个毛毛虫能求出有多少个满足，然后就递归做。 | ||
| + | |||
| + | 思考：考虑构造题的时候，可以多考虑特殊种类的树，如毛毛虫，菊花图等，例如本题要求两个孩子深度差最大，毛毛虫显然是一种极优方案。 | ||
| =====cjy===== | =====cjy===== | ||
| + | |||
| + | ====Mastermind==== | ||
| + | |||
| + | Codeforces Round #658 C | ||
| + | |||
| + | **题意** | ||
| + | |||
| + | 给你一个长度为$n$的数组，元素范围$[1,n+1]$，问是否存在另外一个长度为$n$的数组，元素范围也是$[1,n+1]$，并且它们有$x$位是完全 | ||
| + | |||
| + | 一样的，并且把它进行打乱之后，最多有$y$位是一样的，请构造。 | ||
| + | |||
| + | **思路**： | ||
| + | |||
| + | 这道题本质来说是一类题，“错位排序构造”，就是说给你一个序列，让你用这些数构造一个新的序列，使得没有两个同位置元素是一样的。 | ||
| + | |||
| + | 我们贪心的把x位置一样和n-y位置不一样的元素都去消灭元素个数比较多的元素，这是和“错位排序构造”的实现方式有关的。 | ||
| + | |||
| + | 对于x=y和x=y-1的情况需要单独考虑。 | ||
| + | |||
| + | 否则就转化成了“错位排序构造”。 | ||
| + | |||
| + | 对于“错位排序构造”构造，我们应该关注的是当前序列中限制个数（及原本为这个元素的位置）和剩余个数之和最大的元素。 | ||
| + | |||
| + | 如果它在某个时刻等于了剩余长度，那么剩下的填发就唯一了。 | ||
| + | |||
| + | 否则可以随便填。 | ||
| + | |||
| + | **评论**： | ||
| + | |||
| + | 对于这类题的思路，做了一个总结，以后不能再写不出来了。 | ||
| =====XX===== | =====XX===== | ||
2020-2021/teams/running_chicken/2020_summer_week2_report.1595581371.txt.gz · 最后更改: 2020/07/24 17:02 由 chenjiyuan3
