CF好题选做

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

HNOI2019 JOJO

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

WC2019游记

day 1

THUWC D2挂惨之后,终于有时间能好好放松一下了qwq。

上午去报到,顺便在墙上留了点纪念:

然后去寝室放了下东西。

THUWC2019游记

day -2

非常紧张,不知道该说什么好。

今天的模拟赛考的还行,T2一个能被卡成$O(n^2)$的分块算法竟然被放过去了,开心。可惜T3的35分最后没写出来,被各路神仙爆踩。

考完以后,慌得一比的我到校园里去逛了一大圈冷静了一下,感觉好多了。


下午写了道SAM题,基本是秒切。感觉心里有底了一点点。

下午去打了会儿篮球,然后玩了几局狼人杀,感觉轻松了一点。只可惜最后我居然忘记了是屠边,居然还想着把所有人杀光。。。

还吃了梦寐以求的泡椒风爪!!!爽得要命

晚上复习了一下二项式反演和Min-Max容斥,心里还是很没底。不过THUWC应该不会考这种概率DP题吧?不管怎么说,还是准备一下好。

THUWC的时候,只要我把能拿到的暴力分搞定,再刚出至少一道题的正解,应该就差不多了吧?现在我要做的就是冷静下来,不要自己吓自己,成绩应该不会太差。

话说回来,只要能尽自己的力做到最好,不管结果怎么样,应该都可以释然了吧。

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$轴上,然后查询最长连续红点就可以了。

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

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

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

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

这可以用线段树来维护。

Your browser is out-of-date!

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

×