#include <iostream> #include <vector> #include <algorithm> #include <map> #include <climits> using namespace std; typedef long long LL; int main() { int n; cin >> n; vector<int> type(n), taste(n); for (int i = 0; i < n; i++) cin >> type[i]; for (int...

定理（最近点对分治算法的合并步骤复杂度） 设：   是平面上  个点的集合，且所有点的  坐标均不同。 在分治算法中，递归处理左右子集后，已得到左右两部分点对之间的最小距离 。 设  为分割左右子集的中线  坐标。 令  为  中所有与中线  的垂直距离（即 ）小于  的点构成的子集，并按  坐标升序排序。  则： 对于  中按  坐标排序后的任意一点 ，在排序列表中位于  之后且可能与  构成距离小于  的点对（即满足  的点  ）的数量不超过 6 个。 换言之，在合并步骤中，为寻找可能更新最小距离  的跨分割线点对，只需对  中的每个点 ，检查其后续最多 6 个点即可。这保证了合并步骤可以...

#include <iostream> #include <cstring> using namespace std; const int MOD = 1000000007; int main() { int n, m, K; cin >> n >> m >> K; string A, B; cin >> A >> B; // 调整字符串索引从1开始，方便处理 A = " " + A; B = " " + B; // dp[j][k] 表示当前处理A的前i个字符时，匹配B的前j个字符，并分成k个子串的方案数 /...