2020牛客暑期多校训练营(第三场)cjy J/K xx H zrx I
Codeforces Round #657 xx F zrx E
2020牛客暑期多校训练营(第四场)cjy E/J xx A zrx I
Codeforces Round #658 xx C zrx D cjy E
BUAA ICPC 2020-2021 cjy A/E xx B/C zrx E/K
本周无
2020.07.18 Topcoder Parallel 2B
2020.07.19 Codeforces Round #657
2020.07.22 Codeforces Round #658
2020牛客暑期多校训练营(第三场)K
本周无
2020.07.18 2020牛客暑期多校训练营(第三场)
2020.07.21 cf div1
2020牛客暑期多校训练营(第三场)I
Codeforces Round #657 zrx E
2020牛客暑期多校训练营(第四场)I
Codeforces Round #658 D
编辑了AC自动机初稿
编辑了后缀数组初稿
编辑了笛卡尔树初稿
2020.07.19 Codeforces Round #657 (Div. 2)
2020牛客多校第三场 H
2020牛客多校第四场 A
Codeforces Round #657 E
题意:构造一科有n个点的满二叉树,且恰好有k个点两个儿子最深的长度 一个是另一个的两倍
题解:考虑毛毛虫,这样构造出来的一定是最多的,对于一个毛毛虫能求出有多少个满足,然后就递归做。
思考:考虑构造题的时候,可以多考虑特殊种类的树,如毛毛虫,菊花图等,例如本题要求两个孩子深度差最大,毛毛虫显然是一种极优方案。
Codeforces Round #658 C
题意
给你一个长度为$n$的数组,元素范围$[1,n+1]$,问是否存在另外一个长度为$n$的数组,元素范围也是$[1,n+1]$,并且它们有$x$位是完全
一样的,并且把它进行打乱之后,最多有$y$位是一样的,请构造。
思路:
这道题本质来说是一类题,“错位排序构造”,就是说给你一个序列,让你用这些数构造一个新的序列,使得没有两个同位置元素是一样的。
我们贪心的把x位置一样和n-y位置不一样的元素都去消灭元素个数比较多的元素,这是和“错位排序构造”的实现方式有关的。
对于x=y和x=y-1的情况需要单独考虑。
否则就转化成了“错位排序构造”。
对于“错位排序构造”构造,我们应该关注的是当前序列中限制个数(及原本为这个元素的位置)和剩余个数之和最大的元素。
如果它在某个时刻等于了剩余长度,那么剩下的填发就唯一了。
否则可以随便填。
评论:
对于这类题的思路,做了一个总结,以后不能再写不出来了。
2020牛客暑期多校第3场H题
题意:
给一个串s,一个排列p,一个数组d。第i次操作为:将$s_{i-1}$的第$p_{i}$位换成$d_{i}$,求$s_{0}$、$s_{1}$、……$s_{n}$的排名。
思路:
对于原串的第i位,假设它是在第k次操作中被改变的,如果:
1. d[k] > s[i] ,那么$s_{k}$,……$s_{n}$排在$s_{0}$……$s_{k-1}$后面
2. d[k] < s[i] ,那么$s_{k}$,……$s_{n}$排在$s_{0}$……$s_{k-1}$前面
3. d[k] > s[i] ,那就当什么都没发生过
所以我们可以从第一位开始考虑,看它是在什么时候被改变的就可以了。但是,我们如何处理才能做到O(n)呢?按照笛卡尔树dfs序!
笛卡尔树的查询操作时O(logn)的,如果是用来在线查找区间最值的话并不占优势,所以以前一直觉得它没什么用。这不就真香了……