Home

世界树

如果不会建立虚树的话可以参考这个 题意 我们得到一棵树。这些节点中会定期选出几个关键点。对于所有的点他们受到距离他们最小的点且编号最小的点的控制,求最后每个关键点都会控制多少个点。 思路 我们不难想到一种树上 DP 的方式,首先先从子树向上传递,然后再由父节点向子树传递,就可以传递成功了。 但由于我们的询问轮数太多了,我们根本来不及一个一个传递。那么对于一些点我们建立一颗虚树。 我们记该点受 g[u] 点控制,其距离为 d[u]。 我们拷贝t=size[x] 并遍历点 x 的所有子树。 x 和 y 表示虚树上的两个节点,且 x 和 y 两个节点受到的控制点不一样。那么我们计算得出两个控制点之间的分界点 z(z 受到 x 控制)。 然后我们将这个分为三个部分 ...

Read more

骑士

题意 有 $n$ 个点,第 $i$ 个点连着 $a_i$ 点。其中每个点都有一个权值。对于每条边而言,其两端的点不可以同时加入总和。我们要求总和最大值。 思路 可以借鉴之前的blog 首先,这个图可以看出是一个个基环数组成。我们要求的就是所有基环数的总和最大值的和。 对于一个基环树,我们有入下图所示的样子。 从图中我们不难发现,我们有如下一个环,[1,12,7,14,4,11] ,如果我们断开其中一个路径,那么他的样子就成为树了,我们断开 [1,11] 这条路径。分别以 $1$ 为根和以 $11$ 为根做树形 dp。 先忽略环的影响,那么我们对于如下的树我们该怎么计算才能得到正确答案呢? 我们设 f[i,0/1] f[i,0] 表示第 $i$ 个点不包含的最大...

Read more

Island

https://www.luogu.com.cn/problem/P4381 题意 有 $n$ 个点,每个点 $i$ 都有一条出发到 $a_i$ 的边有权值 $w_i$ 。 求这些点形成的基环树他们的直径之和。 思路 对于这样的一个基环树 11 3 23 15 8 10 7 12 9 7 1 3 10 6 2 5 15 3 2 5 1 15 1 90 14 3 11 10 4 23 11 8 78 13 1 12 6 5 54 9 6 1 3 10 3 我们可以将其变形为这样 那么我们就得到了一个环和环上点的子树。 那么我们基环树的直径就变成了两个部分,要么是子树的最大直径,要么是环上最大长度。 对于子树最大直径不再赘述。 环上的直径如何计算呢。首先,我...

Read more

Directed Roads

题意 我们有 $n$ 个点和 $n$ 个边,其中第 $i$ 条边连接至 $a_i$ 点。每条边需要指定一个方向。求问,有多少种方案使图中不出现环。 思路 我们可以发现,每个点的度至少为一,那么我们便可以得出以下的结论。 假如我们一共 $k$ 个连通图,那么我们这 $k$ 个连通图中边的数量一定等于点的数量。 如果边的数量等于点的数量的话,我们的图便是一个基环树,假若我们的图如下所示有多个基环树。 我们不难发现基环树可以拆分为两个部分 以紫色为边的环 以环的点为根的树 对于所有的树,无论我们怎么算都无法将其变为环图,因此我们只需要统计树中边的个数 $k$ 即可算出这部分的答案 $2^k$ 对于所有的环,我们只有两种方案(都朝向一个地方)让他们成为环,因此我...

Read more

No Adding

题意 有一组两两各不相同的数字,每次我们可以进行如下的操作。 取两个数字 [x,y] 如果 gcd(x,y) 没有在这组数字中将其加入这组数据。 求问,最多可以加多少组数字。 思路 如果将每个数字进行唯一分解的话,我们可以发现我们添加的数字就是那些数字的相同部分。 如果我们将这个相同部分提取出来的话,那么剩下的部分进行 gcd 的话,他们的结果一定为 1. code

Read more

Interacdive Problem

https://codeforces.com/contest/1624/problem/F 题意简述 这是一道交互式题目。 有一个数 $x$ 和一个数 $n$ 其中 $1\le x < n$ 你可以进行如下的询问: + c 将 $x$ 的值变为 $x + c$ 其中 $1\le c < n$ 然后返回一个值 $\lfloor\frac{x}{n}\rfloor$ 如果你在十次之内猜到的话则输出 $x$ 即可。 思路 由于我们只能得到 $\lfloor\frac{x}{n}\rfloor$ 那么我们不妨用二分的想法来考虑这个题目 对于我们上一个得到的 $k = \lfloor\frac{x}{n}\rfloor$ 我们可以分析出我们需要的数值一定...

Read more

This is my site

welcome!