Luogu – P3698 – [CQOI2017]小Q的棋盘

题意

给定一棵 $n$ 个节点的有根树,定义一次移动为:从当前所在节点移动到一个相邻节点。问从根节点出发,移动 $k$ 次后,最多经过多少个不同的节点。

每个节点可以被重复经过,但只计算一次。

$n\leq 100$.

分析

这道题可以用树形 DP 来做,这里只提供时间复杂度更优的贪心做法。

首先很容易想到,我们要尽可能保证每一次移动都到达一个新的节点,所以要先向深度最深的节点走。

如果走的过程中,$k$ 次移动机会就用完了,答案即为 $k$.

若否,我们要耗费尽可能少的移动次数,来到达一个新的节点。可以发现,在走完最长链之后,每到一个新节点都只需要 $2$ 步

Snipaste_2021-05-12_16-34-24.png

如上图所示。先选择最长链 $1\to 2\to 5\to 9\to 12$. 此时如果要再添加点,只需要找一个与任意一个被选节点相邻的节点即可。

比如选择了点 $4$,那路径就变成:$1\to 2\to 4\to 2\to 5\to 9\to 12$.

由于每次新选的点,都与一个路径中的点相邻,所以只要在路径中插入两步,一定可以走到这个新的节点。

因此,在选完最长链之后,剩余的步数每两步都可以走到一个新的节点

形式化地,设这棵树的节点个数为 $n$,最长链长度为 $l$,可用步数为 $k$,可以这样表示出答案:

  • 若 $k\leq l – 1$,步数只够在最长链上移动,则答案为 $k$.
  • 若 $k > l – 1$,走完最长链之后有剩余步数,则答案为:
$$
\max
\left\{
\begin{array}{lr}
l + \left\lfloor{\frac{k-l+1}{2}}\right\rfloor\\
n
\end{array}
\right.
$$

这里注意,如果步数足够多,也最多只能走完所有点,此时答案为 $n$.

时间复杂度为 $\mathcal{O}(n)$.

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 108;
int n, k;
struct Edge{
    int to, nxt;
}edge[MAXN << 1];
int head[MAXN], e_cnt = 0;
void add(int u, int v) {
    edge[++e_cnt].to = v;
    edge[e_cnt].nxt = head[u];
    head[u] = e_cnt;
}
int deepest = 1;//最长链的长度
void dfs(int x, int fa, int dep) {
    deepest = max(deepest, dep);
    for(int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].to; if(v == fa) continue;
        dfs(v, x, dep + 1);
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++) {
        int a, b; scanf("%d%d", &a, &b); a++, b++;
        add(a, b); add(b, a);
    }
    dfs(1, 0, 1);
    if(deepest >= k + 1) cout << k + 1 << endl;
    else cout << min(deepest + (k - deepest + 1) / 2, n);
    return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇