henry_y

分类

A-学习笔记(10) A-游记/杂谈(2) B-题库-51nod(2) B-题库-AtCoder(7) B-题库-BZOJ(48) B-题库-CodeForces(5) B-题库-HDU(5) B-题库-LibreOJ(7) B-题库-Luogu(16) B-题库-POJ(1) B-题库-牛客网(8) C-博客园美化(1) C-比赛记录及刷题计划(2) 动态规划-DP(12) 图论-网络流(1) 图论·最短路(3) 字符串-hash(1) 字符串-KMP(1) 字符串-Trie(2) 思想-分块(4) 思想-前缀和(1) 数据结构及算法-单调队列(4) 数据结构及算法-堆(2) 数据结构及算法-树链剖分(2) 数论-其他(3) 数论-博弈论(1) 数论-数论分块(1) 数论-欧拉函数(1) 数论-莫比乌斯反演(1) 数论·筛法(4) 未归档(3) 深度优先搜索-dfs(1) 贪心(1) 题解(37)

/ 注册

全部文章（共3篇）

题解|创世纪题解

这道题的边连起来的话是个基环树森林的样子(i往a[i]连边)，先考虑如果是个树怎么做，设f[i][0/1]表示节点i不选和选可投放的最大节点数量，则（因为一定要有至少一个子节点不选以限制当前节点）。可以先连的有向边，拓扑排序找出每个基环树里面的环，然后断掉环上的一条边来实现这个过程（在这之前重新建一...

基环树单调队列树形dp

2019-09-02

0 593

题解 | Island题解

基环树直径的板子。但是dfs会爆栈...所以最后改成了bfs。还是一个很考验码力的板子。首先基环树的直径显然有两种情况，在不进入环的情况下在一个子树内，这直接dp求就好了。第二种是一个子树中的链+环上一段+另外一个子树中的链。按这两种情况分类讨论即可。对于这种情况，可以在先求第一种情况的同时把子树中...

基环树单调队列树形dp

2019-09-02

0 605

[luogu 2458][SDOI2006]保安站岗

题目描述五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需...

贪心 DP 树形dp

2018-09-02

0 564