【算法】 性感理解支配树 ——litble

前言 orz一下这位大神。 本文献给想要性感地理解支配树的同学,如果你想更性感一点,所有证明均可跳过。 litble特别菜,有错误请指出,谢谢。 支配点 很久很久以前,有一张有向图,有向图有一个起点$S$,有一个叫小X的强盗,占据一个点拦路打劫。当小X占据了$x$点后,若从$S$出发就到不了$y$点 阅读更多…

【算法】 简单容斥模型 -boshi

容斥 本文将简单介绍几种常见的容斥模型,以及容斥方法。容斥和反演是离不开的,因为实际上它们就是同一种东西的两种表现形式,一种出现于小学课本,另一种出现于大学的教材。但是,容斥原理所运用的手段与技巧完全是基于反演理论的,因此,想熟练运用容斥原理,第一步就是完全搞清楚反演是什么。文章:从卷积到反演 经典 阅读更多…

【题解】 Blue and Red Tree 时光倒流 AGC014E

1. 题目 传送门= ̄ω ̄= 题目描述 有一个$N$个节点的树,节点从$1$到$n$标号,$N−1$条边中的第$i$条边连接节点$a _ i$和$b _ i$。 开始的时候所有的边都是蓝色,$Takahashi$会通过$n−1$步操作把这个蓝色的树变成红色。 每次操作包含以下步骤: $1$.选择一个 阅读更多…

【题解】 Split the Tree 树型dp 贪心 CF1059E ——quhengyi11

传送门:Split the Tree 题意:给棵树,每个点有权值,求把整棵树剖分成最少的路径(路径中每个点必须是深度依次递增的),每条路径上的点数要小于等于L,路径上所有点的权值和小于等于S 其实是一道想到题解蛮简单的题啦QAQ,可惜我比赛的时候调D题调了几年(感觉就算让我读到第E题也要调几年QwQ 阅读更多…

【题解】 宝藏 状压Dp NOIP 2017

//为了证明自己还活着赶紧写一篇文章.jpg 让我们病娇地学习QvQ 1. 题目 传送门= ̄ω ̄= 2. 题解 这题状态比较妙。。。 题目要生成树嘛。。。 首先可以想到枚举根节点,也就是直接从地面打通哪个点。 然后设$f[i]$表示状态为$i$时的最小花费。 枚举$i$的超集$j$(准确地说是“真超 阅读更多…