CF好题选做

这里收录一些我做过的cf题及题解,供各位大佬吊打。

HNOI2019 JOJO

(此题考查了对KMP的理解以及乱搞能力有理有据的优化)

luoguP4102 [HEOI2014]林中路径

原题传送门:>Here<

当路径长度$=L$,且只要求路径条数时,我们是很容易做的,只要用邻接矩阵乘一下就好了。

然而此题需要路径长度$\le L$的路径的长度平方和,感觉些微复杂。

我们先考虑$\le L$怎么做。

CF1100F. Ivan and Burgers

原题传送门:>Here<

我们发现一个询问$l,r$相当于把$[l,r]$里的所有数丢进线性基里,然后查询最大异或和。

用线段树维护线性基复杂度是$O(nlog^3n)$。我们考虑优秀一点的做法。

考虑分治。假设当前分治到$(l,r)$,中点为$mid$。

我们分别预处理出从$mid$往左右连续的线性基。

也就是对于$num_i$,当$i<mid$时,$num_i$为$[i,mid]$的线性基;否则就是$[mid,i]$的线性基。

这样对于一个跨越$mid$的询问,我们可以$O(log^2n)$合并线性基并$O(logn)$计算。对于一个只在左边/只在右边的询问,我们继续递归下去。

总复杂度$O(nlog^2n)$。

1220模拟赛 区间积

题目大意:

给一个序列和一些限制$l,r,ans$表示需要使得

$$\prod_{i=l}^{r}a_i\equiv ans(mod \space 10)$$

询问满足条件的序列个数。序列中每个数$0\le a_i< 10$。

我们发现$10$不是个素数,很难处理,所以我们把$10$拆成$2$和$5$,分别处理。

对于每个素数,我们考虑判断每个区间中有没有$0$。

设$g_{l,r}$为区间$[l,r]$中可以有$0$时的方案数,$f_{l,r}$为没有$0$时的方案数。

loj#2289. 「THUWC 2017」在美妙的数学王国中畅游

原题传送门:>Here<

这道题乍一看很高端,其实只要瞎JB泰勒展开一下再维护一下前几项的值就好了。。。

我们考虑对三个函数泰勒展开:

$$\sin(ax+b)=\sin(b)+a\cdot \cos(b)x- {a^2\sin(b)x^2 \over 2}-{a^3\cos(b)x^3 \over 6}+\cdots$$

$$e^{ax+b}=e^b+e^bax+{e^ba^2x^2\over 2}+{e^ba^3x^3\over 6}+\cdots$$

$$
ax+b=sb玩意儿
$$

接下来就是基本$LCT$处理了。

loj#6508. 「雅礼集训 2018 Day7」B

原题传送门:>Here<

我们发现有性质$(a,n)=1$,也就是说,$a\cdot i+b \mod n$的取值不会重复。

我们考虑对$S[0\cdots m-1]$建线段树,线段树下标为$a\cdot i + b\mod n$,存储的值是当前区间内$T$上对应位置为$1$的数的个数。

这样说可能有点抽象,我详细说明一下。

以样例为例:

1
2
3
9 5 6 4 3
101
...

构成的$S$的$a\cdot i+b\mod n$数组的前$m$项为

luoguP4385 [COCI2009]Dvapravca

原题传送门:>Here<

我们考虑随机选两个点,然后连一条经过这两个点的直线,并向两边扩展。做10000组就可以AC了。

以上是乱搞做法。

我们考虑当平行线平行于$x$轴时怎么办。

在这种情况下,我们只要把点投影到$y$轴上,然后查询最长连续红点就可以了。

其实绝对位置不重要,所以我们只要把点对纵坐标排序就行了。

现在我们考虑旋转平行线。

每次我们只需要把点投影到与平行线垂直的直线上,然后查询最长连续红点。

我们发现旋转平行线时,当两个点构成的直线与平行线平行时,也就说明这两个点的投影重合。那么在旋转前后,两个点的位置会进行交换。

这可以用线段树来维护。

loj#6132. 「2017 山东三轮集训 Day1」Flair

原题传送门:>Here<

做过家喻户晓的小凯的疑惑的人应该会熟悉一个性质,即两种互质钱币最大不能表示的数为$ab-a-b​$。

而我们发现一个非常好的性质:$c_ic_j\le 10000(i\ne j)$

设$v=gcd(c_1,c_2,\cdots,c_m)$,则所有$\ge 10000$的$v​$的倍数都可以被表示。

这时我们只需要考虑选出的菜的数量$\%v=i​$的方案数。

设$f=(100-p)+px$,我们对这个多项式做循环卷积,得到$f^n$,$f^n_i$表示的就是在$n$道菜中随机选,选出菜的数量$\%v=i​$的方案数。

这样答案就是$\sum_{i=1}^{v-1}f^n_i(v-i)$

0112模拟赛 吃干饭

题目大意:选择$[l,r]$中的若干数异或起来(也可以不选),问答案有多少种可能。

首先此题有一个$r-l\le 10000$的部分分很显然,只要把所有数丢到线性基里就ok了。

现在我们考虑正解。

我们发现当一个数可以被比它小的数表示时,就不需要加入线性基中。接下来我们考虑减少加入线性基中的数字数量。

我们发现对于两个相邻的数,$(2n)\oplus(2n+1)=1(n\in \mathbb{N})$。

所以我们找到$[l,r]​$中的第一个偶数(设为$x​$),则从$x+3​$开始的所有奇数都可以被表示为
$$
\begin{equation}
(y-1)\oplus(x)\oplus(x+1) \
=(y-1)\oplus1 \
=y
\end{equation}
$$
其中$y$为奇数。

这样在$[l,r]$的所有奇数中,只有$x-1$和$x+1$无法被这样表示。

以此类推,所有$\%4=2$的数也都是一样的:我们先找到第一个四的倍数$x$,然后把$x-2$和$x+2$加入线性基。

这样我们最多只需要加入$64\times 2$个数就ok了。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×