差别

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

--- 2020-2021:teams:running_chicken:2020_summer_week2_report [2020/07/22 13:56]
chenjiyuan3 [todolist（补题）]
+++ 2020-2021:teams:running_chicken:2020_summer_week2_report [2020/07/31 21:34] (当前版本)
selia [todolist（补题）]
@@ 行 6: / 行 6: @@
 .07.20 [[.nowcodersummer4|2020牛客暑期多校训练营（第四场）]]
+.07.23 [[.2020buaasummertrain1|2020北航暑期内部训练1]]
 ======个人======
@@ 行 13: / 行 15: @@
 牛客暑期多校训练营（第三场）cjy J/K xx **H** zrx I
-Codeforces Round #657 xx F zrx E
+Codeforces Round #657 xx **F** zrx **E**
-牛客暑期多校训练营（第四场）cjy E/J xx A zrx I
+牛客暑期多校训练营（第四场）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=====
 ====专题====
+本周无
 ====比赛====
+.07.18 Topcoder Parallel 2B
+.07.19 Codeforces Round #657
+.07.22 Codeforces Round #658
 ====题目====
+牛客暑期多校训练营（第三场）K
 =====ZRX=====
 ====专题====
+本周无
 ====比赛====
+.07.18 [[.nowcodersummer3|2020牛客暑期多校训练营（第三场）]]
+.07.21 cf div1
 ====题目====
+牛客暑期多校训练营（第三场）I
+Codeforces Round #657 zrx E
+牛客暑期多校训练营（第四场）I
+Codeforces Round #658 D
 =====XX=====
@@ 行 48: / 行 75: @@
 ====题目====
+牛客多校第三场 H
+牛客多校第四场 A
 ======本周推荐======
 =====zrx=====
+Codeforces Round #657 E
+题意：构造一科有n个点的满二叉树，且恰好有k个点两个儿子最深的长度 一个是另一个的两倍
+题解：考虑毛毛虫，这样构造出来的一定是最多的，对于一个毛毛虫能求出有多少个满足，然后就递归做。
+思考：考虑构造题的时候，可以多考虑特殊种类的树，如毛毛虫，菊花图等，例如本题要求两个孩子深度差最大，毛毛虫显然是一种极优方案。
 =====cjy=====
-=====selia=====
+====Mastermind====
+Codeforces Round #658 C
+**题意**
+给你一个长度为$n$的数组，元素范围$[1,n+1]$，问是否存在另外一个长度为$n$的数组，元素范围也是$[1,n+1]$，并且它们有$x$位是完全
+一样的，并且把它进行打乱之后，最多有$y$位是一样的，请构造。
+**思路**：
+这道题本质来说是一类题，“错位排序构造”，就是说给你一个序列，让你用这些数构造一个新的序列，使得没有两个同位置元素是一样的。
+我们贪心的把x位置一样和n-y位置不一样的元素都去消灭元素个数比较多的元素，这是和“错位排序构造”的实现方式有关的。
+对于x=y和x=y-1的情况需要单独考虑。
+否则就转化成了“错位排序构造”。
+对于“错位排序构造”构造，我们应该关注的是当前序列中限制个数（及原本为这个元素的位置）和剩余个数之和最大的元素。
+如果它在某个时刻等于了剩余长度，那么剩下的填发就唯一了。
+否则可以随便填。
+**评论**：
+对于这类题的思路，做了一个总结，以后不能再写不出来了。
+=====XX=====
+====Sort the Strings Revision====
+牛客暑期多校第3场H题
+===笛卡尔树===
+**题意**：
+给一个串s，一个排列p，一个数组d。第i次操作为：将$s_{i-1}$的第$p_{i}$位换成$d_{i}$，求$s_{0}$、$s_{1}$、……$s_{n}$的排名。
+**思路**：
+对于原串的第i位，假设它是在第k次操作中被改变的，如果：
+. d[k] > s[i] ，那么$s_{k}$，……$s_{n}$排在$s_{0}$……$s_{k-1}$后面
+. d[k] < s[i] ，那么$s_{k}$，……$s_{n}$排在$s_{0}$……$s_{k-1}$前面
+. d[k] > s[i] ，那就当什么都没发生过
+所以我们可以从第一位开始考虑，看它是在什么时候被改变的就可以了。但是，我们如何处理才能做到O(n)呢？按照笛卡尔树dfs序！
+[[https://ac.nowcoder.com/acm/contest/5668|题目]]
+[[https://blog.csdn.net/micaudience/article/details/107494237|代码]]
+[[https://blog.csdn.net/micaudience/article/details/107493694|笛卡尔树]]
+笛卡尔树的查询操作时O(logn)的，如果是用来在线查找区间最值的话并不占优势，所以以前一直觉得它没什么用。这不就真香了……

CVBB ACM Team

用户工具

站点工具

差别

页面工具