抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

CF490F Treeland Tour

题意 求树上严格 LIS 的长度。 n\le 6000 。 题解 比较平凡的 O(n^2\log n) 做法这里不考虑。 假定一个最朴素的 dp 状态: f_{u, 0/1, x} 表示 u 子树中往...
OIsol

2019 CSP-S 题解

前言 这场没来打,但看上去很不好打的样子。 D1T1 格雷码 Description 略 Solution 直接按照题意递归模拟即可,注意 2^{64} 超出了 long long 的范围,需要特判。 123456789101112131415161718192021222324252627#include <cstdio>#define FOR...
OIsoloi

解题报告 P1099 树网的核

题意 给定一棵边带权的树,在直径上取一条长度小于等于 s 的路径(可以退化成点)最小化树上其他点到路径上的最大距离。 思路 观察直径的性质 首先一棵树可以有很多条直径,但是他们分别必定关于他们的交点对称。 所以我们可以只考虑一条直径,不妨设两个端点分别为 P_1 , P_2 。下面指的路径全部为直径上的路径 然后,对于一个路径上的一...

解题报告 P2279 [HNOI2003]消防局的设立

题意 给定一棵树,一个选定的点可以覆盖距离小于等于二的点,求最少选点个数使整棵树被覆盖 思路 定义状态 f_{u,s} ( s\in\lbrace0,1,2,3,4\rbrace )分别表示当前子树根为 u ,满足状态 s 的最小消防局个数:...

解题报告 P3574 [POI2014]FAR-FarmCraft

题目内容 P3574 大意:村庄是一棵树,住在 1 号的管理要给每个房子送电脑,通过每个房子之间的道路需要 1 分钟,每个村民需要不同的时间安装电脑,而当管理把电脑送到村民后,村民会立即开始安装,最后管理会回到自己家给自己装电脑,求从管理出发到最后一个人装好电脑花费的时间。 解题思路 可以考虑每一个子树需要安装的最短时间。设住在 i 处的村民需要 c_i ...

解题报告 P6082 [JSOI2015]salesman

题目内容 P6082 大意:给定一棵 n 个点的树,有点权,从 1 号点开始一次旅行,最后回到 1 号点。每到达一个点,就能获得等于该点点权的收益。每个点都有进入该点的次数限制,且每个点的收益只获得一次。求最大收益以及方案是否唯一。 解题思路 不难发现,这道题满足最优子结构,一棵子树的答案可由这棵子树的子树合并而来。 注意到进入限制这个性质,到达这个点进入了一次,去到每一棵...



Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme