首页 > 其他分享 >codeforces 树上题目总结

codeforces 树上题目总结

时间:2023-07-04 11:13:34浏览次数:48  
标签:pre 那么 题目 复杂度 codeforces sqrt 最小 mathcal 树上

codeforces 树上题目总结

CF1559D2

先猜一个结论——一定能通过加边让一个森林变成一棵树,归纳一下发现是对的,并且随便加合法的边都符合条件,所以暴力是 \(\mathcal O(n^2)\) 的。

那么考虑如何降低复杂度。我并没有想到。我一直是在往快速找到两个不属于同一集合的点这个方向思考的,其实中间想过先贪心的将其中一个点暴力连边,但是并没有往这个方式深入思考导致错过正解。

正解就是先连一个点 \(x\),然后分为三个点集:\(S\) 集合中的点表示连接了 \(A\) 森林中的 \(x\) 并且没有连接 \(B\) 森林中的 \(x\);\(T\) 集合表示连接了 \(B\) 中的 \(x\) 而没有连接 \(A\) 中的 \(x\),\(U\) 集合表示剩下的点的点集。

然后可以发现:\(S\) 中的任何一个点可以和 \(T\) 中的任何一个点连边,所以说就让 \(S_i\) 连 \(T_i\),\(1\le i\le \min(|S|,|T|)\) 即可。

CF1521D

这题挺简单的,容易想到设 \(dp_{x,0/1}\) 分别表示使 \(x\) 子树内形成 \(x\) 是/不是链的一个端点的最小代价,然后记录一下 \(son_x\) 表示当形成的链的端点有一端是 \(x\) 时由谁转移过来,\(ls_x,rs_x\) 表示两端都不是 \(x\) 时的转移对象。然后就能输出方案了。

CF1637F

第一个结论:建造场地在叶子。当时做这道题的时候状态不是很好,直接点开了题解,感觉吧这道题荒废了。

然后其实比较正常的就能想到把权值从小到大或者从大到小考虑,这题从大到小考虑比较好。将权值最大的点作为根,那么一定有两个在不同子树内的点的代价是 \(\max\{a_i\}\),接着就可以发现,其他点 \(x\) 只需要满足子树内有一个叶子的代价大于等于 \(a_x\) 就行了,这是很好 DP 出最小代价的,最后贪心的选取两个 \(\max\{a_i\}\) 放置的位置即可。

这题到这里就结束了,复杂度 \(\mathcal O(n\log n)\)。

CF1253F

看起来就很最小生成树,但肯定不能暴力去建,要观察性质。

其实这棵树 \(i\) 和 \(j(i\le k,j\le k)\) 之间的连边的权值是原图中 \(i\) 和 \(j\) 的最短路,那么肯定是魔改一下 \(dijkstra\) 然后能够把所有可能有用的边在一个较低的复杂度内找出来。

其实我最开始想的是从 \(1\) 号点开始拓展跑单源最短路,在过程中如果找到了一个点 \(x\le k\),那么将它的 \(dis_x\) 变为 \(0\) 继续跑最短路,但是假的离谱。

单源最短路不行肯定想多元最短路。一个比较显而易见的想法是记录 \(dis_{x,0/1},pre_{x,0/1}\) 表示从 \(1\sim k\) 这些点出发到达 \(x\) 的最小值、非严格次小值以及它们对应的起点。但是这样子虽然连出来的边正确性有保证但是无法保证连出来的不是森林而是一颗树。原因是一个点有可能作为生成树上多个相邻点对之间路径上的点

那么如何找?既然点有可能重复那么边呢?边是不可能在多个树上相邻点对之间出现的,不然就有环了,所以说不妨枚举边,按照边来存,即存下来 \(x_i,y_i\) 表示第 \(i\) 条边有可能作为 \(x,y\) 路径上的边,很容易发现这样的 \(x,y\) 最多只有一对,因为假设第 \(i\) 条边在原图上两端是 \(p_i,q_i\),他们的在多元最短路上的最短路的出发点记为 \(pre_{p_i},pre_{q_i}\),肯定只有那么所有包含第 \(i\) 条边的路径中只有从 \(pre_{p_i}\) 到 \(pre_{q_i}\) 的路径是最短的,因此按照最小生成树的构建方法可以发现,这样的 \(x_i,y_i\) 只有可能是 \(pre_{p_i},pre_{q_i}\)。

然后就结束了,建出来最小生成树之后就乱求了。

CF1508C

下文中“没有出现过的边”指出去题中的 \(m\) 条边之外的边。

我没做出来。首先有一条性质,就是说存在一种最优方案使得在所有没有出现过的边中最多只有一条边非零,证明如下:

引理:记 \(S\) 表示所有没有出现过的边的边权的集合,则 \(\&_{x\in S}x=0\)。

这个比较显然,因为如果存在两个边权 \(x\&y\not=0\),那么让这两个边的边权同时减去 \(x\&y\) 即可。

由上述引理可知:\(\sum_{x\in S}x=\bigoplus_{x\in S}x=\bigoplus_{i=1}^{m}val_{e_i}\),这是确定的,那么接下来我们分成两种情况:

  1. 当我们用上所有没有出现过的边时,那么不管怎么分配答案都一样。
  2. 当我们有至少一条没出现过的边没有用到时,那显然让那条没出现过的边非零就行,这样其他边都是 \(0\) 了,肯定优秀。

综上结论得证,所以说我们现在有一个关键任务就是把这张图的补图的联通性搞清楚,可以 \(\mathcal O(\dfrac{n^2}{w})\) 做,但是有更快的方法,就是先将补图中度数最大的点连的边暴力连出来,剩余没连过的点最多有 \(\dfrac{m}{n}\) 个,那么剩余的点就可以暴力做了。我并没有想到这个方法,还是没有从第一步贪心往后面想,并且平衡方向错了,我一直是想用连通块个数是 \(\mathcal O(\dfrac{m}{n})\) 来做的。

然后把连通性搞出来了,就分成两种情况:

  1. 没有用到所有没出现过的边,那么直接最小生成树即可,记这颗最小生成树为 \(T\)。
  2. 用到了所有出现过的边。其实有两种做法,一种是分析之后发现这种情况下 \(n\) 是 \(\mathcal O(\sqrt m)\) 级别的,随便做都行,另一种则是说:可以把没出现过的边给替换掉的边一定是原图的最小生成树上的边并且不在 \(T\) 上的边,其实很显然哈(因为如果不在原图最小生成树上那肯定不是用它来替换,而是用别的边权比他小的边来替换)。当然还可以树剖啥的,都能做,不难。

到这里就做完了,其实我也做的差不多,关键性质都发现了,就是本来以为 \(\mathcal O(\dfrac{n^2}{w})\) 过不了,浪费太长时间。

CF1467E

这题很简单,但我做了很长时间,主要是重构次数太多了,最后写了个很蠢的虚树做法,没脑子,不写了。

有一个结论:不能存在一条链上有三个相同的权值,否则答案为 \(0\)。然后对于其他情况,对于每个颜色,如果有多于一个相同颜色的点,就把他们相背对的子树标记为不合法即可。

CF804D

没做出来/kk。这题优化方向搞错了/oh。暴力怎么做就不细说了,直接算就行,复杂度 \(\mathcal O(n^2)\)。有一个比较显然的启发性的优化就是每次枚举点数少的那棵树连那些点,然后复杂度就是对的,具体为啥对呢,根号分治!

像这种 \(\sum size=n\) 的题其实一般都该往根号上想一想,我也想了,不过方向又错了——我想成 \(size\) 只有 \(\sqrt n\) 中了,然后发现一点儿用没有,下面说复杂度证明:

对于较小树大小是小于 \(\sqrt n\) 的询问,显然复杂度是 \(\mathcal O(q\sqrt n)\),而如果两个都是点数大于 \(\sqrt n\) 的树,那么每一颗点数大于 \(\sqrt n\) 的树最多只会被作为较小树 \(\sqrt n\) 次,所以说复杂度是 \(\mathcal O(\sqrt n\times \sum_{size_i\ge \sqrt n}size_i)=\mathcal O(n\sqrt n)\),记忆化一下就行。

CF1485E

很简单,\(dp_{i,j}\) 表示从红色在 \(i\),蓝色在 \(j\) 这个状态开始操作能获得的最大价值,优化就是 \(dp_{i}\) 表示从红色在 \(i\) 时开始的最大价值,转移可以树状数组啥的轻松转移。

CF1779F

首先考虑 \(n\) 是偶数时,显然对根连续操作两次即可。

这个很有启发性意义,我们可以发现如果子树 \(subtree(x)\) 有奇数个点那么操作它没用,而如果有偶数个点,我们对 \(x\) 连续操作两次可以是相当于对于全局的异或和又异或了一个 \(sum_x\),而且我们发现,对全局异或和有影响的所有操作位置不能有祖先儿子关系,否则作为儿子的点操不操作没区别。

然后就可以 DP 了。

CF1065F

首先有一个贪心思想就是说如果对于子树 \(x\),如果我们想回到 \(x\) 及它的上面,我们肯定是先遍历深度最大的儿子,最后便利深度最小的儿子,然后就设 \(f_x,g_x\) 分别表示能不能回到 \(x\) 的最大价值。转移就行。

标签:pre,那么,题目,复杂度,codeforces,sqrt,最小,mathcal,树上
From: https://www.cnblogs.com/zyc070419-blog/p/17525186.html

相关文章

  • Codeforces 293B Distinct Paths
    发现\(n,m\)的数据范围是假的,因为每一步一个颜色最多也就\(k\le10\)种颜色,所以当\(n+m-1>k\)时一定无解。接下来发现这个数据范围挺小的,考虑状压,设\(f_{x,y}\)为走到\((x,y)\)点所用的颜色的集合,其可以由\(f_{x-1,y},f_{x,y-1}\)推来。然后就可以......
  • Codeforces Round 878 (Div3)
    B.BinaryCafe\(1\leqn,k\leq10^9\)题解:思维考虑两种情况第一种:钱足够多,每种咖啡都可以买的情况下,答案为\(2^k\)第二种:钱不够多,因为任一面值的钱数都有唯一的二进制表达方式,所以答案为\(n+1\)所以我们不妨先判断一下\(2^k\)有没有超过\(10^9\),如果超过了说明钱......
  • CodeForces 1508D Swap Pass
    洛谷传送门CF传送门先忽略掉所有\(a_i=i\)的点。考虑我们钦定一个点\(s\),每次与\(a_s\)换直到\(a_s=s\)为止。不难发现这样相当于在置换环上删掉\(a_s\)这个点。这样可以解决\(s\)所在的环。问题是可能会形成很多个环。我们把其他点按照\(s\)极角排序,注意......
  • Codeforces 585D Lizard Era: Beginning
    很容易想到可以对于每个任务选不去的那一个人进行搜索,时间复杂度\(O(3^n)\),明显过不了。发现\(n\le25,\lceil\frac{n}{2}\rceil\le13\),且各个任务间不会互相影响,便可以用折半搜索分成\(2\)部分来搜最后来合并。考虑如何合并两部分,令前一部分得到的值分别为\(a,b,c\),后......
  • 2022年AMC8数学竞赛题目及考点分析
     2022年AMC8数学竞赛题目及考点分析!1.选择题答题技巧❶ 特定值法➤ 当几何图形不是唯一确定时,可以假设某些特殊条件(例如某个特殊角度或者某条边长),然后再进行计算;➤ 题目中要求最大值或者最小值时,从最极端的情况开始考虑,此时往往假设变量中的一个取到其最值;➤......
  • Codeforces Round 881 Div2 A-F1题解
    codeforcesround881div2题解马上要秋招了,自己本事全丢了,感觉如果这样的话今年就估计要饿死了。先打div3,7月份得开始收心了A.SashaandArrayColoring题意,可以分任意组,每组的贡献是max-min,问最大贡献显然是贪心,从大到小配对一下就行,不想放代码了’B.LongLong给出一......
  • 一类做法基于变化次数的题目的总结
    最近遇到不少这类题目啊,但自己像个【数据删除】一样完全没有总结经验,被花式吊打。所以痛定思痛,决定总结一下。CF475D.CGCDSSQ我们可以把询问离线下来,求区间\(\gcd\)等于\(x\)的等价于求区间\(\gcd\)不大于\(x\)的减去不大于\(x-1\)的。考虑固定左端点,每次暴力往右拓......
  • 题目集4,5的总结性blog
    前言:题目集4和5的知识点、题量、难度等情况如下:知识点:JAVA基础,基础算法,面向对象程序设计题量:共计2道题目难度:题目较难,有挑战性和突破性设计与分析:本次Blog重点分析成绩计算系列题目,即题目集4的7-1、题目集5的7-1。这两道题都是计价系统的迭代,延用前几次......
  • Codeforces Round #877 (Div. 2) A-E
    A代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;boolsolve(){intn;cin>>n;intmx=-2e9,mi=2e9;for(inti=1;i<=n;i++){intx;cin>>x;mi=min(x,mi);......
  • C/C++《数据结构课程设计》题目[2023-07-01]
    C/C++《数据结构课程设计》题目[2023-07-01]《数据结构课程设计》题目一、【大数四则运算】——线性表[习题描述]设计—个实现任意长的整数进行四则运算和幂次运算的演示程序。[基本要求]利用双向循环链表实现大数的存储,每个结点含一个整型变量。[实现提示]实现原理:任何一......