RK_little

分类

翻译(1) 题解(39)

/ 注册

全部文章（共38篇）

46th ICPC 上海 H Life is a Game

H Life is a Game 思路该题采用kruskal重构树。 kruskal 重构树的特点是将边权化为点权。当我们使用kruskal求取最小生成树的时候，我们不需要直接生成该树。每次，我们得到两个点的时候，我们将其连成边时，我们只需要将这棵树两个点提出来，然后我们新加上一个点，且该点的...

lca kruskal重构树

2022-03-16

1 627

P5903 【模板】树上 k 级祖先

read it on blog P5903 【模板】树上 k 级祖先题意给定一棵树，我们要求 x 的上 k 级祖先。思路由于该题为长链剖分的模板题，因此重要介绍一下，长链剖分。对于一棵树，我们的长链剖分和重链剖分，我们对每个链取最长的那条链作为我们的重链。如上图所示，我们可以把这棵树拆成...

长链剖分

2022-03-16

0 603

P3647 连珠线

P3647 连珠线题解题意我们有 n 个珠子，我们可以选择一枚珠子作为我们的起点。然后我们可以选择用红线将新珠子与已有的珠子连起来，或者在用红线连起来的两个点间加入一个点，并将红线替换为两个蓝线。蓝线的长度即为我们的分数，求最大得分。思路首先我们任意选取一个节点作为根。那么一定会出现下...

树形DP

2022-02-20

0 369

ABC238F Two Exams

ABC238F Two Exams 题意在一个地方有 NNN 名考生，共参加了两次考试两次考试的排名分别为 Pi QiP_i \ Q_iPi Qi 。现在要求选出 KKK 名考生，使得这 KKK 名考生中不存在某位考生的两次排名 (Pi,Qi)(P_i , Q_i)(Pi...

背包

2022-02-20

0 483

ABC238E Range Sums

ABC238E Range Sums 这个题目属实没想到，头一次在这个颜色的题目上栽跟头了。不过也算上一种开开眼界了吧。题意我们有一组长为 N 的数列 A，现在你知道 Q 组 [L,R][L , R][L,R] 并且知道 AL+...+ARA_L+...+A_RAL+...+AR 的值。求...

并查集图论前缀和

2022-02-20

0 444

CF708C Centroids 题解

CF708C Centroids 题解可以选择在这里阅读题意你拥有一棵树，现在你又一次改造树的机会，即删去原来树中的一个边，并且加上一个边使得其依然为树。求问对于每个点而言，是否存在机会使得改造后的树其可以成为树的重心。思路我们如果想要求其改造后是否可以取得重心，因此我们对任意一个节点，我...

树形DP

2022-02-19

0 295

# CF1632 E2 Distance Tree (hard version)

Distance Tree (hard version) 可以在这个地方阅读题意你拥有一棵树，定义其根为 1 号节点，现在你有能力在这棵树中再添加一条边。使得这棵树的最长路径改变。现在你添加的这个边的边权从 1 - n 依次增大，求问，每次增大后加入一条边，使之最长路径的最短距离为多少思路首...

树形DP 贪心

2022-02-01

1 666

P3354 Riv 河流

P3354 Riv 河流也可以选择在这里阅读题意有一个 n + 1 个节点的树，其中 0 号节点为根。每个节点上都有一些物品，每个边都有长度。现在所有的物品只能朝着根的方向前进，现在设置k节点作为终点。问所有物品的移动距离之和最小是多少。思路首先，如果我们要求解其最小花费，我们发现其情况...

树形DP

2022-01-31

0 357

ACM is all you need

ACM is all you need 题意我们得到一个数组 f[n] 。同时我们定义 local minimum 为 f[i]<min⁡(f[i−1],f[i+1])f[i] < \min(f[i - 1] , f[i + 1])f[i]<min(f[i−1],f[i+1]) ...

数组贪心

2022-01-25

3 395

炸鸡块君与FIFA22

炸鸡块君与FIFA22 题意我们的分数有以下的规则胜利 +1 分平局不变失败 -1 分，如果我们此时是 3 的倍数那么分数不变现在我们得到一个字符串，表示其游戏的情况。现在我们要求每次询问时的游戏状况为 [l,r] 区间的最终得分思路对于该题目，我们假设我们在这个区间的初始值分...

动态规划倍增

2022-01-25

4 618