CF好题选做

CF好题选做

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

CF176E Archaeology

简要题意:

给一个树,现在有一个点集,支持加点和删点,要求在每次操作后求出当前点集的虚树上的点数。

做法:

我们考虑一个点集的虚树上的点数其实就是将点集按dfn排序后,$\sum$相邻点的距离/2。

所以只要用一个set维护点集,每次加入时维护相邻点间的距离就好了。

CF150E Freezing with Style

简要题意:

给一棵树,边有边权,询问所有长度在$L$到$R$之间的边中边权中位数最大的是哪条。如果有多组答案,输出任意一条。

做法:

首先显然二分+点分治,将每条边的边权定义为$c_i\ge mid?1:-1$,

这样问题就转化为了询问所有长度在$L$到$R$之间的边中有无边权和$\ge 0$的边。

假设当前做到一条边,长度为$x$,边权和为$y$,则问题就变成查询长度在$L-x$到$R-x$之间的边中的最大权值是否大于$-y$。

于是问题就变成了区间查询最大值。

假设我们当前做到分治中心的第$i$棵子树,那么这就是一个在长度为$n$的序列上进行$m$次询问的问题,要求做到$O(m)$的复杂度(否则总复杂度就变成$O(nlog^3n)$了),其中

$$n=\max_{j=1}^{i-1}(min(maxlength_j,R))$$

$$m=min(maxlength_i,R)$$

我们知道如果要求复杂度为$O(n)$的话,可以使用单调队列解决。

我们考虑乱搞一下:将子树按照$maxlength$排序,这样每次我们做的时候,$n$就比$m$小了。

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

CF975E Hag’s Khashba

简要题意:

给一个凸多边形,刚开始时1号点和2号点上钉着钉子。有两种操作:

1 f t: 拔去f号点的钉子,等待凸多边形受重力旋转。然后在t号点处钉一个钉子;

2 v:查询v号点当前的坐标。

做法:

我们考虑拔去一个钉子后,当凸多边形停止旋转时,剩下一个钉子与该凸多边形的重心的连线必定是垂直的。

我们首先求出重心,然后对于每个点,得到开始时该点与重心的连线与y轴所成的辐角$deg_i$以及该点到重心的距离$length_i$。

最后我们再存一下重心当前的位置$center$以及当前凸多边形旋转的角度$nowdeg$。

旋转的时候,设当前点为$i$,我们把$nowdeg$设为$-deg_i$,然后更新下$center$就可以了。

计算几何,注意细节。

PS: 在xay巨爷的帮助下,终于用acos通过了此题。

long double求三角函数记得using namespace std;

CF319E Ping-Pong

简要题意:

给一个区间的集合,定义区间(a,b)能走到(c,d)当且仅当$c<a<d$或$c<b<d$。

先有两种操作:

1 a b: 添加区间(a,b),满足(a,b)的长度严格大于之前的所有区间。

2 a b: 询问第a个区间能否走到第b个区间。

做法:

我们考虑从一个区间能走到另一个区间当且仅当这两个区间交叉或前者被后者包含。

对于第一种情况,我们发现这样的两个区间之间必定连了双向边,可以使用并查集维护。

每次加入一个区间时,把它和所有包含它的端点的区间连在一起。这可以用线段树维护。

查询两个区间联通时,特判一下a区间被b区间所在的连通块包含的情况就可以了。

CF809E Surprise me!

简要题意:

给一棵树,点有点权,点权为长度为n的排列,求

$$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\phi(a_i\times a_j)\times dist(i,j)$$

做法:

对于$a,b$,显然有

$$\phi(a)\times \phi(b)\times {gcd(a,b)\over \phi(gcd(a,b))}=\phi(a\times b)$$

所以原式可以变成

$$\sum_{i=1}^{n}\sum_{j=i+1}^n\phi(a_i)\times \phi(a_j)\times {gcd(a_i,a_j)\over \phi(gcd(a_i,a_j))}\times dist(i,j)$$

$$=\sum_{d=1}^{n}{d\over \phi(d)}\times \sum_{i=1}^{n}\sum_{j=i+1}^{n}[d=gcd(a_i,a_j)]\times \phi(a_i)\times \phi(a_j)\times dist(i,j)$$

考虑进行莫比乌斯反演,定义$g_d$为

$$\sum_{i=1}^{n}\sum_{j=i+1}^{n}[d=gcd(a_i,a_j)]\times \phi(a_i)\times \phi(a_j)\times dist(i,j)$$

$f_d$为

$$\sum_{i=1}^{n}\sum_{j=i+1}^{n}[d|gcd(a_i,a_j)]\times \phi(a_i)\times \phi(a_j)\times dist(i,j)$$

我们考虑求解$f_d$:

对于每个$d$,我们把满足$d|a[i]$的点$i$拿出来建虚树。这样式子就变成

$$\sum_i\sum_j\phi(a_i)\times \phi(a_j)\times (dep_i+dep_j-2\times dep_lca)$$

可以简单树形dp。

由中华级数可知,虚树总点数是$O(nlogn)$的。

CF700D Huffman Coding on Segment

简要题意:

给一个序列,每次询问提取出一个区间,对这个区间中每种权值的出现次数建Huffman树并求WPL。

做法:

首先显然需要莫队。

对于出现次数大于$O(\sqrt{n})$的权值,我们把它们的出现次数丢到堆里。

对于出现次数小于$O(\sqrt{n})$的权值,我们从小到大枚举出现次数进行处理,把合并后大于$O(\sqrt{n})$的再放到堆里。

最后再搞一下堆中元素就好了。

CF375E Red and Black Tree

简要题意:

给一棵树,边有边权,点有红黑两种颜色,定义一次操作为交换两个点的颜色,问至少需交换多少次,使得对于所有点,都存在至少一个黑点到其距离不超过X。

做法:

因为$n\le 500$,考虑一个$O(n^3)$的DP。

定义$f_{x,i,j}$为到点x距离不超过X的点为i,x的子树中已确定j个黑点所需的最小交换次数;

定义

$$best_{x,j}=\min_{i=1}^{n}f_{x,i,j}$$

转移时:(设u为x的一个子节点)

$$\begin{cases} f_{x,i,k-l}+best_{u,l} \to f_{x,i,k} \ f_{x,i,k-l+1}+f_{u,i,l}-[i是红点]\to f_{x,i,k}\end{cases}$$

有点卡空间,可以考虑使用unsigned short或者vector解决。

CF235D Graph Game

简要题意:

给一棵基环树,定义基环树上的点分治流程如下:

1
2
3
4
5
6
7
8
9
10

solve(t) (t为一棵基环树)

0.Cost+=size[t]

1.在t中选取一个点;

2.删去这个点;

3.对于删去点后剩下的每个连通块递归调用solve。

询问在每个1操作都是等概率随机在t中选点的情况下,Cost的期望是多少。

做法:

先考虑一棵树时怎么做。

显然答案可以看做$\sum$每个点在点分树上的深度,也就是每个点的祖先个数。

这可以转换成每个祖先都产生1的贡献。

对于两个点(a,b),我们考虑什么情况下a是b的祖先。

显然a是b的祖先,当且仅当a比a到b的链上其他的点都要早选。

概率即为$1\over dist(a,b)$

我们现在考虑基环树的情况。

我们依然考虑a什么情况下是b的祖先。

当a到b的路径上不包括环时,和树的情况一样。

当包括环时:

定义在a到b的路径上,且不在环上的点个数为X;

定义在环上两条路经上的点个数分别为Y,Z;

显然选a时a到b应当是联通的。

答案即是(X和Y此时都没被选的概率)+(X和Z此时都没被选的概率)-(X,Y和Z此时都没被选的概率)

CF1088F Ehab and a weird weight formula

简要题意:

给一棵树,点有点权,满足点权最小的点只有一个,且对于其他所有点u,都存在至少一个v使得$a_u>a_v$。

要求构造一棵新树,并最小化

$$\sum_{i=1}^{n}degnew_i\times a_i+\sum_{(u,v)\in newtree}\lceil log2(DistOld(u,v))\rceil\times min(a_u,a_v)$$

做法:

# cf

Comments

Your browser is out-of-date!

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

×