Home

Hot Hotels 加强版

https://www.luogu.com.cn/problem/P5904 题意 求在一个树内有多少个三元组$(i,j,k)$满足 $dis(i,j)=dis(i,k)=dis(j,k)$ 思路 假定,我们对于所有的三元组都处理成如下图所示的模样。 其中 I B K J 都是 点 A 的子树。 我们定义如下的变量。 F[u][i] --> 表示在点 u 的所有子结点中到达点 u 长度为 i 的个数。 G[u][i] --> 表示如上的二元组,连接到的中心节点 B 到达点 A 还剩下来的长度。 如果不明白看下图。 那么如果我们对于点 u ,其子树 v 我们的答案可以由 F[u][i] * G[v][i + 1] + F[v][i] + G[u][i...

Read more

连珠线

题意 我们有 n 个珠子,我们可以选择一枚珠子作为我们的起点。然后我们可以选择用红线将新珠子与已有的珠子连起来,或者在用红线连起来的两个点间加入一个点,并将红线替换为两个蓝线。 蓝线的长度即为我们的分数,求最大得分。 思路 首先我们任意选取一个节点作为根。 那么一定会出现下图所示的的状况。 那么对于一个节点我们有两种情况,要么是两个蓝线的终点,要么不是,那么因此我们用 $F[u][0 / 1]$ 来表示。 其中 0 表示不是中点,1表示是中点。 那么我们的答案就可以像下面这样的更新,假设点 $v$ 为点 $u$ 的子节点,$len$ 为两点间的距离。 \(F[u][0] = \sum_v \max(F[v][0] ,F[v][1] + len) \\ F[u][1]...

Read more

ABC238F Two Exams

https://atcoder.jp/contests/abc238/tasks/abc238_f 题意 在一个地方有 $N$ 名考生,共参加了两次考试两次考试的排名分别为 $P_i \ Q_i$ 。现在要求选出 $K$ 名考生,使得这 $K$ 名考生中不存在某位考生的两次排名 $(P_i , Q_i)$ 都比某位未选上的考生的两次排名$(P_j,Q_j)$ 低。 思路 对于该题目我们不妨将这些排名按照第一关键字为 $P_i$ 第二关键字为 $Q_i$ 排序。 我们发现如果在后面的考生想要参选,那么依照我们的排序规则我们已经知道了 $P_i < P_j$ 那么必须满足当前同学的排序 $Q_i > Q_j$ 才可以参选。 由于 $P_i$ 顺序是固定的,那么我们不...

Read more

Range Sums

https://atcoder.jp/contests/abc238/tasks/abc238_e 这个题目属实没想到,头一次在这个颜色的题目上栽跟头了。 不过也算上一种开开眼界了吧。 题意 我们有一组长为 N 的数列 A,现在你知道 Q 组 $[L , R]$ 并且知道 $A_L+…+A_R$ 的值。求解 $A_1+…+A_N$ 是否可知。 思路 我们可以将数列 $A$ 转化为前缀 $S$ 那么对于每次知道的的 $[L , R]$ 就可以相应的转化为 $S_R - S_{L - 1}$ 。 那么每次我们都得到一组 $(L - 1 , R)$ 如果我们将这个模型转化为图的的话,我们最终的目标是 $S_N - S_0$ 那么也就变成了存在一条从点 $0$ 通往点 $N$ 的...

Read more

Centroids

https://codeforces.com/contest/708/problem/C 可以选择在这里阅读 题意 你拥有一棵树,现在你又一次改造树的机会,即删去原来树中的一个边,并且加上一个边使得其依然为树。求问对于每个点而言,是否存在机会使得改造后的树其可以成为树的重心。 思路 我们如果想要求其改造后是否可以取得重心,因此我们对任意一个节点,我们需要求得其最大子树中,最大可以切出来多少个点。 那么图也就变为如下所示。 还有一种情况是其最大子树是点 u 的父节点。 如我我们需要更新这个节点的话,我们不妨设置如下几个变量。 s[u] 表示将其及其子树可以切下最大合法的子树 f[u] 表示在其父节点中除了点 u 外可以切下的最大合法子树 g[u] 表...

Read more

Distance Tree(hard version)

https://codeforces.com/contest/1632/problem/E2 可以在这个地方阅读 题意 你拥有一棵树,定义其根为 1 号节点,现在你有能力在这棵树中再添加一条边。使得这棵树的最长路径改变。现在你添加的这个边的边权从 1 - n 依次增大,求问,每次增大后加入一条边,使之最长路径的最短距离为多少 思路 首先,我们可以贪心的去思考问题。对于新加入的一个边,如果我们边的其中一个端点是 1 号点的话,那么可保证,最优解中一定存在端点连接 1 号节点的点。 然后,如何寻找的最优解呢。 如果我们在子树中寻找到了一个最长链,我们取其中点,那么我们如果我们链接一条从 1 号点的边到这个点,那么此时,我们的答案便可以分割为两个部分,一个部分是 $\lceil...

Read more

Riv 河流

也可以选择在这里阅读 题意 有一个 n + 1 个节点的树,其中 0 号节点为根。每个节点上都有一些物品,每个边都有长度。现在所有的物品只能朝着根的方向前进,现在设置k节点作为终点。问所有物品的移动距离之和最小是多少。 思路 首先,如果我们要求解其最小花费,我们发现其情况过于复杂。但是如果我们从另一个角度来看这个题目的话,就会变的简单许多。原本,u 节点到 0 点需要 deep[u] * w[u] 这么多的花费,如果我们在这里设置中终点,那么这些节点的花费就被我们省下来了。对于原本属于 u 的子树中的所有节点,如果它原本是要到终点。那么同样的也将省下来 deep[u] * w[x]。 因此我得到如下的策略,每次计算出来节省的最多的花费。 我们设置如图所示的状态。 ...

Read more

炸鸡块君与fifa22

https://ac.nowcoder.com/acm/contest/23106/B 炸鸡块君与FIFA22 题意 我们的分数有以下的规则 胜利 +1 分 平局 不变 失败 -1 分,如果我们此时是 3 的倍数那么分数不变 现在我们得到一个字符串,表示其游戏的情况。 现在我们要求每次询问时的游戏状况为 [l,r] 区间的最终得分 思路 对于该题目,我们假设我们在这个区间的初始值分别为 0,1,2 那么也就对应了三种情况,其中 0 的状况对我们来说稍微有点特殊,因为对于这个点而言它的分数并不会降低。因此我们依照这样的情况分别写出对于该点而言,经历一个区间其分数的增减情况。 如果我们想要算出一个区间的增减情况的话,那么我们不免的需要遍历一遍。 但是,由于...

Read more

This is my site

welcome!