标签：随机化根号分治

随机两个数作差，枚举这个数的因数作为可能的答案验证。

1005比赛总结

时间线 Time Line

• 08:00 开始考试

• 08:00 开 $A$

• 09:45 结束 $A$，开 $B$

• 10:10 结束 $B$，开 $C$

• 11:00 开 $\text{Excel}$ ，跑 $C$ 大样例

• 11:45 结束 $C$，开 $D$

• 12:00 结束考试

结果 Result

• $A;;40,pts.$ (低于预期)

• $B;;80,pts.$ (高于预期)

• $C;;35,pts.$ (低于预期)

• $D;;0;,pts.$ (不好评价)

• $Total;;155,pts.$

从排名来看高于预期，从绝对得分来看符合预期。

总结 Summary

首先，这次比赛最大的一个问题是时间的安排，$A$ 与 $C$ 题均耗费了一个小时以上的时间，导致 $B$ 与 $C$ 题只有很少的时间写。戏剧性的是，$B$ 只耗费了 $25\text{min}$ 却是本场比赛中拿分最高的题。

其次则是思路上的问题，$A$ 题在赛时有正解的想法，但是因为没有仔细下去或是不敢往下想而放弃（那时已经 9:10 了，因此不敢拿剩下的时间去赌这道题）。$C$ 题也是如此，在提交代码后大约 $30\text{s}$ 就找的了赛时没找到的 BUG。

最后就是码力上的问题，其实也是因为思路被禁锢了，$C$ 题明明有一种写起来+调起来都更舒服的方式，可惜没想到，导致耗费了大量时间在调试上。

这告诉我什么？

• 及时止损，切换思路

• 提高码力，估准难度

• 仔细思考，加强深度

• 合理化时间分配

• 关于知识点的联系

• 暴力！暴力！暴力！！！不会也得打暴力！

第一阶段总结

第一阶段主要是关于动态规划的序列问题的，可以分为两种：

• 最长公共子序列（LCS）

• 最长上升子序列（LIS）

首先，LIS可以用来求LCS，其时间复杂度为 $O(n\log n)$ 。

最长公共子序列又有几个经典问题：

• 求长度（模板）

• 求方案数：动态规划+转移计数

• 求方案：动态规划+转移倒推

• 求字典序最小方案：动态规划+统计字母出现位置

• 给定两个字符串求最短包含串的方案（数）：动态规划+双指针

而最长上升子序列的问题就多了去了，以下只列一些：

• 求长度（模板）

• 求字典序最小/大方案（动态规划+贪心递推）

• 求方案数（动态规划+计数+ $O(n\log n)$ 树状数组或二分优化）

• 求本质不同的方案数（同上，加个去重）

• 求LCS（用一个序列“离散化”另一个序列）

• 判断一个数是否出现在LIS上（动态规划$O(n\log n)$+统计位置：一定在序列上的数位置不变，不一定则位置可能变化）

• 构造指定长度的LISDL序列（不好说）

一阶段的问题主要都体现在1005的比赛中了，比赛中的问题就是要解决的问题。

关于最长上升子序列的 $O(n\log n)$ 写法：

1. 二分

空间复杂度 $O(n)$ 即数组长度空间。

这种方法本身不能求出具体方案，可以求出最长上升子序列的长度。

其原理简单来说就是对于每次新加一个元素，看它是否能接着当前这个序列下去，如果不能，则找到最小的一个大于（等于）它的元素并替换。

代码实现如下：

1
2
3
4
5
6
7
8

memset(g, 0x3f, sizeof g);
int ans = 0;
for (int i = 1; i <= n; i++) {
	int p = lower_bound(g+1, g+n+1, a[i]) - g;
	g[p] = a[i];
	f[i] = p;
}
while (g[(++ans)+1] != inf) continue;

（f 数组的定义和朴素转移一样，$f_i$ 记录以 $a_i$ 结尾的最长上升子序列）

2. 树状数组

注意：本方法空间复杂度为 $O(k)$ （$k$ 是 $a_i$ 的取值范围）

所谓优化，要么在算法上优化，码量小，但难想；如果在数据结构上优化，码量大，但是基本不动脑子。

具体而言，我们做出如下分析：

• 优化什么？第二维 j 的转移。

• 怎么优化？树状数组，对值域开数组，每次转移拿当前的 $a_i$ 的值查询并更新树状数组。

• 如何证明正确性？感性理解，分析朴素转移中有哪些限制：①. $j<i$；②. $a_j<a_i$。①我们在循环更新的过程中从未往数组中加入 $i\leq j$ 的元素，自然也不会从后面的状态转移过来；②因为我们是对值域开数组，因此在当前 $a_i$ 前面的一定是那些 $a_j<a_i$ 的状态。

至此，所有问题均被解决，剩下的只是代码实现了（这里不贴代码了，待会连着统计方案数的题一起贴）。

注意树状数组只是优化哪些数能被转移以及加快转移过程，不是把 f 数组开到树状数组上！

有了这些法宝，接下来就看例题啦！

经典例题

例一

题目：给定字符串 $a$ 和 $b$ ，求最短的字符串 $c$ ，使得 $a$ 与 $b$ 均为 $c$ 的子序列。输出所有满足条件的 $c$ 中字典序最小的。