题面 蒟蒻博客：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 挺有意思的一道题。 题面已经挺明显的描述出了这题的主要思想：倍增。 先这样想，我们可以把这题这样建模：有一堆点，若两个点之间的距离之和可以达到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,...

题面 传送门:https://www.luogu.org/problemnew/show/P1005 Solution 我们可以先考虑贪心 我们每一次都选左右两边尽可能小的数,方便大的放在后面 听起来挺OK的 实则并不OK 反例: 3 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 如果贪心的话,我们会优先把右边那一串2先选了,再去选3和1 但是正确答案显然是先把3和1选了,再...

标签（空格分隔）： 题面: 传送门:BZOJ Solution 看到这道题,我们不妨先考虑一下20分怎么搞 想到暴力,本蒟蒻第一反应就是dfs,想法也很简单: 枚举n个数中的每一个数,枚举完每一种情况都判断一下是否满足要求 复杂度$O(n^m)$ 显然,这样的复杂度一分都得不到,但是可以作为对拍用的暴力程序 既然dfs行不通了,那我们换个想法吧,考虑一下用dp来搞这个问题 设$f[i][...

题面: 传送门:POJ Solution DP+DP 首先,我们可以很轻松地求出所有物品都要的情况下的选择方案数,一个简单的满背包DP就好 即:$f[i][j]$表示前i个物品装满容量为j的背包的方案数. 转移也很简单 $f[i][j]=f[i-1][j]+f[i-1][j-w[i]] (i:1~n,j:1~m)$ (即选和不选的问题) 初始化 $f[i][0]=1 (i:[0~n])$ ...