水题记录(一)

6 / 6

异或运算

题意:给出数组$a[]$和$b[]$,$a[i]$,$b[j]$异或起来得到矩阵中的$M_{i,j}$,询问子矩阵的第$K$大

题解:直接建矩阵显然不行,考虑建出一行,每次相当于直接把一行异或上一个数。,

考虑按位建立主席树,查询的时候整体带着异或,左儿子存$0$,右儿子存$1$,查询的时候查询相反的方向。

暴力一点的做法是二分,暴力查询,复杂度$O(nlog^2n)$,期望得分$40$。

优秀的做法就是在主席树里面二分,类似区间$k$大就行了,复杂度$O(nlogn)$,期望得分$100$

解密运算

题意:把数组排序后给出最后一列,询问原串

题解:首先可以直接排序算出第一列的元素,也就知道了每个元素的下一个是什么,考虑从.开始算,对于相同的东西按照顺序标号(字典序小的在前面),直接算就行,全部代码30行。

平方运算

题意:维护区间平方(取模)&区间和(不模)

题解:看到神奇的模数就觉得有玄机,打暴力会发现每个数在很少的操作后就会进入环,而且所有环的$LCM$不会超过$60$。维护一个区间的环,每次平移相当于把区间的东西都$+1$,类似区间开根,如果一个区间都在环里面,维护区间加法,不是的话暴力计算。修改单点后从下往上更新区间的环,代码不是很好打,但也不是很难。

补退选

题意:插入串或者删除串,询问前缀为$S$的串最早在什么时候出现次数大于$V$,强制在线

题解:维护和持久化$Trie$单点修改,维护子树里的历史最大值,二分答案判断。

成绩单

题意:区间操作,最小化 $a \times k+b \times \sum_{i=1}^k(max_i – min_i)^2 $

题解:区间$DP$,记录$DP[l][r][a][b$]表示区间$L,R$中最大值为$b$,最小$a$的最小值,枚举分裂点,和不分裂取最小值,记忆化搜索转移。

在美妙的数学王国中畅游

题意:维护动态加边,删边,边上有三种函数,询问从一个点开始到另一个点,把给出的值带入边上的函数相加,最后是多少

题解:考虑在序列上的问题,就变得简单。只需要实现函数的叠加形如$H(X)=F(X)+G(X)+P(X)$

得到这样的$H$即可。对于一个函数$f(x)$,若$f(x)$的$n$阶导数在$[a,b]$上连续,对于$f(x)$在$x_0$处使用$n$次拉格朗日中值定理可以得到拉格朗日余项的泰勒展开式
$$
f(x)=f(x_0)+\frac{f'(x0)(x0-x)}{1!}+\frac{f”(x0)(x0-x)}{2!}…..+\frac{f^{(n-1)}(x_0)(x-x_0)^{n-1}}{(n-1)!}+\frac{f^{(n)}(ξ)(x-x_0)^{n}}{n!}
$$
其中,当 $x>x0$时,$ξ\in[x0,x]$。当 $x<x_0$ 时,$ξ∈[x,x0]$

$f^{(n)}$表示函数 $f$ 的 $n$ 阶导数

当多求几次导以后,余项$ξ$对答案的影响很小就可以直接忽略掉。

如果在序列上面,直接拿线段树维护,如果加边删边,上个$LCT$岂不是显然。

总结

三套题里面个人觉得难度$2017WC>2015SC>2016SC$,感觉又在强行把不可做的题根据特殊性质出题,强行数据结构。

综上所诉,题目都好神啊,我好菜啊QAQ

《水题记录(一)》上有3条评论

    1. 帮我搭博客的巨神Orz。膜拜膜拜膜拜

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*