Beyond the Void

首先求出每个A*B的矩阵的数值和，以及每个C*D的矩阵的数值和，用递推的方法可以达到O(N*M)。
接下来，求出每个(A-2)*(B-2)范围内最小的C*D的矩阵（因为花坛不能建在绿化带边缘），可以...

这是一个动态规划可行性判定问题。

设玩具名字的字符串为A，状态 F[i,j,k] 表示A中，从第i位到第j位，是否可以变换成字符k。

状态转移方程

F[i,j,k] = Or{F[i,l,k1] And F[l+1,j,k2] | i&...

原来背包问题还有这种解法，动态规划+容斥原理。由于有tot次询问，如果对每次询问单独都做一次多重背包问题，会超时。有一种一次预处理，每次询问只有O(1)的神奇解法：容斥原理。

前两问是最短路，第三问是标准的次短路径。求法是先求出最短路径，然后枚举每条从S到T的最短路径上的边，删除以后再求一次最短路径，保留最小值就是次短路径。