题面 蒟蒻博客：QAQ Solution 这是一道神题 首先，我们不妨想一下K=0，即求最短路方案数的部分分。 我们很容易可以想到一个做法，就是魔改迪杰斯特拉做法： 一个点可以更新到达其他点的距离，那个点的方案数就是这个点的方案数；如果一个点所更新出来的距离和之前的相等，那个点的方案数加等当前点的方案数。 用式子可以表现为： $$f[i]=f[i] (dis[j]>dis[i]+x)...

题面 传送门：洛谷 Solution 这是一道神奇的题目，我们有两种方法来处理这个问题，一种是DP，一种是组合数。 这题需要高精度，以下省略此声明 . DP 如果你对数学不感兴趣/喜欢写DP/(不想虐待自己)，这里是DP做法。 首先，我们可以发现，这个数最多有$w/k$位(向上取整),如下图所示： 那么，我们就可以以这个特性做DP啦。 设$f[i][j]$表示枚举到第i位(指2^k进制下...

题面 传送门：洛谷 Solution 这道题的是一道很巧妙的状压DP题。 首先，看到数据范围，应该状压DP没错了。 根据我们之前状压方程的设计经验，我们很快就能设计出这样的方程： 设$f[i][j]$表示用到第i个元素，当前连接状态为j的开销的min 但是我们很快就会发现，这个方程没法转移，因为随着连接方案的不同，新插入的点的K值会不同。 怎么办呢？ 这时候我们可以重新设计一个巧妙的的状态...

题面 传送门：洛谷 Solution 这是一道很有意思的在背包里面做容斥的题目。 首先，我们可以很轻松地想到暴力做背包的做法。 就是对于每一次询问，我们都做一次背包。 复杂度$O(tot_s_log(di))$ (使用二进制背包优化) 显然会T得起飞。 接下来，我们可以换一种角度来思考这个问题。 首先，我们可以假设没有每个物品的数量的限制，那么这样就会变成一个很简单的完全背包问题。 至于完...

题面 传送门：洛谷 Solution 这是一道十分经典的树形DP题，这种类型的树形DP有一种很普遍的解法。 首先，观察题目，我们把这道题转换一下：给定一颗树，选出包含1号节点（根)的一颗子树，使得点权和最大。 我们可以这样子定义状态： 设$f[i][j]$ 表示以i为根节点的子树，选出j个节点，所能达到的最大点权值。 对于二叉树来说，转移很显然，就是枚举左子树分配多少个节点，就可以对应的得...

题面 传送门：洛谷 Solution 这是一道简单的树形DP题。 首先，我们可以转换一下题面，可以发现，题目要求我们求出一颗树上的最大联通子图。 因为我们是在树上取的，实际上就是取一颗子树。 这个就是最基础的树形DP模型了。 我们可以设f[i]表示我们选的子图以i为根所能取的子树的最大值。 转移是： $f[i] = beauty[i] + xigema(max(f[j],0))$ （也就是...

题面 传送门:洛咕 Solution 挺有意思的一道题。 题面已经挺明显的描述出了这题的主要思想：倍增。 先这样想，我们可以把这题这样建模：有一堆点，若两个点之间的距离之和可以达到2的n次方，那么这两个点可以用1的时间相互到达。 也就是说，我们把距离能为2的n次方的点对用边权为1的边连上，再做一次最短路径，就可以求出答案了。 接下来问题就是如何求出每两个点是否能以2的n次方的时间相互到达。...

题面 传送门：洛谷 Solution 这题显然要先把缩点做了。 然后我们就可以考虑如何处理走反向边的问题。 像我这样的蒟蒻，当然是使用搜索，带记忆化的那种（滑稽）。 考虑设$f(i,j)$表示到达第i个点，还能走j次反向边，所能到达的最多的点的数量。 转移可以表示为： 如果x能到达1所在的强连通分量或max出来的值不为0，说明当前状态可行，否则不可行。 然后用记忆化搜索表达出来就OK了 ...

题面 传送门:洛谷 Solution 裸的求极大子矩阵 感谢wzj dalao的教学 首先,有一个很显然但很重要的结论,那就是求极大子矩阵肯定要贴着边或一个障碍点,否则就会浪费 根据这个定理,我们可以考虑一种做法 我们可以枚举每一个可放置的点 我们可以很轻松的得知它与它左边的障碍点(或边界)的距离,也可以得知它上面与下面能扩展到哪里(即无障碍点最多能到哪里) 那这个点能扩出的长方形的最大...

题面 传送门:洛咕 Solution 挺显然但需要一定理解的网络(应该是那么叫吧)DP 首先有一个显然但重要的结论要发现:从左上走到右下再从右下走回左上=从左上走两次到右下 那么接下来可以考虑: 设f[i][j][k][l]为第一次走到了(i,j)第二次走到了(k,l) 在路径不交错为前提下的能取到的最大友好值 转移方程也挺好写的 考虑这种情况能从哪里转移过来就好(i,j)可以从(i-1,...