旅游题目题解_牛客竞赛OJ

摸鱼学大师

发表于 2021-11-01 19:01:11

题目的主要信息：地图上有 n 个城市，它们之间通过 n-1 条道路联通，即一棵无向树第一天会在 s 市住宿，并游览与它距离不超过 1 的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过 1 的所有城市不能住在一个已经浏览过的城市，最多要游览多少天因为每个会去到与这个城市相连展开全文

ray52033

发表于 2020-06-07 10:10:48

树形DP 其实这道题大体思路跟牛客小白月赛25的C题差不多，或者说是大部分的树形DP可能都是这个思路吧。首先在这道题中，一共有条边，很明显是棵树，接着看，它限制了每次游览只能游览当前住宿过的城市周围距离为1的所有城市，这不就是对于一个点去参观所有他的儿子节点吗？再然后，他会选择一个城市住宿，那么我展开全文

shyyhs

发表于 2021-01-16 15:48:24

思路: 简单的思考一下,这题就是没有上司的舞会.首先,我假如选了这个点,那么它的子节点都不能选,假如我这个点选了的话,那么它的子节点既可以选,又可以不选. 代码: #include <bits/stdc++.h> using namespace std; const int N=5e5+ 展开全文

Kur1su

发表于 2020-06-05 23:50:45

Description Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。旅行地图上有n个城市，它们之间通过n-1条道路联通。Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。他们不想住在一个已经浏展开全文

DaMing

发表于 2020-06-01 15:24:16

题目描述Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。旅行地图上有n个城市，它们之间通过n-1条道路联通。Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。他们不想住在一个已经浏览过的城市，又想展开全文

萝卜朝天椒

发表于 2020-06-01 23:59:36

题意：给定一棵 n 个节点的树，初始选择节点 s，第一天定居在s，并将s和与s相邻的节点染色。之后每一天选择一个未染色的点定居，将定居点和定居点相邻的节点染色。问最多能定居多少个节点。题解每个点都会被染***r>考虑如何给叶子节点染色，发现要把叶子节点染色，定居在叶子处最佳，所以我们首先选择展开全文

zzugzx

发表于 2020-06-01 12:12:35

题目链接题意：题解：AC代码 /* Author:zzugzx Lang:C++ Blog:blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #define fi 展开全文

wxyww

发表于 2020-06-01 16:31:09

solution 以为根进行。设表示以为根的子树中，是()否()选择了这个点，这个点是()否()被游览过的方案数。答案就是考虑如何转移。对于，既然这个点没被游览过，那么他的儿子就肯定不能选择，而且因为没选这个点，所以他的儿子就不能通过选择来被游览，所以就只能从转移过来。对于，可以覆盖他的儿展开全文

JQK2020

发表于 2020-06-02 16:10:49

题目描述Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。旅行地图上有n个城市，它们之间通过n-1条道路联通。Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。他们不想住在一个已经浏览过的城市，又想展开全文

小琢卷不动

发表于 2021-11-23 20:30:10

本质上就是一个没有上司的舞会。不能同时选相邻的两个点，另外根结点必选，直接考虑套没有上司的舞会的模板即可： f[u]f[u]f[u] 表示 uuu 必选，以 uuu 为根的子树的答案； g[u]g[u]g[u] 表示 uuu 不选，以 uuu 为根的子树的答案； f[u]←g[v]f[u 展开全文

相关比赛

等你来战