题面 P4606 [SDOI2018]战略游戏 Solution 圆方树上圆方果， 圆方树下你和我。 圆方树前建虚树， 欢乐多又多。 好吧，我们来说正题。 这题就比较强。根据常识，如果我们爆掉的点能影响这个图的连通性，那么，这个点一定是割点。 因此，我们要先对原图做Tarjan求点双。接下来，我们考虑用圆方树来解决一个问题。 我们先考虑暴力怎么做，我们先对原图求出圆方树。 接下来，我们...

题面 P3233 [HNOI2014]世界树 Solution 这是一道虚树妙题。 我们不妨先考虑一下每一次$O(n)$计算的暴力怎么做。 $O(n\cdot m)$的暴力肥肠简单，我们只需要做两遍dfs。考虑设$f[i]$表示离$i$最近的聚居地是什么，$MIN[i]$表示$i$到最近的聚居地的距离。我们第一遍dfs先找出$i$到它子树内的聚居地的最小距离，之后再做一遍dfs来找$i$往...

题面 P4297 [NOI2006]网络收费 Solution 这题喵啊。 首先，我们会发现统计两个点互相的贡献是一个极其困难的问题。 但是，仔细观察那张收费表格后会发现，我们可以重新定义一下这个收费：我们假设路由器节点的颜色为叶子中数目较多的颜色，当一个叶子结点颜色与路由器节点颜色相同的时候不收钱，否则收一份钱。我们可以惊讶的发现，这样做之后我们的新收费做法就与原来题目要求的重合了，而且...

题面 4438 [HNOI/AHOI2018]道路 Solution 这是一道树形DP妙题。 平时，我们设计树形DP的状态一般都是以子树为基础来设计的。很不幸的是，这题因为那个蜜汁柿子无法化简，导致了极其严重的后效性。因此，我们这里并不能以子树为基础来设计状态了。 这题妙就妙在这个状态设计。这题我们考虑以链为基础来设计状态。 设$f[i][j][k]$表示从根节点到达第$i$个点，一路上经...

题面 SDOI2009 学校食堂 Solution 这是一道状压妙题。 首先，因为后面的东西能提到前面来做，导致了严重的后效性。为了消除这个后效性，考虑用状压来处理这个问题。 我们可以发现最多的提前量很小，只有7，考虑这样设： 设$f[i][j][k]$表示$[1,i-1]$已经完成了，从$i$开始往后7个的完成状态为$j$，上一个完成的相对$i-1$的位置为k。 转移比较正常：我们枚举一...

题面 洛谷P3174 Solution 我们不难发现，一条“毛毛虫”一定是由一条主链外加主链的点所连到的点构成的。 那既然是一条链，它的形态无外乎以下两种： 因此，我们可以直接枚举最上面的那个点，他做为根会产生的最大的答案即为其孩子的最大答案与次大答案之和再减去多算的一小部分即可。(具体转移可以看看代码，要做点简单的分类讨论) 时间复杂度$O(n)$ 就酱，这题我们就切掉啦(*´ﾟ∀ﾟ｀...

题面 传送门：SPOJ 694 Solution 这题可以用SAM来搞，也可以用SA来搞。但无论是哪种搞法，都是基本操作。下面我们来分别讲解一下怎么搞。 SAM 这题用SAM来求就十分粗暴简单。不会SAM的小伙伴可以戳这里 首先，我们先把SAM建出来。根据SAM的性质，我们从出发点随着SAM任意走，走到哪里都是一个完全不同的子串。因此，我们只需要对SAM做一个拓扑序DP/记忆化搜索即可求出...

题面 传送门：洛咕 Solution 感谢神仙@lizbaka的教学 这题是数位DP的非常非常模板的题目，只是状态有点多 . 这题我使用记忆化搜索实现的 中国有句古话说的好，有多少个要求就设多少个状态。 所以说，考虑这样设置状态: 设$f[i][j][k][2][2][2][2][2]$表示当前填到第i位，上一位填了j，上两位填了k，是否卡上界，上一个数是否为前导零，是否有4，是否有8，是...

题面 传送门：UOJ Solution 这题的数位DP好蛋疼啊qwq 好吧，我们说回正题。 首先，我们先回忆一下LUCAS定理： $C_n^m \equiv C_{n/p}^{m/p} \times C_{n\%p}^{m\%p} (\%p)$ 我们仔细观察这个定理，就可以发现一个事实：LUCAS定理本质上是在对n，m两个数做K进制下的数位分离 所以说，LUCAS定理我们可以这样表示： $...

题面：洛谷 Solution 首先，我们可以先康一康题目的数据范围：n<=18，应该是状压或者是搜索。 事实上，这题搜索和状压DP都是能做的。 （因为搜索在我心中留下了阴影（斗地主），所以在这里，我讲状压DP的做法） 根据我们以往设计状压DP的经验，我们可以很轻松地设计这一题的状态： 设f[i]表示打下的猪猪的状态为i的方案数，（状态在这里用二进制方式来表示，例如：00101表示打下...